S. Shenker
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.
- Chi89.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.]] Google Scholar
Digital Library
- Col80.P. Collet and J.-P. Eckmann, "Iterated Maps on the Interval as Dynamical Systems", Birkhauser, Boston 1980.]]Google Scholar
- Dem89.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.]] Google ScholarDigital Library
- Fin89.G. Finn, "A Connectionless Congestion Control Algorithm", Computer Communications Review, Volume 19, Number 5, pp 12-31, 1989.]] Google ScholarDigital Library
- Gaf82.E. Gafni, '*The Integration of Routing and Flow Control for Voice and Data in a Computer Communication Network", MIT Report, LIDS-TH- 1239, 1982.]]Google Scholar
- Gaf84.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.]]Google ScholarCross Ref
- Has89.E. Hashem, "Analysis of Random Drop for Gateway Congestion Control", MIT-LCS thesis, 1989.]]Google Scholar
- Hay81.H. Hayden, "Voice Flow Control in Integrated Voice and Data Communication Network", MIT Report, LIDS-TH-1115, 1981.]]Google Scholar
- Jac88.V. Jacobsen, "Congestion Avoidance and Control", Proceedings of ACM Sigcomm, Computer Communications Review, Volume 18, Number 4, pp 314-329, 1988.]] Google ScholarDigital Library
- Jaf80.J. Jaffe, "A Decentralized, 'Optimal', Multiple User, Flow Control Algorithm". Proceedings of the Fifth International Conference on Computer Communications, pp. 839-844, October 1980.]]Google Scholar
- Jaf81.J. Jaffe, "Bottleneck Flow Control". IEEE Transactions on Communications, Vol 29, No. 7, pp. 954-962, July 1981.]]Google ScholarCross Ref
- Jai87.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)]] Google ScholarDigital Library
- Jai88.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.]]Google ScholarCross Ref
- Mor89.S. Morgan, "Queueing Disciplines and Passive Congestion Control in Byte-Stream Networks", IEEE INFOCOM '89 Proceedings, pp. 711-720, 1989.]]Google Scholar
- Mos84.J. Mosely, "Asynchronous Distributed Flow Control Algorithms", MIT LIDS thesis, 1984.]]Google Scholar
- Nag87.J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Volume 35, pp 435-438, 1987.]]Google ScholarCross Ref
- Pos81.J. Postel, "Internet Control Message Protocol (ICMP)", RFC-792, Network Information Center, SRI International, 1981.]] Google ScholarDigital Library
- Pos87.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.]]Google Scholar
- Ram87.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.]]Google Scholar
- Ram88.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.]] Google ScholarDigital Library
- Reg86.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.]]Google Scholar
- She89.S. Shenker, "Making Greed Work in Networks: A Game-Theoretic Analysis of G#teway Service Disciplines", preprint, 1989.]]Google Scholar
- Zha89.L. Zhang, "A New Architecture for Packet Switching Network Protocols", MIT-LCS thesis, 1989.]]Google Scholar
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