2 D,M Chiu R Jain/Congestion Aooidance in Computer Networks Cliff ueues start overflowing, the response time in- The point at which the packets start getting lost is called a cliff due to the fact that the throughput falls off rapidly after this point. We use the term knee to descnbe the point alter which the increase increase in the response time results a scheme that allows the network to operate at Load the knee is called as distinguished from a congestion control scheme that tries to keep the network operating in the zone to the left of the cliff. a properly designed congestion avoidance scheme will ensure that the users are encouraged to increase their traffic load as long as this does not significantly affect ul response time, and are rcquircd to dcercase them if that happens. Thus, the network load oscillates around the knee Both congestion avoidance and congestion con- Fig. 1. Network performance as a funetion of the load. Broken trol mechanisms are dynamic resource manage curves inuiuaie perfulInance will detcatiliMliy ct nterarnval times. ment problems that can be formulated as system control problems in which the system senses its state and feeds this back to its users who adjust their controls. For the congestion problem, the sucl as lucal auea networks(LANs) and fibcr statc consists of the load on the network and the optic LANs have resulted in a significant increase control is the number of packets put into the in the bandwidths of computer network links. network by the users. Often a window mechanism However, these new technologies must coexist with is used in the transport layer protocols to limit the the old low bandwidth media such as the twisted number of packets put into the network. An alter pair. This heterogeneity has resulted in a mis- native mechanism consists of setting a limit on the match of arrival and service rates in the inter ate(packets per second or bits per second)that mediate nodes in the network causing increased can be sent by a user. In either case, the control queuing and cor (window or rate)can be dynamically adjusted as Traditional congestion control schemes help the total load on the system changes. This control, improve performance after congestion has oc- which we call the increase/decrease algorithm, is rred. Figure 1 shows general patterns of re- at the heart of all congestion avoidance mecha sponse time and throughput of a network as the nism. network load increases. If the load is small, We have investigated a number of congestion throughput generally keeps up with the load. As avoidance mechanisms, reported in a series of the load increases, throughput increases. After the papers, and this paper is a part of that serie load reaches the network capacity, throughput [1,8 U, Il]. The concept of congestion avoidance stops increasing. If the load is increased any fur- and several alternatives are described in [7]. We ther, the queues start building, potentially result hose a particular alternative called the"binary ing in packets being dropped. Throughput ma feedback scheme"which is described in detail in suddenly drop when the lo creases heyond [11]. This scheme is later extended in (101 this point and the network is said to be congested. include a "selective feedback "mechanism in which The response-time curve follows a similar pattern. the routers monitor different users and permit At first the response time increases little with some users to increase load while requesting others load. When the queues start building up, the re- to decrease load. All of our work on congestion sponse time increases linearly until finally, as the avoidance is summarized in [8]