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

research-article

Incentive compatibility and dynamics of congestion control

Authors:

P. Brighten Godfrey,

Michael Schapira,

Scott ShenkerAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 38, Issue 1

Pages 95 - 106

https://doi.org/10.1145/1811099.1811051

Published: 14 June 2010 Publication History

Abstract

his paper studies under what conditions congestion control schemes can be both efficient, so that capacity is not wasted, and incentive compatible, so that each participant can maximize its utility by following the prescribed protocol. We show that both conditions can be achieved if routers run strict priority queueing (SPQ) or weighted fair queueing (WFQ) and end-hosts run any of a family of protocols which we call Probing Increase Educated Decrease (PIED). A natural question is whether incentive compatibility and efficiency are possible while avoiding the per-flow processing of WFQ. We partially address that question in the negative by showing that any policy satisfying a certain "locality" condition cannot guarantee both properties.

Our results also have implication for convergence to some steady-state throughput for the flows. Even when senders transmit at a fixed rate (as in a UDP flow which does not react to congestion), feedback effects among the routers can result in complex dynamics which do not appear in the simple topologies studied in past work.

References

[1]

A. Akella, S. Seshan, R. Karp, S. Shenker, and C. Papadimitriou. Selfish behavior and stability of the internet: a game-theoretic analysis of tcp. SIGCOMM Comput. Commun. Rev., 32(4):117--130, 2002.

Digital Library

[2]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In SIGCOMM '89: Symposium proceedings on Communications architectures & protocols, pages 1--12, New York, NY, USA, 1989. ACM.

Digital Library

[3]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Journal of Internetworking Research and Experience, pages 3--26, October 1990.

[4]

J. Feigenbaum, C. H. Papadimitriou, R. Sami, and S. Shenker. A BGP-based mechanism for lowest-cost routing. Distributed Computing, 18(1):61--72, 2005.

Digital Library

[5]

J. Feigenbaum, C. H. Papadimitriou, and S. Shenker. Sharing the cost of multicast transmissions. Journal of Computer System Sciences, 63(1):21--41, 2001.

Digital Library

[6]

J. Feigenbaum, V. Ramachandran, and M. Schapira. Incentive-compatible interdomain routing. In EC '06: Proceedings of the 7th ACM conference on Electronic commerce, pages 130{139, New York, NY, USA, 2006. ACM.

Digital Library

[7]

J. Feigenbaum, M. Schapira, and S. Shenker. Distributed Algorithmic Mechanism Design. A chapter in "Algorithmic Game Theory". Cambridge University Press, 2007.

[8]

S. Floyd. Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic. Computer Communication Review (CCR), 21(5):30--47, October 1991.

Digital Library

[9]

S. Floyd. Connections with multiple congested gateways in packet-switched networks part 2: two-way traffic, 1991. Unpublished manuscript.

[10]

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, 1999.

Digital Library

[11]

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

Digital Library

[12]

R. J. Gibbens and F. P. Kelly. Resource pricing and the evolution of congestion control. Automatica, 35:1969--1985, 1999.

Digital Library

[13]

S. Goldberg, S. Halevi, A. D. Jaggard, V. Ramachandran, and R. N. Wright. Rationality and traffic attraction: incentives for honest path announcements in BGP. In SIGCOMM, pages 267--278, 2008.

Digital Library

[14]

V. Jacobson. Congestion avoidance and control. In ACM SIGCOMM '88, pages 314{329, Stanford, CA, August 1988.

Digital Library

[15]

F. Kelly. Mathematical modelling of the internet. In B. Engquist and W. Schmid, editors, Mathematics Unlimited - 2001 and Beyond, pages 685--702. Springer-Verlag, 2001.

[16]

F. P. Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommuncations, 8:33--37, 1997.

[17]

T. Kelly, S. Floyd, and S. Shenker. Patterns of congestion collapse, 2003. Unpublished manuscript.

[18]

E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, pages 404--413, 1999.

Digital Library

[19]

H. Levin, M. Schapira, and A. Zohar. Interdomain routing and games. In STOC 08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 57--66, Victoria, British Columbia, Canada, May 2008.

Digital Library

[20]

D. Lin and R. Morris. Dynamics of random early detection. SIGCOMM Comput. Commun. Rev., 27(4):127--137, 1997.

Digital Library

[21]

S. H. Low, F. Paganini, J. Wang, S. Adlakha, and J. C. Doyle. Dynamics of tcp/red and a scalable control. In In Proceedings of IEEE INFOCOM 2002, pages 239--248, 2002.

[22]

N. Nisan and A. Ronen. Algorithmic mechanism design. Games and Economic Behavior, 35(1):166--196, 2001.

[23]

R. Oliveira, B. Zhang, D. Pei, R. Izhak-Ratzin, and L. Zhang. Quantifying path exploration in the Internet. In Proc. Internet Measurement Conference, October 2006.

Digital Library

[24]

A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Trans. Netw., 1(3):344--357, 1993.

Digital Library

[25]

B. Raghavan and A. Snoeren. Decongestion control. In Proceedings of the Fifth Workshop on Hot Topics in Networks (HotNets-V), pages 61--66. ACM Press, November 2006.

[26]

I. Stoica, S. Shenker, and H. Zhang. Core-stateless fair queueing: Achieving approximately fair bandwidth allocations in high speed networks. In Proc. SIGCOMM, 1998.

Digital Library

[27]

K. Varadhan, R. Govindan, and D. Estrin. Persistent route oscillations in inter-domain routing. Computer Networks, 32(1):1--16, March 2000.

Cited By

Zarchy DMittal RSchapira MShenker S(2019)Axiomatizing Congestion ControlProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261483:2(1-33)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326148
Renganathan SPadmanabhan VNambi A(2018)Rethinking Networking for "Five Computers"Proceedings of the 17th ACM Workshop on Hot Topics in Networks10.1145/3286062.3286076(92-98)Online publication date: 15-Nov-2018
https://dl.acm.org/doi/10.1145/3286062.3286076
Jalaparti VBliznets IKandula SLucier BMenache IBarcellos MCrowcroft JVahdat AKatti S(2016)Dynamic Pricing and Traffic Engineering for Timely Inter-Datacenter TransfersProceedings of the 2016 ACM SIGCOMM Conference10.1145/2934872.2934893(73-86)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2934872.2934893
Show More Cited By

Index Terms

Incentive compatibility and dynamics of congestion control
1. Networks
  1. Network protocols
    1. Application layer protocols

Recommendations

Incentive compatibility and dynamics of congestion control
SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

his paper studies under what conditions congestion control schemes can be both efficient, so that capacity is not wasted, and incentive compatible, so that each participant can maximize its utility by following the prescribed protocol. We show that both ...
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-...
Comparative analysis of TCP congestion control mechanisms
NISS '20: Proceedings of the 3rd International Conference on Networking, Information Systems & Security

TCP (Transmission Control Protocol) is the most used transport protocol for wired and wireless networks. It provides many services (reliability, end to end delivery ...) to the applications running over the Internet, but to be able to manage traffics ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 38, Issue 1

Performance evaluation review

June 2010

382 pages

ISSN:0163-5999

DOI:10.1145/1811099

Issue’s Table of Contents

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2010
398 pages
ISBN:9781450300384
DOI:10.1145/1811039
General Chair:
Vishal Misra
Columbia University, USA
,
Program Chairs:
Paul Barford
University of Wisconsin-Madison, USA
,
Mark Squillante
IBM T.J. Watson Research Center, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2010

Published in SIGMETRICS Volume 38, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
367
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zarchy DMittal RSchapira MShenker S(2019)Axiomatizing Congestion ControlProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3341617.33261483:2(1-33)Online publication date: 19-Jun-2019
https://dl.acm.org/doi/10.1145/3341617.3326148
Renganathan SPadmanabhan VNambi A(2018)Rethinking Networking for "Five Computers"Proceedings of the 17th ACM Workshop on Hot Topics in Networks10.1145/3286062.3286076(92-98)Online publication date: 15-Nov-2018
https://dl.acm.org/doi/10.1145/3286062.3286076
Jalaparti VBliznets IKandula SLucier BMenache IBarcellos MCrowcroft JVahdat AKatti S(2016)Dynamic Pricing and Traffic Engineering for Timely Inter-Datacenter TransfersProceedings of the 2016 ACM SIGCOMM Conference10.1145/2934872.2934893(73-86)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2934872.2934893
Cheng YDeng XPi YYan X(2015)Can Bandwidth Sharing Be Truthful?Algorithmic Game Theory10.1007/978-3-662-48433-3_15(190-202)Online publication date: 10-Dec-2015
https://doi.org/10.1007/978-3-662-48433-3_15
Shi WZhang LWu CLi ZLau F(2014)An online auction framework for dynamic resource provisioning in cloud computingACM SIGMETRICS Performance Evaluation Review10.1145/2637364.259198042:1(71-83)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2637364.2591980
Shi WZhang LWu CLi ZLau FSanghavi SShakkottai SLelarge MSchroeder B(2014)An online auction framework for dynamic resource provisioning in cloud computingThe 2014 ACM international conference on Measurement and modeling of computer systems10.1145/2591971.2591980(71-83)Online publication date: 16-Jun-2014
https://dl.acm.org/doi/10.1145/2591971.2591980
Engelberg RFabrikant ASchapira MWajc DKearns MMcAfee PTardos É(2013)Best-response dynamics out of syncProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2482540.2482609(379-396)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2482540.2482609
Yang DXue GFang XMisra SZhang J(2013)A game-theoretic approach to stable routing in max-min fair networksIEEE/ACM Transactions on Networking10.1109/TNET.2013.224741621:6(1947-1959)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1109/TNET.2013.2247416
Wang CGong ZTao YZhang ZZhao B(2013)CRSG: A congestion control routing algorithm for security defense based on social psychology and game theory in DTNJournal of Central South University10.1007/s11771-013-1505-z20:2(440-450)Online publication date: 7-Feb-2013
https://doi.org/10.1007/s11771-013-1505-z
Ferraioli DPenna P(2013)Imperfect Best-Response MechanismsAlgorithmic Game Theory10.1007/978-3-642-41392-6_21(243-254)Online publication date: 2013
https://doi.org/10.1007/978-3-642-41392-6_21
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