IEEE Network • May/June 200116he Internet was simply designed for packet delivery.However recent developments such as commercializa-tion and the diversity of application requirementsmake it obvious that a more concrete definition of thetype of service delivered to the user is needed. This descriptionof the service delivered by the network is called the servicemodel and documents the commitments the network makes tothe clients that request service. It describes a set of end-to-end services and it is up to the network to ensure that the ser-vices offered at each link along a path combine meaningfullyto support the end-to-end service.Traditionally, in the Internet all packets are treated thesame without any discrimination or explicit delivery guaran-tees. This is known as the best effort service model; all the net-work promises is to exert its best effort to deliver the packetsinjected into it without committing to any quantitative perfor-mance (quality of service, QoS) bounds.1Users do not requestpermission before transmitting, and therefore perceived per-formance is determined not only by the network itself, butalso from other users’ offered load, resulting in a completelack of isolation and protection. The best effort service modelhas no formal specification; rather, it is specified operational-ly; packet delivery should be an expectation rather than an excep-tion. The traditional applications and protocols were flexible,adaptive, and robust enough to operate under a wide range ofnetwork conditions without requiring any particularly well-defined service.The Problem of CongestionCongestion is the state of sustained network overload wherethe demand for network resources is close to or exceedscapacity. Network resources, namely link bandwidth andbuffer space in the routers, are both finite and in many casesstill expensive. The Internet has suffered from the problemof congestion which is inherent in best effort datagram net-works due to uncoordinated resource sharing. It is possiblefor several IP packets to arrive at the router simultaneously,needing to be forwarded on the same output link. Clearly,not all of them can be forwarded simultaneously; there mustbe a service order. In the interim buffer space must be pro-vided as temporary storage for the packets still awaitingtransmission.Sources that transmit simultaneously can create a demandfor network resources (arrival rate) higher than the networkcan handle at a certain link. The buffer space in the routersoffers a first level of protection against an increase in trafficarrival rate. However, if the situation persists, the buffer spaceis exhausted and the router has to start dropping packets. Tra-ditionally Internet routers have used the first come first served(FCFS) service order, typically implemented by a first in firstout (FIFO) queue, and drop from the tail at buffer overflowas their queue management strategy.The problem of congestion cannot be solved by introduc-ing “infinite” buffer space inside the network; the queueswould then grow without bound, and the end-to-end delaywould increase. Moreover, when packet lifetime is finite, thepackets coming out of the router would have timed outalready and been retransmitted by the transport protocols [1].0890-8044/01/$10.00 © 2001 IEEECongestion Control Mechanisms and theBest Effort Service ModelPanos Gevros, Jon Crowcroft, Peter Kirstein, and Saleem BhattiUniversity College LondonAbstractIn the last few years there has been considerable research toward extending theInternet architecture to provide quality of service guarantees for the emerging real-time multimedia applications. QoS provision is a rather controversial endeavor. Atone end of the spectrum there were proposals for reservations and per-flow state inthe routers. These models did not flourish due to the network’s heterogeneity, thecomplexity of the mechanisms involved, and scalability problems. At the other end,proposals advocating that an overprovisioned best effort network will solve all theproblems are not quite convincing either. The authors believe that more control isclearly needed for protecting best effort service. An important requirement is to pre-vent congestion collapse, keep congestion levels low, and guarantee fairness.Appropriate control structures in a best effort service network could even be used forintroducing differentiation. This could be achieved without sacrificing the best effort natureof the Internet or stressing its architecture beyond its limits and original design princi-ples. In this article we revisit the best effort service model and the problem of conges-tion while focusing on the importance of cooperative resource sharing to theInternet’s success, and review the congestion control principles and mechanismswhich facilitate Internet resource sharing.TT1The QoS bounds are usually any combination of the three following met-rics: throughput, end-to-end delay, and packet loss ratio.IEEE Network • May/June 200117In fact, too much buffer space in the routers can be moreharmful than too little, because the packets will have to bedropped only after they have consumed valuable networkresources.The Threat of Congestion CollapseCongestion in the Internet can cause high packet loss rates,increased delays, and can even break the whole system by caus-ing congestion collapse (or “Internet meltdown”). This is astate where any increase in the offered load leads to adecrease in the useful work done by the network (Fig. 1, thearea beyond the “cliff”). The threat of congestion collapse isnot a new one; it dates back to the early days of the Internet(then ARPANET) and can take several forms. In 1984 Nagle[2] reported on congestion collapse due to TCP connectionsunnecessarily retransmitting packets that were either in transitor already received at the receiver. This form of congestioncollapse is a stable condition which results in throughput thatis only a small fraction of the normal. This phenomenon, aspredicted by Nagle, occurred several times in 1986–1987 witha large number of sites experiencing simultaneous slowdownof their network services for prolonged periods. At that timeBBN, the firm maintaining the Internet backbone, respondedto the collapse by providing additional link capacity. However,this could only ever be a temporary fix.Another form of congestion collapse is the one fromundelivered packets; in this case bandwidth is wasted by deliv-ering packets that will be dropped before