×

Qualitative properties of \(\alpha\)-fair policies in bandwidth-sharing networks. (English) Zbl 1304.60102

Flow-level network models are simplified versions of complex models which are useful, e.g., for Internet traffic description and evaluation for admission control. The most important question to be attacked with such models is to find conditions for stabilization of the network, i.e., for ergodicity of the describing Markov processes. Given this, the natural question is to decide about finiteness of stationary flows and to provide bounds for the mean number of ongoing flows in the stationary state. Under the so-called \(\alpha\)-fair bandwidth sharing policy of network capacities, the authors derive such bounds for the transient finite time phase of the network and for the stationary state as well. For underloaded networks, exponentially decaying bounds for the tails of the steady state distribution are derived and under heavy-traffic assumptions, the diffusion scaling provides insight into the transient as well as the limiting behaviour.
It turns out that the (positive) value of \(\alpha\) is decisive for obtaining some of the results. Another interesting aspect is that introducing new Lyapunov functions can lead to better bounds than those so far available in the literature.

MSC:

60K20 Applications of Markov renewal processes (reliability, queueing networks, etc.)
60K25 Queueing theory (aspects of probability theory)
68M12 Network protocols
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Bertsekas, D. (1999). Nonlinear Programming . Athena Scientific, Belmont, MA. · Zbl 1015.90077
[2] Bertsimas, D., Gamarnik, D. and Tsitsiklis, J. N. (2001). Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. 11 1384-1428. · Zbl 1012.60082
[3] Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003
[4] Bonald, T. and Massoulié, L. (2001). Impact of fairness on Internet performance. ACM SIGMETRICS Performance Evaluation Review 29 82-91.
[5] Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Systems Theory Appl. 30 89-148. · Zbl 0911.90162
[6] De Veciana, G., Konstantopoulos, T. and Lee, T. (2001). Stability and performance analysis of networks supporting elastic services. IEEE/ACM Transactions on Networking 9 2-14.
[7] Eryilmaz, A. and Srikant, R. (2012). Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst. 72 311-359. · Zbl 1273.90054
[8] Foss, S. and Konstantopoulos, T. (2004). An overview of some stochastic stability methods. J. Oper. Res. Soc. Japan 47 275-303. · Zbl 1134.93412
[9] Gallager, R. (1996). Discrete Stochastic Processes . Kluwer Academic, Norwell, MA. · Zbl 0925.60005
[10] Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16 56-90. · Zbl 1094.60052
[11] Grimmett, G. R. and Stirzaker, D. R. (2001). Probability and Random Processes , 3rd ed. Oxford Univ. Press, New York. · Zbl 1015.60002
[12] Hajek, B. (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. in Appl. Probab. 14 502-525. · Zbl 0495.60094
[13] Kang, W. N., Kelly, F. P., Lee, N. H. and Williams, R. J. (2009). State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Ann. Appl. Probab. 19 1719-1780. · Zbl 1203.60140
[14] Kelly, F. P., Maulloo, A. K. and Tan, D. K. H. (1998). Rate control for communication networks: Shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49 237-252. · Zbl 1111.90313
[15] Kelly, F. P. and Williams, R. J. (2004). Fluid model for a network operating under a fair bandwidth-sharing policy. Ann. Appl. Probab. 14 1055-1083. · Zbl 1066.60093
[16] Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8 556-567.
[17] Roberts, J. and Massouli√©, L. (2000). Bandwidth sharing and admission control for elastic traffic. Telecomunication Systems 15 185-201. · Zbl 1030.68774
[18] Shah, D., Tsitsiklis, J. N. and Zhong, Y. (2010). Qualitative properties of alpha-weighted scheduling policies. ACM SIGMETRICS Performance Evaluation Review 38 239-250.
[19] Srikant, R. (2005). Models and methods for analyzing Internet congestion control algorithms. In Advances in Communication Control Networks. Lecture Notes in Control and Inform. Sci. 308 65-86. Springer, Berlin.
[20] Stolyar, A. L. (2008). Large deviations of queues sharing a randomly time-varying server. Queueing Syst. 59 1-35. · Zbl 1152.60074
[21] Subramanian, V. G. (2010). Large deviations of max-weight scheduling policies on convex rate regions. Math. Oper. Res. 35 881-910. · Zbl 1213.60153
[22] Venkataramanan, V. J. and Lin, X. (2009). On the large-deviations optimality of scheduling policies minimizing the drift of a Lyapunov function. In Proceedings of the 47 th Annual Allerton Conference on Communication , Control , and Computing 919-926. IEEE.
[23] Williams, R. J. (1998). Diffusion approximations for open multiclass queueing networks: Sufficient conditions involving state space collapse. Queueing Systems Theory Appl. 30 27-88. · Zbl 0911.90171
[24] Ye, H. and Yao, D. (2012). A stochastic network under proportional fair resource control-diffusion limit with multiple bottlenecks. Oper. Res. 60 716-738. · Zbl 1260.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.