Browsing by Author "Sarkar, Saswati"
Results Per Page
Sort Options
Item Distributed Algorithms for Computation of Fair Rates in Multirate Multicast Trees(1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISRWe study fairness in arbitrary networks with multicast capabilities.Multicast traffic in internet and ATM provides a motivationfor studying these networks. A study of fairness in multicastnetworks poses several interesting problems e.g., the issueof {it intra-session} fairness in addition to thatof {it inter-session} fairness in unicastnetworks. We develop a mathematical frameworkto model the fair allocation of bandwidth in multicast networkswith minimum and maximum rate constraints. We presentdistributed algorithms for computation of maxmin fair ratesallocated to various source-destination pairs.Item Fair Allocation of Discrete Bandwidth Layers in Multicast Networks(1999) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISRWe study fairness when receivers in a multicast network can not subscribeto fractional layers. This case arises whenthe source hierarchically encodes its signal and the hierarchical structureis predetermined. Unlike the case of the fractional layer allocation,which has been studied extensively in a previous work, bandwidth canbe allocated in discrete chunks only. Fairness issues becomevastly different. Computation of lexicographically optimal rateallocation becomes NP-hard in this case, while lexicographicallyoptimal rate allocation is polynomial complexity computablewhen fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case.We introducea new notion of fairness, maximal fairness.We propose a polynomialcomplexity algorithm for computation of maximally fair ratesallocated to various source-destination pairs. Even though, maximal fairnessis a weaker notion of fairness, itcoincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. So the algorithmfor computing maximally fair rate allocation computes maxmin fairrate allocation, when the latter exists.Item A Framework for Routing and Congestion Control for Multicast Information Flows(1998) Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNWe propose a new multipurpose multicast routing and schedulingalgorithm (MMRS). The routing policy load balances amongstvarious possible routes between the source and the destinations,relying its decisions on the message queue lengths at thesource node. The scheduling amongst various sessionssharing links is devised such that the flow of a sessiondepends on the congestion of the next hop links. MMRSis throughput optimal and computationally simple.The algorithm can be implemented in a distributed,asynchronous manner. It has several parameters which can besuitably modified to control the end-to-end delay, packet lossin a topology specific manner. These parameters can be adjustedto offer limited priorities to some desired sessions. MMRS is expectedto play a significant role in end-to-end congestion controlin the multicast scenario.Item A Low-Overhead Rate Control Algorithm for Maximizing Aggregate Receiver Utility for Multirate Multicast Sessions(2000) Kar, Koushik; Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNIn multirate multicasting, different users (receivers) within the same multicastgroup could receive service at different rates, depending on user requirementsand network congestion level. Compared to unirate multicasting, this provides moreflexibility to the user, and allows more efficient usage of network resources.In this paper, we address the rate control problem for multirate multicast sessions,with the objective of maximizing the total receiver utility.This aggregate utility maximization problem not only takes into account the heterogeneityin user requirements, but also provides a unified framework for diverse fairness objectives.
We propose an algorithm for this problem and show, through analysis andsimulation, that it converges to the optimal rates.
In spite of the non-separability of the problem,the solution that we develop is completely decentralized, scalableand does not require the network to know the receiver utilities.Moreover, the algorithm requires very simple computations both forthe user and the network, and also has very low overhead of network congestionfeedback.
Item Optimization Based Rate Control for Multipath Sessions(2001) Kar, Koushik; Sarkar, Saswati; Tassiulas, Leandros; ISR; CSHCNIn this paper, we consider the rate control problem for multipath sessionswith the objective ofmaximizing the total user (session) utility. This problem provides a frameworkin which flow control and routing are jointly optimized.We consider two cases of this problem, anddevelop two different rate control algorithms for these two cases.The first algorithm is an end-to-endrate control algorithm which requires, on the part of the user, explicitknowledge of the paths that the user uses.The second algorithm is a hop-by-hop rate control algorithm whichdoes not require the user to keep track of the paths it uses.
Both the algorithms aredistributed and do not require the network to knowthe user utility functions.We analyze the convergence properties of these algorithms, anddiscuss how they can be implemented in a real network. Both of thesealgorithms are computationally simple, and have very low communication overhead.
Item Optimization Based Rate Control for Multirate Multicast Sessions(2000) Kar, Koushik; Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNMultirate multicasting, where the receivers of a multicast group can receive service at different rates, is an efficient mode of data delivery for many real-time applications.In this paper, we address the problem of achieving rates that maximize the total receiver utility for multirate multicast sessions. This problem not only takes into account the heterogeneity in user requirements, but also provides a unified framework for diverse fairness objectives. We propose two algorithms and prove that they converge to the optimal rates for this problem.
The algorithms are distributed and scalable, and do not require the network to know the receiver utilities. We discuss how these algorithms can be implemented in a real network, and also demonstrate their convergence through simulation experiments.
Item A Primal Algorithm for Optimization Based Rate Control for Unicast Sessions(2000) Kar, Koushik; Sarkar, Saswati; Tassiulas, Leandros; Tassiulas, Leandros; ISR; CSHCNIn this paper, we consider the rate control problem with the objective ofmaximizing the total user utility. It takes into account the possible differences in user requirements, and also provides a framework for achieving a wide range of fairness objectives.We propose a simple algorithm for achieving the optimal rates for this problem. The algorithm can be implemented in a distributed way and does not require the network to know the user utility functions.
In our algorithm, the network communicates to the user the number of congested links on the user's path, and the user (end-host) adjusts its rate accordingly, taking into account its utility function and the network congestion feedback.
We show through analysis and experimentation that our algorithm converges to the optimum rates.