EE 122 Congestion Control and Avoidance Kevin Lai October 23 2002 Problem At what rate do you send data flow control make sure that the receiver can receive sliding window based flow control receiver reports window size to sender higher window higher throughput throughput wnd RTT congestion control make sure that the network can deliver laik cs berkeley edu 2 Solutions Everyone sends as fast as they can excess gets dropped very bad idea leads to congestion collapse Reserve bandwidth low utilization never have packet drops queueing delays Congestion control and avoidance high utilization occasionally have packet drops queueing delays laik cs berkeley edu 3 Non decreasing Efficiency under Load Efficiency useful work time critical property of system design ok network technology protocol or application good knee otherwise system collapses exactly when most demand for its operation trade lower overall efficiency for this Efficiency laik cs berkeley edu cliff Load 4 Congestion Collapse Decrease of network efficiency under load efficiency utilization of bandwidth Waste resources on useless or undelivered data Network layer load drops 1 fragment dropped Transport layer retransmit too many times no congestion control avoidance laik cs berkeley edu 5 Transport Layer Congestion Collapse 1 network is congested a router drops packets the receiver didn t get a packet sender waits but not long enough timeout too short retransmit again adds to congestion increases likelihood that retransmission will be dropped or delayed rinse repeat assume that everyone is doing the same network will become more and more congested with duplicate packets rather than new packets Solution fix timeout previous lecture laik cs berkeley edu 6 Transport Layer Congestion Collapse 2 Penalized 90 loss ignores loss bw wasted Waste resources on undelivered data A flow sends data at a high rate despite loss Its packets consume bandwidth at earlier links only to be dropped at a later link laik cs berkeley edu 7 knee point after which throughput increases slowly delay increases quickly cliff point after which throughput decreases quickly to zero congestion collapse delay goes to infinity Congestion avoidance stay at knee knee cliff congestion collapse under utilization Delay Throughput Congestion Collapse and Efficiency saturation over utilization Load Congestion control stay left of but usually close to cliff laik cs berkeley edu Load 8 TCP Congestion Control Operate to the left of the cliff less efficient than operating at the knee but requires less support from network Solution Carefully manage number of packets in network starting up increase number of packets allowed equilibrium maintain constant number of packets must probe periodically for more available bandwidth congestion decrease number of packets allowed laik cs berkeley edu 9 TCP Congestion Control Components Measure available bandwidth slow start fast hard on network additive increase multiplicative decrease slow gentle on network Detecting congestion timeout based on RTT last lecture robust causes low throughput duplicate acks Fast Retransmit can be fooled maintains high throughput Recovering from loss Fast recovery avoid slow start when few packets lost laik cs berkeley edu 10 Congestion Window cwnd Limits how much data can be in transit Integrate with flow control implemented as of bytes describe as packets MaxWindow min cwnd AdvertisedWindow EffectiveWindow MaxWindow LastByteSent LastByteAcked LastByteAcked LastByteSent sequence number increases laik cs berkeley edu 11 Slow Start Goal Goal discover congestion quickly used to get rough initial estimate of cwnd Slow Start used when a new connection or after timeout or after connection has been idle for a while 12 Slow Start Algorithm Algorithm Set cwnd 1 Each time a segment is acknowledged increment cwnd by one cwnd Slow Start increases cwnd exponentially called Slow because it gradually increases sending rate according to the RTT predecessor just increased to advWin immediately laik cs berkeley edu 13 Slow Start Example cwnd doubles every RTT cwnd 1 segment 1 ACK for segm cwnd 2 ent 1 segment 2 segment 3 ents 2 3 ACK for segm cwnd 4 cwnd 8 laik cs berkeley edu segment 4 segment 5 segment 6 segment 7 ents 4 5 6 7 m g se r fo K C A 14 Slow Start Problem Slow Start can cause serious loss loss bottleneck bandwidth RTT Example bottleneck link is 8 Mb s RTT is 100ms at some point cwnd 800 000 bits exactly right for bottleneck 100 ms late cwnd 1 600 000 bits twice the bottleneck 800 000 bits lost oops Need to switch to something else when throughput is close to bottleneck bandwidth laik cs berkeley edu 15 Exiting Slow Start cwnd advWin limited by receiver s advertised window if cwnd allowed to increase would grow unbounded congestion reached available bandwidth switch to AI MD cwnd ssthresh ssthresh slow start threshold ssthresh is a hint about when to slow down calculated from previous congestion on same connection we experienced congestion beyond this point before slow down laik cs berkeley edu 16 Additive Increase Multiplicative Decrease Used Slow Start to get rough estimate of cwnd Goal maintain operating point at the left of the cliff Additive increase starting from the rough estimate slowly increase cwnd to probe for additional available bandwidth Multiplicative decrease cut congestion window size aggressively if congestion occurs Why not AI AD MI MD MI AD mathematical models show A M is only choice that converges to fairness and efficiency 17 AI MD Algorithm ssthresh a segment is acknowledged increment cwnd by 1 cwnd cwnd 1 cwnd as a result cwnd is increased by one only if all segments in a cwnd have been acknowledged congestion detected timeout ssthresh cwnd 2 cwnd 1 begin slow start duplicate acks Fast Retransmit later laik cs berkeley edu 18 Slow Start AI MD Example cwnd 1 Assume that ssthresh 8 cwnd 4 14 12 10 cwnd 8 8 6 ssthresh 4 2 cwnd 9 t 6 t 4 t 2 0 t 0 Cwnd in segments cwnd 2 Roundtrip times cwnd 10 laik cs berkeley edu 19 The big picture cwnd Timeout AI MD Timeout AI MD ssthresh Slow Start Slow Start Slow Start Time 20 Slow Start AI MD Pseudocode Initially cwnd 1 ssthresh infinite New ack received if cwnd ssthresh Slow Start cwnd cwnd 1 else Congestion Avoidance cwnd cwnd 1 cwnd Timeout Multiplicative decrease ssthresh win 2 cwnd 1 21 AI MD Problem If available bandwidth increases suddenly e g other flows finish route changes then AI MD will be slow to use it Without help from network there is a
View Full Document
Unlocking...