A delay-based approach for congestion avoidance in interconnected heterogeneous computer networks

ABSTRACT

In heterogeneous networks, achieving congestion avoidance is difficult because the congestion feedback from one subnetwork may have no meaning to sources on other subnetworks. We propose using changes in round-trip delay as an implicit feedback. Using a black-box model of the network, we derive an expression for the optimal window as a function of the gradient of the delay-window curve.The problems of selfish optimum and social optimum are also addressed. It is shown that without a careful design, it is possible to get into a race condition during heavy congestion, where each user wants more resources than others, thereby leading to a diverging condition.It is shown that congestion avoidance using round-trip delay is a promising approach. The approach has the advantage that there is absolutely no overhead for the network itself. It is exemplified by a simple scheme. The performance of the scheme is analyzed using a simulation model. The scheme is shown to be efficient, fair, convergent, and adaptive to changes in network configuration.The scheme as described works only for networks which can be modeled with queueing servers with constant service times. Further research is required to extend it for implementation in practical networks. Several directions for future research have been suggested.

REFERENCES

• 1: [1] V. Ahuja, "Routing and Flow Control in Systems Network Architecture," IBM Systems Journal, Vol. 18, No. 2, 1979, pp. 298-314.
• 2: [2] W. Bux and D. Grillo, "Flow Control in Local-Area Networks of Interconnected Token Rings," IEEE Transactions on Communications, Vol. COM-33, No. 10, October 1985, pp. 1058-66.
• 3: 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]
• 4: [4] Digital Equipment Corp., "DECnet Digital Network Architecture (Phase V) General Description," Order NO. EK-DNAPV-GD, September 1987.
• 5: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 6: [6] M. Gerla and L. Kleinrock, "Flow Control: A Comparative Survey," IEEE Transactions on Communications, Vol. COM-28, No. 4, April 1980, pp. 553-574.
• 7: [7] A. Giessler, J. Haanle, A. Konig and E. Pade, "Free Buffer Allocation - An Investigation by Simulation," Computer Networks, Vol. 1, No. 3, July 1978, pp. 191-204.
• 8: [8] International Organization of Standardization, "ISO 8073: Information Processing Systems-Open Systems Interconnection - Connection Oriented Transport Protocol Specification," July 1986.
• 9: [9] M. Irland, "Buffer Management in a Packet Switch," IEEE Trans. on Commun., Vol. COM- 26, March 1978, pp. 328-337.
• 10: [10] J. M. Jaffe, "Flow Control Power is Nondecentralizable," IEEE Transaction on Communications, Vol. COM-29, No. 9, September 1981, pp. 1301-1306.
• 11: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 12: [12] Raj Jain, Dah-Ming Chiu, and William Hawe, "A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems," Digital Equipment Corporation, Technical Report DEC-TR-301, September 1984.
• 13: [13] Raj Jain, "A Timeout-Based Congestion Control Scheme for Window Flow-Controlled Networks," IEEE Journal on Selected Areas in Communications, Vol. SAC-4, No. 7, October 1986, pp. 1162-1167.
• 14: [14] Raj Jain, K. K. Ramakrishnan, and Dah-Ming Chiu, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer," Digital Equipment Corporation, Technical Report DEC-TR-506, August 1987.
• 15: [15] Raj Jain and K. K. Ramakrishnan, "Congestion Avoidance in Computer Networks with a Connectionless Network Layer: Concepts, Goals and Methodology," Proc. IEEE Computer Networking Symposium, Washington, D. C., April 1988, pp. 134-143.
• 16: [16] L. Kleinrock, "Power and Deterministic Rules of Thumb for Probabilistic Problems in Computer Communications," in Proc. Int. Conf. Commun., June 1979, pp. 43.1.1-10.
• 17: [17] J. C. Majithia, et al, "Experiments in Congestion Control Techniques," Proc. Int. Symp. Flow Control Computer Networks, Versailles, France. February 1979.
• 18: [18] N. F. Maxemchuk and M. E. Zarki, "Routing and Flow Control in High Speed, Wide Area Networks," Proceedings of IEEE, to appear.
• 19: [19] J. B. Nagle, "On Packet Switches with Infinite Storage," IEEE Transactions on Communications, Vol. COM-35, No. 4, April 1987, pp. 435- 438.
• 20: 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
• 21: [21] J. M. Selga, "New Flow Control Power is Decentralizable and Fair," Proc. IEEE INFOCOM'84, pp. 87-94.
• 22: [22] B. A. Sanders, "An Incentive Compatible Flow Control Algorithm for Fair Rate Allocation in Computer/Communication Networks," Proc. Sixth International Conf. on Distributed Computing Systems, 1986, pp. 314-320.

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.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

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

General Terms:
Algorithms, Design, Performance