EECS 122: Introduction to Computer Networks Congestion ControlWhat We KnowImplicationsAbstract ViewThree Congestion Control ProblemsSingle Flow, Fixed BandwidthSingle Flow, Varying BandwidthMultiple FlowsRealityWhat’s Really Happening? View from a Single FlowGeneral ApproachesGeneral Approaches (cont’d)TCP Congestion ControlCongestion Window (cwnd)Two Basic ComponentsDetecting CongestionRate AdjustmentProblem #1: Single Flow, Fixed BWSlow-StartProblems with Slow-StartProblem #2: Single Flow, Varying BWProblem #3: Multiple FlowsBuffer and Window DynamicsAIMD Sharing DynamicsAIAD Sharing DynamicsEfficient Allocation: Challenges of Congestion ControlAIMDImplementing AIMDSlow Start/AIMD PseudocodeThe big picture (with timeouts)Congestion Detection RevisitedFast RetransmitsFast Recovery: After a Fast RetransmitFast Retransmit and Fast RecoveryTCP Congestion Control SummaryKatz, Stoica F04EECS 122: Introduction to Computer Networks Congestion ControlComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04What We KnowWe know:How to process packets in a switchHow to route packets in the networkHow to send packets reliablyWe 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.3Katz, Stoica F04ImplicationsSend too slow: link is not fully utilized-Wastes timeSend 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)4Katz, Stoica F04Abstract ViewIgnore internal structure of router and model it as having a single queue for a particular input-output pairSending Host Buffer in RouterReceiving HostA B5Katz, Stoica F04Three Congestion Control ProblemsAdjusting to bottleneck bandwidthAdjusting to variations in bandwidthSharing bandwidth between flows6Katz, Stoica F04Single Flow, Fixed BandwidthAdjust rate to match bottleneck bandwidth-Without any a priori knowledge-Could be gigabit link, could be a modemA B100 Mbps7Katz, Stoica F04Single Flow, Varying BandwidthAdjust rate to match instantaneous bandwidth-Assuming you have rough idea of bandwidthA BBW(t)8Katz, Stoica F04Multiple FlowsTwo Issues:Adjust total sending rate to match bandwidthAllocation of bandwidth between flowsA2 B2100 MbpsA1A3B3B19Katz, Stoica F04RealityCongestion control is a resource allocation problem involving many flows, many links, and complicated global dynamics10Katz, Stoica F04What’s Really Happening?View from a Single Flow Knee – point after which -Throughput increases very slow-Delay increases fastCliff – point after which-Throughput starts to decrease very fast to zero (congestion collapse)-Delay approaches infinityNote (in an M/M/1 queue)-Delay = 1/(1 – utilization)LoadLoadThroughputDelayknee cliffcongestioncollapsepacketloss11Katz, Stoica F04General ApproachesSend without care-Many packet drops-Not as stupid as it seemsReservations-Pre-arrange bandwidth allocations-Requires negotiation before sending packets-Low utilizationPricing-Don’t drop packets for the high-bidders-Requires payment model12Katz, Stoica F04General 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 implementAll three techniques have their place-But for generic Internet usage, dynamic adjustment is the most appropriate-Due to pricing structure, traffic characteristics, and good citizenship13Katz, Stoica F04TCP Congestion ControlTCP connection has window-Controls number of unacknowledged packetsSending rate: ~Window/RTTVary window size to control sending rate14Katz, Stoica F04Congestion Window (cwnd) Limits how much data can be in transitImplemented as # of bytesDescribed as # packets in this lectureEffectiveWindow = MaxWindow – (LastByteSent – LastByteAcked)MaxWindow = min(cwnd, AdvertisedWindow) LastByteAckedLastByteSentsequence number increasesMaxWindowEffectiveWindow15Katz, Stoica F04Two Basic ComponentsDetecting congestionRate adjustment algorithm-Depends on congestion or not-Three subproblems within adjustment problem•Finding fixed bandwidth•Adjusting to bandwidth variations•Sharing bandwidth16Katz, Stoica F04Detecting CongestionPacket dropping is best sign of congestion-Delay-based methods are hard and riskyHow 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 expectedTwo signs of packet drops-No ACK after certain time interval: time-out-Several duplicate ACKs (ignore for now)17Katz, Stoica F04Rate AdjustmentBasic structure:-Upon receipt of ACK (of new data): increase rate-Upon detection of loss: decrease rateBut what increase/decrease functions should we use?-Depends on what problem we are solving18Katz, Stoica F04Problem #1: Single Flow, Fixed BWWant to get a first-order estimate of the available bandwidth-Assume bandwidth is fixed-Ignore presence of other flowsWant to start slow, but rapidly increase rate until packet drop occurs (“slow-start”)Adjustment: -cwnd initially set to 1-cwnd++ upon receipt of ACK19Katz, Stoica F04Slow-Startcwnd 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 pointsegment 1cwnd = 1cwnd = 2segment 2segment 3cwnd = 4segment 4segment 5segment 6segment 7cwnd = 8cwnd = 320Katz, Stoica F04Problems with Slow-StartSlow-start can result in many losses-Roughly the size of cwnd ~ BW*RTTExample:-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 bandwidth21Katz, Stoica F04Problem #2: Single Flow, Varying BWWant to be able to track available bandwidth, oscillating around its current valuePossible variations:
View Full Document
Unlocking...