Goals of Today s Lecture Principles of congestion control Learning that congestion is occurring Adapting to alleviate the congestion EE 122 TCP Congestion Control Ion Stoica TAs Junda Liu DK Moon David Zats TCP congestion control Additive increase multiplicative decrease AIMD How to begin transmitting Slow Start http inst eecs berkeley edu ee122 Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 2 It s Not Just The Sender Receiver What We Know We know How to process packets in a switch How to route packets in the network How to send packets reliably Flow control keeps one fast sender from overwhelming a slow receiver Congestion control keeps a set of senders from overloading the network Three congestion control problems We don t know How fast to send Adjusting to bottleneck bandwidth 3 Without any a priori knowledge Could be a Gbps link could be a modem Adjusting to variations in bandwidth Sharing bandwidth between flows 4 1 Congestion is Unavoidable Congestion Collapse Two packets arrive at the same time The node can only transmit one and either buffers or drops the other If many packets arrive in a short period of time The node cannot keep up with the arriving traffic and the buffer may eventually overflow Definition Increase in network load results in a decrease of useful work done Due to Undelivered packets Packets consume resources and are dropped later in network Spurious retransmissions of packets still in flight Unnecessary retransmissions lead to more load Pouring gasoline on a fire Mid 1980s Internet grinds to a halt Until Jacobson Karels Berkeley devise TCP congestion control 5 Knee point after which Throughput increases very slowly Delay increases quickly Throughput View from a Single Flow knee 6 General Approaches packet loss cliff congestion collapse Send without care 1 Reservations Cliff point after which Throughput starts to decrease very fast to zero congestion collapse Delay approaches infinity Delay Load Many packet drops Pre arrange bandwidth allocations Requires negotiation before sending packets Low utilization 2 Pricing Load 7 Don t drop packets for the high bidders Requires payment model 8 2 General Approaches cont d TCP Congestion Control 3 Dynamic Adjustment Probe network to test level of congestion Speed up when no congestion Slow down when congestion Suboptimal messy dynamics simple to implement All three techniques have their place TCP connection has window Controls number of unacknowledged packets But for generic Internet usage dynamic adjustment is the most appropriate Due to pricing structure traffic characteristics and good citizenship Sending rate Window RTT Vary window size to control sending rate 9 Sizing the Windows EffectiveWindow cwnd Congestion Windows How many bytes can be sent without overflowing routers Computed by congestion control algorithm AdvertisedWindow 10 Limits how much data can be in transit Implemented as of bytes Described as packets segments in this lecture MaxWindow min cwnd AdvertisedWindow How many bytes can be sent without overflowing the sender Determined by the receiver EffectiveWindow MaxWindow LastByteSent LastByteAcked MaxWindow LastByteAcked 11 LastByteSent EffectiveWindow sequence number increases 12 3 Two Basic Components Detecting Congestion Detecting congestion Packet dropping is best sign of congestion Rate adjustment algorithm Depends on congestion or not Three subproblems within adjustment problem Delay based methods are hard and risky How do you detect packet drops ACKs TCP uses ACKs to signal receipt of data ACK denotes last contiguous byte received Finding fixed bandwidth Adjusting to bandwidth variations Sharing bandwidth Actually ACKs indicate next segment expected Two signs of packet drops No ACK after certain time interval time out Several duplicate ACKs ignore for now 13 Problem 1 Single Flow Fixed BW Rate Adjustment Basic structure Upon receipt of ACK of new data increase rate Upon detection of loss decrease rate Want to get a first order estimate of the available bandwidth But what increase decrease functions should we use 14 Depends on what problem we are solving Want to start slow but rapidly increase rate until packet drop occurs slow start Adjustment 15 Assume bandwidth is fixed Ignore presence of other flows cwnd initially set to 1 cwnd upon receipt of ACK 16 4 Slow Start cwnd increases exponentially cwnd doubles every time a full cwnd of packets has been sent Each ACK releases two packets Slow start is called slow because of starting point cwnd 1 segment 1 cwnd 2 segment 2 segment 3 5 Minute Break cwnd 3 cwnd 4 Questions Before We Proceed segment 4 segment 5 segment 6 segment 7 cwnd 8 17 Problem 2 Single Flow Varying BW Problems with Slow Start Slow start can result in many losses 18 Roughly the size of cwnd BW RTT Possible variations in terms of RTTs Example Want to be able to track available bandwidth oscillating around its current value At some point cwnd is enough to fill pipe After another RTT cwnd is double its previous value All the excess packets are dropped Four alternatives Need a more gentle adjustment algorithm once have rough estimate of bandwidth 19 Multiplicative increase or decrease cwnd a cwnd Additive increase or decrease cwnd cwnd b AIAD gentle increase gentle decrease AIMD gentle increase drastic decrease MIAD drastic increase gentle decrease too many losses MIMD drastic increase and decrease 20 5 Problem 3 Multiple Flows Buffer and Window Dynamics A Want steady state to be fair Many notions of fairness but here all we require is that two identical flows end up with the same bandwidth This eliminates MIMD and AIAD AIMD is the only remaining solution x B C 50 pkts RTT No congestion x increases by one packet RTT every RTT Congestion decrease x by factor 2 21 AIAD Sharing Dynamics AIMD Sharing Dynamics A D x1 x2 22 A B D E No congestion rate increases by one packet RTT every RTT Congestion decrease rate by factor 2 x1 x2 B E No congestion x increases by one packet RTT every RTT Congestion decrease x by 1 Rates equalize fair share 23 24 6 Efficient Allocation Challenges of Congestion Control Example 1 Too slow Overshoot knee overload high delay loss May all under over shoot large oscillations Optimal overload underload Efficiency line 0 5 0 5 Inefficient x1 x2 0 7 User 1 x1 xi Xgoal 0 2 0 5 Efficient x1 x2 1 Not fair Efficiency 1 distance from efficiency line User 1 x1 bI x1h aD bI x2h aD fairness line x1h x2h x1h aD x2h aD efficiency line
View Full Document
Unlocking...