DOC PREVIEW
CMU CS 15744 - TCP Basics

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

TCP Basics 15 744 Computer Networking 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 Applications L 4 TCP Srinivasan Seshan 2004 L 4 10 7 04 Key Things You Should Know Already Overview Port numbers TCP UDP checksum Sliding window flow control TCP reliability timer driven 2 TCP reliability data driven Sequence numbers Congestion sources and collapse TCP connection setup Congestion control basics TCP congestion control TCP modeling Srinivasan Seshan 2004 L 4 10 7 04 3 Srinivasan Seshan 2004 L 4 10 7 04 4 1 Introduction to TCP Evolution of TCP Communication abstraction Reliable Ordered Point to point Byte stream Full duplex Flow and congestion controlled 1984 Nagel s algorithm to reduce overhead of small packets predicts congestion collapse 1975 Three way handshake Raymond Tomlinson In SIGCOMM 75 1983 BSD Unix 4 2 supports TCP IP 1974 TCP described by Vint Cerf and Bob Kahn In IEEE Trans Comm Protocol implemented entirely at the ends 1987 Karn s algorithm to better estimate round trip time 1986 Congestion collapse observed 1982 TCP IP Fate sharing RFC 793 791 1990 4 3BSD Reno fast retransmit delayed ACK s 1988 Van Jacobson s algorithms congestion avoidance and congestion control most implemented in 4 3BSD Tahoe Sliding window with cumulative acks Ack field contains last in order packet received Duplicate acks sent when out of order packet received Srinivasan Seshan 2004 L 4 10 7 04 1975 5 TCP Through the 1990s 1980 Srinivasan Seshan 2004 1985 1990 L 4 10 7 04 6 What s Different From Link Layers Logical link vs physical link 1994 T TCP Braden Transaction TCP 1993 TCP Vegas Brakmo et al real congestion avoidance 1994 ECN Floyd Explicit Congestion Notification Must establish connection 1996 SACK TCP Floyd et al Selective Acknowledgement 1996 Hoe Improving TCP startup Variable RTT May vary within a connection 1996 FACK TCP Mathis et al extension to SACK Reordering How long can packets live max segment lifetime Can t expect endpoints to exactly match link Buffer space availability Transmission rate 1993 Srinivasan Seshan 2004 1994 1996 L 4 10 7 04 Don t directly know transmission rate 7 Srinivasan Seshan 2004 L 4 10 7 04 8 2 Timeout based Recovery Initial Round trip Estimator Wait at least one RTT before retransmitting Importance of accurate RTT estimators Round trip times exponentially averaged New RTT old RTT 1 new sample Recommended value for 0 8 0 9 Low RTT unneeded retransmissions High RTT poor throughput 0 875 for most TCP s Retransmit timer set to RTT where 2 RTT estimator must adapt to change in RTT Every time timer expires RTO exponentially backed off Like Ethernet But not too fast or too slow Spurious timeouts Not good at preventing spurious timeouts Conservation of packets principle more than a window worth of packets in flight Srinivasan Seshan 2004 L 4 10 7 04 9 Jacobson s Retransmission Timeout Srinivasan Seshan 2004 L 4 10 7 04 10 Retransmission Ambiguity Key observation At high loads round trip variance is high A Solution Base RTO on RTT and standard deviation or RRTT rttvar dev 1 rttvar Sample RTT L 4 10 7 04 A retran smiss ion B Original trans m ission X RTO RTO Sample RTT ission ACK retran smiss ion ACK dev linear deviation Inappropriately named actually smoothed linear deviation Srinivasan Seshan 2004 B Original trans m 11 Srinivasan Seshan 2004 L 4 10 7 04 12 3 Karn s RTT Estimator Timestamp Extension Accounts for retransmission ambiguity If a segment has been retransmitted Used to improve timeout mechanism by more accurate measurement of RTT When sending a packet insert current timestamp into option 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 transmission 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 packet Srinivasan Seshan 2004 L 4 10 7 04 13 Srinivasan Seshan 2004 Timer Granularity Delayed ACKS Many TCP implementations set RTO in multiples of 200 500 1000ms Why Problem L 4 10 7 04 14 In request response programs you send separate ACK and Data packets for each transaction Avoid spurious timeouts RTTs can vary quickly due to cross traffic Make timers interrupts efficient Srinivasan Seshan 2004 L 4 10 7 04 Solution 15 Don t ACK data immediately Wait 200ms must be less than 500ms why Must ACK every other packet Must not delay duplicate ACKs Srinivasan Seshan 2004 L 4 10 7 04 16 4 Overview TCP Flavors TCP reliability timer driven Tahoe Reno Vegas differ in data driven reliability TCP Tahoe distributed with 4 3BSD Unix TCP reliability data driven Original implementation of Van Jacobson s mechanisms VJ paper Includes Congestion sources and collapse Congestion control basics Slow start Congestion avoidance Fast retransmit TCP congestion control TCP modeling Srinivasan Seshan 2004 L 4 10 7 04 17 Fast Retransmit Srinivasan Seshan 2004 L 4 10 7 04 18 Fast Retransmit What are duplicate acks dupacks Repeated acks for the same sequence When can duplicate acks occur Loss Packet re ordering Window update advertisement of new flow control window Retransmission X Duplicate Acks Sequence No Assume re ordering is infrequent and not of large magnitude Use receipt of 3 or more duplicate acks as indication of loss Don t wait for timeout to retransmit packet Time Srinivasan Seshan 2004 L 4 10 7 04 19 Srinivasan Seshan 2004 L 4 10 7 04 20 5 Multiple Losses Tahoe X X X X X X Now what X Retransmission X Duplicate Acks Sequence No Sequence No Time Srinivasan Seshan 2004 L 4 10 7 04 Time 21 TCP Reno 1990 Srinivasan Seshan 2004 L 4 10 7 04 22 Reno All mechanisms in Tahoe Addition of fast recovery X X Opening up congestion window after fast retransmit X Delayed acks Header prediction X Now what timeout Sequence No Implementation designed to improve performance Has common case code inlined With multiple losses Reno typically timeouts because it does not receive enough duplicate acknowledgements Time Srinivasan Seshan 2004 L 4 10 7 04 23 Srinivasan Seshan 2004 L 4 10 7 04 24 6 NewReno NewReno The ack that arrives after retransmission partial ack should indicate that a second loss occurred


View Full Document

CMU CS 15744 - TCP Basics

Documents in this Course
Lecture

Lecture

25 pages

Lecture

Lecture

10 pages

Lecture

Lecture

10 pages

Lecture

Lecture

45 pages

Lecture

Lecture

48 pages

Lecture

Lecture

19 pages

Lecture

Lecture

97 pages

Lecture

Lecture

39 pages

Lecture

Lecture

49 pages

Lecture

Lecture

33 pages

Lecture

Lecture

21 pages

Lecture

Lecture

52 pages

Problem

Problem

9 pages

Lecture

Lecture

6 pages

03-BGP

03-BGP

13 pages

Lecture

Lecture

42 pages

lecture

lecture

54 pages

lecture

lecture

21 pages

Lecture

Lecture

18 pages

Lecture

Lecture

18 pages

Lecture

Lecture

58 pages

lecture

lecture

17 pages

lecture

lecture

46 pages

Lecture

Lecture

72 pages

Lecture

Lecture

44 pages

Lecture

Lecture

13 pages

Lecture

Lecture

22 pages

Lecture

Lecture

48 pages

lecture

lecture

73 pages

17-DNS

17-DNS

52 pages

Lecture

Lecture

10 pages

lecture

lecture

53 pages

lecture

lecture

51 pages

Wireless

Wireless

27 pages

lecture

lecture

14 pages

lecture

lecture

18 pages

Lecture

Lecture

16 pages

Lecture

Lecture

14 pages

lecture

lecture

16 pages

Lecture

Lecture

16 pages

Lecture

Lecture

37 pages

Lecture

Lecture

44 pages

Lecture

Lecture

11 pages

Lecture

Lecture

61 pages

Multicast

Multicast

61 pages

Lecture

Lecture

19 pages

Lecture

Lecture

8 pages

Lecture

Lecture

81 pages

Lecture

Lecture

9 pages

Lecture

Lecture

6 pages

Lecture

Lecture

63 pages

Lecture

Lecture

13 pages

Lecture

Lecture

63 pages

Lecture

Lecture

50 pages

lecture

lecture

35 pages

Lecture

Lecture

47 pages

Lecture

Lecture

29 pages

Lecture

Lecture

92 pages

Load more
Download TCP Basics
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view TCP Basics and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view TCP Basics 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?