15-441 Computer NetworkingOverviewTCP Congestion ControlCongestion AvoidanceCongestion Avoidance Sequence PlotCongestion Avoidance BehaviorSlow Start Packet PacingSlow Start ExampleSlow Start Sequence PlotReturn to Slow StartTCP Saw Tooth BehaviorSlide 12TCP FlavorsFast RetransmitSlide 15Multiple LossesTahoeTCP Reno (1990)RenoNewRenoNewRenoSACKSACKPerformance IssuesSlide 25How to Change WindowFast RecoveryFast RecoveryNewReno ChangesRate Halving RecoveryDelayed Ack ImpactSlide 32TCP ExtensionsProtection From WraparoundWindow Size vs ThroughputWindow Scaling: Example Use of OptionsLarge WindowsMaximum Segment Size (MSS)Slide 39TCP ModelingOverall TCP BehaviorSimple TCP ModelSimple Loss ModelTCP FriendlinessSlide 45Changing WorkloadsProblems with Short Concurrent FlowsSharing InformationShort TransfersEnhanced TCP Loss RecoverySlide 51Slide 52Well Behaved vs. Wild WestTCP Fairness IssuesSlide 55Low Bandwidth LinksTCP HeaderHeader CompressionNon-reliable Protocols15-441 Computer NetworkingTCP (cont.)Lecture 16: 10-30-01 2Overview•TCP congestion control•TCP modern loss recovery•TCP interactions•TCP options•TCP modeling•Workload changes•Header compressionLecture 16: 10-30-01 3TCP Congestion Control•Packet loss is seen as sign of congestion and results in a multiplicative rate decrease •Factor of 2•TCP periodically probes for available bandwidth by increasing its rateTimeRateLecture 16: 10-30-01 4Congestion Avoidance•If loss occurs when cwnd = W•Network can handle 0.5W ~ W segments•Set cwnd to 0.5W (multiplicative decrease)•Upon receiving ACK•Increase cwnd by 1/cwnd •Implements AIMDLecture 16: 10-30-01 5Congestion Avoidance Sequence PlotTimeSequence NoLecture 16: 10-30-01 6Congestion Avoidance BehaviorTimeCongestionWindowPacket loss+ TimeoutGrabbingback BandwidthCutCongestionWindowand RateLecture 16: 10-30-01 7Slow Start Packet Pacing•How do we get this clocking behavior to start?•Initialize cwnd = 1•Upon receipt of every ack, cwnd = cwnd + 1•Implications•Window actually increases to W in RTT * log2(W)•Can overshoot window and cause packet lossLecture 16: 10-30-01 8Slow Start Example1One RTTOne pkt time0R21R342R56783R910111213141512 34 5 6 7Lecture 16: 10-30-01 9Slow Start Sequence PlotTimeSequence No...Lecture 16: 10-30-01 10Return to Slow Start•If packet is lost we lose our self clocking as well•Need to implement slow-start and congestion avoidance together•When timeout occurs set ssthresh to 0.5w•If cwnd < ssthresh, use slow start•Else use congestion avoidanceLecture 16: 10-30-01 11TCP Saw Tooth BehaviorTimeCongestionWindowInitialSlowstartFast Retransmitand RecoverySlowstartto pacepacketsTimeoutsmay stilloccurLecture 16: 10-30-01 12Overview•TCP congestion control•TCP modern loss recovery•TCP interactions•TCP options•TCP modeling•Workload changes•Header compressionLecture 16: 10-30-01 13TCP Flavors•Tahoe, Reno, Vegas•TCP Tahoe (distributed with 4.3BSD Unix)•Original implementation of Van Jacobson’s mechanisms (VJ paper)•Includes:•Slow start •Congestion avoidance•Fast retransmitLecture 16: 10-30-01 14Fast Retransmit•What are duplicate acks (dupacks)?•Repeated acks for the same sequence•When can duplicate acks occur?•Loss•Packet re-ordering•Window update – advertisement of new flow control window•Assume re-ordering is infrequent and not of large magnitude•Use receipt of 3 or more duplicate acks as indication of loss•Don’t wait for timeout to retransmit packetLecture 16: 10-30-01 15Fast RetransmitTimeSequence NoDuplicate AcksRetransmissionXLecture 16: 10-30-01 16Multiple LossesTimeSequence NoDuplicate AcksRetransmissionXXXXNow what?Lecture 16: 10-30-01 17TimeSequence NoXXXXTahoeLecture 16: 10-30-01 18TCP Reno (1990)•All mechanisms in Tahoe•Addition of fast-recovery •Opening up congestion window after fast retransmit•Delayed acks•Header prediction •Implementation designed to improve performance•Has common case code inlined•With multiple losses, Reno typically timeouts because it does not see duplicate acknowledgementsLecture 16: 10-30-01 19RenoTimeSequence NoXXXXNow what? - timeoutLecture 16: 10-30-01 20NewReno•The ack that arrives after retransmission (partial ack) could indicate that a second loss occurred•When does NewReno timeout?•When there are fewer than three dupacks for first loss•When partial ack is lost•How fast does it recover losses?•One per RTTLecture 16: 10-30-01 21NewReno TimeSequence NoXXXXNow what? – partial ackrecoveryLecture 16: 10-30-01 22SACK•Basic problem is that cumulative acks only provide little information•Ack for just the packet received•What if acks are lost? carry cumulative also•Not used•Bitmask of packets received •Selective acknowledgement (SACK)•How to deal with reorderingLecture 16: 10-30-01 23SACK TimeSequence NoXXXXNow what? – sendretransmissions as soonas detectedLecture 16: 10-30-01 24Performance Issues•Timeout >> fast rexmit•Need 3 dupacks/sacks•Not great for small transfers•Don’t have 3 packets outstanding•What are real loss patterns like?•Right edge recovery•Allow packets to be sent on arrival of first and second duplicate ack•Helps recovery for small windows•How to deal with reordering?Lecture 16: 10-30-01 25Overview•TCP congestion control•TCP modern loss recovery•TCP interactions•TCP options•TCP modeling•Workload changes•Header compressionLecture 16: 10-30-01 26How to Change Window•When a loss occurs have W packets outstanding•New cwnd = 0.5 * cwnd•How to get to new state?Lecture 16: 10-30-01 27Fast Recovery•Each duplicate ack notifies sender that single packet has cleared network•When < cwnd packets are outstanding•Allow new packets out with each new duplicate acknowledgement•Behavior•Sender is idle for some time – waiting for ½ cwnd worth of dupacks•Transmits at original rate after wait•Ack clocking rate is same as before lossLecture 16: 10-30-01 28Fast Recovery TimeSequence NoSent for each dupack afterW/2 dupacks arriveXLecture 16: 10-30-01 29NewReno Changes•Send a new packet out for each pair of dupacks•Adapt more gradually to new window•Will not halve congestion window again until recovery is completed •Identifies congestion events vs. congestion signalsLecture 16: 10-30-01 30Rate Halving RecoveryTimeSequence NoSent after everyother dupackXLecture 16: 10-30-01 31Delayed Ack Impact•TCP congestion control triggered by
View Full Document
Unlocking...