Announcements. TCP Performance. Time-Sequence Plots. Goals of Today s Lecture. Example of Time-Sequence Plot. Example of Time-Sequence Plot

Please download to get full document.

View again

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report



Views: 0 | Pages: 8

Extension: PDF | Download: 0

Related documents
Announcements TCP Performance Be sure to look over & comprehend the TCP congestion control pseudo-code sent to the mailing list Including small fix sent subsequently EE 122: Intro to Communication Networks
Announcements TCP Performance Be sure to look over & comprehend the TCP congestion control pseudo-code sent to the mailing list Including small fix sent subsequently EE 122: Intro to Communication Networks Fall 2007 (WF 4-5:30 in Cory 277) Vern Paxson TAs: Lisa Fowler, Daniel Killebrew & Jorge Ortiz Reminder: Homework #3 due 3:50PM Phase 1 of Project #2 due 11PM Materials with thanks to Jennifer Rexford, Ion Stoica, and colleagues at Princeton and UC Berkeley 1 2 Goals of Today s Lecture A look at a range of TCP mechanisms that influence its behavior & performance: Window limitations Timeout, slow start, exponential backoff Acking policies Fast Retransmit Fast Recovery (full AIMD) Window scaling Visualized using time-sequence plots 3 Time-Sequence Plots Powerful tool for visualizing transport protocol dynamics Plot sequence number (Y axis) vs. time (X axis) For data packet, sequence number = header seqno + payload length o i.e., seqno that would appear in an ACK if payload is in-sequence 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 tshark or tcpdump Illuminates performance achieved & why As well as problems o Both network and in endpoint stacks o (and also beware measurement errors) 4 Example of Time-Sequence Plot 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? Note: Receiver acks every other segment Delayed Acknowledgments Receiver generally delays sending an ACK Upon receiving a packet, sets a timer o Typically, 200 msec; at most, 500 msec If application generates data, go ahead and send o 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 ) o This is the usual case for streaming transfers 7 8 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 o In slow start, 50% increase/rtt rather than 100% o 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? 9 ACK-splitting Round- Trip Time (RTT) Sender Data 1:1461 ACK 486 ACK 973 ACK 1461 Data 1461:2921 Data 2921:4381 Data 4381:5841 Data 5841:7301 Receiver Rule: grow window by one full-sized packet for each valid ACK received Send M (distinct) ACKs for one packet Growth factor proportional to M What s the fix? line change to Linux TCP Sequence Plot for an Entire Transfer Page fetch from Sequence Number (bytes) Modified Client Normal Client (Courtesy of Stefan Savage) Why does this transfer only achieve 50 KB/s? Time (sec) Beginning of Transfer - Slow Start Mid-Transfer: Self-Clocking 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? A: Delayed ack (just for 1 MSS) As do the ACKs Sliding Window induces Self-Clocking Mid-Transfer: Why Doesn t CWND Grow? Bottleneck link stretches out data packets Next flight of packets goes out with bottleneck s spacing Spacing is preserved upon arrival and hence in the ACKs Bottleneck doesn t subsequently affect ACK spacing (From [JK88]) Receiver Window = 8 MSS Same Transfer w/ Large Recv. Window Circles show advertised window Throughput doubles But why isn t sender using entire window? Ample window Sliding Window Allow a larger amount of data in flight Allow sender to get ahead of the receiver though not too far ahead Same Transfer w/ Large Recv. Window Sender s window is 9.2 KB (about double receiver s) Sending process Receiving process TCP Last byte written TCP Last byte read Sender has Next byte expected Last byte ACKed limited amount of kernel buffer Last byte received Last byte sent Same Transfer w/ Large Snd. Window Short-term throughput again goes up But what happens here? 5 Minute Break Questions Before We Proceed? Detecting Loss: Timeout Detecting Loss: Timeout - Recv. View 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 47.9 sec 63.8 sec 23.8 sec Slow Start until CWND 4 MSS, then Cong. Avoidance RTO progresses 1.8*, 3.0, 6.0, 12.0 sec How Many Packets Were Lost? Answer: Zero! Fast Retransmission Same Fast Recv. After pending data ack d, slow start. CWND = 2 MSS since ACK arrival incremented it by MSS Again, arrivals much more smooth due to bottleneck shaping Window stays at 5 MSS transition to Congestion Avoidance What happened here? Third dup triggers retransmission Effectiveness of Fast Retransmit When does Fast Retransmit work best? Long data transfers o High likelihood of many packets in flight Large window size o High likelihood of many packets in flight Low burstiness in packet losses o Higher likelihood that later packets arrive successfully Implications for Web traffic Most Web transfers are short (e.g., 10 packets) o 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 Retransmit & Loss of Performance Big juicy pre-loss throughput takes a large hit, even given slow-start to open up CWND again 32 Fast Recovery Algorithm 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). Connection proceeds at half prev. rate Packet resent due to Fast Retransmit is ack d, but not beyond it. At this point, progress stalls. until timeout (followed by Slow Start) Same From Receiver Perspective Significant holes in original arrivals Many packets are retransmitted unnecessarily (which also causes more dups) Fix: Selective Acknowledgment (SACK) option. Sender learns just what receiver has received. Avoids both timeout on second loss, and unnecessary rexmits. 35 Summary of TCP Mechanisms Delayed Acknowledgment 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 Fast Recovery Avoids needing to Slow Start after Fast Retransmit True AIMD SACK Both speeds recovery and avoids unnecessary rexmit. 36 6 A Precautionary Tale Different Problem. What s up now? Is this a measurement drop? What s the evidence? What s strange about this ACK? Going Fast Window Scaling Option (RFC 1323) Q: on a path with RTT = 100 msec, what s the absolute fastest rate that TCP can achieve? Q: what s the absolute largest sliding window that TCP can use? A: advertised window is 16 bits 65,535 bytes Thus: max speed = 65,535 bytes / 100 msec = 655 KB/s Q: how can we fix this problem? A: we need a larger window Q: how do we make the window larger? A: using a TCP option HdrLen specifies 4 bytes of options. Kind=3 indicates Window Scaling. Kind=0 indicates end of options. Len=6 Source port 0 Sequence number Acknowledgment Flags Destination port Advertised window Checksum Urgent pointer Kind=3 Length=3 shift.cnt Kind= Data Window Scaling, con t Window Scaling, con t Sent in initial SYN If server s SYN-ACK also includes a Window Scaling option, then scaling is in effect The server including the option confirms its use shift.cnt specifies scaling factor for units used in window advertisement E.g., shift.cnt = 5 advertised window is 2 5 = 32-byte units Q: Now how large can the window be? A: Clearly, must not exceed 2 32 If it does, then can t disambiguate data in flight So, scaling 16 In fact, somewhat subtle requirements limit window to 2 30 to allow receiver to determine whether data fits in the offered window So, scaling Window Scaling, con t Now we can go fast. Suppose high-speed LAN, RTT = 1 msec. How fast can we transmit? 1 GB/msec = 1 TB/sec. What problem arises if packets are occasionally delayed in the network for 10 msec? Sequence number wrap: can t tell earlier, delayed segments from later instances. Fix: another TCP option to associate (high-res) timestamps with TCP segments Essentially, adds more bits to sequence space (Side effect: no more need for Karn/Partridge restriction not to compute RTT for ACKs of retransmitted packets) 43 Summary Time-Sequence plots provide a powerful tool for visualizing TCP behavior & performance Spectrum of TCP mechanisms influence performance Advertised window, sender window Timeout, slow start, exponential backoff Acking policy (delayed; ack-splitting) Fast Retransmit (avoid RTO stall) Fast Recovery (full AIMD) Window scaling (required for large bandwidth-delay product) Next lecture: a broader view of performance 44 8
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks