Saswati Sarkar Professor Dept. of Electrical Eng

RESEARCH INTERESTS AND ACTIVITIES

What is a network today ? Easier to identify perhaps of what is not a network. From electronic communication to transportation to disease propagation to finance to social and professional connections, there is always an underlying network. Networks propagate information, spread diseases, transfer commodities, help individuals communicate and build opinions and coalitions. Some networks remain stationary for a long time, while others rapidly evolve. Multiple processes may propagate over shared networks. My research seeks to understand the science underlying various networks and design novel strategies for their utilization in various fields. Motivated by the overarching impact of networks in every aspect of our lives today, my research has focused on science, economics and security of diverse classes of networks (e.g., communication, social, transportation, power, economic) with emphasis on pricing and market economics, security, resource allocation, optimization and control of stochastic systems, distributed systems and algorithms. A brief description of my research areas and my most recent projects follow.

Optimal control of epidemic evolutions

Epidemic behavior emerges whenever interactions among a large number of individual entities affect the overall evolution of the encompassing system. Mathematical models based on nonlinear differential equations have been developed and applied in a variety of systems as diverse as infectious outbreaks and information diffusion in a human society (social media advertising) to the dissemination of messages in mobile networks or peer-to-peer networks. What a resource manager of such systems is interested in is to control the evolutions of the states. Most often, exertion of a control incurs a cost, either directly as the control may consume restricted resources, or indirectly as it may introduce adverse side effects. Much work has been done in modeling and validating the epidemic models in biological networks, relatively less, however, is known about their application in other domains, or even control of such systems through epidemic modeling. We construct a unifying framework that models the interactions of the control and the elements in systems with epidemic behavior spanning application domains as diverse as wireless networks, biological epidemics, opinion formation and transportation networks. In wireless networks, we seek to understand the propagation and control of wireless malware. In transportation networks, we seek to understand how messages spread through a combination of vehicular mobility and wireless transmission between vehicles and from vehicles to infrastructure. Considering opinion formation, we seek to understand how opinions may be optimally influenced through a combination of external and peer influence subject to budgetary constraints. For biological epidemics, we investigate the control of the spread of contagion through targeted testing, vaccination and peer to peer and awareness campaigns.

Competition, Neutrality and Service Quality in Cellular Wireless Access

Network neutrality regulations continue to be debated as their core economic issues constitute a topic of active research. The debate concerns all participants in the enormous and growing public-commodity Internet economy: cellular-wireless Internet service access providers (ISPs), content providers (CPs and CDNs), end-users and government regulators. Proponents of network neutrality claim that non-neutrality disincentivizes innovation on the CP side, decreases the competition among CPs, reinforces ISP oligopolies, and undermines the so called "free Internet". On the other hand, those who advicate relaxing network neutrality rules claim that neutrality, as it is perceived commonly, is a barrier to further developments on the Internet since it disincentivizes ISPs to invest in their costly last-mile infrastructure and managed servuces. This debate has largely been conducted on a qualitative level without without rigorous economic and technical analyzes. This is the deficit that this research addresses. Broadly, the goals of the research has been to quantitatively characterize the strategies of different entities in the cellular-wireless internet marketplace, namely the content provider (CP), internet service provider (ISP) and end user (EU) in presence of: 1) service differentiation in a marketplace comprising of entities of different nature 2) advertising revenue and side payments 3) competition between providers providing similar services but operating under different paradigms, namely neutral or non-neutral. Game theoretic models are underway for the goals.

Economics of resource allocation in wireless networks

The advent of cognitive radio technology promises to effectively address the limited availability of spectrum that has been deterring the proliferation of wireless services. This is because such limitation is in fact artificial - large swaths of spectrum are under-utilized as revealed by recent measurements. Cognitive radio networks are invaluable in the elimination of this artificial shortage by providing the flexibility to users to access licensed parts of the spectrum. But, economic incentives must be in place to incentivize the license holders (primaries) to use the spectrum they have licensed in an intelligent manner, and thereby facilitate access by the rest (secondaries). More specifically, license-holders should be allowed to sell their white spaces (unused spectrum bands) in an open spectrum market, which needs to be designed while remaining cognizant of the features that distinguish spectrum trade from that of any other commodity. Radio spectrum has the distinctive feature that transmissions at neighboring locations on the same channel interfere with each other, whereas the same channel can be used at far-off locations without mutual interference. In addition, each primary who has an available white-space is uncertain about the competition he faces since he does not know the spectrum usage patterns (and therefore white-space availability) of other primaries. So, during a white-space sale, each primary must jointly select a set of mutually non-interfering locations within the region (which corresponds to an independent set in the conflict graph representing the region) at which to sell unused spectrum and the price at each location considering uncertainties in competition. We have developed pricing strategies for primaries that consider the above distinctive features. The price competition scenario turned out to be a game over graphs where classical results in game theory did not guarantee the existence of Nash equilibrium let alone its uniqueness and characterization. Yet, exploiting properties specific to spectrum, we could show that the Nash equilibrium exists, is unique, and more importantly can be explicitly characterized. We subsequently provided a framework for designing contracts for spectrum trade among primaries and secondaries. We developed ``spectrum portfolio optimization'' techniques that allow primaries to package their available spectrum in an adequate mix of spectrum stocks (contracts that provide bandwidth guarantees to secondaries) and spectrum bonds (contracts that promise only best effort service) so as to attain desired tradeoffs between risk management and profit expectancy.

Moving out of the realm of competition to cooperation among wireless providers, which will be a reality provided individual providers can significantly enhance their incentives through cooperation, we provided a framework to evaluate economic incentives for cooperation among wireless service providers. Specifically, if providers cooperate by jointly deploying and poolingtheir resources, such as spectrum and infrastructure (e.g., basestations), and agree to serve each others' customers, theiraggregate payoffs, and individual shares, may substantially increase through opportunistic utilization of resources. The potential of such cooperation can, however, be realized only if each provider intelligently determines who it would cooperate with, when it would cooperate, and how it would deploy and share its resources during such cooperation, so as to maximize its individual incentive. Also, developing a rational basis forsharing the aggregate payoffs is imperative for the stability of the coalitions. We showed using coalitional game theory that the optimum cooperation strategy, which involves the acquisition, deployment and allocation of the channels and base stations (to customers), can be computed as the solution of a concave optimization. We next showed that the grand coalition is stable in many different settings, i.e., if all providers cooperate, there is always an operating point that maximizes the providers' aggregate payoff, while offering each a share that removes any incentive to split from the coalition. The optimal cooperation strategy and the stabilizing payoff shares can be obtained in polynomial time, by respectively solving the primals and the duals of the above optimizations, using distributed computations and limited exchange of confidential information among the providers.

Foundations for malware control in mobile wireless networks

Malicious self-replicating codes, known as malware, pose substantial threat to wireless networks, and the economic viability of the investments directed towards wireless infrastructure is contingent on the design of effective countermeasures. We have obtained fundamental bounds on the damages inflicted by the attack and also on the efficacy of the counter-measures, and subsequently show that the bounds in each case may be attained by distributed and easy-to-implement strategies. Our first step has been to anticipate malware hazards, and understand the threat before the attacks are actually launched. We have quantified the fundamental limits on the damage that the malware can inflict by optimally choosing its actions. Such limitations arise because the capabilities of the malware are limited by the resource constraints of wireless networks which the malware utilizes as well to propagate the contagion. Specifically, malware needs to decide how best to utilize the limited battery reserves of the host in scanning the media and transmitting packets that carry the contagion, as once the host's battery is depleted, the network incurs a cost, but so does the malware as the host can no longer be utilized to propagate the contagion and also in fulfilling its subversive ends. We formulated the maximization of the overall damage inflicted on the network as an optimal control problem, and subsequently identified structural properties of the optimal actions of the malware using Pontryagin's Maximum Principle. We showed that the malware can inflict the maximum damage by choosing simple bang-bang control functions with at most two jumps. The network can launch counter-measures through power control based quarantining strategies and also by fetching security patches that immunize the vulnerable and heal the infected hosts. Such power control strategies however deteriorate the quality of service in the network, and the transmission of patches consume valuable transmission resources such as spectrum and energy. Our work has been the first to formulate the optimal countermeasure selection as optimal control problems and identify structural properties of the optimal solutions. The optimal strategies again turn out to be bang-bang functions with at most two jumps, and should therefore be readily implementable in resource constrained wireless devices. We formulated the interactions between the attack and the defense as a dynamic game and proved that the robust defense retains its simple structures.

Joint allocation of resources in multihop wireless networks

Our research has contributed towards providing a theoretical framework for overcoming the resource constraints in multihop wireless networks by exploiting the interdependence of the key resources and the network users. This interdependence arises from the fact that the temporary scarcity of one key resource can be compensated by leveraging the availability of another, and different users can share the same resource using temporally and spatially disjoint sharing schemes. We have focussed on an important paradigm in wireless networks, that of group communications. We have shown that the very nature of group communications leads to fundamental changes in relation between important quality of service metrics like throughput, stability and packet loss, e.g., a strategy that maximizes the throughput does not necessarily maximize the stability region or minimize the packet loss. Having demonstrated that group communications requires new design paradigms, we obtained computationally simple, closed form resource allocation strategies that provably maximize important performance metrics without using any information about network traffic statistics. We next considered joint optimization of allocation of multiple resources, and designed scheduling strategies that provably optimize the use of bandwidth, memory and energy. Finally, we considered equitable sharing of resources, and proposed computationally simple flow control and scheduling schemes that provably attain fair sharing of bandwidth and power. Many of our results generalize to arbitrary constrained queueing networks and should therefore be of independent interest in the stochastic control and optimization communities.

Distributed and partial information based optimal control in multihop wireless networks

The theoretical framework described above identifies the best possible performance of the network provided resource contentions can be resolved using centralized resolution mechanisms. But, given the current state of the art in wireless networks, only distributed control strategies that rely on only local information at each node can be implemented. Obtaining provable performance guarantees with distributed control strategies for access of radio-spectrum has however remained a long-standing open problem. The results emerging from our research have provided key steps towards solving theseopen problems. We started with a simple distributed packet transmission schedulingstrategy, maximal scheduling, which is readily implementable inexisting wireless networks, and completely characterized itsperformance in arbitrary wireless networks. The characterizations prove that maximal scheduling is guaranteed to attain a certain fraction of the maximum possible stability region of the network; this fraction is a constant in important special cases. This guaranteed global performance bounds using local decisions in wireless networks. We subsequently designed scheduling policies that attain in a large class of topologies arbitrary desired tradeoffs between throughput and computation complexity. Specifically, given any desired approximation factor, the policy provides a throughput that is lower than the maximum throughput by at most the given factor while using computation time that depends only on the appproximation factor and the maximum node degree (and is independent of the size of the network otherwise). The policy was developed using a novel graph-partitioning technique that had seen only limited use in networking until then. Finally, we have developed distributed resource allocation strategies with provable performance guarantees in context of specific protocols like ALOHA and Bluetooth.

In another branch of this work, we have considered the dominating set problem, one of the oldest NP-hard problems in computer science and one that finds extensive applications in several different contexts including wireless networks, and have proved that a distributed pproximation algorithm not only attains the best possible approximation ratio but also emulates the performance of the best known centralized algorithm. Thus, in this case, globally optimum approximation ratio can be obtained using locally optimum decisions. We expect this result to be of independent interest in the algorithms community. Using this algorithm, we obtained a local-information based polynomial-time computable sensor activation scheduling policy that attains provable guarantees on network lifetime (relative to the maximum possible lifetime) while guaranteeing complete coverage of the target area during the lifetime, and without assuming any knowledge of sensor locations.

Resource allocation in multicast networks

The bulk of the multicast traffic in internet consists of multimedia applications, which consume huge network resources. Good resource allocation strategies can be used for congestion control. The constraint is that any practical resource allocation strategy must be comutationally simple, adaptive and local information based. We have investigated routing and scheduling policies which optimize the system performance and satisfies the above constraints. Multicast transmission allows several receivers to join the same applicaton. These receivers have diverse requirements and capabilities. For this purpose, the multimedia signals are coded in several levels of precisions, and receivers adapt to congeston by appropriately choosing the precision level of reception. This advanced multimedia coding technique calls for innovative distribution strategies. We have studied network resource allocation for multilevel coding, and have developed computing and scheduling strategies for ataining several resource allocation objectives.

EDUCATION

Ph.D. in Electrical and Computer Engineering, University of Maryland, College Park, August 2000

Master of Engineering in Electrical Communication Engineering department in Indian Institute of Science, 1996

Bachelor of Engineering in Electronics and Telecommunications in Jadavpur University in 1994

Awards and Honor

Professional Activities

TEACHING , SELECTED PUBLICATIONS , DOCTORAL STUDENTS