Improving TCP Start-up over High Bandwidth Delay PathsRen Wang, Giovanni Pau, M.Y. Sanadidi and Mario Gerla UCLA Computer Science Departmentwww.cs.ucla.edu/NRLMarch, 2003 UCLA Computer Science Department2Motivation • TCP Reno/Newreno Mechanism:Ø Slow-start: cwnd grows exponentially until hit ssthreshØ Congestion-avoidance: cwnd grows linearly • By setting initial ssthresh to an arbitrary value, TCP may suffer: Ø ssthresh too high: multiple loss and coarse timeoutØ ssthresh too low: premature exit of slow-start and low utilization• Majority of TCP flows are short-lived• The Bandwidth Delay Product(BDP) has been growing fast, resulting in poor utilization for short-lived connections with current TCP implementation:010203040506070809010 20 40 100 200Bandwidth (Mbps)Utilization (%)Utilization during the first 20 seconds (RTT=100ms)March, 2003 UCLA Computer Science Department3Related Work• Larger initial cwndØ Good for transfers with a few packets• Fast StartØ Cached information may be stale • Smooth StartØ Assuming initial ssthresh is large enough• Shared passive network discovery(SPANK)Ø Needs leaky bucket pacing• TCP Vegas• Hoe’s MethodMarch, 2003 UCLA Computer Science Department4TCP Vegas(1)• Sender watches for sign that router’s queue is building up and congestion will happen; e.g.,§ RTT grows§ sending rate flattens• Sender lowers sending rate to avoid buffer overflow• During Slow-start, Vegas doubles cwnd every other RTT• Until diff (between expected and achieved rate) exceeds a threshold:nRTTcwndbaseRTTcwnddiff −=March, 2003 UCLA Computer Science Department5TCP Vegas(2)0204060801001201400 1 2 3 4 5cwnd in packetsTime (sec)start of cwnd doubling periodqueue length corresponding to measured RTTVegas cwndInstant Queue Length• Problem: premature exit due to RTT over-estimation, caused by temporary queue buildup:• Under-utilization becomes severe when the bandwidth delay product increases:• Exit cwnd: the congestion window when a connection exits slow start00.050.10.150.20.250.30.350.40.4510 20 40 80 150Bandwidth (Mbps)Ratio of exit cwnd to ideal windowRatio of Slow-start termination cwnd to the ideal window (=BDP) (RTT =100ms)March, 2003 UCLA Computer Science Department6Hoe’s method(1)• Setting initial ssthresh to estimated BDPØ Bandwidth: packet pair bandwidth estimateØ RTT: measured RTT of the first segment transmitted • May achieve high utilization, but not robust to buffer variation and dynamic load during slow start phase01002003004005006007000 5 10 15 20 25 30cwnd in packetsTime (sec)Ideal exit window =Path BDP = 500 packetscwnd with large buffer (500)March, 2003 UCLA Computer Science Department7Hoe’s method(2)• Problem:Ø The bottleneck buffer is small compared to BDPØ Other large volume traffic join in during Slow-start phase • è Multiple losses, timeout, and low utilization 01002003004005006007000 5 10 15 20 25 30cwnd in packetsTime (sec)Ideal exit window =min (BDP,2*buffersize)= 250cwnd with small buffer (125)01002003004005006000 2 4 6 8 10cwnd in packetsTime (sec)20 Mbps CBR starts at 0.5secMultiple losses in Hoe's methodcwnd of Hoe's method(a)Small buffer cause multiple losses (b) Traffic interference cause multiple lossesMarch, 2003 UCLA Computer Science Department8Adaptive Start (Astart) Approach• Take advantage of Eligible Rate Estimation (ERE) in TCP Westwood (TCPW)Ø Adaptively and repeatedly reset ssthresh to estimated bandwidth share or Eligible Rate Estimate, if appropriate• Key idea in TCPW and EREØ Enhance congestion control via the Eligible Rate Estimate§ ERE is estimated at the sender by sampling and exponential filtering measures from ACK stream§ Samples are determined from ACK inter-arrival times and info about bytes deliveredØ after packet loss (ie, 3 DUPACKs, or Timeout), ERE is used by sender to set cwnd, ssthresh=ERE x RTTminMarch, 2003 UCLA Computer Science Department9TCP Westwood: the Control Algorithm• TCPW Algorithm Outline:Ø When three duplicate ACKs are detected:§ set ssthresh=ERE*RTTmin (instead of ssthresh=cwin/2 as in Reno and NewReno)§ if (cwin > ssthresh) set cwin=ssthreshØ When a TIMEOUT expires:§ set ssthresh=ERE*RTTmin (instead of ssthresh=cwnd/2 as in Reno) and cwin=1Note: RTTmin = min round trip delay experienced by the connectionMarch, 2003 UCLA Computer Science Department10ERE in TCPWBE Sampling:Packet pair, may overestimate ( e.g. inCongestion), effective in random lossTkCongestionTkNo CongestionRTTdkRTTktjtjs∑=−> RE Sampling:Packet train, fair estimate in congestion, may underestimate (e.g. in random loss))/(1−−=kkkkttdS•ERE estimate: adapt the sample interval Tkaccording to current measured congestion level (Vegas measure of congestion level)•Tkranges from one ACK interarrival interval à RTT•RE <= ERE <= BEMarch, 2003 UCLA Computer Science Department11Adaptive Start (Astart) (1)Astart uses ERE to adaptively and repeatedly reset ssthresh during the startup phase (connection startup and after a coarse timeout):if ( 3 DUPACKS are received)switch to congestion avoidance phase;else (ACK is received)if (ssthresh < (ERE*RTTmin)/seg_size)ssthresh =(ERE*RTTmin)/seg_size;endifif (cwnd >ssthresh) /*mini congestion avoid. phase*/increase cwnd by 1/cwnd;else if (cwnd <ssthresh) /*mini slow start phase*/ increase cwnd by 1;endifendifMarch, 2003 UCLA Computer Science Department12Astart (2)• Astart continuously uses ERE• Contains mini slow-start and mini congestion-avoidance phases• cwnd grows slower as it approaches BDP(a)Big buffer (500 packets) BDP = 500 packets (b) Small buffer(125 packets)01002003004005006007008009000 5 10 15 20 25 30cwnd in packetsTime (sec)cwndSlow Start Threshold01002003004005006007000 5 10 15 20 25 30cwnd in packetsTime (sec)cwndSlow Start Threshold4204304404504604704804905005101.6 1.7 1.8 1.9 2 2.1 2.2cwnd in packetsTime (sec)mini congestion avoidance phasesmini slow start phasescwnd(c)A closer look at Astart cwnd dynamicMarch, 2003 UCLA Computer Science Department13Astart (3)Astart cwnd dynamic with 5 connections startup simultaneously cwnd dynamic with UDP traffic joins in during startup phase (compare Astart and Hoe’s method)0501001502002503003504000 2 4 6 8 10cwnd in packetsTime (sec)cwnd (connection 1)cwnd (connection 2)cwnd (connection 3)cwnd (connection 4)cwnd (connection 5)01002003004005006000 2 4 6 8 10cwnd in packetsTime (sec)cwnd of Astart20 Mbps CBR starts at
View Full Document
Unlocking...