Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
Search Results
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 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.
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 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 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.