EE 122: Congestion Control and AvoidanceProblemSolutionsNon-decreasing Efficiency under LoadCongestion CollapseTransport Layer Congestion Collapse 1Transport Layer Congestion Collapse 2Congestion Collapse and EfficiencyTCP Congestion ControlTCP Congestion Control ComponentsCongestion Window (cwnd)Slow Start GoalSlow Start AlgorithmSlow Start ExampleSlow Start ProblemExiting Slow StartAdditive Increase/ Multiplicative DecreaseAI/MD AlgorithmSlow Start/AI/MD ExampleThe big pictureSlow Start/AI/MD PseudocodeAI/MD ProblemCongestion DetectionFast RetransmitFast Recovery: After a Fast RetransmitFast Recovery ProblemFast Retransmit and Fast RecoveryOther TCP-related techniquesTCP Congestion Control SummaryEE 122: Congestion Control and AvoidanceKevin LaiOctober 23, [email protected] 2ProblemAt what rate do you send data?flow control-make sure that the receiver can receive -sliding-window based flow control:•receiver reports window size to sender•higher window higher throughput•throughput = wnd/RTTcongestion control-make sure that the network can [email protected] 3SolutionsEveryone sends as fast as they can-excess gets dropped-very bad idea: leads to congestion collapseReserve bandwidth-low utilization-never have packet drops, queueing delaysCongestion control and avoidance-high utilization-occasionally have packet drops, queueing [email protected] 4Non-decreasing Efficiency under LoadEfficiency = useful_work/timecritical property of system design-network technology, protocol or applicationotherwise, system collapses exactly when most demand for its operationtrade lower overall efficiency for this?LoadEfficiencykneecliffok? [email protected] 5Congestion CollapseDecrease of network efficiency under load-efficiency = utilization of bandwidthWaste resources on useless or undelivered dataNetwork layer-loaddrops, 1 fragment droppedTransport layer-retransmit too many times-no congestion control / [email protected] 6Transport Layer Congestion Collapse 1network is congested (a router drops packets) the receiver didn’t get a packetsender waits, but not long enough -timeout too short, retransmit again-adds to congestion, increases likelihood that retransmission will be dropped, or delayedrinse, repeatassume that everyone is doing the samenetwork will become more and more congested-with duplicate packets rather than new packetsSolution: fix timeout (previous lecture)[email protected] 7Transport LayerCongestion Collapse 2Waste resources on undelivered dataA flow sends data at a high rate despite lossIts packets consume bandwidth at earlier links, only to be dropped at a later link90% lossbw wastedignores [email protected] 8Congestion Collapse and Efficiencyknee – point after which -throughput increases slowly-delay increases quicklycliff – point after which-throughput decreases quickly to zero (congestion collapse)-delay goes to infinityCongestion avoidance-stay at kneeCongestion control-stay left of (but usually close to) cliffLoadLoadThroughputDelayknee cliffover utilizationunder utilizationsaturationcongestion [email protected] 9TCP Congestion ControlOperate to the left of the cliff-less efficient than operating at the knee, but requires less support from networkSolution: Carefully manage number of packets in network-starting up: increase number of packets allowed-equilibrium: maintain constant number of packets•must probe periodically for more available bandwidth-congestion: decrease number of packets [email protected] 10TCP Congestion Control ComponentsMeasure available bandwidth-slow start•fast, hard on network-additive increase/multiplicative decrease•slow, gentle on networkDetecting congestion-timeout based on RTT (last lecture)•robust, causes low throughput-duplicate acks (Fast Retransmit)•can be fooled, maintains high throughputRecovering from loss-Fast recovery: avoid slow start when few packets [email protected] 11Congestion Window (c wnd) Limits how much data can be in transitIntegrate with flow controlimplemented as # of bytes, describe as # packetsEffectiveWindow = MaxWindow – (LastByteSent – LastByteAcked)MaxWindow = min(cwnd, AdvertisedWindow) LastByteAcked LastByteSentsequence number increases12Slow Start GoalGoal: discover congestion quickly-used to get rough initial estimate of cwndSlow Start used when-a new connection, or-after timeout, or-after connection has been idle for a [email protected] 13Slow Start AlgorithmAlgorithm:-Set cwnd =1 -Each time a segment is acknowledged increment cwnd by one (cwnd++)Slow Start increases cwnd exponentially-called “Slow” because it gradually increases sending rate according to the RTT-predecessor just increased to advWin [email protected] 14Slow Start Examplecwnd doubles every RTTACK for segment 1segment 1cwnd = 1cwnd = 2segment 2segment 3ACK for segments 2 + 3cwnd = 4segment 4segment 5segment 6segment 7ACK for segments 4+5+6+7cwnd = [email protected] 15Slow Start ProblemSlow Start can cause serious loss-loss = bottleneck bandwidth * RTTExample:-bottleneck link is 8 Mb/s-RTT is 100ms-at some point cwnd = 800,000 bits•exactly right for bottleneck-100 ms late, cwnd = 1,600,000 bits•twice the bottleneck, 800,000 bits lost (oops)Need to switch to something else when throughput is close to bottleneck [email protected] 16Exiting Slow Startcwnd>=advWin-limited by receiver’s advertised window if cwnd allowed to increase, would grow unboundedcongestion-reached available bandwidth switch to AI/MDcwnd>=ssthresh-ssthresh: slow start threshold-ssthresh is a hint about when to slow down, calculated from previous congestion on same connection-“we experienced congestion beyond this point before, slow down”17Additive Increase/Multiplicative DecreaseUsed Slow Start to get rough estimate of cwndGoal: maintain operating point at the left of the cliff-Additive increase: starting from the rough estimate, slowly increase cwnd to probe for additional available bandwidth-Multiplicative decrease: cut congestion window size aggressively if congestion occursWhy not AI/AD, MI/MD, MI/AD:-mathematical models show A/M is only choice that converges to fairness and [email protected] 18AI/MD Algorithmssthresh = a
View Full Document
Unlocking...