Slide 1OutlineIntroductionAn “Island” of RoutersCore-Stateless Fair QueueingEdge – Core Router ArchitectureFluid Model AlgorithmFluid Model AlgorithmFluid Model AlgorithmPacket AlgorithmFlow Arrival RateLink Fair Rate EstimationHeuristic AlgorithmCSFQ AlgorithmCSFQ Algorithm (cont.)Label RewritingSimulationsFRED (Flow Random Early Drop)DRR (Deficit Round Robin)ns-2 Simulation DetailsA Single Congested LinkFigure 3a: 32 UDP FlowsFigure 3b : One UDP Flow, 31 TCP FlowsA Single Congested LinkFigure 4 : One TCP Flow, N-1 UDP FlowsMultiple Congested LinksMultiple Congested LinksFigure 6a : UDP sourceFigure 6b : TCP SourceUnfriendly FlowsConclusionsSignificanceProblems/ WeaknessesExtra SlidesReceiver-driven Layered MulticastReceiver-driven Layered MulticastFigure 7c : FREDFigure 7d : REDFigure 7e : FIFOFigure 7a : DRRFigure 7b : CSFQIon Stoica, Scott Shenker, and Hui ZhangSIGCOMM’98, Vancouver, August 1998subsequentlyIEEE/ACM Transactions on Networking 11(1), 2003, pp. 33-46 . Presented by: Camille GaspardOriginally taken from:web.cs.wpi.edu/~rek/Adv_Nets/Summer2003/CSFQ. pptCore-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks1IntroductionCore-Stateless Fair Queueing (CSFQ)Fluid Model AlgorithmPacket AlgorithmFlow Arrival RateLink Fair Share Rate EstimationNS SimulationsConclusions2OutlineThis paper brings forward the concept of “fair” allocation.The claim is that fair allocation inherently requires routers to maintain state and perform operations on a per flow basis.The authors present an architecture and a set of algorithms that is “approximately” fair while using FIFO queueing at internal routers.3Introduction4An “Island” of RoutersEdgeRouterCoreRouterSourceDestinationDestinationIngress edge routers compute per-flow rate estimates and insert these estimates as labels into each packet header.Only edge routers maintain per flow state.Labels are updated at each router based only on aggregate information.FIFO queueing with probabilistic dropping of packets on input is employed at the core routers.5Core-Stateless Fair Queueing6Edge – Core Router ArchitectureAssume the bottleneck router has an output link with capacity C.Assume each flow’s arrival rate, ri (t) , is known precisely. The main idea is that max-min fair bandwidth allocations are characterized such that all flows that are bottlenecked by a router have the same output rate.This rate is called the fair share rate of the link.Let α(t) be the fair share rate at time t.7Fluid Model AlgorithmIf max-min bandwidth allocations are achieved, each flow receives service at a rate given by min ( ri (t), α(t) )Let A(t) denote the total arrival rate:If A(t) > C then the fair share is the unique solution to8Fluid Model AlgorithmThus, the probabilistic fluid forwarding algorithm that achieves fair bandwidth allocation is:Each incoming bit of flow i is dropped with probability max (0, 1 - α(t) / ri(t) ) (2)These dropping probabilities yield fair share arrival rates at the next hop. 9Fluid Model AlgorithmMoving from a bit-level, buffer-less fluid model to a packet-based, buffer model leaves two challenges:Estimate the flow arrival rates ri(t)Estimate the fair share α(t)This is possible because the rate estimator incorporates the packet size.10Packet AlgorithmAt each edge router, use exponential averaging to estimate the rate of a flow. For flow i, letlik be the length of the kth packet.tik be the arrival time of the kth packet.Then the estimated rate of flow i, ri is updated every time a new packet is received: rinew = (1 - e-T/K ) * L / T + (e-T/K) * riold (3)where T = Tik = tik – tik-1 L = lik and K is a constant11Flow Arrival RateLink Fair Rate EstimationIf we denote the estimate of the fair share by and the acceptance rate by , we haveNote – if we know ri(t) then can be determined by finding the unique solution to F(x) = C.However, this requires per-flow state !12Heuristic AlgorithmThe heuristic algorithm needs three aggregate state variables: , , where is the estimated aggregate arrival rate.When a packet arrives, the router computes: (5)and similarly computes .13CSFQ Algorithm When a packet arrives, is updated using exponential averaging (equation 5).If the packet is dropped, remains the same.If the packet is not dropped, is updated using exponential averaging.At the end of an epoch (defined by Kc ), if the link is congested (C< ), update :14CSFQ Algorithm (cont.)If the link is not congested, is set to the largest rate of any active flow. feeds into the calculation of drop probability, p, for the next arriving packet as α in p = max (0 , 1 – α / label)15At core routers, outgoing rate is merely the minimum between the incoming rate and the fair rate, α. Hence, the packet label L can be rewritten by L new = min (L old , α )16Label RewritingA major effort of the paper is to compare CSFQ to four algorithms via ns-2 simulations.FIFORED (Random Early Drop)FRED (Flow Random Early Drop)DRR (Deficit Round Robin)17SimulationsMaintains per flow state in router.FRED preferentially drops a packet of a flow that has either:Had many packets dropped in the pastA queue larger than the average queue sizeMain goal : FairnessFRED-2 guarantees to each flow a minimum number of buffers.18FRED (Flow Random Early Drop)Represents an efficient implementation of WFQ.A sophisticated per-flow queueing algorithm.Scheme assumes that when router buffer is full the packet from the longest queue is dropped.Can be viewed as “best case” algorithm with respect to fairness.19DRR (Deficit Round Robin)Use TCP, UDP, RLM and On-Off traffic sources in separate simulations.Bottleneck link: 10 Mbps, 1 ms latency, 64 KB bufferRED, FRED (min, max) thresholds: (16 KB, 32 KB)K and Kc = 100 ms. = 200ms.20ns-2 Simulation DetailsKαFirst Experiment : 32 UDP CBR flowsEach UDP flow is indexed from 0 to 31 with flow 0 sending at 0.3125 Mbps and each of the i subsequent flows sending (i+ 1) times its fair share of 0.3125 Mbps.Second Experiment : 1 UDP CBR flow, 31 TCP flowsUDP flow sends at 10 Mbps31 TCP flows share a single 10 Mbps
View Full Document