research-article

Incentive compatibility and dynamics of congestion control

Authors:

P. Brighten Godfrey,

Michael Schapira,

Scott ShenkerAuthors Info & Claims

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 95 - 106

https://doi.org/10.1145/1811039.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
Zarchy DMittal RSchapira MShenker S(2017)An Axiomatic Approach to Congestion ControlProceedings of the 16th ACM Workshop on Hot Topics in Networks10.1145/3152434.3152445(115-121)Online publication date: 30-Nov-2017
https://dl.acm.org/doi/10.1145/3152434.3152445
Jaggard ALutz NSchapira MWright R(2017)Dynamics at the Boundary of Game Theory and Distributed ComputingACM Transactions on Economics and Computation10.1145/31071825:3(1-20)Online publication date: 9-Aug-2017
https://dl.acm.org/doi/10.1145/3107182
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
Performance evaluation review

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 Conferences

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

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

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]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMETRICS '10

Sponsor:

SIGMETRICS

SIGMETRICS '10: ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

June 14 - 18, 2010

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

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 29 Nov 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
Zarchy DMittal RSchapira MShenker S(2017)An Axiomatic Approach to Congestion ControlProceedings of the 16th ACM Workshop on Hot Topics in Networks10.1145/3152434.3152445(115-121)Online publication date: 30-Nov-2017
https://dl.acm.org/doi/10.1145/3152434.3152445
Jaggard ALutz NSchapira MWright R(2017)Dynamics at the Boundary of Game Theory and Distributed ComputingACM Transactions on Economics and Computation10.1145/31071825:3(1-20)Online publication date: 9-Aug-2017
https://dl.acm.org/doi/10.1145/3107182
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
Ferraioli DPenna P(2015)Imperfect Best-Response MechanismsTheory of Computing Systems10.1007/s00224-014-9597-x57:3(681-710)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00224-014-9597-x
Shnayder VParkes DKawadia VHoon JWu JCheng XLi XSarkar S(2014)Truthful prioritization for dynamic bandwidth sharingProceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing10.1145/2632951.2632956(235-244)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2632951.2632956
Engelberg RFabrikant ASchapira MWajc DKearns MMcAfee PTardos É(2013)Best-response dynamics out of syncProceedings of the fourteenth ACM conference on Electronic commerce10.1145/2492002.2482609(379-396)Online publication date: 16-Jun-2013
https://dl.acm.org/doi/10.1145/2492002.2482609
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
Wang CZhao BYu WWu CGong Z(2012)SARMProceedings of the 2012 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing10.1109/UIC-ATC.2012.44(869-875)Online publication date: 4-Sep-2012
https://dl.acm.org/doi/10.1109/UIC-ATC.2012.44
Wang CZhao BPeng WWu CGong Z(2012)Following RoutingProceedings of the 2012 15th International Conference on Network-Based Information Systems10.1109/NBiS.2012.46(727-732)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1109/NBiS.2012.46
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 Table of Contents