Fair Allocation of Discrete Bandwidth Layers in Multicast Networks

Loading...
Thumbnail Image
Files
TR_99-43.pdf(645.86 KB)
No. of downloads: 710
Publication or External Link
Date
1999
Authors
Sarkar, Saswati
Tassiulas, Leandros
Advisor
Tassiulas, Leandros
Citation
DRUM DOI
Abstract
We 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.
Notes
Rights