Research On Achieving Fairness Based On Active Queue Management Mechanism

1 IntroductionFairness is one of important indexes that measure QoS. FQ (Fair Queueing)scheduling mechanisms provide max-min fairness but are more complex, keepingstate for all flows going through the router.For solving the fairness problems, activequeue management mechanism should distinguish from different data flows,thereby can more fairly assign bandwidth in the bottleneck link.Random Early Detection(RED)is an efficient active queue managementalgorithm based on routers by IETF recommended. But in some networkenvironment, RED provides little protection from high-bandwidth flows that use alot of bandwidth. That can result in extreme unfairness among per-flow, even resultin congestion collapse.This paper puts forward a AQM(Active Queue Management)algorithm CHRED(Controlling High Bandwidth Flow RED)based on history ofpacket drops from a queue with RED queue management. This algorithm canprotects the fairness among per-flow through controlling the high-bandwidth flowsidentified.2 CHRED2.1 Structure of CHREDCHRED is shown in Figure 1. There are two components in CHRED: the first,identifying the high-bandwidth flows, and the second, controlling the bandwidthobtained by these flows. Packets from high-bandwidth flows are ahead dropped,and the survivors are put in the output queue. Packets from other flows are put inthe output queue directly. The next two sections will discuss each of themrespectively.2.2 Principle of CHRED2.2.1 Identifying of High-Bandwidth Flows1. Description of principleRED is a queue management algorithm that randomly drops (or marks)packets on detecting incipient congestion. Since RED drops are probabilistic, andnot the result of a buffer overflow, the packet drop history is a reasonably randomsample of incoming traffic, and provides a cheap means for identification. A flowwith more drops in the history is very likely to have higher sending rate. So,CHRED uses the packet drop history of RED to detect high-bandwidth flows.CHRED uses the RED drop history to identify flow sending rate more than thetarget sending rate. The target sending rate is defined as the sending rate of areference TCP flow with the target round-trip time R and the drop rate p at theoutput queue. Let f(R, p) denote the average sending rate in pkts/s of a TCP flowwith the target round-trip time R and a steady-state packet drop rate p. From thecomplicated model of TCP(b =1, tRTO = 4tRTT), we have:In Monitored? Controlling Output Queue OutEngineIdentificationEngineFigure 1 The structure of CHREDCHRED's goal is to identify flows that are sending at rate higher than f(R, p),the sending rate of the reference TCP. In the deterministic model of TCP, a TCPcongestion epoch contains exactly one packet drop, and therefore contains 1/ppackets. Hence, the congestion epoch length CL(R, p) of a TCP flow with the targetround-trip time R and packet drop rate p is:( )132226332(,)1(,)1( ,)RppCL Rp= f Rpp=fRpp=Rp++ (2)Its unit is second.Flows sending at a rate higher than f(R, p) will have, on average, more thanone drop in CL(R, p) seconds. CHRED maintains the packet drop history overK·CL(R, p) seconds, for some small integer K, and only identified flows with morethan K drops in this history. Instead of keeping the drop history as a single big list,CHRED partitions the history into multiple lists containing drops from consecutiveintervals of time. CHRED keeps M lists, where the length of a list is:MK CL( R,p)= MK???? R32p+6R32p(1 +32p2)???? (3)Its unit is second. CHRED identifies flows with losses in at least K of M lists.2. Choosing of Identification ParametersWe now discuss our choice of various parameters used in the identificationscheme. We first consider K, the number of congestion epoch lengths CL(R, p) thatmake up the drop history. Larger values of K make identification more reliable.These benefits come at the expense of an increase in the time required to identifyhigh-bandwidth flows. Smaller values of K increase the chances of catchingunlucky flows, that is, low-bandwidth flows that happen to suffer more drops. Inour simulations, a value of K=3 gives a reasonably prompt response along with areasonable identification for high-bandwidth flows.The next parameter to consider is M, the number of separate lists. Clearly, Mshould be greater than K because we identify flows that have drops in at least Klists. Given our choice of K=3, a value of M=5 has worked well in our simulations.The parameter R, the target round-trip time, is the single most importantparameter for CHRED's identification mechanism. The choice of R will vary atdifferent installations depending on factors like composition of traffic, and thedesired degree of fairness. Increasing R increases the degree of fairness (as moreflows are identified), and at the same time increases the state kept at the router.Thedefault of CHRED's target round-trip time is 40ms.2.2.2 Controlling of High-Bandwidth FlowsAfter identifying high-bandwidth flows, we need to reduce the arrival rate ofthese flows to the output queue. An important component of controllingHigh-Bandwidth Flows is determining the ahead dropping probability of eachmonitored flow. CHRED base each flow's ahead dropping probability directly onthe identification mechanism itself. The dropping probability for a monitored flowis not changed when the the flow appears in at least one but fewer than K of the Mdrop lists. This provides the necessary hysteresis for stabilizing the droppingprobability. We now specify how CHRED changes a flow's ahead droppingprobability.1. Increasing of the ahead dropping probabilityWhen increasing a flow's ahead dropping probability, both the RED's droprate and the arrival rate of the flow need to be considered. When the RED's droprate is high, high-bandwidth flows need to be brought down sooner, so the increasequanta should be large. In addition, different monitored flows will have differentahead dropping probability for providing relative fairness between monitoredflows.Let the drop rate in the output queue is p, the average number of drops amongthe flows identified in this round is avg_drop, and the number of drops for themonitored flow is f_drop. The equation below for a monitored flow's increasequanta P' takes into account both the drop rate in the output queue and the arrivalrates of the monitored flows.P'= ( f_drop / avg_drop)×p (4)A monitored flow is likely to continue to be identified if its arrival rate to theoutput queue is higher than f(R, p). For such flows the dropping probability isincreased. If this increase quantum is more than the flow's existing drop rate, wejust set the existing drop rate as the flow's ahead dropping probability (to makesure we don't increase a flow's drop rate all of a sudden). The existing drop rate fora flow is the sum of the ahead dropping rate and the drop rate at the output queue.2. Reducing of the ahead dropping probabilityIf the monitored flow cuts down its sending rate and does not appear in any ofthe last M drop lists, its dropping probability is decreased. If the droppingprobability of a flow becomes negligible, because the flow reduced its sending rate,the flow is unmonitored.The reduction d_max dropping probability is bounded by a maximumallowable decrease in one step, max decrease (0.05), to reduce oscillations. Thismechanism ensures that control over a monitored flow is not loosened by a largeamount in one step. When a monitored flow's ahead dropping probability less thanP_min (0.005), we release the monitored flow.2.3 Simulation of CHREDWe use a combination of analysis and simulation to evaluate CHRED's abilityto protect the low-bandwidth flows and control the high-bandwidth ones. Wecarried out the simulations using the network simulator NS2. CHRED's ability ofenforcing fairness among flows by iterative increasing and decreasing the aheaddropping probability for the high-bandwidth flows is validated in simulation. Andwe validate that CHRED react rapidly to a sudden increase or decrease of a flow'ssending rate. Finally, we demonstrate how the choice of CHRED's configured tRTTparameter R affects the degree of fairness in simulation.3 ConclusionWith the information society coming, new network applications havecontinuously appeared. The applications are urgent to the need of QoS, make QoSbe hotspot of studing. Fairness is one of important indexes that measure QoS.Fairness is very essential to guarantee the different flows to obtain fair allotment inthe bottleneck link, for the different network applications.This paper proposes CHRED, an active queue management mechanism thatcombines simplicity and protection by keeping state for just the high-bandwidthflows. CHRED uses the RED's packet drop history to detect high-bandwidth flowsin times of congestion and ahead drop packets from these flows to control thethroughput of high-bandwidth flows. CHRED achieves fairness by keeping statefor the high-bandwidth flows only, so it is simple.