WUSTL CSE 573S - A Binary Feedback Scheme for Congestion Avoidance in Computer Networks

Unformatted text preview:

A Binary Feedback Scheme for Congestion Avoidance in Computer Networks K. K. RAMAKRISHNAN and RAJ JAIN Digital Equipment Corporation We propose a scheme for congestion auoidunce 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. Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design-network communications; distributed networks, packet networks, store and forward networks; C.2.3 [Computer Communication Networks]: Network Operations-network monitoring; C.4 [Computer System Organization]: Performance of Systems--design studies General Terms: Algorithms, Design, Performance Additional Key Words and Phrases: Computer communication networks, congestion, congestion avoidance, congestion control, congestion indication, connectionless network layer, fairness, network performance, network power 1. INTRODUCTION Congestion in computer networks is a significant problem due to the growth of networks and increased link speeds. Flow control and congestion control are problems that have been addressed by several researchers in the past [4]. With the increasing range of speeds of links and the wider use of networks for distributed computing, effective control of the network load is becoming more important. The lack of control may result in congestion loss and, with retrans- missions, may ultimately lead to congestion collapse [ll]. The control mechanisms adopted to control the traffic on computer networks may be categorized into two distinct types: flow control and congestion control. An earlier version of this paper was presented at the “ACM SIGCOMM 88 Symposium on Commu- nications Architectures and Protocols,” Stanford, Calif., August 16-19, 1988. Authors’ address: Distributed Systems Architecture and Performance, Digital Equipment Corpora- tion, Littleton, MA 01460-1289. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1990 ACM 0734.2071/90/0500-0158 $01.50 ACM Transactions on Computer Systems, Vol. 8, No. 2, May 1990, Pages 158-181A Binary Feedback Scheme for Congestion Avoidance * 159 End-to-end flow control mechanisms are used to ensure that the logical link has sufficient buffers at the destination. It is thus a “selfish” control function. Control mechanisms for congestion, on the other hand, address the “social” problem of having the various logical links in the network cooperating to avoid/recover from congestion of the intermediate nodes that they share. This paper proposes a mechanism for effective avoidance of congestion in connectionless networks. We distinguish between congestion control, which has been studied in the past [2, 8, 141, and congestion avoidance. We call the point at which throughput falls off rapidly before the network reaches congestion collapse as the cliff. This is also the point at which the response time approaches infinity. The purpose of a congestion control scheme [2, 141 is to detect the fact that the network has reached the cliff, resulting in packet losses, and to reduce the load so that the network can recover to an uncongested state. Congestion avoidance, on the other hand, operates the network at a highly desirable point, which is at the knee of the response time (or delay) curve. This is the point beyond which the increase in throughput is small, but the response time increases rapidly with load. This enables the network to reduce significantly the probability of packet loss and prevents the possibility of serious congestion developing and impacting user performance in the network. A more detailed discussion of the differences is presented in [9]. Congestion control mechanisms that detect whether the network has gone beyond the cliff have been proposed [2, 181. The feedback that indicates conges- tion in the network results is the loss of packets and the resulting time-out while waiting for the acknowledgment. Other forms of feedback of congestion infor- mation have also been used. An example is to send “choke” or “source quench” packets as part of a congestion control mechanism [l, 13, 141. There are two differences between these mechanisms for congestion control and the scheme we propose in this paper. We propose a congestion avoidance policy that drives the operation of the network toward the knee of the delay curve, rather than recovering from operation near the cliff. Second, to achieve this operating point, the network provides explicit feedback by using a field in the packet that flows from source to destination to signal congestion.


View Full Document

WUSTL CSE 573S - A Binary Feedback Scheme for Congestion Avoidance in Computer Networks

Download A Binary Feedback Scheme for Congestion Avoidance in Computer Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view A Binary Feedback Scheme for Congestion Avoidance in Computer Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view A Binary Feedback Scheme for Congestion Avoidance in Computer Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?