Bottleneck Routing with Elastic Demands
Pages 384 - 397
Abstract
Bottleneck routing games are a well-studied model to investigate the impact of selfish behavior in communication networks. In this model, each user selects a path in a network for routing their fixed demand. The disutility of a used only depends on the most congested link visited. We extend this model by allowing users to continuously vary the demand rate at which data is sent along the chosen path. As our main result we establish tight conditions for the existence of pure strategy Nash equilibria.
References
[1]
Banner R and Orda A Bottleneck routing games in communication networks IEEE J. Sel. Area Commun. 2007 25 6 1173-1179
[2]
Busch, C., Kannan, R., Samman, A.: Bottleneck routing games on grids. In: Proceedings 2nd International ICST Conference on Game Theory for Networks, pp. 294–307 (2011)
[3]
Busch C and Magdon-Ismail M Atomic routing games on maximum congestion Theor. Comput. Sci. 2009 410 36 3337-3347
[4]
Caragiannis I, Galdi C, and Kaklamanis C Deng X and Du D-Z Network load games Algorithms and Computation 2005 Heidelberg Springer 809-818
[5]
Cole, R., Dodis, Y., Roughgarden, T.: Bottleneck links, variable demand, and the tragedy of the commons. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 668–677 (2006)
[6]
Cominetti R and Guzman C Network congestion control with markovian multipath routing Math. Program. Ser. A 2014 147 1–2 231-251
[7]
de Keijzer B, Schäfer G, and Telelis OA Kontogiannis S, Koutsoupias E, and Spirakis PG On the inefficiency of equilibria in linear bottleneck congestion games Algorithmic Game Theory 2010 Heidelberg Springer 335-346
[8]
Gai, Y., Liu, H., Krishnamachari, B.: A packet dropping mechanism for efficient operation of queues with selfish users. In: Proceedings of the 30th IEEE International Conference on Computer Communications, pp. 2687–2695 (2011)
[9]
Han H, Shakkottai S, Hollot CV, Srikant R, and Towsley DF Multi-path TCP: a joint congestion control and routing scheme to exploit path diversity in the internet IEEE/ACM Trans. Netw. 2006 16 6 1260-1271
[10]
Harks T, Hoefer M, Klimm M, and Skopalik A Computing pure nash and strong equilibria in bottleneck congestion games Math. Program. Ser. A 2013 141 193-215
[11]
Harks, T., Hoefer, M., Schewior, K., Skopalik, A.: Routing games with progressive filling. In: Proceedings of the 33rd IEEE International Conference on Computer Communications, pp. 352–360 (2014)
[12]
Harks, T., Klimm, M.: Congestion games with variable demands. In: Apt, K. (ed.) Proceedings of the 13th Conference Theoretical Aspects of Rationality and Knowledge, pp. 111–120 (2011)
[13]
Harks, T., Klimm, M.: Equilibria in a class of aggregative location games. J. Math. Econom. (2015) forthcoming
[14]
Harks T, Klimm M, and Möhring R Strong equilibria in games with the lexicographical improvement property Internat. J. Game Theory 2012 42 2 461-482
[15]
Kakutani S A generalization of Brouwer’s fixed point theorem Duke Math. J. 1941 8 3 457-458
[16]
Kannan R and Busch C Kontogiannis S, Koutsoupias E, and Spirakis PG Bottleneck congestion games with logarithmic price of anarchy Algorithmic Game Theory 2010 Heidelberg Springer 222-233
[17]
Kannan R, Busch C, and Vasilakos AV Jain R and Kannan R Optimal price of anarchy of polynomial and super-polynomial bottleneck congestion games Game Theory for Networks 2012 Heidelberg Springer 308-320
[18]
Kelly F, Maulloo A, and Tan D Rate control in communication networks: Shadow prices, proportional fairness, and stability J. Oper. Res. Soc. 1998 49 237-252
[19]
Keshav S An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network 1997 Boston Addison-Wesley
[20]
Key PB, Massoulié L, and Towsley DF Path selection and multipath congestion control Commun. ACM 2011 54 1 109-116
[21]
Key PB and Proutiere A Routing games with elastic traffic SIGMETRICS Perform. Eval. Rev. 2009 37 2 63-64
[22]
Korilis Y and Lazar A On the existence of equilibria in noncooperative optimal flow control J. ACM 1995 42 3 584-613
[23]
Kukushkin, N.: Acyclicity of improvements in games with common intermediate objectives. Russian Academy of Sciences, Dorodnicyn Computing Center, Moscow (2004)
[24]
Kukushkin N Congestion games revisited Internat. J. Game Theory 2007 36 57-83
[25]
Miller, K., Harks, T.: Utility max-min fair congestion control with time-varying delays. In: Proceedings of the 27th IEEE International Conference on Computer Communicatins, pp. 331–335 (2008)
[26]
Paganini F and Mallada E A unified approach to congestion control and node-based multipath routing IEEE/ACM Trans. Netw. 2009 17 5 1413-1426
[27]
Qiu L, Yang Y, Zhang Y, and Shenker S On selfish routing in Internet-like environments IEEE/ACM Trans. Netw. 2006 14 4 725-738
[28]
Rosenthal R A class of games possessing pure-strategy Nash equilibria Internat. J. Game Theory 1973 2 1 65-67
[29]
Sheffi Y Urban Transp. Netw. 1985 Upper Saddle River Prentice-Hall
[30]
Shenker S Fundamental design issues for the future Internet IEEE J. Sel. Area Commun. 1995 13 1176-1188
[31]
Srikant R The Mathematics of Internet Congestion Control 2003 Basel Birkhäuser
[32]
Voice T Stability of multi-path dual congestion control algorithms IEEE/ACM Trans. Netw. 2007 15 6 1231-1239
[33]
Wardrop, J.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers (Part II), vol. 1, pp. 325–378 (1952)
[34]
Wydrowski B, Andrew LLH, and Zukerman M Maxnet: a congestion control architecture for scalable networks IEEE Commun. Lett. 2003 7 511-513
[35]
Yang D, Xue G, Fang X, Misra S, and Zhang J A game-theoretic approach to stable routing in max-min fair networks IEEE/ACM Trans. Netw. 2013 21 6 1947-1959
[36]
Zhang Y, Kang S, and Loguinov D Delay-independent stability and performance of distributed congestion control IEEE/ACM Trans. Netw. 2007 15 4 838-851
[37]
Zhang Y, Leonard D, and Loguinov D Jetmax: scalable max-min congestion control for high-speed heterogeneous networks Comput. Netw. 2008 52 6 1193-1219
[38]
Zhang Y and Loguinov D On delay-independent diagonal stability of max-min congestion control IEEE Trans. Autom. Control 2009 54 5 1111-1116
Index Terms
- Bottleneck Routing with Elastic Demands
Index terms have been assigned to the content through auto-classification.
Recommendations
Strategic Pricing in Next-Hop Routing with Elastic Demands
We consider a model of next-hop routing by self-interested agents. In this model, nodes in a graph (representing ISPs, Autonomous Systems, etc.) make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, ...
Strategic pricing in next-hop routing with elastic demands
SAGT'11: Proceedings of the 4th international conference on Algorithmic game theoryWe consider a model of next-hop routing by self-interested agents. In this model, nodes in a graph (representing ISPs, Autonomous Systems, etc.) make pricing decisions of how much to charge for forwarding traffic from each of their upstream neighbors, ...
A game theoretic framework for joint routing and pricing in networks with elastic demands
VALUETOOLS '09: Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and ToolsIn this paper, we study the economic interactions between network users and providers. Each user must ship his traffic from a source to a destination node, splitting it over multiple paths, each owned by an independent network provider. Users are ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2015
427 pages
© Springer-Verlag Berlin Heidelberg 2015.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 09 December 2015
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 29 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in