Proportional fairness and its relationship with multi-class queueing networks.

*(English)*Zbl 1198.60039The connections between three different models of multi-class single-server queueing network are determined. The first model concerns a single-server multiclass queueing network and is treated as a microscopic model of a macroscopic model. The second, i.e., the macroscopic model, is a specific stochastic flow level model and the models document transfer across a packet switched network. The third, known as the teleological model, refers to the descriptions of the network.

The first result of this paper shows that a sequence of multi-class queueing network modeling of document transfer across a packet switching network weakly converges in the Skorokhod topology of these networks with a specific stochastic flow level model. The author referred to the resulting stochastic flow level model as the spinning network. The second result of this paper is concerned with connecting both microscopic and macroscopic models with the teleological model. This paper provides proofs of the mathematical relationship between multi-class networks of single-server queues and proportional fairness. It was observed that the constraints of a network may include transfer rates. By applying the Contraction Principle a new rate function \(\alpha(.)\), expressed as a convex optimization problem, is gained. In its primal form \(\alpha(.)\) is interpreted as maximizing entropy subject to a constraints. The determined dual form of \(\alpha(.)\) is up to constant, proportional to the observed throughput of these networks. The final observation is that the multi-class queueing networks considered here have no prescribed optimization structure. It is surprising to see that asymptotically these networks implicitly solve a utility optimization problem.

The first result of this paper shows that a sequence of multi-class queueing network modeling of document transfer across a packet switching network weakly converges in the Skorokhod topology of these networks with a specific stochastic flow level model. The author referred to the resulting stochastic flow level model as the spinning network. The second result of this paper is concerned with connecting both microscopic and macroscopic models with the teleological model. This paper provides proofs of the mathematical relationship between multi-class networks of single-server queues and proportional fairness. It was observed that the constraints of a network may include transfer rates. By applying the Contraction Principle a new rate function \(\alpha(.)\), expressed as a convex optimization problem, is gained. In its primal form \(\alpha(.)\) is interpreted as maximizing entropy subject to a constraints. The determined dual form of \(\alpha(.)\) is up to constant, proportional to the observed throughput of these networks. The final observation is that the multi-class queueing networks considered here have no prescribed optimization structure. It is surprising to see that asymptotically these networks implicitly solve a utility optimization problem.

Reviewer: Jerzy Martyna (Kraków)

##### MSC:

60K25 | Queueing theory (aspects of probability theory) |

60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |

90B22 | Queues and service in operations research |

##### References:

[1] | Billingsley, P. (1999). Convergence of Probability Measures , 2nd ed. Wiley, New York. · Zbl 0944.60003 |

[2] | Bonald, T. and Massoulie, L. (2001). Impact of fairness on internet performance. In Proceedings of ACM Sigmetrics 29 82-91. ACM, New York. |

[3] | Bonald, T. and Proutière, A. (2004). On performance bounds for balanced fairness. Performance Evaluation 55 25-50. · Zbl 1073.68018 |

[4] | Bramson, M. (1998). State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. 30 89-148. · Zbl 0911.90162 · doi:10.1023/A:1019160803783 |

[5] | Chen, H. and Yao, D. D. (2001). Fundamentals of Queueing Networks : Performance , Asymptotics , and Optimization. Applications of Mathematics 46 . Springer, New York. · Zbl 0992.60003 |

[6] | Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Applications of Mathematics 38 . Springer, New York. · Zbl 0896.60013 |

[7] | Doyle, P. G. and Snell, J. L. (1984). Random Walks and Electric Networks. Carus Mathematical Monographs 22 . Mathematical Association of America, Washington, DC. · Zbl 0583.60065 |

[8] | 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? IEEE/ACM Transactions on Networking 9 2-14. |

[9] | Kang, W. N., Kelly, F. P., Lee, N. H. and Williams, R. J. (2007). State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Ann. Appl. Probab. · Zbl 1203.60140 · doi:10.1214/08-AAP591 |

[10] | Kang, W. N., Kelly, F. P., Lee, N. H. and Williams, R. J. (2007). Product form stationary distributions for diffusion approximations to a flow level model operating under a proportional fair sharing policy. Performance Evaluation Review 35 36-38. |

[11] | Kelly, F. P. (1979). Reversibility and Stochastic Networks . Wiley, Chichester. · Zbl 0422.60001 |

[12] | Kelly, F. P. (1986). Blocking probabilities in large circuit-switched networks. Adv. in Appl. Probab. 18 473-505. JSTOR: · Zbl 0597.60092 · doi:10.2307/1427309 · links.jstor.org |

[13] | Kelly, F. P. (1989). On a class of approximations for closed queueing networks. Queueing Syst. 4 69-76. · Zbl 0664.60089 · doi:10.1007/BF01150857 |

[14] | Kelly, F. P. (1991). Network routing. Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci. 337 343-367. JSTOR: · Zbl 0746.90023 · doi:10.1098/rsta.1991.0129 · links.jstor.org |

[15] | Kelly, F. P. (1997). Charging and rate control for elastic traffic. European Transactions on Telecommunications 8 33-37. |

[16] | 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 |

[17] | Massoulié, L. (2007). Structural properties of proportional fairness: Stability and insensitivity. Ann. Appl. Probab. 17 809-839. · Zbl 1125.60104 · doi:10.1214/105051606000000907 |

[18] | Massoulie, L. and Roberts, J. (1998). Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15 185-201. · Zbl 1030.68774 · doi:10.1023/A:1019138827659 |

[19] | Massoulie, L. and Roberts, J. (1999). Bandwidth sharing: Objectives and algorithms. INFOCOM ’99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE 3 1395-1403. |

[20] | Pittel, B. (1979). Closed exponential networks of queues with saturation: The Jackson-type stationary distribution and its asymptotic analysis. Math. Oper. Res. 4 357-378. JSTOR: · Zbl 0418.60089 · doi:10.1287/moor.4.4.357 · links.jstor.org |

[21] | Proutière, A. (2003). Insensitivity and stochastic bounds in queueing networks-application to flow level traffic modelling in telecommunication networks. Ph.D. thesis, Ecole Doctorale de l’Ecole Polytechnique. |

[22] | Schassberger, R. (1978). Insensitivity of steady-state distributions of generalized semi-Markov processes with speeds. Adv. in Appl. Probab. 10 836-851. JSTOR: · Zbl 0396.60085 · doi:10.2307/1426662 · links.jstor.org |

[23] | Schweitzer, P. J. (1979). Approximate analysis of multiclass closed networks of queues. In Proceedings of the International Conference on Stochastic Control and Optimization . Free Univ., Amsterdam. |

[24] | Shah, D. and Wischik, D. J. (2008). Heavy traffic analysis of optimal scheduling algorithms for switched networks. Ann. Appl. Probab. |

[25] | Srikant, R. (2004). The Mathematics of Internet Congestion Control . Birkhäuser, Boston, MA. · Zbl 1086.68018 |

[26] | Whittle, P. (1985). Partial balance and insensitivity. J. Appl. Probab. 22 168-176. JSTOR: · Zbl 0561.60095 · doi:10.2307/3213756 · links.jstor.org |

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.