1 15-441 Computer Networking Lecture 18 – TCP Performance 11-01-07 Lecture 19: TCP Congestion Control 2 Outline • TCP congestion avoidance • TCP slow start • TCP modeling 11-01-07 Lecture 19: TCP Congestion Control 3 Additive Increase/Decrease T0 T1 Efficiency Line Fairness Line User 1’s Allocation x1 User 2’s Allocation x2 • Both X1 and X2 increase/ decrease by the same amount over time • Additive increase improves fairness and additive decrease reduces fairness 11-01-07 Lecture 19: TCP Congestion Control 4 Muliplicative Increase/Decrease • Both X1 and X2 increase by the same factor over time • Extension from origin – constant fairness T0 T1 Efficiency Line Fairness Line User 1’s Allocation x1 User 2’s Allocation x22 11-01-07 Lecture 19: TCP Congestion Control 5 What is the Right Choice? • Constraints limit us to AIMD • Improves or keeps fairness constant at each step • AIMD moves towards optimal point x0 x1 x2 Efficiency Line Fairness Line User 1’s Allocation x1 User 2’s Allocation x2 11-01-07 Lecture 19: TCP Congestion Control 6 TCP Congestion Control • Changes to TCP motivated by ARPANET congestion collapse • Basic principles • AIMD • Packet conservation • Reaching steady state quickly • ACK clocking 11-01-07 Lecture 19: TCP Congestion Control 7 Implementation 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) 11-01-07 Lecture 19: TCP Congestion Control 8 ACK Clocking • 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 behavior Pr Pb Ar Ab Receiver Sender As3 11-01-07 Lecture 19: TCP Congestion Control 9 AIMD • 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 rate Time Rate 11-01-07 Lecture 19: TCP Congestion Control 10 Congestion 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 AIMD 11-01-07 Lecture 19: TCP Congestion Control 11 Congestion Avoidance Sequence Plot Time Sequence No Packets Acks 11-01-07 Lecture 19: TCP Congestion Control 12 Congestion Avoidance Behavior Time Congestion Window Packet loss + retransmit Grabbing back Bandwidth Cut Congestion Window and Rate4 11-01-07 Lecture 19: TCP Congestion Control 13 Packet 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) 11-01-07 Lecture 19: TCP Congestion Control 17 Outline • TCP congestion avoidance • TCP slow start • TCP modeling 11-01-07 Lecture 19: TCP Congestion Control 18 Congestion Avoidance Behavior Time Congestion Window Packet loss + retransmit Grabbing back Bandwidth Cut Congestion Window and Rate 11-01-07 Lecture 19: TCP Congestion Control 19 Reaching 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)5 11-01-07 Lecture 19: TCP Congestion Control 20 Slow 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 loss 11-01-07 Lecture 19: TCP Congestion Control 21 Slow Start Example 1 One RTT One pkt time 0R 2 1R 3 4 2R 5 6 7 8 3R 9 10 11 12 13 14 15 1 2 3 4 5 6 7 11-01-07 Lecture 19: TCP Congestion Control 22 Slow Start Sequence Plot Time Sequence No . . . Packets Acks 11-01-07 Lecture 19: TCP Congestion Control 23 Return to Slow Start • If packet is lost we lose our self clocking as well • Need to implement slow-start and congestion avoidance together • When retransmission occurs set ssthresh to 0.5w • If cwnd < ssthresh, use slow start • Else use congestion avoidance6 11-01-07 Lecture 19: TCP Congestion Control 24 TCP Saw Tooth Behavior Time Congestion Window Initial Slowstart Fast Retransmit and Recovery Slowstart to pace packets Timeouts may still occur 11-01-07 Lecture 19: TCP Congestion Control 25 Outline • TCP congestion avoidance • TCP slow start • TCP modeling 11-01-07 Lecture 19: TCP Congestion Control 26 TCP Performance • Can TCP saturate a link? • Congestion control • Increase utilization until… link becomes congested • React by decreasing window by 50% • Window is proportional to rate * RTT • Doesn’t this mean that the network oscillates between 50 and 100% utilization? • Average utilization = 75%?? • No…this is *not* right! 11-01-07 Lecture 19: TCP Congestion Control 27 TCP Congestion Control Only W packets may be outstanding Rule for adjusting W• If an ACK is received: W ← W+1/W • If a packet is lost: W ← W/2 Source Dest t Window size7 11-01-07 Lecture 19: TCP Congestion Control 28 Single TCP Flow Router without buffers 11-01-07
View Full Document
Unlocking...