115-441 Computer NetworkingLecture 18 – More TCP & Congestion ControlLecture 18: 04-23-2004 2Overview• TCP congestion control• TCP modern loss recovery• TCP modelingLecture 18: 04-23-2004 3TCP Congestion Control• Changes to TCP motivated by ARPANET congestion collapse• Basic principles• AIMD• Packet conservation• Reaching steady state quickly• ACK clockingLecture 18: 04-23-2004 4AIMD• Distributed, fair and efficient• 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 rateTimeRate2Lecture 18: 04-23-2004 5Implementation Issue• Operating system timers are very coarse – how to pace packets out smoothly?• Implemented using a congestion window that limits how much data can be in the network.• TCP also keeps track of how much data is in transit• Data can only be sent when the amount of outstanding data is less than the congestion window.• The amount of outstanding data is increased on a “send” and decreased on “ack”• (last sent – last acked) < congestion window• Window limited by both congestion and buffering• Sender’s maximum window = Min (advertised window, cwnd)Lecture 18: 04-23-2004 6Congestion 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 packet)/cwnd• What is 1 packet? Æ 1 MSS worth of bytes• After cwnd packets have passed by Æ approximately increase of 1 MSS• Implements AIMDLecture 18: 04-23-2004 7Congestion Avoidance Sequence PlotTimeSequence NoPacketsAcksLecture 18: 04-23-2004 8Congestion Avoidance BehaviorTimeCongestionWindowPacket loss+ TimeoutGrabbingback BandwidthCutCongestionWindowand Rate3Lecture 18: 04-23-2004 9Packet Conservation• At equilibrium, inject packet into network only when one is removed• Sliding window and not rate controlled• But still need to avoid sending burst of packets Æwould overflow links• Need to carefully pace out packets• Helps provide stability • Need to eliminate spurious retransmissions• Accurate RTO estimation• Better loss recovery techniques (e.g. fast retransmit)Lecture 18: 04-23-2004 10TCP Packet Pacing• Congestion window helps to “pace” the transmission of data packets• In steady state, a packet is sent when an ack is received• Data transmission remains smooth, once it is smooth• Self-clocking behaviorPrPbArAbReceiverSenderAsLecture 18: 04-23-2004 11Reaching Steady State• Doing AIMD is fine in steady state but slow…• How does TCP know what is a good initial rate to start with?• Should work both for a CDPD (10s of Kbps or less) and for supercomputer links (10 Gbps and growing)• Quick initial phase to help get up to speed (slow start)Lecture 18: 04-23-2004 12Slow 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 loss4Lecture 18: 04-23-2004 13Slow Start Example1One RTTOne pkt time0R21R342R56783R910111213141512 34 5 6 7Lecture 18: 04-23-2004 14Slow Start Sequence PlotTimeSequence No...PacketsAcksLecture 18: 04-23-2004 15Return 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 18: 04-23-2004 16TCP Saw Tooth BehaviorTimeCongestionWindowInitialSlowstartFast Retransmitand RecoverySlowstartto pacepacketsTimeoutsmay stilloccur5Lecture 18: 04-23-2004 17Overview• TCP congestion control• TCP modern loss recovery• TCP modelingLecture 18: 04-23-2004 18TCP 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 18: 04-23-2004 19Fast 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 18: 04-23-2004 20Fast RetransmitTimeSequence NoDuplicate AcksRetransmissionXPacketsAcks6Lecture 18: 04-23-2004 21Multiple LossesTimeSequence NoDuplicate AcksRetransmissionXXXXNow what?PacketsAcksLecture 18: 04-23-2004 22TimeSequence NoXXXXTahoePacketsAcksLecture 18: 04-23-2004 23TCP 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 18: 04-23-2004 24RenoTimeSequence NoXXXXNow what? - timeoutPacketsAcks7Lecture 18: 04-23-2004 25NewReno• 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 18: 04-23-2004 26NewRenoTimeSequence NoXXXXNow what? – partial ackrecoveryPacketsAcksLecture 18: 04-23-2004 27SACK• Basic problem is that cumulative acks provide little information• Ack for just the packet received• What if acks are lost? Æ carry cumulative also• This technique is not used• Bitmask of packets received • Selective acknowledgement (SACK)• When to retransmit?• Still need to deal with reordering Æ wait for out of order by 3pktsLecture 18: 04-23-2004 28SACK TimeSequence NoXXXXNow what? – sendretransmissions as soonas detectedPacketsAcks8Lecture 18: 04-23-2004 29Performance 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?• How to deal with reordering?Lecture 18: 04-23-2004 30How to Change Window• When a loss occurs have W packets outstanding• New cwnd = 0.5 * cwnd• How to get to
View Full Document
Unlocking...