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 TradeoffsDiscussion CommentsSlide 18Core-Stateless Fair QueuingSlide 20Edge Router BehaviorCore Router BehaviorF vs. AlphaEstimating Fair ShareOther IssuesSlide 26Slide 27Stochastic Fair QueuingDeficit Round RobinSelf-clocked Fair QueuingSelf-clocked FQStart-time Fair QueuingNext Lecture: TCP & RoutersClass ProjectSlide 35Project IdeasSlide 37Slide 38Slide 3915-744: Computer NetworkingL-5 TCP & Routers2Fair 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 Networks3Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variants4Fairness 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 packet5What 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 granularity6Max-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 resource7Max-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 process8Implementing 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?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•This can be complicated10Bit-by-bit RR Illustration•Not feasible to interleave bits on real networks•FQ simulates bit-by-bit RR11Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variants12Fair 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?13FQ IllustrationFlow 1Flow 2Flow nI/PO/PVariation: Weighted Fair Queuing (WFQ)14Bit-by-bit RR ExampleF=10Flow 1(arriving)Flow 2transmittingOutputF=2F=5F=8Flow 1 Flow 2OutputF=10Cannot preempt packetcurrently being transmitted15Delay 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 used16Fair 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•Finish times change whenever the flow count changesDiscussion Comments•Granularity of fairness•Mechanism vs. policy will see this in QoS•Hard to understand•Complexity – how bad is it?1718Overview•Fairness•Fair-queuing•Core-stateless FQ•Other FQ variants19Core-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 allocation20Core-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 packets21Edge 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 packet22Core Router Behavior•Keep track of fair share rate •Increasing does not increase load (F) by N * •F() = i min(ri, ) what does this look like?•Periodically update •Keep track of current arrival rate•Only update if entire period was congested or uncongested•Drop probability for packet = max(1- /r, 0)23F vs. AlphaNew alphaC [linked capacity]r1 r2 r3 old alphaalphaF24Estimating Fair Share•Need F() = capacity = C•Can’t keep map of F() values would require per flow state•Since F() is concave, piecewise-linear•F(0) = 0 and F() = current accepted rate = Fc•F() = Fc/ •F(new) = C new = old * C/Fc•What if a mistake was made?•Forced into
View Full Document
Unlocking...