Reliable and efficient hop-by-hop flow control

ABSTRACT

Hop-by-hop flow control can be used to fairly share the bandwidth of a network among competing flows. No data is lost even in overload conditions; yet each flow gets access to the maximum throughput when the network is lightly loaded. However, some schemes for hop-by-hop flow control require too much memory; some of them are not resilient to errors. We propose a scheme for making hop-by-hop flow control resilient and show that it has advantages over schemes proposed by Kung. We also describe a novel method for sharing the available buffers among the flows on a link; our scheme allows us to potentially reduce the memory requirement (or increase the number of flows that can be supported) by an order of magnitude. Most of the work is described in the context of an ATM network that uses credit based flow control. However our ideas extend to networks in which flows can be distinguished, and to rate based flow control schemes.

REFERENCES

• AOST93: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High speed switch scheduling for local area networks, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.98-110, October 12-15, 1992, Boston, Massachusetts, United States
• CL85: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• CK94: Alan Chapman and H.T. Kung. Use of flow control for effective statistical multiplexing and notes on implementation. A TM Forum Contribution No.9~.0085, January 1994.
• DKS89: 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
• Gog92: M. Goguen. AN2: a self-confi~ng local ATM network. In Proceedings of the National Communicationa Forum (NCF), 1992.
• Jai86: Raj Jain. A timeout-based congestion control scheme for window flow-controlled networks. IEEE Journal on Selected Areas in Communications, October 1986.
• Jai92: Raj Jain. Myths about congestion management in high speed networks. Internetworking: Research and Experience, 3, 1992.
• KC93: H.T. Kung and Alan Chapman. The FCVC (Flow Controlled Virtual Channel) proposal for ATM networks. Proc. of Int. Conf. on Network Protocols, October 1993.
• LT: N. A. Lynch and M. R. Turtle. An introduction to input/output automata. MIT/LCS/TM-373, Lab for Computer Science Massachusetts Institute of Technology, November 1988.
• MAM+90: M.Schroeder, A.BirreU, M.Burrows, et al Autonet: a high-speed, self-configuring local area network using point-to-point links. TR 59, Digital Systems Research Center, April 1990.
• RJ88: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer, Symposium proceedings on Communications architectures and protocols, p.303-313, August 16-18, 1988, Stanford, California, United States
• RJ90: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• Tan89: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• Tur86: J. Turner. New directions in communications, or which way to the information age? IEEE Communications Magazine, 24(10), October 1986.
• Zha91: Lixia Zhang, VirtualClock: a new traffic control algorithm for packet-switched networks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.101-124, May 1991 [doi>10.1145/103720.103721]

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Performance, Reliability