Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-28T17:41:54.439Z Has data issue: false hasContentIssue false
  • English
  • Français

The Effect of Increasing Routing Choice on Resource Pooling

Published online by Cambridge University Press:  27 July 2009

Stephen R.E. Turner
Stephen R.E. Turner
Affiliation:
Statistical Laboratory, University of Cambridge, 16 Mill Lane, Cambridge CB2 1SB, England
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a network of N identical /M/l or /M/∞ queues. There are two types of arriving customers, those that have no routing choice, and those that first pick r queues at random, and are then routed to the least busy of those queues. We derive the limiting distribution of queue lengths as N→∞, and investigate how this distribution varies with r. We show that even a small amount of routing choice can lead to substantial gains in performance through resource pooling. We corroborate these conclusions by carrying out some simulations of a related model, from which the previous model can be derived by an exchangeable queue simplification. We also observe that the exchangeable queue simplification results in a performance gain for some parameters, in contrast to earlier work.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 1 , January 1998 , pp. 109 - 124
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Billingsley, P. (1968). Convergence of probability measures. New York: John Wiley & Sons.Google Scholar
2.Crametz, J.-P. & Hunt, P.J. (1991). A limit result respecting graph structure for a fully connected loss network with alternative routing. Annals of Applied Probability 1: 436–444.Google Scholar
3.Ethier, S.N. & Kurtz, T.G. (1986). Markov processes: Characterization and convergence. New York: John Wiley & Sons.Google Scholar
4.Foschini, G.J. & Salz, J.(1978). A basic dynamic routing problem and diffusion. IEEE Transactions on Communications 26: 320–327.Google Scholar
5.Gibbens, R.J., & Hunt, P.J. & Kelly, F.P. (1990). Bistability in communication networks. In Grimmett, G.R. & Welsh, D.J.A.(eds.), Disorder in physical systems, pp. 113–127. Oxford: Oxford University Press.Google Scholar
6.Gibbens, R.J., Kelly, F.P. & Turner, S.R.E.(1993). Dynamic routing in multiparented networks. IEEE/ACM Transactions on Networking 1: 261–270.Google Scholar
7.Hajek, B.(1990). Performance of global load balancing by local adjustment. IEEE Transactions on Information Theory 36: 1398–1414.Google Scholar
8.Harrison, J.M.(1985). Brownian motion and stochastic flow systems. New York: John Wiley & Sons.Google Scholar
9.Harrison, J.M. & van Mieghem, J.A.(1997). Dynamic control of Brownian networks: State space collapse and equivalent workload formulations. Annals of Applied Probability 7: 747–771.Google Scholar
10.Hunt, P.J.(1990). Limit theorems for stochastic loss networks. Ph.D. thesis, University of Cambridge.Google Scholar
11.Hunt, P.J.(1995). Loss networks under diverse routing, I. The symmetric star network. Advances in Applied Probability 27: 255–272.Google Scholar
12.Hunt, P.J. & Laws, C.N.(1992). Least busy alternative routing in queueing and loss networks. Probability in the Engineering and Informational Sciences 6: 439–456.Google Scholar
13.Hunt, P.J. & Laws, C.N.(1993). Asymptotically optimal loss network control. Mathematics of Operations Research 18: 880–900.Google Scholar
14.Hunt, P.J., Laws, C.N. & Pitsilis, E.(1993). Asymptotically optimal dynamic routing in fully connected queueing networks. Research Report 1993–19, University of Cambridge Statistical Laboratory.Google Scholar
15.Kelly, F.P.(1991). “Loss networks. Annals of Applied Probability 1:319–378.Google Scholar
16.Kelly, F.P. & Laws, C.N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems: Theory and Applications 13: 47–86.Google Scholar
17.Reiman, M.I.(1984). Some diffusion approximations with state space collapse. In Baccelli, F. & Fayolle, G. (eds.), Modelling and performance evaluation methodology. Lecture Notes in Control and Information Sciences, number 60, INRIA. Berlin: Springer-Verlag.Google Scholar
18.Rogers, L.C.G. & Williams, D. (1994). Diffusions, Markov processes, and martingales, Vol. 1: Foundations, 2nd ed.New York: John Wiley & Sons.Google Scholar
19.Stoyan, D. (1983). Comparison methods for queues and other stochastic models. Translated from German, D.J. Daley (ed.). New York: John Wiley & Sons.Google Scholar
20.Turner, S.R.E. (1996). A join the shorter queue model in heavy traffic. Research Report 1996–1, University of Cambridge Statistical Laboratory.Google Scholar
21.Turner, S.R.E. (1997). Resource pooling via large deviations (in preparation).Google Scholar
22.Vvedenskaya, N.D., Dobrushin, R.L. & Karpelevich, F.I.(1996). Queueing system with the selection of the shortest of two queues: An asymptotic approach. Problems of Information Transmission 32: 15–27.Google Scholar
23.Whitt, W. (1980). Some useful functions for functional limit theorems. Mathematics of Operations Research 5:67–85.Google Scholar
24.Whitt, W. (1985). Blocking when service is required from several facilities simultaneously. AT&T Technical Journal 64: 1807–1856.Google Scholar