15-744: Computer NetworkingCongestion ControlOverviewCongestionCongestion CollapseOther Congestion Collapse CausesWhere to Prevent Collapse?Congestion Control and AvoidanceCongestion Control vs. AvoidanceSlide 10ObjectivesBasic Control ModelLinear ControlPhase plotsSlide 15Additive Increase/DecreaseMultiplicative Increase/DecreaseConvergence to EfficiencyDistributed Convergence to EfficiencyConvergence to FairnessConvergence to Efficiency & FairnessIncreaseWhat is the Right Choice?Slide 25TCP Congestion ControlTCP Congestion Control - SolutionsTCP Congestion Control BasicsSelf-clockingSlow StartSlow Start ExampleSlow Start Sequence PlotCongestion WindowCongestion AvoidanceReturn to Slow StartCongestion Avoidance Sequence PlotOverall TCP BehaviorSlide 38How to Change WindowFast RecoveryFast RecoveryNewReno ChangesRate Halving RecoveryNext Lecture: Transport Alternatives15-744: Computer NetworkingL-8 Congestion ControlL -8; 10-03-02© Srinivasan Seshan, 2002 2Congestion Control•Congestion control basics•TCP congestion control•Assigned reading•[JK88] Congestion Avoidance and Control•[CJ89] Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer NetworksL -8; 10-03-02© Srinivasan Seshan, 2002 3Overview•Congestion sources and collapse•Congestion control basics•TCP congestion control•TCP interactionsL -8; 10-03-02© Srinivasan Seshan, 2002 4Congestion•Different sources compete for resources inside network•Why is it a problem?•Sources are unaware of current state of resource•Sources are unaware of each other•In many situations will result in < 1.5 Mbps of throughput (congestion collapse)10 Mbps100 Mbps1.5 MbpsL -8; 10-03-02© Srinivasan Seshan, 2002 5Congestion Collapse•Definition: Increase in network load results in decrease of useful work done•Many possible causes•Spurious retransmissions of packets still in flight•Classical congestion collapse•How can this happen with packet conservation•Solution: better timers and TCP congestion control•Undelivered packets•Packets consume resources and are dropped elsewhere in network•Solution: congestion control for ALL trafficL -8; 10-03-02© Srinivasan Seshan, 2002 6Other Congestion Collapse Causes•Fragments•Mismatch of transmission and retransmission units•Solutions•Make network drop all fragments of a packet (early packet discard in ATM)•Do path MTU discovery•Control traffic•Large percentage of traffic is for control•Headers, routing messages, DNS, etc.•Stale or unwanted packets•Packets that are delayed on long queues•“Push” data that is never usedL -8; 10-03-02© Srinivasan Seshan, 2002 7Where to Prevent Collapse?•Can end hosts prevent problem?•Yes, but must trust end hosts to do right thing•E.g., sending host must adjust amount of data it puts in the network based on detected congestion•Can routers prevent collapse?•No, not all forms of collapse•Doesn’t mean they can’t help •Sending accurate congestion signals•Isolating well-behaved from ill-behaved sourcesL -8; 10-03-02© Srinivasan Seshan, 2002 8Congestion Control and Avoidance•A mechanism which:•Uses network resources efficiently•Preserves fair network resource allocation•Prevents or avoids collapse•Congestion collapse is not just a theory•Has been frequently observed in many networksL -8; 10-03-02© Srinivasan Seshan, 2002 9Congestion Control vs. Avoidance•Avoidance keeps the system performing at the knee•Control kicks in once the system has reached a congested stateLoadThroughputLoadDelayL -8; 10-03-02© Srinivasan Seshan, 2002 10Overview•Congestion sources and collapse•Congestion control basics•TCP congestion control•TCP interactionsL -8; 10-03-02© Srinivasan Seshan, 2002 11Objectives•Simple router behavior •Distributedness•Efficiency: Xknee = xi(t)•Fairness: (xi)2/n( xi2)•Power: (throughput/delay)•Convergence: control system must be stableL -8; 10-03-02© Srinivasan Seshan, 2002 12Basic Control Model•Let’s assume window-based control•Reduce window when congestion is perceived•How is congestion signaled?•Either mark or drop packets•When is a router congested?•Drop tail queues – when queue is full•Average queue length – at some threshold•Increase window otherwise•Probe for available bandwidth – how?L -8; 10-03-02© Srinivasan Seshan, 2002 13Linear Control•Many different possibilities for reaction to congestion and probing•Examine simple linear controls•Window(t + 1) = a + b Window(t)•Different ai/bi for increase and ad/bd for decrease•Supports various reaction to signals•Increase/decrease additively•Increased/decrease multiplicatively•Which of the four combinations is optimal?L -8; 10-03-02© Srinivasan Seshan, 2002 14Phase plots•Simple way to visualize behavior of competing connections over timeEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2L -8; 10-03-02© Srinivasan Seshan, 2002 15Phase plots•What are desirable properties?•What if flows are not equal?Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2Optimal pointOverloadUnderutilizationL -8; 10-03-02© Srinivasan Seshan, 2002 16Additive Increase/DecreaseT0T1Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2•Both X1 and X2 increase/decrease by the same amount over time•Additive increase improves fairness and additive decrease reduces fairnessL -8; 10-03-02© Srinivasan Seshan, 2002 17Multiplicative Increase/Decrease•Both X1 and X2 increase by the same factor over time•Extension from origin – constant fairnessT0T1Efficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2L -8; 10-03-02© Srinivasan Seshan, 2002 18Convergence to EfficiencyxHEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2L -8; 10-03-02© Srinivasan Seshan, 2002 19Distributed Convergence to EfficiencyxHEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2a=0b=1L -8; 10-03-02© Srinivasan Seshan, 2002 20Convergence to FairnessxHEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2xH’L -8; 10-03-02© Srinivasan Seshan, 2002 21Convergence to Efficiency & FairnessxHEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2xH’L -8; 10-03-02© Srinivasan Seshan, 2002 22IncreaseEfficiency LineFairness LineUser 1’s Allocation x1User 2’s Allocation x2xLL -8;
View Full Document
Unlocking...