Stability, Fairness, and Performance: A Flow-Level Study on Nonconvex and Time-Varying Rate Regions

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 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> -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 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> in <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> -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 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> -fair allocations, there exists a tradeoff between the stability region and the fairness parameter <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> . 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.