Jonathan Stanton1Spring 2004 / Lecture 10Network IICS 184 High Performance NetworkingDepartment of Computer ScienceGeorge Washington UniversityJonathan Stanton2Spring 2004 / Lecture 10• An Engineering Approach to Computer Networkingby S. Keshav.– Chapter 13 and 14.• Also web references from class page.Additional ResourcesJonathan Stanton3Spring 2004 / Lecture 10Window Flow Control• ~ W packets per RTT• Lost packet detected by missing ACKRTTtimetimeSourceDestination1 2 W1 2 W1 2 WdataACKs1 2 WJonathan Stanton4Spring 2004 / Lecture 10Source Rate• Limit the number of packets in the network towindow W• Source rate = bps• If W too small then rate « capacityIf W too big then rate > capacity=> congestionRTTMSSW Jonathan Stanton5Spring 2004 / Lecture 10TCP Window Flow Controls• Receiver flow control– Avoid overloading receiver– Set by receiver– awnd: receiver (advertised) window• Network flow control– Avoid overloading network– Set by sender– Infer available network capacity– cwnd: congestion window• Set W = min (cwnd, awnd)Jonathan Stanton6Spring 2004 / Lecture 10Receiver Flow Control• Receiver advertises awnd with each ACK• Window awnd– closed when data is received and ack’d– opened when data is read• Size of awnd can be the performance limit (e.g. on aLAN)– sensible default ~16kBJonathan Stanton7Spring 2004 / Lecture 10Network Flow Control• Source calculates cwnd from indication of networkcongestion• Congestion indications– Losses– Delay– Marks• Algorithms to calculate cwnd– Tahoe, Reno, Vegas, RED, REM …Jonathan Stanton8Spring 2004 / Lecture 10TCP Congestion Controls• Tahoe (Jacobson 1988)– Slow Start– Congestion Avoidance– Fast Retransmit• Reno (Jacobson 1990)– Fast Recovery• Vegas (Brakmo & Peterson 1994)– New Congestion Avoidance•RED (Floyd & Jacobson 1993)– Probabilistic markingJonathan Stanton9Spring 2004 / Lecture 10TCP Tahoe (Jacobson 1988)SStimewindowCASS: Slow StartCA: Congestion AvoidanceJonathan Stanton10Spring 2004 / Lecture 10Slow Start• Start with cwnd = 1 (slow start)• On each successful ACK increment cwndcwnd  cnwd + 1• Exponential growth of cwndeach RTT: cwnd  2 x cwnd• Enter CA when cwnd >= ssthreshJonathan Stanton11Spring 2004 / Lecture 10Slow Startdata packetACKreceiversender1 RTTcwnd12345678cwnd  cwnd + 1 (for each ACK) cwnd123412345678Jonathan Stanton12Spring 2004 / Lecture 10Congestion Avoidance• Starts when cwnd  ssthresh• On each successful ACK: cwnd  cwnd + 1/cwnd• Linear growth of cwndeach RTT: cwnd  cwnd + 1Jonathan Stanton13Spring 2004 / Lecture 10Congestion Avoidancecwnd1231 RTT4data packetACKcwnd  cwnd + 1 (for each cwnd ACKS) receiversender1 RTT1234Jonathan Stanton14Spring 2004 / Lecture 10Packet Loss• Assumption: loss indicates congestion• Packet loss detected by– Retransmission TimeOuts (RTO timer)– Duplicate ACKs (at least 3)1234 56123PacketsAcknowledgements3373Jonathan Stanton15Spring 2004 / Lecture 10Fast Retransmit• Wait for a timeout is quite long• Immediately retransmits after 3 dupACKs withoutwaiting for timeout• Adjusts ssthreshflightsize = min(awnd, cwnd)ssthresh  max(flightsize/2, 2)• Enter Slow Start (cwnd = 1)Jonathan Stanton16Spring 2004 / Lecture 10Successive Timeouts• When there is a timeout, double the RTO• Keep doing so for each lost retransmission– Exponential back-off– Max 64 seconds1– Max 12 restransmits11 - Net/3 BSDJonathan Stanton17Spring 2004 / Lecture 10Summary: Tahoe• Basic ideas– Gently probe network for spare capacity– Drastically reduce rate on congestion– Windowing: self-clocking– Other functions: round trip time estimation, error recoveryfor every ACK { if (W < ssthresh) then W++ (SS) else W += 1/W (CA)}for every loss {ssthresh = W/2 W = 1}Jonathan Stanton18Spring 2004 / Lecture 10TCP Reno (Jacobson 1990)CASSFast retransmission/fast recoveryJonathan Stanton19Spring 2004 / Lecture 10Fast recovery• Motivation: prevent `pipe’ from emptying after fast retransmit• Idea: each dupACK represents a packet having left the pipe(successfully received)• Enter FR/FR after 3 dupACKs–Set ssthresh  max(flightsize/2, 2)– Retransmit lost packet– Set cwnd  ssthresh + ndup (window inflation)– Wait till W=min(awnd, cwnd) is large enough; transmit new packet(s)– On non-dup ACK (1 RTT later), set cwnd  ssthresh (windowdeflation)• Enter CAJonathan Stanton20Spring 2004 / Lecture 109940 0Example: FR/FR• Fast retransmit– Retransmit on 3 dupACKs• Fast recovery– Inflate window while repairing loss to fill pipetimeStimeR1 2 3 4 5 6 878cwnd 8ssthresh1740 0 0Exit FR/FR444110010 11Jonathan Stanton21Spring 2004 / Lecture 10Summary: Reno• Basic ideas– Fast recovery avoids slow start– dupACKs: fast retransmit + fast recovery– Timeout: fast retransmit + slow startslow startretransmitcongestionavoidance FR/FR dupACKstimeoutJonathan Stanton22Spring 2004 / Lecture 10Network Packet Costs• Each packet has a cost.– Key question is how to minimize that cost in relation to thegoodput.• Definitions:– Potential Throughput: The number of bytes that could betransferred in a unit time given the bandwidth of themedium.– Actual Throughput: The number of bytes transferred in aunit time (usually a second)– Goodput: The number of useful bytes of data transferred ina unit time.Jonathan Stanton23Spring 2004 / Lecture 10Protocol Stack OverheadPer-packet over head:• Ethernet Header / Checksum• IP Header / Checksum• TCP Header / Checksum• Coping / interruption processSolution: Increase packet size• Opt Packet Size=min{ packet size along the path}(Fragmentation results in low performance too.)Jonathan Stanton24Spring 2004 / Lecture 10Path MTU Discovery (1191)Current Method:• “Don’t Fragment” bits(Router: Drop/Fragment; Host: Test/Enforce)• MTU=min{576, first hop MTU}• MSS=MTU-40• MTU<=65535 (Architecture)• MSS<=65495 (IP sign-bit bugs…)• Drawback: Usually too smallJonathan Stanton25Spring 2004 / Lecture 10Path MTU Discovery• How to Discover PMTU?Current:• Search (Proportional Decreasing / Binary)• Update (Periodically Increasing – set to the MTU offirst hop)Better:• Search/Update with typical MTU values• Routers: provide suggestion of MTU in ICMP responseindicating the DF pack drop.Jonathan Stanton26Spring 2004 / Lecture 10Path MTU