Advanced Computer Networks Congestion Control - 2 Fair Queuing & DECbit & REDOverviewQueuing DisciplinesTypical Internet QueuingFIFO + Drop-tail ProblemsActive Queue ManagementActive Queue DesignsSlide 8Fairness GoalsWhat is Fairness?Max-min FairnessMax-min Fairness ExampleImplementing max-min FairnessBit-by-bit RRSlide 15Fair QueuingFQ AlgorithmDelay AllocationFair Queuing TradeoffsSlide 20DECbitEnd HostsExplicit Congestion NotificationSlide 26Internet ProblemsRED Design ObjectivesLock-out ProblemFull Queues ProblemRandom Early Detection (RED)RED DetailsRED Details (cont)Slide 34Tuning REDAdvanced Computer NetworksCongestion Control - 2Fair Queuing & DECbit & REDOverviewQueuing disciplinesFairnessFair-queuingDECbit & ECNREDQueuing DisciplinesEach router must implement some queuing disciplineQueuing allocates both bandwidth and buffer space:Bandwidth: which packet to serve (transmit) next Buffer space: which packet to drop next (when required)Queuing also affects latencyTypical Internet QueuingFIFO + drop-tailSimplest choiceUsed widely in the InternetFIFO (first-in-first-out) Implies single class of trafficDrop-tailArriving packets get dropped when queue is full regardless of flow or importanceImportant distinction:FIFO: scheduling disciplineDrop-tail: drop policyFIFO + Drop-tail ProblemsLeaves responsibility of congestion control to edges (e.g., TCP)Does not separate between different flowsNo policing: send more packets get more serviceSynchronization: end hosts react to same eventsActive Queue ManagementDesign active router queue management to aid congestion control Why?Routers can distinguish between propagation delay and persistent queuing delayRouters can decide on transient congestion, based on workloadActive Queue DesignsModify both routers and hostsExplicit congestion notification info in packet headerE.g. DECbit – not used in TCP/IPE.g. ECN – explicit congestion notification to work w/TCPModify routers (hosts use TCP)Fair queuingPer-connection buffer allocationRED (Random Early Detection)Drop packet or set bit in packet header as soon as congestion is startingOverviewQueuing disciplinesFairnessFair-queuingDECbit & ECNREDFairness GoalsAllocate resources fairly Isolate ill-behaved usersRouter does not send explicit feedback to sourceStill needs e2e congestion controlStill achieve statistical muxingOne flow can fill entire pipe if no contendersWork conserving scheduler never idles link if it has a packetWhat is Fairness?At what granularity?Flows, connections, domains?What if flows/connections have different RTTs/links/etc.Should they share a link fairly or be TCP fair?Basically a tough question to answer – typically design mechanisms instead of policyIs TCP CC (TCP Reno) fair ?Max-min FairnessAllocate user with “small” demand what it wants, evenly divide unused resources to “big” usersFormally:Resources allocated in terms of increasing demandNo source gets resource share larger than its demandSources with unsatisfied demands get equal share of resourceMax-min Fairness ExampleAssume sources 1..n, with resource demands X1..Xn in ascending orderAssume 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 processImplementing max-min FairnessBitwise round robin among all queuesWhy not simple round robin?Variable packet length can get more service by sending bigger packetsUnfair instantaneous service rateWhat if arrive just before/after packet departs?But fair in a long termBit-by-bit RRSingle flow: a logical clock ticks when a bit is transmitted For packet i:Pi = time to transmit packet i, Ai = arrival time, Si = begin transmit time, Fi = finish transmit timeFi = Si+Pi = max (Fi-1, Ai) + PiMultiple flows: clock ticks when a bit from all active flows is transmitted round numberFair queuing simulates bit-by-bit RROverviewQueuing disciplinesFairnessFair-queuingDECbit & ECNREDFair QueuingMapping bit-by-bit schedule onto packet transmission scheduleTransmit packet with the lowest Fi at any given timeHow do you compute Fi? Fi = Si+Pi = max (Fi-1, Ai) + PiFQ AlgorithmFor multiple flowscalculate Fi for each packet that arrives on each flowtreat all Fi’s as timestampsnext packet to transmit is one with lowest timestampNot perfect: can’t preempt current packetExampleFlow 1 Flow 2(a) (b)Output OutputF = 8F = 10F = 5F = 10F = 2Flow 1(arriving)Flow 2(transmitting)Delay AllocationReduce delay for flows using less than fair sharePull back arrival times for sources whose queues drain temporarilySchedule based on Bi instead of FiFi = Pi + max (Fi-1, Ai) Bi = Pi + max (Fi-1, Ai - )If Ai < Fi-1, flow is active and has no effectIf Ai > Fi-1, flow is inactive and determines how much history to take into accountInfrequent senders do better when history is usedFair Queuing TradeoffsFQ can control congestion by monitoring flowsNon-adaptive flows can still be a problem – why?Complex stateMust keep queue per flowHard in routers with many flows (e.g., backbone routers)Flow aggregation is a possibility (e.g. do fairness per domain)Complex computationClassification into flows may be hardMust keep queues sorted by finish timesThe round duration changes whenever the flow count changesOverviewQueuing disciplinesFairnessFair-queuingDECbit & ECNREDDECbitRoutermonitors average queue length over last busy+idle cycleset congestion bit if average queue length > 1Queue lengthCurrenttimeTimeCurrentcyclePreviouscycleAveragingintervalEnd HostsDestination echoes CI bit back to sourceSource records how many packets resulted in set bit during the past congestion window intervalIf less than 50% of last window’s worth had bit set increase CongestionWindow by 1 packetIf 50% or more of last window’s worth had bit set decrease CongestionWindow to 0.875 of current oneExplicit Congestion Notification Proposed for standard TCPTCP uses packet losses to detect congestionWasteful and unnecessaryECN (RFC 2481)Routers mark packets instead of dropping themReceiver returns
View Full Document
Unlocking...