TY - JOUR
T1 - Stability, fairness, and performance
T2 - A flow-level study on nonconvex and time-varying rate regions
AU - Liu, Jiaping
AU - Proutière, Alexandre
AU - Yi, Yung
AU - Chiang, Mung
AU - Poor, H. Vincent
N1 - Funding Information:
Manuscript received November 21, 2007; revised January 01, 2009. Current version published July 15, 2009. This work was supported in part by the NSF under Grants CNS-0417607, CNS-0625637, CCF-0448012, CCF-0635034, DARPA CBMANET, KRCF, and IR R&D program of MKE/ITTA [2009-F-045-01]. The material in this paper was presented in part at ACM SIGMETRICS, San Diego, CA, July 2007.
PY - 2009
Y1 - 2009
N2 - The flow-level stability and performance of data networks with utility-maximizing allocations are studied in this paper. Similarly to prior works on flow-level models, exogenous data arrivals with finite workloads are considered. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either nonconvex or time-varying. When the rate region is fixed but nonconvex, sufficient and necessary conditions are characterized for stability for a class of α-fair allocation policies, which coincide when the set of allocated rate vectors have continuous contours. When the rate region is time-varying according to a Markovian stationary and ergodic process, the precise stability region is obtained. In both cases, the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter α-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independent of the value of the fairness parameter. It is further shown that for networks which consist of flows from two different classes under α-fair allocations, there exists a tradeoff between the stability region and the fairness parameter α. Moreover, the impact of this fairness-stability tradeoff on the system performance, e.g., average throughput and mean flow response time, is studied, and numerical experiments that illustrate the new stability region and the performance versus fairness tradeoff are presented.
AB - The flow-level stability and performance of data networks with utility-maximizing allocations are studied in this paper. Similarly to prior works on flow-level models, exogenous data arrivals with finite workloads are considered. However, to model many realistic situations, the rate region, which constrains the feasibility of resource allocation, may be either nonconvex or time-varying. When the rate region is fixed but nonconvex, sufficient and necessary conditions are characterized for stability for a class of α-fair allocation policies, which coincide when the set of allocated rate vectors have continuous contours. When the rate region is time-varying according to a Markovian stationary and ergodic process, the precise stability region is obtained. In both cases, the size of the stability region depends on the resource allocation policy, in particular, on the fairness parameter α-fair utility maximization. This is in sharp contrast with the substantial existing literature on stability under fixed and convex rate regions, in which the stability region coincides with the rate region for many utility-based resource allocation schemes, independent of the value of the fairness parameter. It is further shown that for networks which consist of flows from two different classes under α-fair allocations, there exists a tradeoff between the stability region and the fairness parameter α. Moreover, the impact of this fairness-stability tradeoff on the system performance, e.g., average throughput and mean flow response time, is studied, and numerical experiments that illustrate the new stability region and the performance versus fairness tradeoff are presented.
KW - Fairness
KW - Fluid limit
KW - Markov process
KW - Network utility maximization
KW - Resource allocation
KW - Stability
KW - Tradeoff
UR - http://www.scopus.com/inward/record.url?scp=68249150736&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=68249150736&partnerID=8YFLogxK
U2 - 10.1109/TIT.2009.2023680
DO - 10.1109/TIT.2009.2023680
M3 - Article
AN - SCOPUS:68249150736
SN - 0018-9448
VL - 55
SP - 3437
EP - 3456
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 8
ER -