Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T18:31:23.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Utility Optimization in Congested Queueing Networks

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  14 July 2016

N. S. Walton
N. S. Walton*
Affiliation:
University of Cambridge
*
∗Postal address: Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a multiclass single-server queueing network as a model of a packet switching network. The rates packets are sent into this network are controlled by queues which act as congestion windows. By considering a sequence of congestion controls, we analyse a sequence of stationary queueing networks. In this asymptotic regime, the service capacity of the network remains constant and the sequence of congestion controllers act to exploit the network's capacity by increasing the number of packets within the network. We show that the stationary throughput of routes on this sequence of networks converges to an allocation that maximises aggregate utility subject to the network's capacity constraints. To perform this analysis, we require that our utility functions satisfy an exponential concavity condition. This family of utilities includes weighted α-fair utilities for α > 1.

Keywords

Utility optimizationqueueing networkquasi-reversiblelarge deviationcongestion windowcongestion control

MSC classification

Secondary: 90B15: Network models, stochastic 60K25: Queueing theory 90B22: Queues and service 90B18: Communication networks
Type
Research Article
Information
Journal of Applied Probability , Volume 48 , Issue 1 , March 2011 , pp. 68 - 89
Copyright
Copyright © Applied Probability Trust 2011 

References

[1] Asmussen, S. (2003). Applied Probability and Queues (Appl. Math. 51), 2nd edn. Springer, New York.Google Scholar
[2] Bonald, T. and Massoulié, L. (2001). Impact of fairness on internet performance. In ACM SIGMETRICS Performance Evaluation Review (Proc. SIGMETRICS 2001), Association for Computing Machinery, New York, pp. 82–91.Google Scholar
[3] Bonald, T. and Proutière, A. (2004). On performance bounds for balanced fairness. Performance Evaluation 55, 25–50.CrossRefGoogle Scholar
[4] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications (Appl. Math. 38), 2nd edn. Springer, New York.CrossRefGoogle Scholar
[5] Eryilmaz, A. and Srikant, R. (2007). Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. IEEE/ACM Trans. Networking 15, 1333–1344.CrossRefGoogle Scholar
[6] Ganesh, A., O'Connell, N. and Wischik, D. (2004). Big Queues (Lecture Notes Math. 1838). Springer, Berlin.CrossRefGoogle Scholar
[7] Johari, R. and Tan, D. K. H. (2001). End-to-end congestion control for the internet: delays and stability. IEEE/ACM Trans. Networking 9, 818–832.CrossRefGoogle Scholar
[8] Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley, Chicester.Google Scholar
[9] Kelly, F. P. (1982). Networks of quasireversible nodes. In Applied Probability—Computer Science: the Interface, Vol. 1, Birkhäuser, Boston, MA, pp. 3–29.CrossRefGoogle Scholar
[10] Kelly, F. P. (1989). On a class of approximations for closed queueing networks. Queueing Systems 4, 69–76.CrossRefGoogle Scholar
[11] Kelly, F. P. (1997). Charging and rate control for elastic traffic. Europ. Trans. Telecommun. 8, 33–37.CrossRefGoogle Scholar
[12] Kelly, F. P. (2003). Fairness and stability of end-to-end congestion control. Europ. J. Control 9, 159–176.CrossRefGoogle Scholar
[13] Kelly, F. P., Massoulié, L. and Walton, N. S. (2009). Resource pooling in congested networks: proportional fairness and product form. Queueing Systems 63, 165–194.CrossRefGoogle Scholar
[14] Kelly, F., Maulloo, A. and Tan, D. (1998). Rate control in communication networks: shadow prices, proportional fairness and stability. J. Operat. Res. Soc. 49, 237–252.CrossRefGoogle Scholar
[15] Kunniyur, S. S. and Srikant, R. (2003). Stable, scalable, fair congestion control and AQM schemes that achieve high utilization in the internet. IEEE Trans. Automatic Control 48, 2024–2029.CrossRefGoogle Scholar
[16] Massoulié, L. and Roberts, J. W. (1998). Bandwidth sharing and admission control for elastic traffic. Telecommun. Systems 15, 185–201.CrossRefGoogle Scholar
[17] Massoulié, L. and Roberts, J. (1999). Bandwidth sharing: objectives and algorithms. IEEE/ACM Trans. Networking 10, 320–328.CrossRefGoogle Scholar
[18] Mo, J. and Walrand, J. (2000). Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networking 8, 556–567.CrossRefGoogle Scholar
[19] Pittel, B. (1979). Closed exponential networks of queues with saturation: the Jackson-type stationary distribution and its asymptotic analysis. Math. Operat. Res. 4, 357–378.CrossRefGoogle Scholar
[20] Schweitzer, P. J. (1979). Approximate analysis of multiclass closed networks of queues. In Proc. Intern. Conf. Stochastic Control and Optimization, pp. 25–29.Google Scholar
[21] Srikant, R. (2004). The Mathematics of Internet Congestion Control. Birkhäuser, Boston, MA.CrossRefGoogle Scholar
[22] Stolyar, A. L. (2005). Maximizing queueing network utility subject to stability: greedy primal-dual algorithm. Queueing Systems 50, 401–457.CrossRefGoogle Scholar
[23] Vojnovic, M., Le Boudec, J.-Y. and Boutremans, C. (2000). Global fairness of additive-increase and multiplicative-decrease with heterogeneous round-trip times. In Proc. INFOCOM 2000 (March 2000), pp. 1303–1312.CrossRefGoogle Scholar
[24] Walton, N. S. (2009). Proportional fairness and its relationship with multi-class queueing networks. Ann. Appl. Prob. 19, 2301–2333.CrossRefGoogle Scholar