Announcements Homework 4 should be out tonight TCP Performance Next lecture network performance EE 122 Intro to Communication Networks Fall 2006 MW 4 5 30 in Donner 155 Vern Paxson TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 2 Goals of Today s Lecture Time Sequence Plots Powerful tool for visualizing transport protocol dynamics A look at a range of TCP mechanisms that influence its behavior performance Plot sequence number Y axis vs time X axis Window limitations Timeout slow start exponential backoff Acking policies Fast Retransmit Fast Recovery full AIMD Window scaling For data packet sequence number highest byte carried in packet so header seqno payload length For ack it s just the ack seqno in the header Where do you get the data for the plot Record trace of connection using tcpdump Illuminates performance achieved why Visualized using time sequence plots As well as problems Both network and in endpoint stacks and also beware measurement errors 3 Example of Time Sequence Plot 4 Example of Time Sequence Plot Solid squares Data Slope gives overall throughput bytes sec Hollow squares Acks Window MSS RTT 5 6 1 Same Connection Why So Different Delayed Acknowledgments Receiver generally delays sending an ACK Upon receiving a packet sets a timer Note Receiver acks every other segment Typically 200 msec at most 500 msec If application generates data go ahead and send And piggyback the acknowledgment If the timer expires send a non piggybacked ACK If out of order segment arrives immediately ack if available window changes send an ACK Limiting the wait Receiver supposed to ACK at least every second fullsized packet ack every other This is the usual case for streaming transfers 7 8 ACK splitting Performance Effects of Acking Policies How do delayed ACKs affect performance Increases RTT Window slides a bit later throughput a bit lower How does ack every other affect performance If sender adjusts CWND on incoming ACKs then CWND opens more slowly In slow start 50 increase RTT rather than 100 In congestion avoidance 1 MSS 2 RTT not 1 MSS RTT What does this suggest about how a receiver might cheat and speed up a transfer Sender Receiver Data 1 1461 Rule grow window by one 6 full sized packet for each ACK 48 3 valid ACK received ACK 97 61 ACK 14 Send M distinct ACKs for Data 1 461 29 one packet 21 Data 2 921 43 8 1 Data 4 Growth factor proportional 381 58 41 to M Data 5 841 73 01 What s the fix RoundTrip Time RTT 9 10 line change to Linux TCP 10 Sequence Plot for an Entire Transfer Page fetch from CNN com Sequence Number bytes 60000 Why does this transfer only achieve 50 KB s 50000 40000 Courtesy of Stefan Savage 30000 20000 Modified Client Normal Client 10000 0 0 0 2 0 4 0 6 Time sec 0 8 1 11 12 2 Mid Transfer Self Clocking Beginning of Transfer Slow Start Each flight of packets has the same shape Q Why a gap here A That packet is still in flight Q What is this first small packet A The initial SYN Q Why the long RTT As do the ACKs A Delayed ack just for 1 MSS 13 Sliding Window induces Self Clocking 14 Mid Transfer Why Doesn t CWND Grow Bottleneck link stretches out data packets Next flight of packets goes Spacing is preserved upon arrival out with bottleneck s spacing and hence in the ACKs From JK88 15 16 Same Transfer w Large Recv Window Receiver Window 8 MSS Circles show advertised window Throughput doubles But why isn t sender using entire window 17 18 3 Same Transfer w Large Recv Window Sliding Window Allow a larger amount of data in flight Allow sender to get ahead of the receiver though not too far ahead Sending process TCP Last byte written Sender s window is 9 2 KB about double receiver s Receiving process TCP Last byte read Sender has Next byte expected limited amount of kernel buffer Last byte received Last byte sent Last byte ACKed 19 20 Same Transfer w Large Snd Window Short term throughput again goes up But what happens here 5 Minute Break Questions Before We Proceed 21 Detecting Loss Timeout 22 Detecting Loss Timeout Recv View 23 24 4 Timeout and Effect of SSThresh Illustration of Exponential Backoff We finally increment Prior to timeout CWND in Cong Avoid CWND 8 MSS After timeout CWND 1 MSS SSThresh 4 MSS 63 8 sec 47 9 sec 23 8 sec Slow Start until CWND 4 MSS then Cong Avoidance RTO progresses 1 8 3 0 6 0 12 0 sec 25 How Many Packets Were Lost 26 Answer Zero 27 Fast Retransmission 28 Same Fast Retransmission Recv Again arrivals much more smooth due to bottleneck shaping After pending data ack d slow start CWND 2 MSS since ACK arrival incremented it by MSS Window stays at 5 MSS transition to Congestion Avoidance What happened here Third dup triggers retransmission 29 30 5 Fast Retransmit Loss of Performance Effectiveness of Fast Retransmit When does Fast Retransmit work best Long data transfers High likelihood of many packets in flight High window size High likelihood of many packets in flight Big juicy pre loss throughput takes a large hit even given slow start to open up CWND again Low burstiness in packet losses Higher likelihood that later packets arrive successfully Implications for Web traffic Most Web transfers are short e g 10 packets Short HTML files or small images So often there aren t many packets in flight making fast retransmit less likely to kick in Forcing users to like reload more often 31 Fast Recovery Algorithm 32 Fast Rexmit Recovery with 1 Loss As more dups arrive CWND is inflated eventually allowing more data to be sent After 3 dups subsequent dups indicate packets are leaving the network After pending data ack d window is set to SSTHRESH deflated Packet resent due to Fast Retransmit is ack d but not beyond it At this point progress stalls Connection proceeds at half prev rate until timeout followed by Slow Start 33 Same From Receiver Perspective 34 Summary of TCP Mechanisms Delayed Acknowledgment Many packets are retransmitted unnecessarily which also causes more dups Lessens overhead 40 bytes per ACK But can cause CWND to grow more slowly Fast Retransmit NACK based loss detection in 1 RTT Avoids timeout delay AIMD after subsequent Slow Start reaches SSTHRESH Significant holes in original arrivals Fast Recovery Fix Selective Acknowledgment SACK option Sender learns just what receiver has received Avoids needing to Slow Start after Fast Retransmit True AIMD Avoids both timeout on second loss and unnecessary rexmits SACK Both
View Full Document
Unlocking...