Heavy-traffic approximations for linear networks operating under α-fair bandwidth-sharing policies

ABSTRACT

We consider the flow-level performance of a linear network supporting elastic traffic, where the service capacity is shared among the various classes of users according to a weighted alpha-fair policy. Assuming Poisson arrivals and exponentially distributed service requirements for each class, the dynamics of the user population may be described by a Markov process. While valuable stability results have been established for the family of alpha-fair policies, the distribution of the number of active users has remained intractable in all but a few special cases. In order to gain further insight in the flow-level performance in more general scenarios, we develop approximations for the mean number of users based on the assumption that one or two of the nodes experience heavy-traffic conditions.In case of just a single 'bottleneck' node, we exploit the fact that this node approximately behaves as a two-class Discriminatory Processor-Sharing model. In the case that there are two nodes critically loaded, we rely on the observation that the joint workload process at these nodes is asymptotically independent of the fairness coefficient alpha, provided all classes have equal weights. In particular, the distribution of the joint workload process is roughly equal to that for an unweighted Proportional Fair policy, which is exactly known. In both cases, the numbers of users at non-bottleneck nodes can be approximated by that in an M/M/1 queue with reduced service capacity. Extensive numerical experiments indicate that the resulting approximations tend to be reasonably accurate across a wide range of parameters, even at relatively moderate load values. The approximations for the mean number of users also provide useful estimates for the mean transfer delays and user throughputs.

REFERENCES

• 1: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 2: T. Bonald , L. Massoulié , A. Proutière , J. Virtamo, A queueing analysis of max-min fairness, proportional fairness and balanced fairness, Queueing Systems: Theory and Applications, v.53 n.1-2, p.65-84, June 2006 [doi>10.1007/s11134-006-7587-7]
• 3: T. Bonald , A. Proutière, Insensitive Bandwidth Sharing in Data Networks, Queueing Systems: Theory and Applications, v.44 n.1, p.69-100, May 2003 [doi>10.1023/A:1024094807532]
• 4: Bonald, T., Proutière, A., Roberts, J. W., Virtamo, J. (2003). Computational aspects of balanced fairness. Proceedings of the 18th International Teletraffic Congress, Berlin, Germany, 801--810.
• 5: G. Fayolle , I. Mitrani , R. Iasnogorodski, Sharing a Processor Among Many Job Classes, Journal of the ACM (JACM), v.27 n.3, p.519-532, July 1980 [doi>10.1145/322203.322212]
• 6: Harrison, J. M., Williams, R. J. (1987). Multidimensional reflected Brownian motions having exponential stationary distributions. Annals of Probability, 15: 115--137.
• 7: Kang, W., Kelly, F. P., Lee, N., Williams, R. J. (2004). Fluid and Brownian approximations for an internet congestion control model. Proceedings of the 43rd IEEE Conference on Decision and Control, the Bahamas, 3938--3943.
• 8: Kelly, F. P., Williams, R. J. (2004). Fluid model for a network operating under a fair bandwidth-sharing policy. Annals of Applied Probability, 14: 1055--1083.
• 9: Massoulié, L., Roberts, J. W. (2000). Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems, 15: 185--201.
• 10: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 11: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 12: Varadhan, S., Williams, R. J. (1985). Brownian motion in a wedge with oblique reflection. Communications on Pure and Applied Mathematics, 38: 405--443.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Performance

Keywords:
alpha-fair sharing, flow-level performance, heavy traffic, linear network, simultaneous resource possession