15-744: Computer NetworkingFair QueuingOverviewFairness GoalsWhat is Fairness?Max-min FairnessMax-min Fairness ExampleImplementing max-min FairnessBit-by-bit RRBit-by-bit RR IllustrationSlide 11Slide 12FQ IllustrationBit-by-bit RR ExampleDelay AllocationFair Queuing TradeoffsSlide 17Core-Stateless Fair QueuingSlide 19Edge Router BehaviorCore Router BehaviorF vs. AlphaEstimating Fair ShareOther IssuesSlide 25Stochastic Fair QueuingDeficit Round RobinSelf-clocked Fair QueuingSelf-clocked FQStart-time Fair QueuingXCPXCP Core RoutersSlide 33XCP vs. CSFQNext Lecture: Wireless15-744: Computer NetworkingL-11 Fair QueuingL -11; 10-15-02© Srinivasan Seshan, 2002 2Fair Queuing•Fair Queuing•Core-stateless Fair queuing•Assigned reading•[DKS90] Analysis and Simulation of a Fair Queueing Algorithm, Internetworking: Research and Experience•[SSZ98] Core-Stateless Fair Queueing: Achieving Approximately Fair Allocations in High Speed NetworksL -11; 10-15-02© Srinivasan Seshan, 2002 3Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variantsL -11; 10-15-02© Srinivasan Seshan, 2002 4Fairness Goals•Allocate resources fairly •Isolate ill-behaved users•Router does not send explicit feedback to source•Still needs e2e congestion control•Still achieve statistical muxing•One flow can fill entire pipe if no contenders•Work conserving scheduler never idles link if it has a packetL -11; 10-15-02© Srinivasan Seshan, 2002 5What is Fairness?•At what granularity?•Flows, connections, domains?•What if users have different RTTs/links/etc.•Should it share a link fairly or be TCP fair?•Maximize fairness index?•Fairness = (xi)2/n(xi2) 0<fairness<1•Basically a tough question to answer – typically design mechanisms instead of policy•User = arbitrary granularityL -11; 10-15-02© Srinivasan Seshan, 2002 6Max-min Fairness•Allocate user with “small” demand what it wants, evenly divide unused resources to “big” users•Formally:•Resources allocated in terms of increasing demand•No source gets resource share larger than its demand•Sources with unsatisfied demands get equal share of resourceL -11; 10-15-02© Srinivasan Seshan, 2002 7Max-min Fairness Example•Assume sources 1..n, with resource demands X1..Xn in ascending order•Assume channel capacity C.•Give C/n to X1; if this is more than X1 wants, divide excess (C/n - X1) to other sources: each gets C/n + (C/n - X1)/(n-1)•If this is larger than what X2 wants, repeat processL -11; 10-15-02© Srinivasan Seshan, 2002 8Implementing max-min Fairness•Generalized processor sharing•Fluid fairness•Bitwise round robin among all queues•Why not simple round robin?•Variable packet length can get more service by sending bigger packets•Unfair instantaneous service rate•What if arrive just before/after packet departs?L -11; 10-15-02© Srinivasan Seshan, 2002 9Bit-by-bit RR•Single flow: clock ticks when a bit is transmitted. For packet i:•Pi = length, Ai = arrival time, Si = begin transmit time, Fi = finish transmit time•Fi = Si+Pi = max (Fi-1, Ai) + Pi•Multiple flows: clock ticks when a bit from all active flows is transmitted round number•Can calculate Fi for each packet if number of flows is know at all times•Why do we need to know flow count? need to know A This can be complicatedL -11; 10-15-02© Srinivasan Seshan, 2002 10Bit-by-bit RR Illustration•Not feasible to interleave bits on real networks•FQ simulates bit-by-bit RRL -11; 10-15-02© Srinivasan Seshan, 2002 11Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variantsL -11; 10-15-02© Srinivasan Seshan, 2002 12Fair Queuing•Mapping bit-by-bit schedule onto packet transmission schedule•Transmit packet with the lowest Fi at any given time•How do you compute Fi?L -11; 10-15-02© Srinivasan Seshan, 2002 13FQ IllustrationFlow 1Flow 2Flow nI/PO/PVariation: Weighted Fair Queuing (WFQ)L -11; 10-15-02© Srinivasan Seshan, 2002 14Bit-by-bit RR ExampleF=10Flow 1(arriving)Flow 2transmittingOutputF=2F=5F=8Flow 1 Flow 2OutputF=10Cannot preempt packetcurrently being transmittedL -11; 10-15-02© Srinivasan Seshan, 2002 15Delay Allocation•Reduce delay for flows using less than fair share•Advance finish times for sources whose queues drain temporarily•Schedule based on Bi instead of Fi•Fi = Pi + max (Fi-1, Ai) Bi = Pi + max (Fi-1, Ai - )•If Ai < Fi-1, conversation is active and has no effect•If Ai > Fi-1, conversation is inactive and determines how much history to take into account•Infrequent senders do better when history is usedL -11; 10-15-02© Srinivasan Seshan, 2002 16Fair Queuing Tradeoffs•FQ can control congestion by monitoring flows•Non-adaptive flows can still be a problem – why?•Complex state•Must keep queue per flow•Hard in routers with many flows (e.g., backbone routers)•Flow aggregation is a possibility (e.g. do fairness per domain)•Complex computation•Classification into flows may be hard•Must keep queues sorted by finish times•dR/dt changes whenever the flow count changesL -11; 10-15-02© Srinivasan Seshan, 2002 17Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variantsL -11; 10-15-02© Srinivasan Seshan, 2002 18Core-Stateless Fair Queuing•Key problem with FQ is core routers•Must maintain state for 1000’s of flows•Must update state at Gbps line speeds•CSFQ (Core-Stateless FQ) objectives•Edge routers should do complex tasks since they have fewer flows•Core routers can do simple tasks•No per-flow state/processing this means that core routers can only decide on dropping packets not on order of processing•Can only provide max-min bandwidth fairness not delay allocationL -11; 10-15-02© Srinivasan Seshan, 2002 19Core-Stateless Fair Queuing•Edge routers keep state about flows and do computation when packet arrives•DPS (Dynamic Packet State)•Edge routers label packets with the result of state lookup and computation•Core routers use DPS and local measurements to control processing of packetsL -11; 10-15-02© Srinivasan Seshan, 2002 20Edge Router Behavior•Monitor each flow i to measure its arrival rate (ri)•EWMA of rate•Non-constant EWMA constant •e-T/K where T = current interarrival, K = constant•Helps adapt to different packet sizes and arrival patterns•Rate is attached to each packetL -11; 10-15-02© Srinivasan Seshan, 2002 21Core Router Behavior•Keep track of fair
View Full Document