More Web Proxy on the site http://driver.im/

article

A game-theoretic approach towards congestion control in communication networks

Authors:

Varun KhuranaAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 32, Issue 3

Pages 47 - 61

https://doi.org/10.1145/571697.571723

Published: 01 July 2002 Publication History

Abstract

Most of the end-to-end congestion control schemes are "voluntary" in nature and critically depend on end-user cooperation. We show that in the presence of selfish users, all such schemes will inevitably lead to a congestion collapse. Router and switch mechanisms such as service disciplines and buffer management policies determine the sharing of resources during congestion. We show, using a game-theoretic approach, that all currently proposed mechanisms, either encourage the behaviour that leads to congestion or are oblivious to it.We propose a class of service disciplines called the Diminishing Weight Schedulers (DWS) that punish misbehaving users and reward congestion avoiding well behaved users. We also propose a sample service discipline called the Rate Inverse Scheduling (RIS) from the class of DWS schedulers. With DWS schedulers deployed in the network, max-min fair rates constitute a unique Nash and Stackelberg Equilibrium. We show that RIS solves the problems of excessive congestion due to unresponsive flows, aggressive versions of TCP, multiple parallel connections and is also fair to TCP.

References

[1]

Network simulator (NS), 2001. URL: http://www.isi.edu/nsnam/ns/.]]

[2]

A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan. Priority encoding transmission. In IEEE Symposium on Foundations of Computer Science, pages 604-612, 1994.]]

Digital Library

[3]

J. C. R. Bennett and H. Zhang. WF2Q: worst-case fair weighted fair queueing. In Proceedings of INFOCOM, pages 120-128, San Fransisco, California, Mar. 1996.]]

[4]

D. P. Bertsekas and R. G. Gallager. Data Networks. Prentice Hall, Englewood Cliffs, NJ, USA, 1992.]]

Digital Library

[5]

L. S. Brakmo and S. W. O'Malley. TCP Vegas: New techniques for congestion detection and avoidance. In Proceedings of SIGCOMM, pages 34-35, London, United Kingdom, Aug. 1994. ACM.]]

Digital Library

[6]

A. K. Choudhury and E. L. Hahne. Dynamic queue length thresholds in a shared memory ATM switch. In Proceedings of INFOCOM, San Fransisco, California, Mar. 1996.]]

[7]

S. Floyd. Congestion control principles. Request for Comments 2914, Internet Engineering Task Force, Sept. 2000.]]

Digital Library

[8]

S. Floyd and K. Fall. Promoting the use of end-to-end congestion control in the internet. IEEE/ACM Transactions on Networking, 7(4):458-472, August 1999.]]

Digital Library

[9]

S. Floyd and T. Henderson. The NewReno modification to TCP's fast recovery algorithm. Request for Comments 2582, Internet Engineering Task Force, Apr. 1999.]]

Digital Library

[10]

S. Floyd and V. Jacobson. Random early detection gateways for congestion avoidance. ACM/IEEE Transactions on Networking, 1(4):397-413, Aug. 1993.]]

Digital Library

[11]

D. Fudenberg and J. Tirole. Game Theory. MIT Press, October 1991.]]

[12]

R. Garg, A. Kamra, and V. Khurana. Eliciting cooperation from selfish users: A game-theoretic approach towards congestion control in communication networks. Technical Report RI01001, IBM Research, April 2001. Available at http://www.research.ibm.com/resources/paper_search.html.]]

[13]

S. J. Golestani. A self-clocked fair queuing scheme for broadband applications. In Proceedings of INFOCOM, pages 636-646, April 1994.]]

[14]

V. Jacobson. Congestion avoidance and control. Computer Communications Review, 18(4):314-329, Aug. 1988.]]

Digital Library

[15]

J. M. Jaffe. Bottleneck flow control. IEEE Transactions on Communications, 29(7):954-962, 1981.]]

[16]

R. Jain, S. Kalyanaraman, R. Goyal, S. Fahmy, and R. Viswanathan. ERICA switch algorithm: A complete description. Technical report, ATM Forum/96-1172, August 1996.]]

[17]

H. T. Kung, T. Blackwell, and A. Chapman. Credit update protocol for flow-controlled ATM networks: Statistical multiplexing and adaptive credit allocation. In Proceedings of SIGCOMM, pages 101-114, London, UK, Sept. 1994.]]

Digital Library

[18]

D. Lin and R. Morris. Dynamics of random early detection. In Proceedings of the ACM SIGCOMM'97 Conference, pages 127-138, New York, September 1997.]]

Digital Library

[19]

M. Mathis and J. Mahdavi. Forward acknowledgement: Refining TCP congestion control. Computer Communications Review, 26(4):281-291, Oct. 1996.]]

Digital Library

[20]

M. Mathis, J. Mahdavi, S. Floyd, and A. Romanow. TCP selective acknowledgement options. Request for Comments 2018, Internet Engineering Task Force, Oct. 1996.]]

Digital Library

[21]

J. Mo, R. La, V. Anantharam, and J. Walrand. Analysis and comparison of TCP Reno and Vegas. In Proceedings of INFOCOM, New York, Mar. 1999.]]

[22]

A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control - the single node case. In Proceedings of INFOCOM, May 1992.]]

Digital Library

[23]

J. Postel. Transmission control protocol. Request for Comments 793, Internet Engineering Task Force, Sept. 1981.]]

Digital Library

[24]

W. Prue and J. Postel. Something a host could do with source quench: The source quench introduced delay (SQuID). Request for Comments 1016, Internet Engineering Task Force, July 1987.]]

Digital Library

[25]

K. Ramakrishnan and S. Floyd. A proposal to add explicit congestion notification (ECN) to IP. Request for Comments 2481, Internet Engineering Task Force, Jan. 1999.]]

Digital Library

[26]

K. Ramakrishnan and R. Jain. A binary feedback scheme for congestion avoidance in computer networks,. ACM Trans. on Computer Systems, 8(2):158-181, May 1990.]]

Digital Library

[27]

S. Shenker. Making greed work in networks: A game-theoretic analysis of switch service disciplines. In Proceedings of SIGCOMM, pages 47-57, London, UK, Sept. 1994.]]

Digital Library

[28]

D. Stiliadis and A. Varma. Design and analysis of frame-based fair queuing: A new traffic scheduling algorithm for packet switched networks. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 104-115, New York, May 1996.]]

Digital Library

[29]

I. Stoica, S. Shenker, and H. Zhang. Core-stateless fair queueing: Achieving approximately fair bandwidth allocations in high speed networks. In ACM Sigcomm '98, Septermber 1998.]]

Digital Library

[30]

B. Suter, T. V. Lakshman, D. Stiliadis, and A. K. Choudhury. Buffer management schemes for supporting TCP in gigabit routers with per-flow queueing. IEEE Journal on Selected Areas in Communications, 17(6):1159-1169, June 1999.]]

Digital Library

[31]

A. Varma and D. Stiliadis. Hardware implementation of fair queueing algorithms for asynchronous transfer mode networks. IEEE Communications Magzine, pages 54-68, December 1997.]]

[32]

C.-Q. Yang and A. V. S. Reddy. A taxonomy for congestion control algorithms in packet switching networks. IEEE Network Magazine, 9(5), July/August 1995.]]

[33]

H. Zhang and J. C. R. Bennett. Hierarchical packet fair queueing algorithms. In Proceedings of ACM SIGCOMM, pages 143-156. ACM, September 1997.]]

Digital Library

[34]

L. Zhang. Virtual clock : A new traffic control algorithm for packet switching networks. ACM Transactions on Computer Systems, 9:101-124, May 1991.]]

Digital Library

Cited By

Huang ZLiu KPan J(2023)End-to-End Congestion Control as Learning for Unknown Games with Bandit Feedback2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00060(327-338)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00060
Taye GSharma SShah PNuriye Y(2023)Exploring the Role of Artificial Intelligence in Class Scheduling and Management: A Comprehensive Survey and Review2023 International Conference on Computer Science and Emerging Technologies (CSET)10.1109/CSET58993.2023.10346898(1-11)Online publication date: 10-Oct-2023
https://doi.org/10.1109/CSET58993.2023.10346898
Ignatenko OMolchanov O(2016)Evolutionary games in TCP networks with speed restriction policiesPROBLEMS IN PROGRAMMING10.15407/pp2016.04.033(033-047)Online publication date: Dec-2016
https://doi.org/10.15407/pp2016.04.033
Show More Cited By

Index Terms

A game-theoretic approach towards congestion control in communication networks
1. Human-centered computing
  1. Human computer interaction (HCI)
    1. Interaction paradigms
2. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers
  2. Network protocols

Recommendations

On Explicit Congestion Notification for Stream Control Transmission Protocol in Lossy Networks

As a congestion avoidance mechanism, Explicit Congestion Notification (ECN) is designed to inform a data source to react to potential congestion early. Currently, the new transport protocol, Stream Control Transmission Protocol (SCTP), is not ECN-...
An efficient and fair explicit congestion control protocol for high bandwidth-delay product networks

XCP and VCP can achieve excellent performance under high bandwidth-delay product networks, but they all have some defects. In XCP, router needs to calculate a feedback for each departing packet, the cost will be un-negligible in high-speed networks. In ...
Multicasting with Localized Control in Wireless Ad Hoc Networks

This paper investigates how to support multicasting in wireless ad hoc networks without throttling the dominant unicast flows. Unicast flows are usually congestion-controlled with protocols like TCP. However, there are no such protocols for multicast ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 32, Issue 3

July 2002

79 pages

ISSN:0146-4833

DOI:10.1145/571697

Issue’s Table of Contents

Copyright © 2002 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2002

Published in SIGCOMM-CCR Volume 32, Issue 3

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
1,299
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZLiu KPan J(2023)End-to-End Congestion Control as Learning for Unknown Games with Bandit Feedback2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS57875.2023.00060(327-338)Online publication date: Jul-2023
https://doi.org/10.1109/ICDCS57875.2023.00060
Taye GSharma SShah PNuriye Y(2023)Exploring the Role of Artificial Intelligence in Class Scheduling and Management: A Comprehensive Survey and Review2023 International Conference on Computer Science and Emerging Technologies (CSET)10.1109/CSET58993.2023.10346898(1-11)Online publication date: 10-Oct-2023
https://doi.org/10.1109/CSET58993.2023.10346898
Ignatenko OMolchanov O(2016)Evolutionary games in TCP networks with speed restriction policiesPROBLEMS IN PROGRAMMING10.15407/pp2016.04.033(033-047)Online publication date: Dec-2016
https://doi.org/10.15407/pp2016.04.033
Brun O(2016)PERFORMANCE OF NON-COOPERATIVE ROUTING OVER PARALLEL NON-OBSERVABLE QUEUESProbability in the Engineering and Informational Sciences10.1017/S026996481600009730:3(455-469)Online publication date: 19-May-2016
https://doi.org/10.1017/S0269964816000097
Jingyu Wang Jianxin Liao Jing Wang Qi Qi Shengwen Tian Tonghong Li (2014)Introducing collaborations for multi-path selection of multiple selfish overlays2014 IEEE Symposium on Computers and Communications (ISCC)10.1109/ISCC.2014.6912456(1-6)Online publication date: Jun-2014
https://doi.org/10.1109/ISCC.2014.6912456
Wang JLiao JLi TWang J(2014)On the collaborations of multiple selfish overlays using multi-path resourcesPeer-to-Peer Networking and Applications10.1007/s12083-013-0245-z8:2(203-215)Online publication date: 3-Jan-2014
https://doi.org/10.1007/s12083-013-0245-z
Canzian LYuanzhang Xiao Zame WZorzi Mvan der Schaar M(2013)Intervention with Complete and Incomplete Information: Application to Flow ControlIEEE Transactions on Communications10.1109/TCOMM.2013.061013.12055961:8(3206-3218)Online publication date: Aug-2013
https://doi.org/10.1109/TCOMM.2013.061013.120559
Andon FIgnatenko O(2013)Modeling conflict processes on the internetCybernetics and Systems Analysis10.1007/s10559-013-9548-649:4(616-623)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1007/s10559-013-9548-6
Park Jvan der Schaar M(2012)The Theory of Intervention Games for Resource Sharing in Wireless CommunicationsIEEE Journal on Selected Areas in Communications10.1109/JSAC.2012.12011530:1(165-175)Online publication date: Jan-2012
https://doi.org/10.1109/JSAC.2012.120115
Kesselman ALeonardi S(2012)Game-theoretic analysis of Internet switching with selfish usersTheoretical Computer Science10.1016/j.tcs.2012.05.029452(107-116)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.tcs.2012.05.029
Show More Cited By

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 Publication

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