Structural properties of proportional fairness: stability and insensitivity. (English) Zbl 1125.60104
Summary: We provide a novel characterization of the proportionally fair bandwidth allocation of network capacities, in terms of the Fenchel-Legendre transform of the network capacity region. We use this characterization to prove stability (i.e., ergodicity) of network dynamics under proportionally fair sharing, by exhibiting a suitable Lyapunov function. Our stability result extends previously known results to a more general model including Markovian users routing. In particular, it implies that the stability condition previously known under exponential service time distributions remains valid under so-called phase-type service time distributions.
We then exhibit a modification of proportional fairness, which coincides with it in some asymptotic sense, is reversible (and thus insensitive), and has an explicit stationary distribution. Finally we show that the stationary distributions under modified proportional fairness and balanced fairness, a sharing criterion proposed because of its insensitivity properties, admit the same large deviations characteristics.
These results show that proportional fairness is an attractive bandwidth allocation criterion, combining the desirable properties of ease of implementation with performance and insensitivity.
We then exhibit a modification of proportional fairness, which coincides with it in some asymptotic sense, is reversible (and thus insensitive), and has an explicit stationary distribution. Finally we show that the stationary distributions under modified proportional fairness and balanced fairness, a sharing criterion proposed because of its insensitivity properties, admit the same large deviations characteristics.
These results show that proportional fairness is an attractive bandwidth allocation criterion, combining the desirable properties of ease of implementation with performance and insensitivity.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 90B15 | Stochastic network models in operations research |
References:
| [1] | Asmussen, S. (2003). Applied Probability and Queues. Springer, New York. · Zbl 1029.60001 · doi:10.1007/b97236 |
| [2] | Bertsekas, D. and Gallager, R. (1992). Data Networks . Prentice Hall, New York. · Zbl 0734.68006 |
| [3] | Bonald, T. and Massoulié, L. (2001). Impact of fairness on Internet performance. In Proceedings of ACM Sigmetrics 82–91. |
| [4] | Bonald, T., Massoulié, L., Proutière, A. and Virtamo, J. (2006). A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing System Theory Appl. 53 65–84. · Zbl 1114.90016 · doi:10.1007/s11134-006-7587-7 |
| [5] | Bonald, T. and Proutière, A. (2003). Insensitive bandwidth sharing in data networks. Queueing Systems 44 69–100. · Zbl 1023.90003 · doi:10.1023/A:1024094807532 |
| [6] | Bramson, M. (2005). Communication at the INFORMS Applied Probability Conference, Ottawa. |
| [7] | Bratley, P., Fox, B. L. and Schrage, L. E. (1986). A Guide to Simulation . Springer, New York. · Zbl 0515.68070 |
| [8] | Ceragioli, F. M. (1999). Discontinuous ordinary differential equations and stabilization. Ph.D. dissertation, Univ. degli Studi di Firenze. · Zbl 0927.34034 |
| [9] | Dai, J. G. (1995). On positive Harris recurrence of multiclass queuing networks: A unified approach via fluid limit models. Ann. Appl. Probab. 5 49–77. · Zbl 0822.60083 · doi:10.1214/aoap/1177004828 |
| [10] | De Veciana, G., Lee, T. J. and Konstantopoulos, T. (1999). Stability and performance analysis of networks supporting services with rate control—could the Internet be unstable? In Proc. IEEE Infocom ’ 99 . |
| [11] | Falconer, K. (1990). Fractal Geometry. Mathematical Foundations and Applications . Wiley, Chichester. · Zbl 0689.28003 |
| [12] | Hoeffding, W. (1940). Masstabinvariante korrelationstheorie. Schriften des Mathematischen Instituts und des Instituts für Angewandte Mathematik der Universitat Berlin 5 179–233. · Zbl 0024.05602 |
| [13] | Kelly, F. (1997). Charging and rate control for elastic traffic. Eur. Trans. Telecommun. 8 33–37. |
| [14] | Kelly, F., Maulloo, A. and Tan, D. (1998). Rate control in communication networks: Shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49 237–252. · Zbl 1111.90313 · doi:10.1057/palgrave.jors.2600523 |
| [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 · doi:10.1214/105051604000000224 |
| [16] | Key, P. and Massoulié, L. (2006). Fluid models of integrated traffic and multipath routing. Queueing Systems Theory Appl. 53 85–98. · Zbl 1114.90007 · doi:10.1007/s11134-006-7588-6 |
| [17] | Mazumdar, R., Mason, L. and Douligeris, C. (1991). Fairness in network optimal flow control: Optimality of product forms. IEEE Trans. Commun. 39 775–782. |
| [18] | McShane, E. J. (1947). Integration . Princeton Univ. Press. · Zbl 0033.05302 |
| [19] | Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8 556–567. |
| [20] | Nash, J. (1950). The bargaining problem. Econometrica 18 155–162. JSTOR: · Zbl 0267.90006 · doi:10.2307/1907266 |
| [21] | Robert, P. (2003). Stochastic Networks and Queues . Springer, Berlin. · Zbl 1038.60091 |
| [22] | Rockafellar, R. T. (1970). Convex Analysis . Princeton Univ. Press. · Zbl 0193.18401 |
| [23] | Rockafellar, R. T. and Wets, R. J. B. (2004). Variational Analysis . Springer, Berlin. · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3 |
| [24] | Rybko, A. N. and Stolyar, A. L. (1992). Ergodicity of stochastic processes describing the operations of open queueing networks. Problemy Pederachi Informatsii 28 2–26. · Zbl 0768.60089 |
| [25] | Schassberger, R. (1986). Two remarks on insensitive stochastic models. Adv. in Appl. Probab. 18 791–814. JSTOR: · Zbl 0623.60110 · doi:10.2307/1427188 |
| [26] | Shorak, G. and Wellner, J. (1986). Empirical Processes with Applications to Statistics . Wiley, New York. |
| [27] | Stefanescu, A. and Stefanescu, M. W. (1984). The arbitrated solution for multiobjective convex programming. Rev. Roum. Math. Pure Appl. 29 593–598. · Zbl 0547.90093 |
| [28] | Whitt, W. (1976). Bivariate distributions with given marginals. Ann. Statist. 4 1280–1289. · Zbl 0367.62022 · doi:10.1214/aos/1176343660 |
| [29] | Ye, H. Q. (2003). Stability of data networks under an optimization-based bandwidth allocation. IEEE Trans. Automat. Control 48 1238–1242. · Zbl 1364.90103 · doi:10.1109/TAC.2003.814269 |
| [30] | Ye, H. Q., Ou, J. H. and Yuan, X. M. (2005). Stability of data networks: Stationary and bursty models. Oper. Res. 53 107–125. · Zbl 1165.90371 · doi:10.1287/opre.1040.0139 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
