A binary feedback scheme for congestion avoidance in computer networks

ABSTRACT

We propose a scheme for congestion avoidance in networks using a connectionless protocol at the network layer. The scheme uses a minimal amount of feedback from the network to the users, who adjust the amount of traffic allowed into the network. The routers in the network detect congestion and set a congestion-indication bit on packets flowing in the forward direction. The congestion indication is communicated back to the users through the transport-level acknowledgment. The scheme is distributed, adapts to the dynamic state of the network, converges to the optimal operating point, is quite simple to implement, and has low overhead. The scheme maintains fairness in service provided to multiple sources. This paper presents the scheme and the analysis that went into the choice of the various decision mechanisms. We also address the performance of the scheme under transient changes in the network and pathological overload conditions.

REFERENCES

• 1: AHUJA, V. Routing and flow control in systems network architecture. IBM Syst. J. 18, 2 (1979), 293-314.
• 2: Sux, W., AND GRILLO, D. Flow control in local-area networks of interconnected token rings. IEEE Trans. Commun. COM-33, 10 (Oct. 1985), 1058-1066.
• 3: DIGITAL EQUIPMENT CORPORATION. DECnet digital network architecture (phase IV) general description. Order AA-N149A-TC, Digital Equipment Corporation, Maynard, Mass., 1982.
• 4: GERLA, M., AND KLEINROCK, L. Flow control: A comparative survey. IEEE Trans. Comrnun. COM-28, 4 (Apr. 1980), 553-574.
• 5: GIESSLER, A., HAANLE, J., KONIG, A., AND PADE, E. Free buffer allocation--An investigation by simulation. Comput. Networks 1, 3 (July 1978), 191-204.
• 6: HARRISON, P.G. An analytic model for flow control schemes in communication network nodes. IEEE Trans. Commun. COM-32, 9 (Sept. 1984), 1013-1019.
• 7: INTERNATIONAL ORGANIZATION FOR STANDARDIZATION. ISO 8073: Information processing systems--Open systems interconnection--Connection oriented transport protocol specification. ISO 8073-1986 (E), International Organization for Standardization, July 1986.
• 8: jAIN, R. A timeout-based congestion control scheme for window flow-controlled networks. IEEE J. Sel. Areas Comraun. SAC-4, 7 (Oct. 1986), 1162-1167.
• 9: JAIN, R., AND RAMAKRISHNAN, K. K. Congestion avoidance in computer networks with a connectionless network layer, part I--Concepts, goals and alternatives. DEC Tech. Rep. TR-507, Digital Equipment Corporation, Littleton, Mass., Apr. 1987.
• 10: JAIN, R. K., CHIU, D.-M., AND HAWE, W.R. A quantitative measure of fairness and discrimination for resource allocation in shared systems. DEC Tech. Rep. TR-301, Digital Equipment Corporation, Littleton, Mass., Sept. 1984.
• 11: KLEINROCK, L. On flow control in computer networks. In Proceedings of the International Conference on Communications (June 1978), pp. 27.2.1-27.2.5.
• 12: KLEINROCK, L. Power and deterministic rules of thumb for probabilistic problems in computer communications. In Proceedings of the International Conference on Communications (June 1979), pp. 43.1.1-43.1.10.
• 13: MAJITHIA, J. C., IRLAND, M., GRANGE, J. L., COHEN, N., AND O'DONELL, C. Experiments in congestion control techniques. In Proceedings of the International Symposium on Flow Control in Computer Networks (Feb. 1979), pp. 211-234.
• 14: John Nagle, Congestion control in IP/TCP internetworks, ACM SIGCOMM Computer Communication Review, v.14 n.4, p.11-17, October 1984 [doi>10.1145/1024908.1024910]
• 15: POSTEL, J. B. Transmission control protocol. Tech. Rep. RFC 793, Information Sciences institute, Sept. 1981.
• 16: RAMAKRISHNAN, K.K. Analysis of a dynamic window congestion control protocol in heterogeneous environments including satellite links. In Proceedings of the Computer Networking Symposium (Nov. 1986). IEEE, New York, 1986, pp. 94-101.
• 17: Martin Reiser, Queueing and Delay Analysis of a Buffer Pool with Resume Level, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.25-32, May 25-27, 1983
• 18: TAN~.NBAUM, A.S. Computer Networks. Prentice-Hall, Englewood Cliffs, N.J., 1981.
• 19: YUM, T. P., AND YEN, H.-M. Design algorithm for a hysteresis buffer congestion control strategy. In Proceedings of the IEEE International Conference on Communications (June 1983). IEEE, New York, 1983, pp. 499-503.
• 20: John Zahorjan , Kenneth C. Sevcik , Derek L. Eager , Bruce Galler, Balanced job bound analysis of queueing networks, Communications of the ACM, v.25 n.2, p.134-141, Feb 1982 [doi>10.1145/358396.358447]

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.3 Network Operations
          Subjects: Network monitoring

General Terms:
Algorithms, Design, Performance