Transcript Document
Network Technologies essentials Week 8: TCP congestion control Note that videos are numbered 7-* Compilation made by Tim Moors, UNSW Australia Original slides by David Wetherall, University of Washington ISBN-10: 0133766624 © 2014 For the book A. Tanenbaum and D. Wetherall: Computer Networks, 5th ed, Prentice-Hall, 2011 Tim added green graffiti Fast Retransmit (2) ... Third duplicate ACK, so send 14 ACK jumps after loss is repaired Computer Networks Ack 10 Ack 11 Ack 12 Ack 13 Ack 13 Ack 13 Ack 13 Ack 13 ... Ack 20 ... ... Data 14 was lost earlier, but got 15 to 20 Data 20 ... Data 14 Retransmission fills in the hole at 14 ... 7-7.6 2 Effects of Congestion (2) • What happens to performance as we increase the load? Computer Networks 7-1.8 3 Efficiency vs. Fairness (3) • If we care about efficiency: – Maximize total traffic in network – AB: 1 unit, BC: 1, and AC, 0 – Total traffic rises to 2 units! A Computer Networks 1 B 1 C 7-2.6 4 Adapting over Time (2) Flow 1 slows when Flow 2 starts Flow 1 speeds up when Flow 2 stops Flow 3 limit is elsewhere Time Computer Networks 7-2.17 5 AIMD Game (3) • AI and MD move the allocation Host 1 1 Additive Increase Multiplicative Decrease 0 Computer Networks Congested Fair, y=x Optimal Allocation Efficient, x+y=1 1 Host 2 7-3.9 6 AIMD Game (5) • Always converge to good allocation! Host 1 1 Congested Fair A starting point Efficient 0 Computer Networks 1 Host 2 7-3.11 7 Benefit of ACK Clocking (2) • Segments are buffered and spread out on slow link Segments “spread out” Fast link Computer Networks Slow (bottleneck) link Fast link 7-5.5 8 Additive Increase Timeline Increment cwnd by 1 packet every cwnd ACKs (or 1 RTT) Computer Networks 7-6.9 9 Slow-Start Solution • Start by doubling cwnd every RTT Window (cwnd) – Exponential growth (1, 2, 4, 8, 16, …) – Start slow, quickly reach large values Computer Networks Fixed Slow-start AI Time 7-6.5 10 Slow-Start (Doubling) Timeline Increment cwnd by 1 packet for each ACK Computer Networks 7-6.8 11 Fast Recovery (2) Third duplicate ACK, so send 14 Set ssthresh, cwnd = cwnd/2 More ACKs advance window; may send segments before jump Computer Networks Ack 12 Ack 13 Ack 13 Ack 13 Ack 13 Ack 13 Ack 13 Ack 20 ... ... Exit Fast Recovery Data 14 was lost earlier, but got 15 to 20 Data 20 Retransmission fills Data 14 in the hole at 14 Data 21 Data 22 7-7.10 12 TCP Reno TCP sawtooth ACK clock running MD of ½ , no slow-start Computer Networks 7-7.12 13 ECN (Explicit Congestion Notification) • Router detects the onset of congestion via its queue – When congested, it marks affected packets (IP header) Computer Networks 7-8.5 14 END © 2013 D. Wetherall Slide material from: TANENBAUM, ANDREW S.; WETHERALL, DAVID J., COMPUTER NETWORKS, 5th Edition, © 2011. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey Computer Networks 15