Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-24T13:10:56.653Z Has data issue: false hasContentIssue false
  • English
  • Français

Alternative routeing in fully connected queueing networks

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  01 July 2016

C. N. Laws  and
Y. C. Teh
C. N. Laws*
Affiliation:
University of Oxford
Y. C. Teh*
Affiliation:
University of Oxford
*
∗ Postal address: Department of Statistics, University of Oxford, 1 South Parks Road, Oxford, OX1 3TG, UK.
∗∗ Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a fully connected queueing network in which customers have one direct and many alternative routes through the network, and where customer routeing is dynamic. We obtain an asymptotically optimal routeing policy, taking the limit as the number of queues of the network increases. We observe that good policies route customers directly, unless there is a danger of servers becoming idle, in which case customers should be routed alternatively so as to avoid such idleness, and this leads to policies that perform well in moderate-sized networks.

Keywords

Queueing networksalternative routeingoptimizationdynamic routeing

MSC classification

Primary: 90B15: Network models, stochastic
Secondary: 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 32 , Issue 4 , December 2000 , pp. 962 - 982
Copyright
Copyright © Applied Probability Trust 2000 

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] Anderson, E. J. and Nash, P. (1987). Linear Programming in Infinite-Dimensional Spaces. John Wiley, Chichester.Google Scholar
[2] Bean, N. G., Gibbens, R. J. and Zachary, S. (1995). Asymptotic analysis of single resource loss systems in heavy traffic, with applications to integrated networks. Adv. Appl. Prob. 27, 273–292.CrossRefGoogle Scholar
[3] Bean, N. G., Gibbens, R. J. and Zachary, S. (1997). Dynamic and equilibrium behavior of controlled loss networks. Ann. Appl. Prob. 7, 873–885.Google Scholar
[4] Billingsley, P. (1968). Convergence of Probability Measures. John Wiley, New York.Google Scholar
[5] Crametz, J.-P. and Hunt, P. J. (1991). A limit result respecting graph structure for a fully connected loss network with alternative routing. Ann. Appl. Prob. 1, 436–444.CrossRefGoogle Scholar
[6] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, New York.Google Scholar
[7] Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1990). Bistability in communication networks. In Disorder in Physical Systems, eds Grimmett, G. R. and Welsh, D. J. A.. Oxford University Press, pp. 113–127.Google Scholar
[8] Gibbens, R. J. and Kelly, F. P. (1990). Dynamic routing in fully connected networks IMA J. Math. Control Inf. 7, 77–111.CrossRefGoogle Scholar
[9] Harrison, J. M. (1996). The Bigstep approach to flow management in stochastic processing networks. In Stochastic Networks: theory and applications (R. Statist. Soc. Lecture Notes 4), eds Kelly, F. P., Zachary, S. and Ziedins), I.. Oxford University Press, pp. 57–90.CrossRefGoogle Scholar
[10] Harrison, J. M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. Ann. Appl. Prob. 8, 822–848.CrossRefGoogle Scholar
[11] Hunt, P. J. (1995). Loss networks under diverse routing: the symmetric star network. Adv. Appl. Prob. 27, 255–272.CrossRefGoogle Scholar
[12] Hunt, P. J. and Kurtz, T. G. (1994). Large loss networks. Stoch. Proc. Appl. 53, 363–378.CrossRefGoogle Scholar
[13] Hunt, P. J. and Laws, C. N. (1992). Least busy alternative routing in queueing and loss networks. Prob. Eng. Inf. Sci. 6, 439–456.CrossRefGoogle Scholar
[14] Hunt, P. J. and Laws, C. N. (1993). Asymptotically optimal loss network control. Math. Operat. Res. 18, 880–900.CrossRefGoogle Scholar
[15] Hunt, P. J., Laws, C. N. and Pitsilis, E. (1993). Asymptotically optimal dynamic routing in fully connected queueing networks. Res. Rept 1993-19, Statistical Laboratory, University of Cambridge.Google Scholar
[16] Kelly, F. P. (1991). Loss networks. Ann. Appl. Prob. 1, 319–378.CrossRefGoogle Scholar
[17] Kelly, F. P. (1994). Bounds on the performance of dynamic routing schemes for highly connected networks. Math. Operat. Res. 19, 1–20.CrossRefGoogle Scholar
[18] Kelly, F. P. and Laws, C. N. (1993). Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing Systems 13, 47–86.CrossRefGoogle Scholar
[19] Kurtz, T. G. (1992). Averaging for martingale problems and stochastic approximation. In Applied Stochastic Analysis (Proc. US–French Workshop) (Lecture Notes in Control and Inf. Sci. 177), eds Karatzas, I. and Ocone, D.. Springer, Berlin, pp. 186–209.CrossRefGoogle Scholar
[20] Martin, J. B. and Suhov, Yu. M. (1999). Fast Jackson networks. Ann. Appl. Prob. 9, 854–870.CrossRefGoogle Scholar
[21] Teh, Y. C. (2000). Dynamic scheduling for queueing networks derived from discrete-review policies. In Analysis of Communication Networks (Fields Inst. Commun. 28), eds McDonald, D. and Turner, S.. AMS, Providence.Google Scholar
[22] Teh, Y. C. (1999). Threshold Routing Strategies for Queueing Networks. , University of Oxford.Google Scholar
[23] Thomas, E. (1998). A loss service system with another chance. Unpublished manuscript.Google Scholar
[24] Turner, S. R. E. (1998). The effect of increasing routeing choice on resource pooling. Prob. Eng. Inf. Sci. 12, 109–124.CrossRefGoogle Scholar
[25] Turner, S. R. E. (2000). A join the shorter queue model in heavy traffic. J. Appl. Prob. 37, 212–223.CrossRefGoogle Scholar
[26] Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: an asymptotic approach. Prob. Inf. Trans. 32, 15–27.Google Scholar
[27] Whitt, W. (1980). Some useful functions for functional limit theorems. Math. Operat. Res. 5, 67–85.CrossRefGoogle Scholar
[28] Williams, R. J. (2000). On dynamic scheduling of a parallel server system with complete resource pooling. In Analysis of Communication Networks (Fields Inst. Commun. 28), eds McDonald, D. and Turner, S.. AMS, Providence.Google Scholar