Article

Free access

A theoretical analysis of feedback flow control

Author:

S. ShenkerAuthors Info & Claims

SIGCOMM '90: Proceedings of the ACM symposium on Communications architectures & protocols

Pages 156 - 165

https://doi.org/10.1145/99508.99547

Published: 01 August 1990 Publication History

Abstract

Congestion is a longstanding problem in datagram networks. One congestion avoidance technique is feedback flow control, in which sources adjust their transmission rate in response to congestion signals sent (implicitly or explicitly) by network gateways. The goal is to design flow control algorithms which provide time-scale invariant, fair, stable, and robust performance. In this paper we introduce a simple model of feedback flow control, in which sources make synchronous rate adjustments based on the congestion signals and other local information, and apply it to a network of Poisson sources and exponential servers. We investigate two different styles of feedback, aggregate and individual, and two different gateway service disciplines, FIFO and Fair Share. The purpose of this paper is to identify, in the context of our simple model, which flow control design choices allow us to achieve our performance goals.

Aggregate feedback flow control, in which congestion signals reflect only the aggregate congestion at the gateways, can provide time-scale invariant and stable performance, but not fair or robust performance. The properties of individual feedback flow control, in which the congestion signals reflect the congestion caused by the individual source, depend on the service discipline used in the gateways. Individual feedback with FIFO gateways can provide time-scale invariant, fair, and stable performance, but not robust performance. Individual feedback with Fair Share gateways can achieve all four performance goals. Furthermore, its stability properties are superior to those of the other two design choices. By making robust and more stable performance possible, gateway service disciplines play a crucial role in realizing effective flow control.

References

[1]

D.-M. Chiu and R. Jain, "Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networkstt, Computer Networks and ISDN Systems, Volume 17, pp 1-14, 1989.]]

Digital Library

[2]

P. Collet and J.-P. Eckmann, "Iterated Maps on the Interval as Dynamical Systems", Birkhauser, Boston 1980.]]

[3]

A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm", Proceedings of ACM Sigcomm, Computer Communications Review, Volume 19, Number 4, pp 1-12, 1989.]]

Digital Library

[4]

G. Finn, "A Connectionless Congestion Control Algorithm", Computer Communications Review, Volume 19, Number 5, pp 12-31, 1989.]]

Digital Library

[5]

E. Gafni, '*The Integration of Routing and Flow Control for Voice and Data in a Computer Communication Network", MIT Report, LIDS-TH- 1239, 1982.]]

[6]

E. Gafni and D. Bertsekas, "Dynamic Control of Session Input Rates in Communication Networks", IEEE Transactions on Automatic Control, Volume 29, No. 9, pp 1009-1016, 1984.]]

[7]

E. Hashem, "Analysis of Random Drop for Gateway Congestion Control", MIT-LCS thesis, 1989.]]

[8]

H. Hayden, "Voice Flow Control in Integrated Voice and Data Communication Network", MIT Report, LIDS-TH-1115, 1981.]]

[9]

V. Jacobsen, "Congestion Avoidance and Control", Proceedings of ACM Sigcomm, Computer Communications Review, Volume 18, Number 4, pp 314-329, 1988.]]

Digital Library

[10]

J. Jaffe, "A Decentralized, 'Optimal', Multiple User, Flow Control Algorithm". Proceedings of the Fifth International Conference on Computer Communications, pp. 839-844, October 1980.]]

[11]

J. Jaffe, "Bottleneck Flow Control". IEEE Transactions on Communications, Vol 29, No. 7, pp. 954-962, July 1981.]]

[12]

R. Jain, K. K. Ramakrishnan, and D.-M. Chiu, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer", DEC Technical Report TR-506, Digital Equipment Corporation, 1987. (also reprinted ia "Innovations in Networking't, edited by Craig Partridge, Artech House, Boston, 1988)]]

Digital Library

[13]

R. Jain and K. K. Ramakrishnan, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals, and Methodology*t, Proceedings of Computer Networking Symposium, pp 134-143, 1988.]]

[14]

S. Morgan, "Queueing Disciplines and Passive Congestion Control in Byte-Stream Networks", IEEE INFOCOM '89 Proceedings, pp. 711-720, 1989.]]

[15]

J. Mosely, "Asynchronous Distributed Flow Control Algorithms", MIT LIDS thesis, 1984.]]

[16]

J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Volume 35, pp 435-438, 1987.]]

[17]

J. Postel, "Internet Control Message Protocol (ICMP)", RFC-792, Network Information Center, SRI International, 1981.]]

Digital Library

[18]

J. Pos#el, "Something a Host Could Do with Source Quench: The Source Quench Introduced Delay (SQUID)", RFC-1016, Network Information Center, 8RI International, 1987.]]

[19]

K. K. Ramakrishnan, D.-M. Chiu, and R. J#in #'Congestion Avoidance in Computer Networks with a Connectionless Network Layer, Part IV- A Selective Binary Feedback Scheme for General Topologies", DEC Technical Report TR-510, Digital Equipment Corporation, November 1987.]]

[20]

K. K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer", Proceedings of ACM Sigcomm '88, Computer Communications Review, Volume 18, Number 4, pp 303-313, 1988.]]

Digital Library

[21]

J. Regnier, "Priority Assignment in Integrated Services Networks", Report LIDS-TH-1565, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts, December, 1986.]]

[22]

S. Shenker, "Making Greed Work in Networks: A Game-Theoretic Analysis of G#teway Service Disciplines", preprint, 1989.]]

[23]

L. Zhang, "A New Architecture for Packet Switching Network Protocols", MIT-LCS thesis, 1989.]]

Cited By

Zarchy DMittal RSchapira MShenker S(2019)Axiomatizing Congestion ControlACM SIGMETRICS Performance Evaluation Review10.1145/3376930.337696447:1(51-52)Online publication date: 17-Dec-2019
https://doi.org/10.1145/3376930.3376964
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
Show More Cited By

Index Terms

A theoretical analysis of feedback flow control

Recommendations

A theoretical analysis of feedback flow control

Congestion is a longstanding problem in datagram networks. One congestion avoidance technique is feedback flow control, in which sources adjust their transmission rate in response to congestion signals sent (implicitly or explicitly) by network ...
Congestion control with multipacket feedback

Many congestion control protocols use explicit feedback from the network to achieve high performance. Most of these either require more bits for feedback than are available in the IP header or incur performance limitations due to inaccurate congestion ...
Queueing properties of feedback flow control systems

In this paper, we consider a network with both controllable and uncontrollable flows. Uncontrollable flows are typically generated from applications with stringent QoS requirements and are given high priority. On the other hand, controllable flows are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '90: Proceedings of the ACM symposium on Communications architectures & protocols

August 1990

318 pages

ISBN:0897914058

DOI:10.1145/99508

Chairman:
Phil Karn

ACM SIGCOMM Computer Communication Review Volume 20, Issue 4
Sep. 1990
316 pages
ISSN:0146-4833
DOI:10.1145/99517
Editor:
Phil Karn
Issue’s Table of Contents

Copyright © 1990 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGCOMM90

Sponsor:

SIGCOMM

SIGCOMM90: Communications Architectures & Protocols

September 26 - 28, 1990

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

64
Total Citations
View Citations
1,296
Total Downloads

Downloads (Last 12 months)93
Downloads (Last 6 weeks)23

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zarchy DMittal RSchapira MShenker S(2019)Axiomatizing Congestion ControlACM SIGMETRICS Performance Evaluation Review10.1145/3376930.337696447:1(51-52)Online publication date: 17-Dec-2019
https://doi.org/10.1145/3376930.3376964
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
Abharian AKhaloozadeh HAmjadifard R(2012)Robust stochastic moment control via genetic-pole placement in communication network parameter settingNeural Computing and Applications10.1007/s00521-012-1192-y23:7-8(2351-2365)Online publication date: 30-Sep-2012
https://doi.org/10.1007/s00521-012-1192-y
Johari RTsitsiklis J(2009)Efficiency of Scalar-Parameterized MechanismsOperations Research10.1287/opre.1080.063857:4(823-839)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1287/opre.1080.0638
Zhu XUysal MWang ZSinghal SMerchant APadala PShin K(2009)What does control theory bring to systems research?ACM SIGOPS Operating Systems Review10.1145/1496909.149692243:1(62-69)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1145/1496909.1496922
Sandberg HHjalmarsson HJonsson UKarlsson GJohansson K(2009)On performance limitations of congestion controlProceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference10.1109/CDC.2009.5399657(5869-5876)Online publication date: Dec-2009
https://doi.org/10.1109/CDC.2009.5399657
Sadeghi B(2009)Congestion Control in Wireless Mesh NetworksGuide to Wireless Mesh Networks10.1007/978-1-84800-909-7_11(277-298)Online publication date: 2009
https://doi.org/10.1007/978-1-84800-909-7_11
Guirguis MBestavros AMatta I(2006)Exogenous-loss aware traffic management in overlay networks toward global fairnessComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2005.09.01150:13(2331-2348)Online publication date: 15-Sep-2006
https://dl.acm.org/doi/10.1016/j.comnet.2005.09.011
Papachristodoulou ALi LDoyle J(2004)Methodological frameworks for large-scale network analysis and designACM SIGCOMM Computer Communication Review10.1145/1031134.103113834:3(7-20)Online publication date: 1-Jul-2004
https://dl.acm.org/doi/10.1145/1031134.1031138
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten