|
 ABSTRACT
We study the problem of routing traffic through a congested network. We focus on the simplest case of a network consisting of m parallel links. We assume a collection of n network users, each employing a mixed strategy which is a probability distribution over links, to control the shipping of its own assigned traffic. Given a capacity for each link specifying the rate at which the link processes traffic, the objective is to route traffic so that the maximum expected latency over all links is minimized. We consider both uniform and non-uniform link capacities.How much decrease in global performace is necessary due to the absence of some central authority to regulate network traffic and implement an optimal assignment of traffic to links? We investigate this fundamental question in the context of Nash equilibria for such a system, where each network user selfishly routes its traffic only on those links available to it that minimize its expected latency cost, given the network congestion caused by the other users. We use the coordination ratio, defined by Koutsoupias and Papadimitriou [25] as the ratio of the maximum (over all links) expected latency in the worst possible Nash equlibrium, over the least possible maximum latency had global regulation been available, as a measure of the cost of lack of coordination among the network users.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
E. Altman, "Flow Control Using the Theory of Zero-Sum Markov Games," IEEE Transactions on Automatic Control, Vol. 39, pp. 814-818, April 1994.
|
| |
2
|
E. Altman, T. Basar, T. Jimenez and N. Shimkin, "Competitive Routing in Networks with Polynomial Cost," Proceedings of the 19th IEEE Conference on Computer Communications (IEEE INFOCOM 2000), March 2000.
|
| |
3
|
D. Angluin and L. G. Valiant, "Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings," Journal of Computer and System Sciences, Vol. 18, pp. 155-193, 1979.
|
| |
4
|
Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
|
 |
5
|
Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada
[doi> 10.1145/195058.195412]
|
| |
6
|
T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory, SIAM Series in Classics in Applied Mathematics, Philadelphia, 1999.
|
| |
7
|
|
| |
8
|
J. J. Carrahan, P. A. Russo, K. Kitami and R. Kung, "Intelligent Network Overview," IEEE Communications Magazine, Vol. 31, pp. 30-36, March 1993.
|
| |
9
|
H. Chernoff, "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations," Annals of Mathematical Statistics, Vol. 23, pp. 493-509, 1952.
|
| |
10
|
S. Deering and R. Hinden, Internet Protocol Version 6 Specifacation, Internet Draft, IETF, March 1995.
|
| |
11
|
|
| |
12
|
A. A. Economides and J. A. Silvester, "Multi-objective Routing in Integrated Services Networks: A Game Theory Approach," Proceedings of the IEEE Conference on Computer Communications (IEEE INFOCOM 1991), pp. 1220-1225, 1991.
|
| |
13
|
Joan Feigenbaum , Christos Papadimitriou , Scott Shenker, Sharing the cost of muliticast transmissions (preliminary version), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.218-227, May 21-23, 2000, Portland, Oregon, United States
[doi> 10.1145/335305.335332]
|
| |
14
|
G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford Science Publications, Second Edition, 1992.
|
| |
15
|
M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed (eds.), Probabilistic Methods in Algorithmic Discrete Mathematics, Vol. 16 in Algorithms and Combinatorics, Springer, 1998.
|
| |
16
|
|
| |
17
|
N. L. Johnson and S. Kotz, Urn Models and Their Applications, John Wiley & Sons, 1977.
|
| |
18
|
|
| |
19
|
V. F. Kolchin, V. P. Chistiakov and B. A. Sevastianov, Random Allocations, V. H. Winston, New York, 1978.
|
| |
20
|
|
| |
21
|
Y. A. Korilis, A. A. Lazar and A. Orda, "Architecting Noncooperative Networks," IEEE Journal on Selected Areas in Communications, Vol. 13, No. 7, pp. 1241-1251, 1995.
|
| |
22
|
|
| |
23
|
Y. A. Korilis, A. A. Lazar and A. Orda, "Capacity Allocation under Noncooperative Routing," IEEE Transactions on Automatic Control, Vol. 42, No. 3, pp. 309-325, 1997.
|
| |
24
|
Y. A. Korilis, A. A. Lazar and A. Orda, "Avoiding the Braess Paradox in Non-Cooperative Networks," Journal of Applied Probability, Vol. 36, pp. 211-222, 1999.
|
| |
25
|
E. Koutsoupias and C. H. Papadimitriou, "Worst-case Equilibria," Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, G. Meinel and S. Tison eds., pp. 404-413, Vol. 1563, Lecture Notes in Computer Science, Springer-Verlag, Trier, Germany, March 1999.
|
| |
26
|
|
| |
27
|
|
| |
28
|
M. Mavronicolas, A. Mouskos and P. Spirakis, "The Cost of Lack of Coordination in Distributed Network Routing," unpublished manuscript, April 2000.
|
| |
29
|
R. D. McKelvey and A. McLennan, "Computation of Equilibria in Finite Games," in Handbook of Computational Economics, Vol. 1, pp. 87-142, 1996.
|
| |
30
|
|
| |
31
|
J. F. Nash, "Non-cooperative Games," Annals of Mathematics, Vol. 54, No. 2, pp. 286-295, 1951.
|
| |
32
|
|
| |
33
|
M. J. Osborne and A. Rubinstein, A Course in Game Theory, The MIT Press, 1994.
|
| |
34
|
G. Owen, Game Theory, Third Edition, Academic Press, 1995.
|
| |
35
|
|
| |
36
|
|
| |
37
|
Z. Zhang and C. Douligeris, "Convergence of Synchronous and Asynchronous Greedy Algorithms in a Multiclass Telecommunications Environment," IEEE Transactions on Computers, Vol. 40, pp. 1277-1281, August 1992.
|
CITED BY 43
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Elliot Anshelevich , Anirban Dasgupta , Eva Tardos , Tom Wexler, Near-optimal network design with selfish agents, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alex Fabrikant , Ankur Luthra , Elitza Maneva , Christos H. Papadimitriou , Scott Shenker, On a network creation game, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.347-351, July 13-16, 2003, Boston, Massachusetts
|
|
|
|
|
|
|
|
|
Petra Berenbrink , Tom Friedetzky , Leslie Ann Goldberg , Paul Goldberg , Zengjian Hu , Russell Martin, Distributed selfish load balancing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.354-363, January 22-26, 2006, Miami, Florida
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Michele Flammini , Gianpiero Monaco , Luca Moscardelli , Mordechai Shalom , Shmuel Zaks, Selfishness, collusion and power of local search for the ADMs minimization problem, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.9, p.1721-1731, June, 2008
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2