A theoretical analysis of feedback flow control

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

• Chi89: D.-M. Chiu , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• Col80: P. Collet and J.-P. Eckmann, "Iterated Maps on the Interval as Dynamical Systems", Birkhauser, Boston 1980.
• Dem89: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.4, p.1-12, Sep. 1989
• Fin89: G. G. Finn, A connectionless congestion control algorithm, ACM SIGCOMM Computer Communication Review, v.19 n.5, p.12-31, Oct. 1989 [doi>10.1145/74681.74683]
• 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.
• 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.
• Has89: E. Hashem, "Analysis of Random Drop for Gateway Congestion Control", MIT-LCS thesis, 1989.
• Hay81: H. Hayden, "Voice Flow Control in Integrated Voice and Data Communication Network", MIT Report, LIDS-TH-1115, 1981.
• Jac88: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• 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.
• Jaf81: J. Jaffe, "Bottleneck Flow Control". IEEE Transactions on Communications, Vol 29, No. 7, pp. 954-962, July 1981.
• Jai87: R. Jain , K. K. Ramakrishnan , D.-M. Chiu, Congestion avoidance in computer networks with a connectionless network layer, Innovations in Internetworking, Artech House, Inc., Norwood, MA, 1988
• 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.
• Mor89: S. Morgan, "Queueing Disciplines and Passive Congestion Control in Byte-Stream Networks", IEEE INFOCOM '89 Proceedings, pp. 711-720, 1989.
• Mos84: J. Mosely, "Asynchronous Distributed Flow Control Algorithms", MIT LIDS thesis, 1984.
• Nag87: J. Nagle, "On Packet Switches with Infinite Storage", IEEE Transactions on Communications, Volume 35, pp 435-438, 1987.
• Pos81: J. Postel, "Internet Control Message Protocol (ICMP)", RFC-792, Network Information Center, SRI International, 1981.
• 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.
• 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.
• Ram88: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.303-313, August 1988
• 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.
• She89: S. Shenker, "Making Greed Work in Networks: A Game-Theoretic Analysis of G#teway Service Disciplines", preprint, 1989.
• Zha89: L. Zhang, "A New Architecture for Packet Switching Network Protocols", MIT-LCS thesis, 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.1 Data Communications Devices
          Subjects: Processors**

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Performance, Theory