article

A game-theoretic approach to stable routing in max-min fair networks

Editor: R. Srikant Authors:

Satyajayant Misra,

Jin ZhangAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 21, Issue 6

Pages 1947 - 1959

https://doi.org/10.1109/TNET.2013.2247416

Published: 01 December 2013 Publication History

Abstract

In this paper, we present a game-theoretic study of the problem of routing in networks with max-min fair congestion control at the link level. The problem is formulated as a noncooperative game, in which each user aims to maximize its own bandwidth by selecting its routing path. We first prove the existence of Nash equilibria. This is important, because at a Nash equilibrium (NE), no user has any incentive to change its routing strategy--leading to a stable state. In addition, we investigate how the selfish behavior of users may affect the performance of the network as a whole. We next introduce a novel concept of observed available bandwidth on each link. It allows a user to find a path with maximum bandwidth under max-min fair congestion control in polynomial time, when paths of other users are fixed. We then present a game-based algorithm to compute an NE and prove that by following the natural game course, the network converges to an NE. Extensive simulations show that the algorithm converges to an NE within 10 iterations and also achieves better fairness compared to other algorithms.

References

[1]

R. Banner and A. Orda, "Bottleneck routing games in communication networks," IEEE J. Sel. Areas Commun., vol. 25, no. 6, pp. 1173-1179, Aug. 2007.

[2]

J. Behrens and J. Garcia-Luna-Aceves, "Distributed, scalable routing based on link-state vectors," in Proc. ACM SIGCOMM, 1994, pp. 136-147.

[3]

D. Bertsekas, R. Gallager, and P. Humblet, Data Networks. New York, NY, USA: Prentice-Hall, 1987.

[4]

Boston University, Boston, MA, USA, "BRITE," [Online]. Available: http://www.cs.bu.edu/brite/

[5]

A. Charny, D. Clark, and R. Jain, "Congestion control with explicit rate indication," in Proc. IEEE ICC, 1995, pp. 1954-1963.

[6]

S. Chen and K. Nahrstedt, "Max-min fair routing in connection-oriented networks," in Proc. Euro-Parallel Distrib. Syst. Conf., 1998, pp. 163-168.

[7]

C. Daskalakis, P. Goldberg, and C. Papadimitriou, "The complexity of computing a Nash equilibrium," in Proc. ACM STOC, 2006, pp. 71-78.

[8]

A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a fair queueing algorithm," in Proc. ACM SIGCOMM, 1989, pp. 1-12.

[9]

E. Dijkstra, "A note on two problems in connexion with graphs," Numer. Math., vol. 1, pp. 269-271, 1959.

[10]

M. Fredman and R. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms," J. ACM, vol. 34, pp. 596-615, 1987.

[11]

D. Fudenberg and J. Tirole, Game Theory. Cambridge, MA, USA: MIT Press, 1991.

[12]

L. Gao and J. Rexford, "Stable internet routing without global coordination," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 681-692, Dec. 2001.

[13]

P. Godfrey, M. Schapira, A. Zohar, and S. Shenker, "Incentive compatibility and dynamics of congestion control," in Proc. ACM SIGMETRICS, 2010, pp. 95-106.

[14]

T. Griffin, F. Shepherd, and G. Wilfong, "The stable paths problem and interdomain routing," IEEE/ACM Trans. Netw., vol. 10, no. 2, pp. 232-243, Apr. 2002.

[15]

T. Griffin and G. Wilfong, "A safe path vector protocol," in Proc. IEEE INFOCOM, 2000, pp. 490-499.

[16]

J. Jaffe, "Bottleneck flow control," IEEE Trans. Commun., vol. COM-29, no. 7, pp. 954-962, Jul. 1981.

[17]

E. Koutsoupias and C. Papadimitriou, "Worst-case equilibria," in Proc. ACM STACS, 1999, pp. 404-413.

[18]

Q. Ma, P. Steenkiste, and H. Zhang, "Routing high-bandwidth traffic in max-min fair share networks," in Proc. ACM SIGCOMM, 1996, pp. 206-217.

[19]

A. Mayer, Y. Ofek, and M. Yung, "Approximating max-min fair rates via distributed local scheduling with partial information," in Proc. IEEE INFOCOM, 1996, pp. 928-936.

[20]

D. Nace, N. Doan, E. Gourdin, and B. Liau, "Computing optimal max-min fair resource allocation for elastic flows," IEEE/ACM Trans. Netw., vol. 14, no. 6, pp. 1272-1281, Dec. 2006.

[21]

A. Nahir, A. Orda, and A. Freund, "Topology design and control: A game-theoretic perspective," in Proc. IEEE INFOCOM, 2009, pp. 1620-1628.

[22]

R. Braden, L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource ReSerVation Protocol (RSVP)," RFC 2205, 1997 [Online]. Available: http://tools.ietf.org/html/rfc2205

[23]

M. Schapira and A. Zohar, "Congestion-control games," 2008 [Online]. Available: http://leibniz.cs.huji.ac.il/tr/1060.pdf

[24]

M. Steenstrup, "Inter-domain policy routing protocol specification: Version 1," 1993.

[25]

B. Waxman, "Routing of multipoint connections," IEEE J. Sel. Areas Commun., vol. 6, no. 9, pp. 1617-1622, Dec. 1988.

[26]

D. Yang, G. Xue, X. Fang, S. Misra, and J. Zhang, "Routing in max-min fair networks: A game theoretic approach," in Proc. IEEE ICNP, 2010, pp. 1-10.

Cited By

Dong XLi WZhou XLi KQi H(2020)TINA: A Fair Inter-datacenter Transmission Mechanism with Deadline GuaranteeIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155410(2017-2025)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1109/INFOCOM41043.2020.9155410
Harks THoefer MSchewior KSkopalik AHarks THoefer MSchewior KSkopalik A(2016)Routing Games With Progressive FillingIEEE/ACM Transactions on Networking10.1109/TNET.2015.246857124:4(2553-2562)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2468571
Harks TKlimm MSchneider M(2015)Bottleneck Routing with Elastic DemandsWeb and Internet Economics10.1007/978-3-662-48995-6_28(384-397)Online publication date: 9-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-662-48995-6_28
Show More Cited By

Index Terms

A game-theoretic approach to stable routing in max-min fair networks

Recommendations

Mechanism Design for Perturbation Stable Combinatorial Auctions
Abstract
Motivated by recent research on combinatorial markets with endowed valuations by (Babaioff et al., EC 2018) and (Ezra et al., EC 2020), we introduce a notion of perturbation stability in Combinatorial Auctions (CAs) and study the extent to which ...
Stackelberg Strategies for Selfish Routing in General Multicommodity Networks

A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an α fraction that are routed according to ...
On the Efficiency of All-Pay Mechanisms

We study the inefficiency of mixed Nash equilibria, expressed as the price of anarchy, of all-pay auctions in three different environments: combinatorial, multi-unit and single-item auctions. First, we consider item-bidding combinatorial auctions where ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 21, Issue 6

December 2013

334 pages

ISSN:1063-6692

Editor:
R. Srikant
Dept. Elect. & Comput. Eng., Univ. Illinois at Urbana-Champaign, Urbana, IL

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2013

Accepted: 26 December 2012

Revised: 10 December 2012

Received: 25 May 2012

Published in TON Volume 21, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dong XLi WZhou XLi KQi H(2020)TINA: A Fair Inter-datacenter Transmission Mechanism with Deadline GuaranteeIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155410(2017-2025)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1109/INFOCOM41043.2020.9155410
Harks THoefer MSchewior KSkopalik AHarks THoefer MSchewior KSkopalik A(2016)Routing Games With Progressive FillingIEEE/ACM Transactions on Networking10.1109/TNET.2015.246857124:4(2553-2562)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1109/TNET.2015.2468571
Harks TKlimm MSchneider M(2015)Bottleneck Routing with Elastic DemandsWeb and Internet Economics10.1007/978-3-662-48995-6_28(384-397)Online publication date: 9-Dec-2015
https://dl.acm.org/doi/10.1007/978-3-662-48995-6_28
Guo CKarsten M(undefined)On the feasibility of core-rooted path addressingNOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS.2016.7502826(306-314)
https://dl.acm.org/doi/10.1109/NOMS.2016.7502826

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents