Fair Allocation of Discrete Bandwidth Layers in Multicast Networks

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.