《Lec09congestion》由会员分享，可在线阅读，更多相关《Lec09congestion（28页珍藏版）》请在金锄头文库上搜索。
1、Lec09congestionLec09congestionIssuesTwo sides of the same coinpre-allocate resources so at to avoid congestioncontrol congestion if (and when) is occursTwo points of implementationhosts at the edges of the network (transport protocol)routers inside the network (queuing discipline)Underlying service
2、modelbest-effort (assume for now)multiple qualities of service (later)Spring 20022CS 461FrameworkConnectionless flowssequence of packets sent between source/destination pairmaintain soft state at the routersTaxonomyrouter-centric versus host-centricreservation-based versus feedback-basedwindow-based
3、 versus rate-basedSpring 20023CS 461EvaluationFairnessPower (ratio of throughput to delay)Spring 20024CS 461Queuing DisciplineFirst-In-First-Out (FIFO)does not discriminate between traffic sourcesFair Queuing (FQ)explicitly segregates traffic based on flowsensures no flow captures more than its shar
4、e of capacityvariation: weighted fair queuing (WFQ)Problem?Spring 20025CS 461FQ AlgorithmSuppose clock ticks each time a bit is transmittedLet Pi denote the length of packet iLet Si denote the time when start to transmit packet iLet Fi denote the time when finish transmitting packet iFi = Si + PiWhe
5、n does router start transmitting packet i?if before router finished packet i - 1 from this flow, then immediately after last bit of i - 1 (Fi-1)if no current packets for this flow, then start transmitting when arrives (call this Ai)Thus: Fi = MAX (Fi - 1, Ai) + PiSpring 20026CS 461FQ Algorithm (cont
6、)For multiple flowscalculate Fi for each packet that arrives on each flowtreat all Fis as timestampsnext packet to transmit is one with lowest timestampNot perfect: cant preempt current packetExampleFlow 1Flow 2(a)(b)OutputOutputF = 8F = 10F = 5F = 10F = 2Flow 1(arriving)Flow 2(transmitting)Spring 2
7、0027CS 461TCP Congestion ControlIdeaassumes best-effort network (FIFO or FQ routers) each source determines network capacity for itselfuses implicit feedbackACKs pace transmission (self-clocking)Challengedetermining the available capacity in the first placeadjusting to changes in the available capac
8、itySpring 20028CS 461Additive Increase/Multiplicative DecreaseObjective: adjust to changes in the available capacityNew state variable per connection: CongestionWindowlimits how much data source has in transitMaxWin = MIN(CongestionWindow, AdvertisedWindow)EffWin = MaxWin - (LastByteSent - LastByteA
9、cked)Idea:increase CongestionWindow when congestion goes downdecrease CongestionWindow when congestion goes upSpring 20029CS 461AIMD (cont)Question: how does the source determine whether or not the network is congested?Answer: a timeout occurstimeout signals that a packet was lostpackets are seldom
10、lost due to transmission errorlost packet implies congestionSpring 200210CS 461AIMD (cont)In practice: increment a little for each ACKIncrement = (MSS * MSS)/CongestionWindowCongestionWindow += Increment Algorithmincrement CongestionWindow by one packet per RTT (linear increase)divide CongestionWind
11、ow by two whenever a timeout occurs (multiplicative decrease)SourceDestinationSpring 200211CS 461AIMD (cont)Trace: sawtooth behaviorSpring 200212CS 461Slow StartObjective: determine the available capacity in the firstIdea:begin with CongestionWindow = 1 packetdouble CongestionWindow each RTT (increm
12、ent by 1 packet for each ACK)SourceDestinationSpring 200213CS 461Slow Start (cont)Exponential growth, but slower than all at onceUsedwhen first starting connectionwhen connection goes dead waiting for timeoutTraceProblem: lose up to half a CongestionWindows worth of dataSpring 200214CS 461Fast Retra
13、nsmit and Fast RecoveryProblem: coarse-grain TCP timeouts lead to idle periodsFast retransmit: use duplicate ACKs to trigger retransmissionSpring 200215CS 461ResultsFast recoveryskip the slow start phasego directly to half the last successful CongestionWindow (ssthresh)Spring 200216CS 461Congestion
14、AvoidanceTCPs strategycontrol congestion once it happensrepeatedly increase load in an effort to find the point at which congestion occurs, and then back offAlternative strategypredict when congestion is about to happenreduce rate before packets start being discardedcall this congestion avoidance, i
15、nstead of congestion controlTwo possibilities router-centric: DECbit and RED Gateways host-centric: TCP Vegas Spring 200217CS 461DECbitAdd binary congestion bit to each packet headerRoutermonitors average queue length over last busy+idle cycleset congestion bit if average queue length 1attempts to b
16、alance throughout against delaySpring 200218CS 461End HostsDestination echoes bit back to sourceSource records how many packets resulted in set bitIf less than 50% of last windows worth had bit set increase CongestionWindow by 1 packetIf 50% or more of last windows worth had bit set decrease Congest
17、ionWindow by 0.875 timesSpring 200219CS 461Random Early Detection (RED)Notification is implicit just drop the packet (TCP will timeout)could make explicit by marking the packetEarly random droprather than wait for queue to become full, drop each arriving packet with some drop probability whenever th
18、e queue length exceeds some drop levelSpring 200220CS 461RED DetailsCompute average queue lengthAvgLen = (1 - Weight) * AvgLen + Weight * SampleLen0 Weight 1 (usually 0.002)SampleLen is queue length each time a packet arrivesSpring 200221CS 461RED Details (cont)Two queue length thresholdsif AvgLen =
19、 MinThreshold then enqueue the packetif MinThreshold AvgLen MaxThreshold then calculate probability P drop arriving packet with probability Pif ManThreshold = AvgLen then drop arriving packetSpring 200222CS 461RED Details (cont)Computing probability PTempP = MaxP * (AvgLen - MinThreshold)/ (MaxThres
20、hold - MinThreshold)P = TempP/(1 - count * TempP)Drop Probability CurveSpring 200223CS 461Tuning REDProbability of dropping a particular flows packet(s) is roughly proportional to the share of the bandwidth that flow is currently gettingMaxP is typically set to 0.02, meaning that when the average qu
21、eue size is halfway between the two thresholds, the gateway drops roughly one out of 50 packets.If traffic id bursty, then MinThreshold should be sufficiently large to allow link utilization to be maintained at an acceptably high level Difference between two thresholds should be larger than the typi
22、cal increase in the calculated average queue length in one RTT; setting MaxThreshold to twice MinThreshold is reasonable for traffic on todays InternetPenalty Box for OffendersSpring 200224CS 461TCP VegasIdea: source watches for some sign that routers queue is building up and congestion will happen
23、too; e.g.,RTT growssending rate flattens Spring 200225CS 461Algorithm Let BaseRTT be the minimum of all measured RTTs (commonly the RTT of the first packet)If not overflowing the connection, thenExpectRate = CongestionWindow/BaseRTTSource calculates sending rate (ActualRate) once per RTTSource compa
24、res ActualRate with ExpectRateDiff = ExpectedRate - ActualRateif Diff b bdecrease CongestionWindow linearlyelseleave CongestionWindow unchangedSpring 200226CS 461Algorithm (cont)Parameters -a a = 1 packet-b b = 3 packetsEven faster retransmitkeep fine-grained timestamps for each packet check for timeout on first duplicate ACKSpring 200227CS 461结束结束
