NC State University

Department of Computer Science Colloqua 1999-2000

Date: Friday, February 18, 2000
Time: 3: 30 PM  (talk)
Place: EGRC 246, NCSU Centennial Campus (click for courtesy parking request)

Speaker: Saswati Sarkar,  Electrical and Computer Engineering, University of Maryland

Fairness and Congestion Control in Multirate Multicast Networks

Abstract: This presentation is about our recent research in fairness and congestion control in multicast networks with multirate capabilities. In multirate transmission, the source hierarchically encodes the signal into several layers, and receivers subscribe to appropriate number of layers. It may or may not be possible to allocate fractional layers, depending on the system constraints.

We present distributed algorithms for computation of fair service rates, when fractional layers can be allocated. Fair allocation of network resources become significantly more challenging, if fractional layers cannot be allocated. We show that traditional fair allocations either do not exist, or are computationally NP-hard in this case. We introduce a new notion of fairness, maximal fairness for such scenarios. Maximally fair rate allocation is polynomial complexity computable and has many intuitively appealing fairness properties.

Next, we introduce utility functions connecting service rates with quality of service, and discuss fair allocation
of arbitrary utilities. Computation of fair rates is not always possible on account of insufficient knowledge of system parameters, and message exchange overhead limitations. For this purpose, we present a scheduling policy which attains fair rates, without computing them beforehand. Towards the end of this talk, I shall discuss congestion control via routing and scheduling, and present a throughput optimal congestion control scheme for multicast networks.

Short Bio:  Saswati Sarkar obtained her Bachelor of Engineering  from Jadavpur University in 1994 and Master of Engineering from Indian Institute of Science, Bangalore, in 1996. She joined the Phd program in Department of Electrical and Computer Engineering in  University of Maryland, College Park in 1997, and is currently a Phd candidate there. She was a summer student at IBM T. J. Watson Lab in 1998 summer. She received the Motorola Medal for the best of Master of Engineering student in the division of Electrical Sciences in Indian Institute of Science. Her current research interests are in resource allocation and quality of service provisioning in high speed networks.

Host: George Rouskas, Computer Science, NCSU

Colloquia Home Page.