11TCP PerformanceEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Be sure to look over & comprehend the TCPcongestion control pseudo-code sent to themailing list– Including small fix sent subsequently• Reminder:– Homework #3 due Friday @ 3:50PM– Phase 1 of Project #2 due Tuesday @ 11PM3Goals of Today’s Lecture• A look at a range of TCP mechanisms thatinfluence its behavior & performance:– Window limitations– Timeout, slow start, exponential backoff– Acking policies– Fast Retransmit– Fast Recovery (full AIMD)– Window scaling• Visualized using time-sequence plots4Time-Sequence Plots• Powerful tool for visualizing transport protocoldynamics• Plot sequence number (Y axis) vs. time (X axis)– For data packet, sequence number = header seqno + payload lengtho 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 problemso Both network and in endpoint stackso (and also beware measurement errors)5Example of Time-Sequence PlotHollow squares = AcksSolid squares = DataMSSWindowRTT6Example of Time-Sequence PlotSlope gives overall throughput (bytes/sec)27Same Connection - Why So Different?Note: Receiver acks every other segment8Delayed Acknowledgments• Receiver generally delays sending an ACK– Upon receiving a packet, sets a timero Typically, 200 msec; at most, 500 msec– If application generates data, go ahead and sendo 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 full-sized packet (“ack every other”)o This is the usual case for “streaming” transfers9Performance 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 CWNDopens more slowlyo 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 receivermight cheat and speed up a transfer?10Round-TripTime(RTT)Sender ReceiverACK 486Data 4381:5841Data 1461:2921Data 2921:4381Data 5841:7301ACK 973ACK 1461Data 1:1461• Rule: grow window by one full-sized packet for each valid ACK received• Send M (distinct) ACKs forone packet• Growth factor proportional to M• What’s the fix?ACK-splitting11Page fetch from CNN.com01000020000300004000050000600000 0.2 0.4 0.6 0.8 1Time (sec)Sequence Number (bytes)Modified ClientNormal Client10 line change to Linux TCP(Courtesy ofStefan Savage)12Sequence Plot for an Entire TransferWhy does this transferonly achieve 50 KB/s?313Beginning of Transfer - Slow StartQ: What is this first small packet?A: The initial SYNQ: Why a gap here?A: That packet is still in flightQ: Why the long RTT?A: Delayed ack (just for 1 MSS)14Mid-Transfer: Self-ClockingEach flight of packets has thesame shape!As do the ACKs …15Sliding Window induces Self-Clocking(From [JK88])Bottleneck doesn’tsubsequently affectACK spacingSpacing is preserved upon arrival …… and hence in the ACKsNext flight of packets goesout with bottleneck’s spacingBottleneck link stretchesout data packets16Mid-Transfer: Why Doesn’t CWND Grow?17Receiver Window = 8 MSSCircles show advertised window18Same Transfer w/ Large Recv. WindowThroughput doubles …But why isn’t sender usingentire window?Amplewindow419Sliding Window• Allow a larger amount of data “in flight”– Allow sender to get ahead of the receiver– … though not too far aheadSending process Receiving processLast byte ACKedLast byte sentTCPTCPNext byte expectedLast byte writtenLast byte readLast byte receivedSender haslimited amountof kernel buffer20Same Transfer w/ Large Recv. WindowSender’s window is 9.2 KB(about double receiver’s)21Same Transfer w/ Large Snd. WindowBut what happens here?Short-term throughputagain goes up …225 Minute BreakQuestions Before We Proceed?23Detecting Loss: Timeout24Detecting Loss: Timeout - Recv. View525Timeout and Effect of SSThreshPrior to timeout,CWND = 8 MSSAfter timeout,CWND = 1 MSS,SSThresh = 4 MSSWe finally incrementCWND in Cong. AvoidSlow Start untilCWND > 4 MSS, thenCong. Avoidance26Illustration of Exponential BackoffRTO progresses 1.8*,3.0, 6.0, 12.0 sec23.8 sec47.9 sec63.8 sec27How Many Packets Were Lost?28Answer: Zero!29Fast RetransmissionWindow stays at 5 MSS⇒ transition toCongestion AvoidanceAfter pending data ack’d,slow start. CWND = 2 MSSsince ACK arrivalincremented it by MSSThird dup triggers retransmission30Same Fast Retransmission @ Recv.What happened here?Again, arrivals muchmore smooth due tobottleneck shaping631Effectiveness of Fast Retransmit• When does Fast Retransmit work best?– Long data transferso High likelihood of many packets in flight– Large window sizeo High likelihood of many packets in flight– Low burstiness in packet losseso 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…32Fast Retransmit & Loss of PerformanceBig juicy pre-lossthroughput takes a largehit, even given slow-startto open up CWND again33Fast Recovery AlgorithmAfter 3 dups, subsequentdups indicate packetsare leaving the network.After pendingdata ack’d,window is setto SSTHRESH(deflated).Connectionproceeds athalf prev. rateAs more dups arrive, CWNDis “inflated”, eventuallyallowing more data to be sent34Fast Rexmit/Recovery with > 1 LossPacket resent due to Fast Retransmit isack’d, but not beyond it. At this point,progress stalls ……. until timeout (followed by Slow Start).35Same From Receiver PerspectiveFix: Selective Acknowledgment (SACK) option.Sender learns just what receiver has
View Full Document
Unlocking...