Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-06T09:54:34.008Z Has data issue: false hasContentIssue false
  • English
  • Français

Avoiding the Braess paradox in non-cooperative networks

Part of: Special processes

Published online by Cambridge University Press:  14 July 2016

Yannis A. Korilis ,
Aurel A. Lazar  and
Ariel Orda
Yannis A. Korilis*
Affiliation:
Lucent Technologies
Aurel A. Lazar*
Affiliation:
Columbia University
Ariel Orda*
Affiliation:
Technion
*
∗Postal address: Bell Laboratories, Lucent Technologies, Holmdel, NJ 07733, USA.
∗∗Postal address: Department of Electrical Engineering, Columbia University, New York, NY 10027, USA.
∗∗∗Postal address: Department of Electrical Engineering, Technion, Haifa 32000, Israel. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The exponential growth of computer networking demands massive upgrades in the capacity of existing networks. Traditional capacity design methodologies, developed with the single-class networking paradigm in mind, overlook the non-cooperative structure of modern networks. Consequently, such design approaches entail the danger of degraded performance when resources are added to a network, a phenomenon known as the Braess paradox.

The present paper proposes methods for adding resources efficiently to a non-cooperative network of general topology. It is shown that the paradox is avoided when resources are added across the network, rather than on a local scale, and when upgrades are focused on direct connections between the sources and destinations. The relevance of these results for modern networks is demonstrated.

Keywords

Braess Paradoxcomputer communication networksnon-cooperative gamesrouteing

MSC classification

Primary: 60K30: Applications (congestion, allocation, storage, traffic, etc.)
Type
Research Papers
Information
Journal of Applied Probability , Volume 36 , Issue 1 , March 1999 , pp. 211 - 222
Copyright
Copyright © Applied Probability Trust 1999 

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

Altman, E. (1994). Flow control using the theory of Zero-Sum Markov games. IEEE Trans. Automatic Control 39, 814–818.Google Scholar
Bean, N. G., Kelly, F. P., and Taylor, P. G. (1997). Braess' paradox in a loss network. J. Appl. Prob. 34, 155–159.CrossRefGoogle Scholar
Ben-Israel, A., Ben-Tal, A., and Zlobec, S. (1981). Optimality in Nonlinear Programming: a Feasible Directions Approach. Wiley, New York.Google Scholar
Bertsekas, D., and Gallager, R. (1992). Data Networks, 2nd edn. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Cohen, J. E., and Kelly, F. P. (1990). A paradox of congestion in a queuing network. J. Appl. Prob. 27, 730–734.Google Scholar
Cohen, J. E., and Horwitz, P. (1991). Paradoxical behaviour of mechanical and electrical networks. Nature 352, 699–701.Google Scholar
Cohen, J. E., and Jeffries, C. (1997). Congestion resulting from increased capacity in single-server queueing networks. IEEE/ACM Trans. Networking 5, 305–310.Google Scholar
Dafermos, S., and Nagurney, A. (1984). On some traffic equilibrium theory paradoxes. Transportation Research B 18, 101–110.Google Scholar
Dubey, P. (1986). Inefficiency of Nash equilibria. Math. Operat. Res. 11, 1–8.Google Scholar
Glance, N. S., and Hogg, T. (1995). Dilemmas in computational societies. In Proc. 1st International Conference on Multiagent Systems, San Francisco, CA, June 1995, pp. 117–124.Google Scholar
Irvine, A. D. (1993). How Braess' paradox solves Newcomb's problem. Internat. Stud. Philos. Sci. 7, 141–160.Google Scholar
Korilis, Y. A., Lazar, A. A., and Orda, A. (1995). Architecting non-cooperative networks. IEEE J. Sel. Areas Commun. 13, 1241–1251.Google Scholar
Korilis, Y. A., Lazar, A. A., and Orda, A. (1997). Achieving network optima using Stackelberg routing strategies. IEEE/ACM Trans. Networking 5, 161–173.Google Scholar
Korilis, Y. A., Lazar, A. A., and Orda, A. (1997). Capacity allocation under non-cooperative routing. IEEE Trans. Automatic Control 42, 309–325.Google Scholar
Luenberger, D. G. (1984). Linear and Nonlinear Programming, 2nd edn. Addison Wesley, Reading, MA.Google Scholar
Myerson, R. B. (1991). Game Theory: Analysis of Conflict. Harvard University Press, Cambridge, MA.Google Scholar
Nicholson, W. (1994). Intermediate Microeconomics and its Applications, 6th edn. Dryden Press, Fort Worth, TX.Google Scholar
Orda, A., Rom, R., and Shimkin, N. (1993). Competitive routing in multiuser communication networks. IEEE/ACM Trans. Networking 1, 510–521.CrossRefGoogle Scholar
Zhang, Z., and Douligeris, C. (1992). Convergence of synchronous and asynchronous greedy algorithms in a multiclass telecommunications environment. IEEE Trans. Commun. 40, 1277–1281.Google Scholar