15-744: Computer NetworkingTCP BasicsKey Things You Should Know AlreadyOverviewIntroduction to TCPEvolution of TCPTCP Through the 1990sWhat’s Different From Link Layers?Timeout-based RecoveryInitial Round-trip EstimatorJacobson’s Retransmission TimeoutRetransmission AmbiguityKarn’s RTT EstimatorTimestamp ExtensionTimer GranularityDelayed ACKSSlide 17TCP FlavorsFast RetransmitSlide 20Multiple LossesTahoeTCP Reno (1990)RenoNewRenoSlide 26SACKSlide 28Performance IssuesSlide 30CongestionCauses & Costs of CongestionSlide 33Congestion CollapseOther Congestion Collapse CausesWhere to Prevent Collapse?Congestion Control and AvoidanceSlide 38ObjectivesBasic Control ModelLinear ControlPhase plotsSlide 43Additive Increase/DecreaseMultiplicative Increase/DecreaseConvergence to EfficiencyDistributed Convergence to EfficiencyConvergence to FairnessConvergence to Efficiency & FairnessIncreaseConstraintsWhat is the Right Choice?Slide 53TCP Congestion ControlTCP Congestion Control - SolutionsSlide 56AIMDImplementation IssueCongestion AvoidanceCongestion Avoidance Sequence PlotCongestion Avoidance BehaviorPacket ConservationTCP Packet PacingReaching Steady StateSlow Start Packet PacingSlow Start ExampleSlow Start Sequence PlotReturn to Slow StartTCP Saw Tooth BehaviorHow to Change WindowFast RecoveryFast RecoveryNewReno ChangesRate Halving RecoveryDelayed Ack ImpactSlide 76TCP ModelingOverall TCP BehaviorSimple TCP ModelSimple Loss ModelTCP FriendlinessTCP PerformanceSlide 83Single TCP Flow Router without buffersSummary Unbuffered LinkSlide 86Slide 87Single TCP Flow Router with large enough buffers for full link utilizationSummary Buffered LinkExampleRule-of-thumbIf flows are synchronizedIf flows are not synchronizedCentral Limit TheoremRequired buffer sizeImportant LessonsNext Lecture15-744: Computer NetworkingL-4 TCPL -4; 10-7-04© Srinivasan Seshan, 2004 2TCP Basics•TCP reliability•Congestion control basics•TCP congestion control•Assigned reading•[JK88] Congestion Avoidance and Control•[CJ89] Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks•[FF96] Simulation-based Comparisons of Tahoe, Reno, and SACK TCP•[FHPW00] Equation-Based Congestion Control for Unicast ApplicationsL -4; 10-7-04© Srinivasan Seshan, 2004 3Key Things You Should Know Already•Port numbers•TCP/UDP checksum•Sliding window flow control•Sequence numbers•TCP connection setupL -4; 10-7-04© Srinivasan Seshan, 2004 4Overview•TCP reliability: timer-driven•TCP reliability: data-driven•Congestion sources and collapse•Congestion control basics•TCP congestion control•TCP modelingL -4; 10-7-04© Srinivasan Seshan, 2004 5Introduction to TCP•Communication abstraction:•Reliable•Ordered•Point-to-point•Byte-stream•Full duplex•Flow and congestion controlled•Protocol implemented entirely at the ends•Fate sharing•Sliding window with cumulative acks•Ack field contains last in-order packet received•Duplicate acks sent when out-of-order packet receivedL -4; 10-7-04© Srinivasan Seshan, 2004 6Evolution of TCP1975 1980198519901982TCP & IPRFC 793 & 7911974TCP described byVint Cerf and Bob KahnIn IEEE Trans Comm1983BSD Unix 4.2supports TCP/IP1984Nagel’s algorithmto reduce overheadof small packets;predicts congestion collapse1987Karn’s algorithmto better estimate round-trip time1986Congestion collapseobserved1988Van Jacobson’s algorithmscongestion avoidance and congestion control(most implemented in 4.3BSD Tahoe)19904.3BSD Renofast retransmitdelayed ACK’s1975Three-way handshakeRaymond TomlinsonIn SIGCOMM 75L -4; 10-7-04© Srinivasan Seshan, 2004 7TCP Through the 1990s1993199419961994ECN(Floyd)Explicit CongestionNotification1993TCP Vegas (Brakmo et al)real congestion avoidance1994T/TCP(Braden)TransactionTCP1996SACK TCP(Floyd et al)Selective Acknowledgement1996HoeImproving TCP startup1996FACK TCP(Mathis et al)extension to SACKL -4; 10-7-04© Srinivasan Seshan, 2004 8What’s Different From Link Layers?•Logical link vs. physical link•Must establish connection•Variable RTT•May vary within a connection•Reordering•How long can packets live max segment lifetime•Can’t expect endpoints to exactly match link•Buffer space availability•Transmission rate•Don’t directly know transmission rateL -4; 10-7-04© Srinivasan Seshan, 2004 9Timeout-based Recovery•Wait at least one RTT before retransmitting•Importance of accurate RTT estimators:•Low RTT unneeded retransmissions•High RTT poor throughput•RTT estimator must adapt to change in RTT•But not too fast, or too slow!•Spurious timeouts•“Conservation of packets” principle – more than a window worth of packets in flightL -4; 10-7-04© Srinivasan Seshan, 2004 10Initial Round-trip Estimator•Round trip times exponentially averaged:•New RTT = (old RTT) + (1 - ) (new sample)•Recommended value for : 0.8 - 0.9•0.875 for most TCP’s•Retransmit timer set to RTT, where = 2•Every time timer expires, RTO exponentially backed-off•Like Ethernet•Not good at preventing spurious timeoutsL -4; 10-7-04© Srinivasan Seshan, 2004 11Jacobson’s Retransmission Timeout•Key observation:•At high loads round trip variance is high•Solution:•Base RTO on RTT and standard deviation or RRTT•rttvar = * dev + (1- )rttvar•dev = linear deviation •Inappropriately named – actually smoothed linear deviationL -4; 10-7-04© Srinivasan Seshan, 2004 12Retransmission AmbiguityA BACKSampleRTTOriginal transmissionretransmissionRTOA BOriginal transmissionretransmissionSampleRTTACKRTOXL -4; 10-7-04© Srinivasan Seshan, 2004 13Karn’s RTT Estimator•Accounts for retransmission ambiguity•If a segment has been retransmitted:•Don’t count RTT sample on ACKs for this segment•Keep backed off time-out for next packet•Reuse RTT estimate only after one successful transmissionL -4; 10-7-04© Srinivasan Seshan, 2004 14Timestamp Extension•Used to improve timeout mechanism by more accurate measurement of RTT•When sending a packet, insert current timestamp into option•4 bytes for seconds, 4 bytes for microseconds•Receiver echoes timestamp in ACK•Actually will echo whatever is in timestamp•Removes retransmission ambiguity•Can get RTT sample on any packetL -4; 10-7-04© Srinivasan Seshan, 2004 15Timer Granularity•Many TCP implementations set RTO in multiples of 200,500,1000ms•Why?•Avoid spurious timeouts – RTTs can
View Full Document
Unlocking...