1Congestion Control (cont’d)TCP Congestion ControlReview Congestion control consists of 3 tasks Detect congestion Adjust sending rate Determine available bandwidth How does TCP do each of these?Packets vs. Bytes TCP window sizes are in bytes Congestion control works on packets Increase by 1 packet every RTT Pcwnd = cwnd / MSS Pcwnd = Pcwnd + 1/Pcwnd on each ACK Multiply by MSS to get byte-sized formula cwnd = cwnd + MSS*(MSS/cwnd) on each ACK Increase by 1 MSS every RTTTCP Start Up How do we set initial window size? Additive increase too slow Example: DSL line RTT=100ms, MSS=1500b, BW=200KB/s After 1 RTT, rate is 15 KB/s After 1s, rate is 150 KB/s Takes 8.3s to transfer 500 KB fileSlow Start Objective Determine initial available capacity Idea Begin with CongestionWindow = 1packet Double CongestionWindow eachRTT Increment by 1 packet for each ACK Continue increasing until loss, thenswitch to AIMD Result Exponential growth Slower than all at onceSource Destination…Window rate control Congestion window ensures averagerate is cwnd / RTT Instantaneous rate may be largertime0 2 RTT1 RTTwindow-controlledtransmissionsrate-controlledtransmissions2ACK clocking ACK clocking spreads out bursts Packets sent in a burst arrive spread out ACKs follow the timing of received rateSender Router Receiver100 Mbps 5 MbpsACK clocking ACK clocking spreads out bursts Packets sent in a burst arrive spread out ACKs follow the timing of received rate New sending rate follows ACK rateSender Router Receiver100 Mbps 5 MbpsSlow start ACK clocking, with 2 packets per ACKSender Router ReceiverSlow start ACK clocking, with 2 packets per ACKSender Router ReceiverSlow start ACK clocking, with 2 packets per ACKSender Router ReceiverNB: There’s a proposed alternative to slow-start that uses ACK clockingTCP Timeoutcwndcwndxtimeoutretransmitcumulative ack3Timeout Handling Cumulative ACK opens up entirewindow Do we send entire window all at once? No ACKs to clock transmission Use slow-start to recover ACK clock Reset cwnd to 1 (packet) Use exponential increase(add 1 packet to cwnd for every ACK)Congestion Threshold New variable: Congestion Threshold Target window size Estimate network capacity If cwnd < cthresh, increase exponentially slow start If cwnd > cthresh, increase linearly additive increase Initially, ctrhesh = max window At loss, ctrhesh = 1/2 cwndSlow Start Initial values cthresh = 8 cwnd = 1 Loss after transmission 7 cwnd currently 12 Set cthresh = cwnd/2 Set cwnd = 1Slow Start Example trace of CongestionWindow60201.0 2.0 3.0 4.0 5.0 6.0 7.0 8.0 9.0KB7030405010 Problem Have to wait for timeout Can lose half CongestionWindow of dataCW flattens out due to lossSlow start until CW = CTLinear increaseTimeout: CT = CW/2 = 11, CW = 1Fast Retransmit and FastRecovery Problem Coarse-grain TCPtimeouts lead toidle periods Solution Fast retransmit:use duplicateACKs to triggerretransmissionPacket 1Packet 2Packet 3Packet 4Packet 5Packet 6Retransmitpacket 3ACK 1ACK 2ACK 2ACK 2ACK 6ACK 2Sender ReceiverFast Retransmit and FastRecovery Send ACK for each segment received When duplicate ACK’s received Resend lost segment immediately Do not wait for timeout In practice, retransmit on 3rd duplicate Fast recovery When fast retransmission occurs, skip slow start Congestion window becomes 1/2 previous Start additive increase immediately4TCP Congestion WindowTrace0102030405060700 10 20 30 40 50 60TimeCongestion Windowthresholdcongestionwindowtimeoutsslow start periodadditive increasefast retransmissionTCP Congestion ControlSummary Congestion control mechanisms Timeouts RTT estimation Congestion window Slow start Fast retransmitFairness TCP congestion control is fair Both senders will settle at around 5 Mbps Intuition: flows using more bandwidthmore likely to experience lossSender 2RouterReceiver 120 Mbps 10 MbpsSender 1Receiver 2What’s Fair?Flow AFlow B Flow C Flow DWhich is more fair:Globally Fair: Fa = Capacity/4, Fb = Fc = Fd= 3Capacity/4orLocally Fair: Fa = Fb = Fc = Fd = Capacity/2This is the so-called “max-minfair” rateallocation. Theminimum rate ismaximized.TCP fairness TCP is “RTT-fair” On each congested link, host gets shared ofbandwidth proportional to RTT Intuition: during additive increase, eachhost adds one new packet every RTT If RTT twice as large, additive increase is halfas fast Is this closer to globally fair or locally fair?Why is TCP fair?Two competing sessions: Additive increase improves fairness Multiplicative decrease preserves fairnessRRequal bandwidth shareConnection 1 throughputConnection 2 throughputcongestion avoidance: additive increaseloss: decrease window by factor of 2congestion avoidance: additive increaseloss: decrease window by factor of 25Congestion Avoidance Control vs. avoidance Control: minimize impact of congestion when it occurs Avoidance: avoid producing congestion In terms of operating point limitsloadpoweroptimal loadidealizedpower curvecontrolavoidanceCongestion Avoidance TCP’s strategy Repeatedly cause congestion Control it once it happens Alternative Strategy Predict when congestion is about to happen and reducethe rate at which hosts send data just before packets startbeing discarded Congestion avoidance, as compared to congestion control Approaches Routers implement CA (ATM, RSVP) Routers help end-hosts implement CA (DECbit, RED) End-hosts do it themselves (TCP Vegas)DECbit (DestinationExperiencing Congestion Bit) Developed for the Digital NetworkArchitecture Basic idea One bit allocated in packet header Any router experiencing congestion sets bit Source adjusts rate based on bits Note that responsibility is shared Routers identify congestion Hosts act to avoid congestionDECbit Router Monitors length over last busy + idle cycle Sets congestion bit if average queue length is greater then 1when packet arrives Attempts to balance throughput against delay smaller values result in more idle time larger values result in more queueing delayQueue lengthCurrenttimeTimeCurrent cyclePrevious cycleAveragingintervalDECbit End Hosts Destination echoes congestion bit back to source Source records how
View Full Document
Unlocking...