Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T04:05:00.207Z Has data issue: false hasContentIssue false
  • English
  • Français

Braess's paradox in a loss network

Part of: Special processes Computer system organization

Published online by Cambridge University Press:  14 July 2016

N. G. Bean ,
F. P. Kelly  and
P. G. Taylor
N. G. Bean*
Affiliation:
University of Adelaide
F. P. Kelly*
Affiliation:
University of Cambridge
P. G. Taylor*
Affiliation:
University of Adelaide
*
∗Postal address: Department of Applied Mathematics, University of Adelaide, SA 5005, Australia.
∗∗Postal address: The Statistical Laboratory, University of Cambridge, 16 Mill Lane, CB2 1SB, UK.
∗Postal address: Department of Applied Mathematics, University of Adelaide, SA 5005, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

Braess's paradox is said to occur in a network if the addition of an extra link leads to worse performance. It has been shown to occur in transportation networks (such as road networks) and also in queueing networks. Here, we show that it can occur in loss networks.

Keywords

LOSS NETWORKSBRAESS'S PARADOXBLOCKING PROBABILITIES

MSC classification

Primary: 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Secondary: 68M20: Performance evaluation; queueing; scheduling
Type
Research Papers
Information
Journal of Applied Probability , Volume 34 , Issue 1 , March 1997 , pp. 155 - 159
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

[1] 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 CrossRefGoogle Scholar
[2] Braess, D. (1968) Uber ein Paradoxen der Verkehrsplannung. Unternehmensforschung 12, 258–268.Google Scholar
[3] 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
[4] Calvert, B., Solomon, W. and Ziedins, I. (1997) Braess's paradox in a queueing network with state dependent routing. J. Appl. Prob. 34, 134–154.CrossRefGoogle Scholar
[5] Cohen, J. E. and Horowitz, P. (1991) Paradoxical behaviour of mechanical and electrical networks. Nature 352, 699–701.CrossRefGoogle Scholar
[6] Cohen, J. E. and Kelly, F. P. (1990) A paradox of congestion in a queueing network. J. Appl. Prob. 27, 730–734.CrossRefGoogle Scholar
[7] Fisk, C. (1979) More paradoxes in the equilibrium assignment problem. Transportation Res. B: Methodological 13, 305–309.CrossRefGoogle Scholar
[8] Frank, M. (1981) The Braess paradox. Math. Prog. 20, 283–302.CrossRefGoogle Scholar
[9] Gibbens, R. J., Hunt, P. J. and Kelly, F. P. (1989) Bistability in communication networks. In Disorder in Physical Systems. ed. Grimmett, G. R. and Walsh, D. J. A. Oxford University Press, Oxford. pp. 113–128.Google Scholar
[10] Irvine, A. D. (1993) How Braess' paradox solves Newcomb's problem. Int. Studies Phil. Sci. 7, 141–160.CrossRefGoogle Scholar
[11] Kelly, F. P. (1988) Routing in circuit-switched networks: optimization, shadow prices and decentralization. Adv. Appl. Prob. 20, 112–144.CrossRefGoogle Scholar
[12] Kelly, F. P. (1991) Loss networks. Ann. Appl. Prob. 1, 319–378.CrossRefGoogle Scholar
[13] Kelly, F. P. (1991) Network routing. Phil. Trans. R. Soc. London A 337, 343–367.Google Scholar
[14] Knödel, W. (1969) Graphentheoretische Methoden und ihre Anwendungen. Springer, Berlin.CrossRefGoogle Scholar
[15] Krupp, R. S. (1982) Stabilization of alternate routing networks. In IEEE International Communications Conference. Paper 31.2.Google Scholar
[16] Lablanc, L. J. (1975) An algorithm for the discrete network design problem. Transportation Sci. 9, 183–199.CrossRefGoogle Scholar
[17] Murchland, J. D. (1970) Braess's paradox of traffic flow. Transportation Res. 4, 391–394.CrossRefGoogle Scholar
[18] Nakagome, Y. and Mori, H. (1973) Flexible routing in the global communication network. In Seventh International Teletraffic Congress, ITC 7. Stockholm.Google Scholar
[19] Steinberg, R. and Zangwill, W. I. (1983) The prevalence of Braess' paradox. Transportation Sci. 17, 301–318.CrossRefGoogle Scholar
[20] Stewart, N. F. (1980) Equilibrium vs system-optimal flow: some examples. Transportation Res. A: General. 14, 81–84.CrossRefGoogle Scholar
[21] Wardrop, J. G. (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. II 1, 325–378.Google Scholar
[22] Whitt, W. (1992) Counterexamples for comparisons of queues with finite waiting rooms. Queueing Systems 10, 271–278.CrossRefGoogle Scholar
[23] Wroe, G. A., Cope, G. A. and Whitehead, M. J. (1990) Flexible routing in the BT international access network. In 7th United Kingdom Teletraffic Symposium, Durham , pp. 21/1–21/7.Google Scholar