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 Networks1IntroductionCore-Stateless Fair Queueing (CSFQ)Fluid Model AlgorithmPacket AlgorithmFlow Arrival RateLink Fair Share Rate EstimationNS SimulationsConclusions2OutlineThis 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 RoutersEdgeRouterCoreRouterSourceDestinationDestinationIngress 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 ArchitectureAssume 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 AlgorithmThus, 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 AlgorithmMoving 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 AlgorithmThe 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)15At 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 RewritingA major effort of the paper is to compare CSFQ to four algorithms via ns-2 simulations.FIFORED (Random Early Drop)FRED (Flow Random Early Drop)DRR (Deficit Round Robin)17SimulationsMaintains per flow state in router.FRED preferentially drops a packet of a flow that has either:Had many packets dropped in the pastA queue larger than the average queue sizeMain goal : FairnessFRED-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 bufferRED, FRED (min, max) thresholds: (16 KB, 32 KB)K and Kc = 100 ms. = 200ms.20ns-2 Simulation DetailsKαFirst Experiment : 32 UDP CBR flowsEach 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 flowsUDP flow sends at 10 Mbps31 TCP flows share a single 10 Mbps