CS 268: Computer NetworkingThis Lecture: Congestion ControlIntroduction to TCPKey Things You Should Know AlreadyEvolution of TCPTCP Through the 1990sOverviewCongestionCauses & Costs of CongestionSlide 10Congestion CollapseOther Congestion Collapse CausesWhere to Prevent Collapse?Congestion Control and AvoidanceSlide 15ObjectivesBasic Control ModelLinear ControlPhase plotsSlide 20Additive Increase/DecreaseMultiplicative Increase/DecreaseConvergence to EfficiencyDistributed Convergence to EfficiencyConvergence to FairnessConvergence to Efficiency & FairnessIncreaseConstraintsWhat is the Right Choice?Slide 30TCP Congestion ControlTCP Congestion Control - SolutionsSlide 33AIMDImplementation IssueCongestion AvoidanceCongestion Avoidance Sequence PlotCongestion Avoidance BehaviorPacket ConservationTCP Packet PacingReaching Steady StateSlow Start Packet PacingSlow Start ExampleSlow Start Sequence PlotReturn to Slow StartTCP Saw Tooth BehaviorHow to Change WindowFast RecoveryFast RecoverySlide 50TCP ModelingOverall TCP BehaviorSimple TCP ModelSimple Loss ModelTCP FriendlinessTCP PerformanceSlide 57Single TCP Flow Router without buffersSummary Unbuffered LinkSlide 60Slide 61Single TCP Flow Router with large enough buffers for full link utilizationSummary Buffered LinkExampleRule-of-thumbIf flows are synchronizedIf flows are not synchronizedCentral Limit TheoremRequired buffer sizeImportant LessonsNext LectureTCP Vegas Slow StartPacket PairSlide 75Packet Pair in PracticeTCP Vegas Congestion AvoidanceSlide 79Slide 80Changing WorkloadsBinomial Congestion ControlSlide 83TCP Friendly Rate Control (TFRC)RTO/RTT EstimationLoss EstimationSlide 87Slide 89NewReno ChangesRate Halving RecoveryDelayed Ack ImpactCS 268: Computer NetworkingL-4 TCP2This Lecture: Congestion Control •Congestion Control•Assigned Reading•[Chiu & Jain] Analysis of Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks•[Jacobson and Karels] Congestion Avoidance and Control3Introduction to TCP•Communication abstraction:•Reliable•Ordered•Point-to-point•Byte-stream•Full duplex•Flow and congestion controlled•Protocol implemented entirely at the ends•Fate sharing•Sliding window with cumulative acks•Ack field contains last in-order packet received•Duplicate acks sent when out-of-order packet receivedKey Things You Should Know Already•Port numbers•TCP/UDP checksum•Sliding window flow control•Sequence numbers•TCP connection setup•TCP reliability•Timeout•Data-driven45Evolution of TCP1975 1980198519901982TCP & IPRFC 793 & 7911974TCP described byVint Cerf and Bob KahnIn IEEE Trans Comm1983BSD Unix 4.2supports TCP/IP1984Nagel’s algorithmto reduce overheadof small packets;predicts congestion collapse1987Karn’s algorithmto better estimate round-trip time1986Congestion collapseobserved1988Van Jacobson’s algorithmscongestion avoidance and congestion control(most implemented in 4.3BSD Tahoe)19904.3BSD Renofast retransmitdelayed ACK’s1975Three-way handshakeRaymond TomlinsonIn SIGCOMM 756TCP Through the 1990s1993199419961994ECN(Floyd)Explicit CongestionNotification1993TCP Vegas (Brakmo et al)real congestion avoidance1994T/TCP(Braden)TransactionTCP1996SACK TCP(Floyd et al)Selective Acknowledgement1996HoeImproving TCP startup1996FACK TCP(Mathis et al)extension to SACK7Overview•Congestion sources and collapse•Congestion control basics•TCP congestion control•TCP modeling8Congestion•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 Mbps9Causes & Costs of Congestion•Four senders – multihop paths•Timeout/retransmitQ: What happens as rate increases?10Causes & Costs of Congestion•When packet dropped, any “upstream” transmission capacity used for that packet was wasted!11Congestion 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 traffic12Other 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 used13Where 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 sources14Congestion 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 networks15Overview•Congestion sources and collapse•Congestion control basics•TCP congestion control•TCP modeling16Objectives•Simple router behavior •Distributedness•Efficiency: Xknee = xi(t)•Fairness: (xi)2/n(xi2)•Power: (throughput/delay)•Convergence: control system must be stable17Basic 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?18Linear 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
View Full Document
Unlocking...