EECS 122 Introduction to Computer Networks Congestion Control Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 What We Know We know How to process packets in a switch How to route packets in the network How to send packets reliably We don t know How fast to send As we know there are known knowns There are things we know we know We also know there are known unknowns That is to say we know there are some things we do not know But there are also unknown unknowns the ones we don t know we don t know The Zen of Donald Rumsfeld Katz Stoica F04 2 Implications Send too slow link is not fully utilized Wastes time Send too fast link is fully utilized but Queue builds up in router buffer delay Overflow buffers in routers Overflow buffers in receiving host ignore Why are buffer overflows a problem Packet drops mine and others Interesting history Van Jacobson rides to the rescue Katz Stoica F04 3 Abstract View A Sending Host B Buffer in Router Receiving Host Ignore internal structure of router and model it as having a single queue for a particular input output pair Katz Stoica F04 4 Three Congestion Control Problems Adjusting to bottleneck bandwidth Adjusting to variations in bandwidth Sharing bandwidth between flows Katz Stoica F04 5 Single Flow Fixed Bandwidth A 100 Mbps B Adjust rate to match bottleneck bandwidth Without any a priori knowledge Could be gigabit link could be a modem Katz Stoica F04 6 Single Flow Varying Bandwidth A BW t B Adjust rate to match instantaneous bandwidth Assuming you have rough idea of bandwidth Katz Stoica F04 7 Multiple Flows Two Issues Adjust total sending rate to match bandwidth Allocation of bandwidth between flows A1 A2 A3 B1 100 Mbps B2 B3 Katz Stoica F04 8 Reality Congestion control is a resource allocation problem involving many flows many links and complicated global dynamics Katz Stoica F04 9 Knee point after which Throughput increases very slow Delay increases fast Cliff point after which Throughput starts to decrease very fast to zero congestion collapse Delay approaches infinity Delay Throughput What s Really Happening View from a Single Flow knee packet loss cliff congestion collapse Load Note in an M M 1 queue Delay 1 1 utilization Load Katz Stoica F04 10 General Approaches Send without care Many packet drops Not as stupid as it seems Reservations Pre arrange bandwidth allocations Requires negotiation before sending packets Low utilization Pricing Don t drop packets for the high bidders Requires payment model Katz Stoica F04 11 General Approaches cont d 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 But for generic Internet usage dynamic adjustment is the most appropriate Due to pricing structure traffic characteristics and good citizenship Katz Stoica F04 12 TCP Congestion Control TCP connection has window Controls number of unacknowledged packets Sending rate Window RTT Vary window size to control sending rate Katz Stoica F04 13 Congestion Window cwnd Limits how much data can be in transit Implemented as of bytes Described as packets in this lecture MaxWindow min cwnd AdvertisedWindow EffectiveWindow MaxWindow LastByteSent LastByteAcked MaxWindow LastByteAcked LastByteSent EffectiveWindow sequence number increases Katz Stoica F04 14 Two Basic Components Detecting congestion Rate adjustment algorithm Depends on congestion or not Three subproblems within adjustment problem Finding fixed bandwidth Adjusting to bandwidth variations Sharing bandwidth Katz Stoica F04 15 Detecting Congestion Packet dropping is best sign of congestion 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 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 Katz Stoica F04 16 Rate Adjustment Basic structure Upon receipt of ACK of new data increase rate Upon detection of loss decrease rate But what increase decrease functions should we use Depends on what problem we are solving Katz Stoica F04 17 Problem 1 Single Flow Fixed BW Want to get a first order estimate of the available bandwidth Assume bandwidth is fixed Ignore presence of other flows Want to start slow but rapidly increase rate until packet drop occurs slow start Adjustment cwnd initially set to 1 cwnd upon receipt of ACK Katz Stoica F04 18 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 cwnd 3 cwnd 4 segment 4 segment 5 segment 6 segment 7 cwnd 8 Katz Stoica F04 19 Problems with Slow Start Slow start can result in many losses Roughly the size of cwnd BW RTT Example At some point cwnd is enough to fill pipe After another RTT cwnd is double its previous value All the excess packets are dropped Need a more gentle adjustment algorithm once have rough estimate of bandwidth Katz Stoica F04 20 Problem 2 Single Flow Varying BW Want to be able to track available bandwidth oscillating around its current value Possible variations in terms of RTTs Multiplicative increase or decrease cwnd a cwnd Additive increase or decrease cwnd cwnd b Four alternatives AIAD gentle increase gentle decrease AIMD gentle increase drastic decrease MIAD drastic increase gentle decrease too many losses MIMD drastic increase and decrease Katz Stoica F04 21 Problem 3 Multiple Flows 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 Katz Stoica F04 22 Buffer and Window Dynamics A Rate pkts RTT 60 50 40 30 Backlog in router pkts Congested if 20 20 10 487 460 433 406 379 352 325 298 271 244 217 190 163 136 109 82 55 0 28 C 50 pkts RTT No congestion x increases by one packet RTT every RTT Congestion decrease x by factor 2 1 B x Katz Stoica F04 23 AIMD Sharing Dynamics x y A D 60 Rates equalize fair share 50 40 30 20 10 487 460 433 406 379 352 325 298 271 244 217 190 163 136 109 82 55 0 28 E No congestion rate increases by one packet RTT every RTT Congestion decrease
View Full Document
Unlocking...