1、Transport: TCP,Manpreet Singh(Slides borrowed from various sources on the web),Announcements (1/2),Everybody needs to join the class mailing list.else I cant communicate class info. Check the class archives to see if someone else has picked the same lecture or TCP application We have a group of mach
2、ines you can use for simulation (snoopy, linus, etc.). You need CSUG accounts to access these machines. Well dig up more machines for those who want to do kernel hacking.,Announcements (2/2),Need a volunteer to give the “post-modern“ E2E lecture 9/9 (in class.). The non-research track students will
3、have to do an initial demo by 11/9. Most of the functionality should be there Allows us to give feed back You time to do performance measurements.,Roadmap,Why is TCP fair ? Loss-based congestion schemes Tahoe Reno NewReno Sack Delay-based congestion control (Vegas) Modeling TCP throughput Equation-b
4、ased congestion control,The Desired Properties of a Congestion Control Scheme,Efficiency (high utilization)Optimality (high throughput, utility)Fairness (resource sharing)Distributedness (no central knowledge for scalability)Convergence and stability (fast convergence after disturbance, low oscillat
5、ion),TCP Fairness,Fairness goal: if N TCP sessions share same bottleneck link, each should get 1/N of link capacity,TCP congestion avoidance: AIMD: additive increase, multiplicative decrease increase window by 1 per RTT decrease window by factor of 2 on loss event,AIMD,TCP connection 1,bottleneck ro
6、uter capacity R,TCP connection 2,Why is TCP fair?,Two competing sessions: Additive increase gives slope of 1, as throughout increases multiplicative decrease decreases throughput proportionally,R,R,equal bandwidth share,Connection 1 throughput,Connection 2 throughput,congestion avoidance: additive i
7、ncrease,loss: decrease window by factor of 2,congestion avoidance: additive increase,loss: decrease window by factor of 2,Loss vs Delay as signal ?,TCP,oscillation,Loss is a binary signal Delay is a multi-bit signal,Simulation-based Comparisons of Tahoe, Reno, and SACK TCP,Kevin Fall Sally Floyd,Int
8、roduction,SACK compared with Tahoe, Reno and New-RenoSimulations designed to highlight performance differences with and without SACK,Comparison,Tahoe: Slow start, congestion avoidance and fast retransmit Reno: Tahoe + fast recovery New-Reno: Reno with modified fast recovery SACK: Reno + selective AC
9、Ks,TCP Slowstart,exponential increase (per RTT) in window size (not so slow!) loss event: timeout (Tahoe TCP) and/or or three duplicate ACKs (Reno TCP),initialize: Congwin = 1 for (each segment ACKed)Congwin+ until (loss event ORCongWin threshold),Host A,one segment,RTT,Host B,two segments,four segm
10、ents,TCP Congestion Avoidance,/* slowstart is over */ /* Congwin threshold */ Until (loss event) every w segments ACKed:Congwin+ threshold = Congwin/2 Congwin = 1 perform slowstart,Congestion avoidance (linear phase),1,1: TCP Reno skips slowstart (fast recovery) after three duplicate ACKs,Fast Retra
11、nsmit,Receiving small number of duplicate ACKs (3) signals packet lossLost packet can be retransmitted before timeout This improves channel utilization,TCP/Reno Congestion Control,Initially:cwnd = 1;ssthresh = infinite (64K); For each newly ACKed segment:if (cwnd ssthresh) /* slow start*/cwnd = cwnd
12、 + 1;else/* congestion avoidance; cwnd increases (approx.) by 1 per RTT */ cwnd += 1/cwnd; Triple-duplicate ACKs:/* multiplicative decrease */cwnd = ssthresh = cwnd/2; Timeout:ssthresh = cwnd/2;cwnd = 1; (if already timed out, double timeout value; this is called exponential backoff),TCP/Reno: Big P
13、icture,Time,cwnd,slow start,congestion avoidance,TD,TD: Triple duplicate acknowledgements TO: Timeout,TO,ssthresh,ssthresh,ssthresh,ssthresh,congestion avoidance,TD,congestion avoidance,slow start,congestion avoidance,TD,Tahoe + Fast Recovery,Fast Recovery,Observation: Each duplicate ACK indicates s
14、ome packet has left pipe,New-Reno extension,New-Reno continues with fast recovery if a partial ACK is received,Old cwnd,New cwnd = (old cwnd)/2,Usable window increased by 1 for each duplicate ACK until ACK for LP is received,Packet 1 lost,Packet 2 lost,LP: Last Packet sent before loss detection,Why
15、use SACK?,Without SACK sender has to use one of following retransmission strategies- Retransmit 1 dropped packet / RTTReno, New-Reno- Retransmit packets that might have been successfully deliveredTahoe,SACK option RFC2018,Ex: 2nd segment dropped (each segment has 500 bytes),SACK Congestion Control (
16、1/2),Conservative extensions to Reno Fast recovery algorithm modified Uses a variable called “pipe” to estimate outstanding data in the flowRules for changing “pipe” variable + 1 when packet transmitted - 1 when dup ACK received,SACK Congestion Control (2/2),SACK sender tracks successfully sent pack
17、ets using “scoreboard” structure Missing packets are retransmittedSimilar to New-Reno in exiting from fast recovery exits after all outstanding data at time of loss is ACked,Simulation Model used,Three flows are setup from S1 to K1, 2nd and 3rd flows are used to change packet drop pattern of 1st flo
18、w,One Packet Loss (1/2),Packet dropped,Packet retransmitted,Performs slow start,One Packet Loss (2/2),Packet dropped,Packet retransmitted,Performs fast recovery,Two Packet Loss (1/2),Packets dropped,Packets retransmitted,Performs slow start,Two Packet Loss (2/2),Packets dropped,Packets retransmitted
19、,Performs fast recovery,Three Packet Losses (1/3),Packets dropped,Packets retransmitted,Has to wait for timeout,Three Packet Losses (2/3),Packets dropped,Packets retransmitted,No need for timeout Retransmits 1 pkt/RTT,Three Packet Losses (3/3),Packets dropped,Packets retransmitted,Retransmits more t
20、han 1 pkt /RTT,Observations,Tahoe: Robust, performs slow start Reno: For 2 losses, timeout is often needed New-Reno: Can avoid timeouts, but still cannot retransmit 1 pkt/RTT SACK: Can retransmit 1 pkt/RTT , thus recovers from losses faster,Conclusions,SACK can improve TCP performance SACK can be us
21、ed in high loss links too (Ex: Wireless) New-Reno demonstrates that certain problems of Reno can be avoided without SACK,Reno vs Vegas (Congestion Avoidance),Renos mechanism Characteristics uses the loss of segments as a signal reactive not proactive needs to create losses to find the available band
22、width example,Threshold window,congestion window,send window,TCP Vegas,Idea: source watches for some sign that routers queue is building up and congestion will happen too; e.g., RTT grows sending rate flattens,Congestion window,Avg. source send rate,Buffer space at router,In shaded region we expect
23、throughput to increase but it cannot increase beyond available bandwidth,Vegas approach,Basic idea Vegas tries not to send at a rate that causes buffers to fill maintain the right amount of extra data based on changes in the estimated amount of extra data window size vs. throughput Keep the actual r
24、ate straying too far from the available rate (resulting in smooth congestion avoidance period),Vegas Algorithm,define a given connections BaseRTT BaseRTT = the minimum of all measured RTT expected throughput = WindowSize / BaseRTT Actual rate = Flight size / RTT Calculate the current Actual sending
25、rate Compare Actual (A) to expected (E) and adjusts the window (linear increase or decrease) If (E-A) beta, cwnd - - (congestion state) If (E-A) alpha, cwnd+ (low utilization) When a loss is detected, reduce the window by a half,Algorithm (cont),Parameters a = 1 buffer b = 3 buffers,Black line = act
26、ual rate Green line = expected rate Shaded = region between a and b,Note: Linear decrease in Vegas does not violate AIMD since it Happens before packets loss,Comparison of Reno and Vegas (Retransmission),Renos retransmission mechanism retransmission timeout based on RTT and variance estimates BSD-ba
27、sed : 500ms Fast Retransmit and Fast Recovery When the sender receives duplicate acks, it reduces the window size by a half and avoids timeout which causes retransmission with slow start If multiple drops occur, timeout and slow start will follow anyway. 19% increase in throughput,Vegas Retransmissi
28、on,reads and records the system clock each time a segment is sent when an ACK arrives, Vegas reads the clock again RTT calculation using this time and the timestamp recorded for the relevant segment uses this more accurate RTT estimate to decide to retransmit,Some fun topics to discuss,Modeling TCP
29、throughput,Consider congestion avoidance only,Time,cwnd,congestion avoidance,TD,ssthresh,Assume one packet loss (loss event) per cycle Total packets send per cycle: 3W2/8 Thus p = 1/(3W2/8) = 8/(3W2) =,bottleneck bandwidth,W/2,W,Modeling TCP throughput,1/throughput = c * sqrt(p) * RTT,Equation-based
30、 Congestion Control,Dont need reliability But still want to be friendly to the network What rate should we send the UDP traffic ? Use detailed TCP analysis to relate throughput to loss and RTT. Measure these values and then calculated appropriate throughput directly. Result is rate-based and equation-driven protocol called TFRC.,mulTCP,Effect of AIMD parameters on the throughput of TCP,
