CS551RouterQueue ManagementBill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. ChengNetwork’s key role is to allocate its transmission resourcesto users or applications2Congestion Control vs. Resource Allocation Computer Communications - CSCI 551 Copyright © William C. ChengTwo sides of the same coinLet network do resource allocation (e.g., VCs)Let sources send as much data as they wantdifficult to do allocation of distributed resourcescan be wasteful of resourcesrecover from congestion when it occurseasier to implement, may lose packetsIt doesn’t know about users or applicationsHow can a connectionless network allocate anything to auser?3Connectionless Flows Computer Communications - CSCI 551 Copyright © William C. ChengA sequence of packets between same source - destinationpair, following the same routeFlow:Flow is visible to routers - it is not a channel, which is anend-to-end abstractionRouters may maintain soft-state for a flowFlow can be implicitly defined or explicitly established(similar to VC)Different from VC in that routing is not fixed4 Computer Communications - CSCI 551 Copyright © William C. Cheng GoalsFair Queueing [Demers89a]FairnessRED [Floyd93a]EfficiencyXCP [Katabi02a]StabilityRIO [Clark98a]Service Differentiation5 Computer Communications - CSCI 551 Copyright © William C. Cheng Design DimensionsFair to whom (flows, users, etc.)How quickly do you provide feedbackWhat kind of fairness do you provideHow fair (probabilistic, guarantee, etc.)Definition of fair (equal size, max-min)constant amount, for some flows, for each flowHow efficient you are (router go idle?)How much state you must keepdropping packets vs. explicit feedback (DECbit, ECN)How do you signal congestion6 Computer Communications - CSCI 551 Copyright © William C. Cheng Queueing PoliciesFIFO ("drop tail")also drop headMany policies have been consideredRound robin (per flow)Weighted round robinFair queueingToken bucketVitrual clockClass-based queueing (per class of traffic)Stochastic fair queueing (statistical)Router-centric: address problem from inside network -routers decide what to forward and what to dropRouter-centric v.s. Host-centric7Taxonomy Computer Communications - CSCI 551 Copyright © William C. ChengHost centric: address problem at the edges - hosts observenetwork conditions and adjust behaviorNot always a clear separation: hosts and routers maycollaborate, e.g., routers advise hostsvariant: only at edge-routersReservations: hosts ask for resources, network respondsyes/noimplies router-centric allocationReservation-based v.s. Feedback-based8Taxonomy (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengFeedback: hosts send with no reservation, adjustaccording to feedbackeither router or host centric: explicit (e.g., ICMPsource quench) or implicit (e.g., loss) feedbackFlow control: advertised windowWindow-based v.s. Rate-based9Taxonomy (Cont...) Computer Communications - CSCI 551 Copyright © William C. ChengBoth tell sender how much data to transmitWindow: TCP flow/congestion controlCongestion control: cwndMay be logical choice for reservation-based systemRate: still an open area of researchMostly host-centric, feedback, window basedIn practice, fewer than eight choices10Service Models Computer Communications - CSCI 551 Copyright © William C. ChengBest-effort networksRouter-centric, reservation, rate-basedNetworks with flexible Quality of ServiceTCP as an examplebandwidth: which packets get transmittedEach router must implement some queuing disciplineregardless of what the resource allocation mechanism is11Queueing Disciplines Computer Communications - CSCI 551 Copyright © William C. ChengQueueing discipline allocates:buffer space: which packets get droppedpromptness: when packets get transmittedFIFO: scheduling discipline (which packet to serve next)FIFO:first-in-first-out (or FCFS: first-come-first-served)12FIFO Queuing Computer Communications - CSCI 551 Copyright © William C. ChengArriving packets get dropped when queue is full regardlessof flow or importance - implies droptailImportant distinction:Drop-tail: drop policy (which packet to drop next)ArrivingPacketArrivingPacketDropFree Buffer13Dimensions Computer Communications - CSCI 551 Copyright © William C. ChengPer-connectionstateSingle classSchedulingClass-based queuing Head TailDrop positionRandom locationEarly drop Overflow dropFIFOFIFO lets large user get more data through but sharescongestion with othersUsed widely in the InternetFIFO + drop-tail is the simplest queuing algorithm14FIFO Computer Communications - CSCI 551 Copyright © William C. ChengLeaves responsibility of congestion control to edges(e.g., TCP)Does not provide isolation between different flowsNo policing15 Computer Communications - CSCI 551 Copyright © William C. ChengFair Queueing[Demers89a]Bill Chenghttp://merlot.usc.edu/cs551-f12Maintain a separate queue for each flow currently flowingthrough router Main idea:16Fair Queuing Computer Communications - CSCI 551 Copyright © William C. ChengRouter services queues in Round-Robin fashionProvides isolation between flowsChanges interaction between packets from different flowsIll-behaved flows cannot starve well-behaved flowsAllocates buffer space and bandwidth fairlyFair Queueing (FQ) [Nagle85,Nagle87]17Fair Queueing Illustration Computer Communications - CSCI 551 Copyright © William C. ChengVariation: Weighted Fair Queueing (WFQ)Flow 1Flow 2Flow nI/P O/PSeveral granularities at which one can express flowsWhat constitutes a user?18Some Issues Computer Communications - CSCI 551 Copyright © William C. ChengFor now, assume at the granularity of source-destinationpair, but this assumption is not criticalSource sending longer packets can still grab more thantheir share of resourcesPackets are of different lengthWe really need bit-by-bit round-robinFair Queuing simulates bit-by-bit round-robinnot feasible to interleave bits!logical clock = number of rounds servedPi: length, Ai = arrival time, Si: begin transmit (start time)Fi: finish timeRouter maintains a logical clock19Bit-by-bit Round-robin Computer Communications - CSCI 551 Copyright © William C. ChengSingle flow: suppose clock ticks when a bit is transmitted.For packet i:Multiple flows: logical clock ticks when a bit from all activeflows is transmittedSi = max(Fi-1, Ai)Fi = Si + PiFi = max(Fi-1, Ai) + Pilogical clock advances more slowly when there are moreflowsTransmit
View Full Document
Unlocking...