Saswati SarkarProfessor Dept. of Electrical Eng |
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.
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.
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.
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.
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.
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