K. K. Ramakrishnan
Raj Jain
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.
- 1 AHUJA, V. Routing and flow control in systems network architecture. IBM Syst. J. 18, 2 (1979), 293-314.Google Scholar
- 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.Google Scholar
- 3 DIGITAL EQUIPMENT CORPORATION. DECnet digital network architecture (phase IV) general description. Order AA-N149A-TC, Digital Equipment Corporation, Maynard, Mass., 1982.Google Scholar
- 4 GERLA, M., AND KLEINROCK, L. Flow control: A comparative survey. IEEE Trans. Comrnun. COM-28, 4 (Apr. 1980), 553-574.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 14 NAGLE, J. Congestion control in IP/TCP internetworks. Comput. Commun. Rev. 14, 4 (Oct. 1984), 11-17. Google Scholar
- 15 POSTEL, J. B. Transmission control protocol. Tech. Rep. RFC 793, Information Sciences institute, Sept. 1981.Google Scholar
- 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.Google Scholar
- 17 REXSER, M. Queueing and delay analysis of a buffer pool with resume level. In Performance '83, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement, and Evaluation (College Park, Md., May 1983). A. K. Agrawala and S. K. Tripathi, Eds. North-Holland, New York, 1983, pp. 25-32. Google Scholar
- 18 TAN~.NBAUM, A.S. Computer Networks. Prentice-Hall, Englewood Cliffs, N.J., 1981.Google Scholar
- 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.Google Scholar
- 20 ZAHORJAN, J.p SEVCIK, K. C., EAGER, D. L., AND GALLER, B. Balanced job bound analysis of queueing networks. Comraun. ACM 25, 2 (Feb. 1982), 134-141. Google Scholar
Index Terms
- A binary feedback scheme for congestion avoidance in computer networks
Recommendations
A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer
We propose a scheme for congestion avoidance in networks using a connectionless protocol at the network layer. The scheme uses feedback from the network to the users of the network. The interesting challenge for the scheme is to use a minimal amount of ...
A binary feedback scheme for congestion avoidance in computer networks with a connectionless network layer
SIGCOMM '88: Symposium proceedings on Communications architectures and protocolsWe propose a scheme for congestion avoidance in networks using a connectionless protocol at the network layer. The scheme uses feedback from the network to the users of the network. The interesting challenge for the scheme is to use a minimal amount of ...
Delay-based congestion avoidance for TCP
The set of TCP congestion control algorithms associated with TCP/Reno (e.g., slow-start and congestion avoidance) have been crucial to ensuring the stability of the Internet. Algorithms such as TCP/NewReno (which has been deployed) and TCP/Vegas (which ...
Reviews
John Wesley Kyle
Ramakrishnan and Jain present a method for congestion avoidance based on a model of the network as a feedback control system. The proposed scheme attempts to inject a minimal amount of feedback into the network by setting a single bit in the network-layer header to indicate congestion. The window control agent then examines this congestion bit so it can apply policies for controlling the window size. After introducing the concepts and policies, the authors demonstrate the behavior of the system under both normal and special situations. Congestion control detects that a network has reached or passed the point at which response times approach infinity and then reduces the traffic in order to reestablish an uncongested state. Congestion avoidance operates the network near the peak of the performance curve at all times, instead of periodically recovering from congestion conditions. Ramakrishnan and Jain demonstrate that their congestion avoidance method is effective for both normal and special situations. Given a model with random packet sizes, the maximally efficient aggregate window size was 15.5. In the test, the average aggregate window size of the source was 14.3. Introducing changes to the network, such as increasing the service time of a router or adding new users, results in the network operating at its new maximally efficient point with fairness to every user. This scheme can be applied to connectionless network services like TCP/IP, ISO TPx, or Digital's DNA.
Wai Sum Lai
The authors propose an explicit notification method for avoiding congestion in connectionless networks. In this method, the nodes in a network detect congestion and set a congestion-indication bit in the headers of packets flowing forward. Based on the on or off status of this bit, a network user can dynamically adjust the window size for sending packets into the network. This proposal is elegant: simple to implement, effective in maintaining network performance, and conceptually appealing. Furthermore, if every user cooperates, then fairness in the network service provided can also be achieved. The enforcement of users' cooperation, though, is not covered in the paper. This topic probably deserves a paper of its own. I like the paper for its interesting technical contents, good writing, and presentation of both the scheme and an analysis of alternative design directions.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments