A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer K. K. Ramakrishnan and 1I.a.j Jain Distributed Syslems Architecture and Performance Digital Equipment Corporation Aldract We propose a scheme Car congesliort avoidance in networks using a connectiortless prot,ocol at the neLwork layer. The scheme uses feedback from Lhe network to the users of the network. The interesting challenge for the scheme is to use a minimal anlount of feedback (one bit in each packet) from the network to adjust LII~ amount. of trafic allowed into the network. The servers in the network detect congestion a.nd set, a congestion indicalion. bit on packets flowing in the forward direction. The congestion indication is communicated back Lo the users throngh the transport level acknowledgement. The scheme is distribuLed, adapt,s to the dynalllic state of the net,work, converges to the optimal operaLing point, is quite sirn- ple to implement, and has low overhead while opcralionaf. The scheme also addresses a very important aspect of fairness in the service provided to the various sources utilizing the network. The scheme atLempLs Lo mainlain fairness in service provided Lo mufliple sources. This paper presents the schelne and tile ana.lysis that went inlo Lhe clmice of Lhe various decision mechanisms. We also address I,he perfornlance of lhe schetne under tra.nsirllt changes in Lhe network and for palhological conditions. 1 Introduction Congeslion in computer networks is a significant problem due Lo the growth of networks and increased link speeds. Flow and con- gcsLion control are problems that have been addressed by sev- eral researchers in Ihe past [GK80]. Wit.11 the increasing range of speeds of links and the wider use of networks for distribubed computing, effective control of the network load is becoming more irnporLant. The lack of control rnay result in congeslion loss, and with retransmissions, may ultimately lead to conies- lion collnpse (l<le78]. The control mechanisms adopted to control the traffic on com- puter networks may be categorized into two distinct types: flow conLrol and congestion control. End-to-end fiow control rnech- anisms are used to ensure that the logical link has sullicient 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. o 1988 ACM O-8979 l-279-9/88/008/0303 $1.50 buffers at the destination. It is thus a “selfish” control func- tion. Control mechanisms for congestsion, on the other hand, address the “social” problem of having the various logical links in the network cooperating to avoid congestion of the interrne- diate nodes that they share. This paper proposes a mechanism for effective control in connectionless networks. We distinguish belween congestion. control, which has been stud- icd in tl~c pasl [1X85], [Nag&t], [Jai8Ci], and congestion avoid- ance. Congestion avoidance operates the network at the knee of lho response Lime curve. This is the poinl aL which Lhe increase in throughpul is small, while the response time increa.ses rapidly with load. This enables the network lo significantly reduce the probabiliLy of packet loss and preventing Lhe possibility of se- rious congest,ion dcvelol)ing and impacting user performance in the network. A more detailed discussion of the difl’erences is made in [JR87]. The congestion avoidance policy we propose here drives the op- eration of Lhe network toward Lhe knee of the de1a.y curve. To achieve this operating point, the network provides some type of feedhack so Lhat the users may control the amount of Lraf- fit they place on the network. Congestion control mechanisms have been proposed that dcLcct whether the network has gone beyond Lhe clifl [Jai86], [1X85]. The feedback indicating con- gestion in the network is Lhe loss of packets and the resulLing time-out while waiting for fhe acknowledgment. Other f&Ins of feedback of congesLion information have also been used. An example is Lo send ‘choke’ or ‘source quench’ packeLs to conLro1 congestion [Nag84j, [Ahu79], [Maji79]. The scheme we propose here is designed so that it is suitable for connectionless network services (as in the Digital Network Architecture (DNA) [DNA821 and the use of a connectionless network layer by transport protocols defined by the IS0 Stan- dards [lSO86]). The scheme explicitly feeds back congestion informaLion to the sources of congestion. There are two differ- ences between the feedback mechanism for congestion control using source quench or choke packets and the scheme proposed here. First, we use a lield in Lhe packet flowing in the forward direction to signal congesLion. As such, we do not have ad- ditional packels and therefore avoid additional processing and transmission overhead to process these packets in the network. Second, we use this feedback to achieve congestion avoidance rather than congestion control. l’he interesting feature of the scheme is the use of a minimal amount of feedback from the network to adjust the amounL of trafic allowed into Lhe network. The routers in the network dclect congeslion and set a single ‘congesLion avoidance’ bit on pac.kets flowing in the forward direction. This ‘congest,ion 303avoidance indication is communicated back to the users through the transport level acknowledgment. The scheme is distributed, adapts to the
View Full Document
Unlocking...