Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T14:53:26.840Z Has data issue: false hasContentIssue false
  • English
  • Français

Braess's paradox in a queueing network with state-dependent routing

Part of: Operations research and management science

Published online by Cambridge University Press:  14 July 2016

Bruce Calvert ,
Wiremu Solomon  and
Ilze Ziedins
Bruce Calvert*
Affiliation:
University of Auckland
Wiremu Solomon*
Affiliation:
University of Auckland
Ilze Ziedins*
Affiliation:
University of Auckland
*
∗Postal address: Department of Mathematics, School of Mathematical and Information Sciences, The University of Auckland, Private Bag 92019, Auckland, New Zealand.
∗Postal address: Department of Mathematics, School of Mathematical and Information Sciences, The University of Auckland, Private Bag 92019, Auckland, New Zealand.
∗∗Postal address: Department of Statistics, School of Mathematical and Information Sciences, The University of Auckland, Private Bag 92019, Auckland, New Zealand.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider initially two parallel routes, each of two queues in tandem, with arriving customers choosing the route giving them the shortest expected time in the system, given the queue lengths at the customer's time of arrival. All interarrival and service times are exponential.

We then augment this network to obtain a Wheatstone bridge, in which customers may cross from one route to the other between queues, again choosing the route giving the shortest expected time in the system, given the queue lengths ahead of them.

We find that Braess's paradox can occur: namely in equilibrium the expected transit time in the augmented network, for some service rates, can be greater than in the initial network.

Keywords

BRAESS'S PARADOXQUEUEING NETWORK

MSC classification

Primary: 90B15: Network models, stochastic 90B22: Queues and service 90C35: Programming involving graphs or networks
Type
Research Papers
Information
Journal of Applied Probability , Volume 34 , Issue 1 , March 1997 , pp. 134 - 154
Copyright
Copyright © Applied Probability Trust 1997 

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

Bean, N. G., Kelly, F. P. and Taylor, P. G. (1997) Braess's paradox in loss networks. J. Appl. Prob. 34, 155–159.Google Scholar
Bell, C. E. and Stidham, S. Jr. (1983) Individual versus social optimization in the allocation of customers to alternative servers. Management Sci. 29, 831–839.Google Scholar
Blanc, J. P. C. (1990) The power series algorithm applied to the shortest-queue model. Operat. Res. 40, 157–167.Google Scholar
Braess, D. (1968) Uber ein Paradoxen der Verkehrsplannung. Unternehmenforschung 12, 256–268.Google Scholar
Calvert, B. (1995) The Downs-Thomson effect in a Markov process.Google Scholar
Calvert, B. and Keady, G. (1993) Braess's paradox and power-law nonlinearities in networks. J. Austral. Math. Soc. B 35, 1–22.CrossRefGoogle Scholar
Calvert, B. and Keady, G. (1995) Braess's paradox and power-law nonlinearities in networks II. In Proc. First World Congress of Nonlinear Analysts, WC528 Aug. 92. Vol III. de Gruyter, Berlin. pp. 2223–2230.Google Scholar
Cohen, J. E. and Horowitz, P. (1991) Paradoxical behaviour of mechanical and electrical networks. Nature 352, 699–701.CrossRefGoogle Scholar
Cohen, J. E. and Kelly, F. P. (1990) A paradox of congestion in a queueing network. J. Appl. Prob. 27, 730–734.Google Scholar
Fishwick, R. A. (1990) SimPack Version 2.2 (ftp.cis.ufl.edu).Google Scholar
Foster, F. G. (1953) On stochastic matrices associated with various queueing processes. Am. Math. Stat. 24, 355–360.Google Scholar
Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1990) Bistability in communication networks. In Disorder in Physical Systems. ed. Grimmett, G. R. and Welsh, D. J. A. Oxford University Press, Oxford. pp. 113–127.Google Scholar
Gibbens, R. J., Kelly, F. P. and Key, P. B. (1994) Dynamic alternative routing. In Routing and Communication Networks. ed. Steenstrup, M. Prentice Hall, New York.Google Scholar
Halfin, S. (1985) The shortest queue problem. J. Appl. Prob. 22, 865–878.CrossRefGoogle Scholar
Houck, D. J. (1987) Comparison of policies for routing customers to parallel queueing systems. Operat. Res. 35, 306–310.Google Scholar
Kelly, F. P. (1991) Network routing. Phil. Trans. R. Soc. Lond. A 337, 343–367.Google Scholar
Kingman, J. F. C. (1961) Two similar queues in parallel. Ann. Math. Statist. 32, 1314–1323.Google Scholar
Kumar, P. R. and Walrand, J. (1985) Individually optimal routing in parallel systems. J. Appl. Prob. 22, 989–995.Google Scholar
Laws, C. N. and Louth, G. M. (1990) Dynamic scheduling of a four-station queueing network. Prob. Eng. Info. Sci. 4, 131–156.Google Scholar
Macdougall, M. H. (1987) Simulating Computer Systems: Techniques and Tools. MIT Press, Cambridge, MA.Google Scholar
Rosberg, Z. and Kermani, P. (1989) Customer routing to different servers with complete information. Adv. Appl. Prob. 21, 861–882.CrossRefGoogle Scholar
Soardi, P. M. (1993) Morphisms and currents in infinite nonlinear resistive networks. Potential Anal. 2, 315–347.CrossRefGoogle Scholar
Weber, R. R. (1978) On the optimal assignment of customers to parallel queues. J. Appl. Prob. 15, 406–413.CrossRefGoogle Scholar
Whitt, W. (1985) Deciding which queue to join: some counterexamples. Operat. Res. 34, 55–62.CrossRefGoogle Scholar
Winston, W. (1977) Optimality of the shortest line discipline. J. Appl. Prob. 14, 181–189.CrossRefGoogle Scholar
Wroe, G. A., Cope, G. A. and Whitehead, M. J. (1990) Flexible routing in the BT international access network. Proc. Seventh UK Teletraffic Symposium , IEE, Durham.Google Scholar
Zukowski, C. A. and Wyatt, J. L. (1984) Sensitivity of nonlinear one-port resistor networks. IEEE Trans. Circuits and Systems 31, 1048–1051.Google Scholar