BLUE: A New Class of Active Queue Management AlgorithmsWu-chang FengyDilip D. KandlurzDebanjan SahazKang G. ShinyyDepartment of EECSzNetwork Systems DepartmentUniversity of Michigan IBM T.J. Watson Research CenterAnn Arbor, MI 48105 Yorktown Heights, NY 10598Phone: (313) 763-5363 Fax: (313) 763-4617 Phone: (914) 784-7194 Fax: (914) 784-6205fwuchang,[email protected],[email protected] order to stem the increasing packet loss rates caused by an exponential increase in network traffic,theIETF is consideringthe deployment of active queue management techniquessuch as RED [13]. Whileactive queue management can potentially reduce packet loss rates in the Internet, this paper shows thatcurrent techniques are ineffective in preventing high loss rates. The inherent problem with these queuemanagement algorithms is that they all use queue lengths as the indicator of the severity of congestion.In light of this observation, a fundamentally different active queue management algorithm called BLUEis proposed. BLUE uses packet loss and link idle events to manage congestion. Using simulation andcontrolled experiments, BLUE is shown to perform significantly better than RED both in terms of packetloss rates and buffer size requirements in the network. As an extension to BLUE, a novel technique forenforcing fairness among a large number of flows is described. In particular, this paper proposes andevaluates Stochastic Fair BLUE (SFB), a queue management algorithm which can identify and rate-limitnon-responsive flows using a very small amount of state information.Keywords: Congestion control, Internet,TCP,RED, queue management11 IntroductionIt is important to avoid high packet loss rates in the Internet. When a packet is dropped before it reaches itsdestination, all of the resources it has consumed in transit are wasted. In extreme cases, this situation canlead to congestioncollapse [17]. Improving the congestioncontrol and queue management algorithmsin theInternet has been one of the most active areas of research in the past few years. While a number of proposedenhancements have made their way into actual implementations, connections still experience high packetloss rates. Loss rates are especially high during times of heavy congestion, when a large number of connec-tions compete for scarce network bandwidth. Recent measurements have shown that the growing demandfor network bandwidth has driven loss rates up across various links in the Internet [23]. In order to stemthe increasing packet loss rates caused by an exponential increase in network traffic, theIETF is consideringthe deployment of explicit congestion notification (ECN) [11,24,25] along with active queue managementtechniques such as RED (Random Early Detection) [2, 11]. While ECN is necessary for eliminating packetloss in the Internet [10], this paper shows that RED, even when used in conjunction with ECN, is ineffectivein preventing packet loss.The basic idea behind RED queue management is to detect incipient congestionearly and to convey con-gestion notification to the end-hosts, allowing them to reduce their transmission rates before queues in thenetwork overflow and packets are dropped. To do this, RED maintains an exponentially-weighted movingaverage of the queue length which it uses to detect congestion. When the average queue length exceeds aminimum threshold (minth), packets are randomly dropped or marked with an explicit congestion notifica-tion (ECN) bit. When the average queue length exceeds a maximum threshold, all packets are dropped ormarked. While RED is certainly an improvement over traditional drop-tail queues, it has several shortcom-ings. One of the fundamental problems with RED and all other known active queue management techniquesis that they rely on queue lengths as an estimator of congestion. While the presence of a persistent queueindicates congestion, its length gives very little information as to the severity of congestion, that is, thenumber of competing connections sharing the link. In a busy period, a single source transmitting at a rategreater than the bottleneck link capacity can cause a queue to build up just as easily as a large number ofsources can. Since the RED algorithm relies on queue lengths, it has an inherent problem in determiningthe severity of congestion. As a result, RED requires a wide range of parameters to operate correctly underdifferent congestion scenarios. While RED can achieve an ideal operating point, it can only do so when ithas a sufficient amount of buffer space and is correctly parameterized [5,29].In light of the above observation, this paper proposes BLUE, a fundamentally different active queuemanagement algorithm which uses packet loss and link utilization history to manage congestion. BLUEmaintains a single probability, which it uses to mark (or drop) packets when they are queued. If the queueis continually dropping packets due to buffer overflow, BLUE increments the marking probability, thusincreasing the rate at which it sends back congestion notification. Conversely, if the queue becomes emptyor if the link is idle, BLUE decreases its marking probability. Using simulation and experimentation, thispaper demonstrates the superiority of BLUE to RED in reducing packet losses even when operating with asmaller buffer. Using mechanisms based on BLUE, a novel mechanism for effectively and scalably enforcingfairness among a large number of flows is also proposed and evaluated.The rest of the paper is organized as follows. Section 2 gives a description of RED and shows why it isineffective at managing congestion. Section 3 describes BLUE and provides a detailed analysis and evalua-tion of its performance. Section 4 describes and evaluates Stochastic Fair BLUE (SFB), an algorithm basedon BLUE which scalably enforces fairness amongst a large number of connections. Section 5 compares SFBto other approaches which have been proposed to enforce fairness amongst connections. Finally, Section 6concludes with a discussion of future work.2Sources SinksASources SinksASources SinksASending rate > L Mbs Queue increases some moreSinks generate DupAcks or ECNSources SinksASending rate > L Mbs Queue increases some moreDupAcks/ECN travel backSources SinksA7Queue increases some moreQueue overflows, max_th triggeredSources detect loss/ECNSending rate < L MbsSources SinksASourcesSending rate increases above L MbsSinksL MbsABSending rate > L Mbs Queue increasesSending rate > L
View Full Document
Unlocking...