CSCI-1680 :: Computer Networks

CSCI-1680 :: Computer Networks

CSCI-1680 Transport Layer II Data over TCP Rodrigo Fonseca Based partly on lecture notes by David Mazires, Phil Levis, John Jannotti Last Class Introduction to TCP Header format Connection state diagram Today: sending data First Goal We should not send more data than the receiver can take: flow control

When to send data? Sender can delay sends to get larger segments How much data to send? Data is sent in MSS-sized segments Chosen to avoid fragmentation Flow Control Part of TCP specification (even before 1988) Receiver uses window header field to tell sender how much space it has Flow Control Receiver: AdvertisedWindow = MaxRcvBuffer ((NextByteExpected-1)

LastByteRead) Sender: LastByteSent LastByteAcked <= AdvertisedWindow EffectiveWindow = AdvertisedWindow (BytesInFlight) LastByteWritten LastByteAcked <= Flow Control Advertised window can fall to 0 How? Sender eventually stops sending, blocks application Sender keeps sending 1-byte segments until window comes back > 0 When to Transmit? Nagles algorithm Goal: reduce the overhead of small

packets If available data and window >= MSS Send a MSS segment else If there is unAcked data in flight buffer the new data until ACK arrives else send all the new data now Receiver should avoid advertising a window <= MSS after advertising a window of 0 Delayed Acknowledgments Goal: Piggy-back ACKs on data Delay ACK for 200ms in case application sends data If more data received, immediately ACK second segment Note: never delay duplicate ACKs (if

missing a segment) Warning: can interact very badly with Nagle Temporary deadlock Can disable Nagle with TCP_NODELAY Application can also avoid many small writes Limitations of Flow Control Network may be the bottleneck Signal from receiver not enough! Sending too fast will cause queue overflows, heavy packet loss Flow control provides correctness Need more for performance: congestion control Second goal

We should not send more data than the network can take: congestion control A Short History of TCP 1974: 3-way handshake 1978: IP and TCP split 1983: January 1st, ARPAnet switches to TCP/IP 1984: Nagle predicts congestion collapses 1986: Internet begins to suffer congestion collapses LBL to Berkeley drops from 32Kbps to 40bps 1987/8: Van Jacobson fixes TCP, publishes

seminal paper*: (TCP Tahoe) 1990: Fast transmit and fast recovery added (TCP Reno) * Van Jacobson. Congestion avoidance and control. SIGCOMM 88 Congestion Collapse Nagle, rfc896, 1984 Mid 1980s. Problem with the protocol implementations, not the protocol! What was happening? Load on the network buffers at routers fill up round trip time increases If close to capacity, and, e.g., a large flow arrives suddenly

RTT estimates become too short Lots of retransmissions increase in queue size Eventually many drops happen (full queues) Fraction of useful packets (not copies) decreases TCP Congestion Control 3 Key Challenges Determining the available capacity in the first place Adjusting to changes in the available capacity Sharing capacity between flows Idea Each source determines network capacity for itself Rate is determined by window size Uses implicit feedback (drops, delay) ACKs pace transmission (self-clocking)

Dealing with Congestion TCP keeps congestion and flow control windows Max packets in flight is lesser of two Sending rate: ~Window/RTT The key here is how to set the congestion window to respond to congestion signals Dealing with Congestion Assume losses are due to congestion After a loss, reduce congestion window How much to reduce? Idea: conservation of packets at equilibrium Want to keep roughly the same number of packets in network Analogy with water in fixed-size pipe

Put new packet into network when one exits How much to reduce window? Crude model of the network Let Li be the load (# pkts) in the network at time I If network uncongested, roughly constant Li = N What happens under congestion? Some fraction of packets cant exit the network Now Li = N + Li-1, or Li giL0 Exponential increase in congestion Sources must decrease offered rate exponentially i.e, multiplicative decrease in window size

TCP chooses to cut window in half How to use extra capacity? Network signals congestion, but says nothing of underutilization Senders constantly try to send faster, see if it works So, increase window if no losses By how much? Multiplicative increase? Easier to saturate the network than to recover Too fast, will lead to saturation, wild fluctuations Additive increase? Wont saturate the network Remember fairness (third challenge)? Chiu Jain Phase Plots Flow Rate B

Fair: A = B Goal: fair and efficient! Efficient: A+B = C Flow Rate A Chiu Jain Phase Plots Fair: A = B Flow Rate B MI MD Efficient: A+B = C Flow Rate A Chiu Jain Phase Plots Fair: A = B

Flow Rate B AIAD Efficient: A+B = C Flow Rate A Chiu Jain Phase Plots Fair: A = B Flow Rate B AIMD Efficient: A+B = C Flow Rate A AIMD Implementation In practice, send MSS-sized segments

Let window size in bytes be w (a multiple of MSS) Increase: After w bytes ACKed, could set w = w + MSS Smoother to increment on each ACK w = w + MSS * MSS/w (receive w/MSS ACKs per RTT, increase by MSS/(w/MSS) for each) Decrease: After a packet loss, w = w/2 But dont want w < MSS So react differently to multiple consecutive losses Back off exponentially (pause with no packets in flight)

AIMD Trace AIMD produces sawtooth pattern of window size Always probing available bandwidth Starting Up Before TCP Tahoe On connection, nodes send full (rcv) window of packets Retransmit packet immediately after its timer expires Result: window-sized bursts of packets in network Bursts of Packets Graph from Van Jacobson and Karels, 1988

Determining Initial Capacity Question: how do we set w initially? Should start at 1MSS (to avoid overloading the network) Could increase additively until we hit congestion May be too slow on fast network Start by doubling w each RTT Then will dump at most one extra window into network This is called slow start Slow start, this sounds quite fast! In contrast to initial algorithm: sender would dump entire flow control window at once Startup behavior with Slow Start Slow start implementation

Let w be the size of the window in bytes We have w/MSS segments per RTT We are doubling w after each RTT We receive w/MSS ACKs each RTT So we can set w = w + MSS on every ACK At some point we hit the network limit. Experience loss We are at most one window size above the limit Remember window size (ssthresh) and reduce window Putting it together TCP has two states: Slow Start (SS) and Congestion Avoidance (CA) A window size threshold governs the state transition Window <= threshold: SS

Window > threshold: congestion avoidance States differ in how they respond to ACKs Slow start: w = w + MSS Congestion Avoidance: w = w + MSS2/w (1 MSS per RTT) On loss event: set w = 1, slow start How to Detect Loss Timeout Any other way? Gap in sequence numbers at receiver Receiver uses cumulative ACKs: drops => duplicate ACKs 3 Duplicate ACKs considered loss Which one is worse?

Putting it all together cwnd Timeout AIMD Timeout AIMD ssthresh Slow Start Slow Start Slow Start

Time RTT We want an estimate of RTT so we can know a packet was likely lost, and not just delayed Key for correct operation Challenge: RTT can be highly variable Both at long and short time scales! Both average and variance increase a lot with load Solution Use exponentially weighted moving average (EWMA) Estimate deviation as well as expected value Assume packet is lost when time is well beyond reasonable deviation Originally EstRTT = (1 ) EstRTT + ) EstRTT + ) EstRTT + SampleRTT

Timeout = 2 EstRTT Problem 1: in case of retransmission, ack corresponds to which send? Solution: only sample for segments with no retransmission Problem 2: does not take variance into account: too aggressive when there is more load! Jacobson/Karels Algorithm (Tahoe) EstRTT = (1 ) EstRTT + ) EstRTT + ) EstRTT + SampleRTT Recommended is 0.125 DevRTT = (1 ) DevRTT + | SampleRTT ) DevRTT + ) DevRTT + | SampleRTT | SampleRTT EstRTT | Recommended is 0.25 Timeout = EstRTT + 4 DevRTT

For successive retransmissions: use exponential backoff C O N S E R V A T IO N A T E Q U IL IB R IU M : R O U N D -T R IP T IM IN G 10 12 Old RTT Estimation Figure 5: Performance of an RFC793 retransmit timer 8

6 4


0 RTT (sec.) 2

0 10 20 30 40 50 60 Packet 70 80 90

100 110 A D A P T IN G T O T H E P A T H : C O N G E S T IO N A V O ID A N C E 10 12 Tahoe RTT Estimation Figure 6: Performance of a Mean+Variance retransmit timer 8


4 RTT (sec.) 2

0 3

0 10 20 30 40 50 60 70 80 90

100 110 Packet Same data as above but the solid line shows a retransmit timer computed according to the Slow start every time?! Losses have large effect on throughput Fast Recovery (TCP Reno) Same as TCP Tahoe on Timeout: w = 1, slow start On triple duplicate ACKs: w = w/2 Retransmit missing segment (fast retransmit) Stay in Congestion Avoidance mode Fast Recovery and Fast Retransmit

cwnd AI/MD Slow Start Fast retransmit Time 3 Challenges Revisited Determining the available capacity in the first place Exponential increase in congestion window Adjusting to changes in the available capacity Slow probing, AIMD Sharing capacity between flows AIMD Detecting Congestion Timeout based on RTT

Triple duplicate acknowledgments Fast retransmit/Fast recovery Reduces slow starts, timeouts Next Class More Congestion Control fun Cheating on TCP TCP on extreme conditions TCP Friendliness TCP Future

Recently Viewed Presentations

  • Economic Systems Notes - Troup County School District

    Economic Systems Notes - Troup County School District

    Instructional Approach(s): The teacher should present the information on the slide while the students record the important information on their Economic Systems Foldable Mixed Economy Most democratic countries fall in this category (there are no truly pure Market or Command...
  • Tackling Poverty &amp; Economic Inequality &amp; Promoting Economic ...

    Tackling Poverty & Economic Inequality & Promoting Economic ...

    - Fairerpower Red Rose. Opportunity for a Lancashire Combined Authority to establish a housing development role through establishing a . housing company. Public and community banking. Local impact investments (Retirement Systems of Alabama)
  • Redundancy and Wordiness - Morgan Park High School

    Redundancy and Wordiness - Morgan Park High School

    Concise writing expresses ideas without unnecessary wordiness. Wordiness not only increases the length of your work without adding meaning, but also makes your writing harder to understand. This (wordiness) is a natural result of trying to get your ideas down...


    Qualificação especial para Honors 2020Membros da Equipe GET ouEquipe de Milionários que se qualificarem para Experiência AWT STARS 2020 com 5 STARS oumaisE se qualificarempessoalmentecomo AWT 2019 ou 2020 estãoconvidados a participar do Honors 2020.. HERBALIFE Nutrition
  • Shatter not the branches of the tree of anger

    Shatter not the branches of the tree of anger

    Cramming her emotions into dark penetralia, she thinks her shame is her own "experience of the self by the self" (Sedgwick 1995, 136). She eventually chokes on shame's bile. It rises, she gulps it down. It rises again. She gulps...
  • Fracture Femur - Kmc

    Fracture Femur - Kmc

    Two cm shorting and up to 20 degrees angulation is accepted in children but again no rotation. Complications - Malunion - Leg length discrepancy usually shortening but may be increase in length due to 1- Active healing process( hyperaemia and...
  • Bat Loves the Night lesson 22 day 5 - Etowah County Schools

    Bat Loves the Night lesson 22 day 5 - Etowah County Schools

    Question of the DayObjective: to listen and respond appropriately to oral communication; to record ideas and reflections. If you were an animal, where would you like to live- on earth, in the water, or in the sky?
  • Culinary Arts Program - Red Shield Toolkit

    Culinary Arts Program - Red Shield Toolkit

    Who is the CATP's Chef Instructor?. Chef Timothy is the former Executive Chef at the Salvation Army's Center of Hope Meal Service in Louisville, KY. Inspired by the needs & spirit of the community they served, he developed the Culinary...