Introduction to TCP: Day 1

Jamshid Mahdavi, mahdavi@novell.com
Shawn Ostermann, ostermann@cs.ohiou.edu

Outline

Internet Protocol Stack and Network Layers
The end to end argument
Duties of the Transport Layer
TCP Packet Format
The TCP state machine
Introduction to TCP tracing tools: tcpdump, tptrace, xplot
Sliding Window Flow Control
Loss detection and recovery
Congestion control
Lunch
Lab
Lab discussion; introduction to new developments for TCP
Denial of service

 TCP Header Format (from RFC 793)

                                    
    0                   1                   2                   3   
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   
   |          Source Port          |       Destination Port        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Sequence Number                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Acknowledgment Number                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Data |           |U|A|P|R|S|F|                               |
   | Offset| Reserved  |R|C|S|S|Y|I|            Window             |
   |       |           |G|K|H|T|N|N|                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Checksum            |         Urgent Pointer        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Options                    |    Padding    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             data                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                            TCP Header Format

          Note that one tick mark represents one bit position.

                               Figure 3.

From 793 +---------+ ---------\ active OPEN | CLOSED | \ ----------- +---------+<---------\ \ create TCB | ^ \ \ snd SYN passive OPEN | | CLOSE \ \ ------------ | | ---------- \ \ create TCB | | delete TCB \ \ V | \ \ +---------+ CLOSE | \ | LISTEN | ---------- | | +---------+ delete TCB | | rcv SYN | | SEND | | ----------- | | ------- | V +---------+ snd SYN,ACK / \ snd SYN +---------+ | |<----------------- ------------------>| | | SYN | rcv SYN | SYN | | RCVD |<-----------------------------------------------| SENT | | | snd ACK | | | |------------------ -------------------| | +---------+ rcv ACK of SYN \ / rcv SYN,ACK +---------+ | -------------- | | ----------- | x | | snd ACK | V V | CLOSE +---------+ | ------- | ESTAB | | snd FIN +---------+ | CLOSE | | rcv FIN V ------- | | ------- +---------+ snd FIN / \ snd ACK +---------+ | FIN |<----------------- ------------------>| CLOSE | | WAIT-1 |------------------ | WAIT | +---------+ rcv FIN \ +---------+ | rcv ACK of FIN ------- | CLOSE | | -------------- snd ACK | ------- | V x V snd FIN V +---------+ +---------+ +---------+ |FINWAIT-2| | CLOSING | | LAST-ACK| +---------+ +---------+ +---------+ | rcv ACK of FIN | rcv ACK of FIN | | rcv FIN -------------- | Timeout=2MSL -------------- | | ------- x V ------------ x V \ snd ACK +---------+delete TCB +---------+ ------------------------>|TIME WAIT|------------------>| CLOSED | +---------+ +---------+ TCP Connection State Diagram Figure 6.

References

Textbooks:
- W. R. Stevens, TCP/IP Illustrated, Volume 1: The Protocols, Addison-Wesley, 1994.
- D. Comer, Internetworking with TCP/IP, Volume 1, Prentice Hall, 1991.
- L. L. Peterson and S. Davie, Computer Networks: A Systems Approach, Morgan Kaufman, 1996.
TCP Standards RFCs:
- RFC793: Transmission Control Protocol
- RFC896: Congestion control in IP/TCP internetworks
- RFC1191: Path MTU Discovery
- RFC1323: TCP Extensions for High Performance
- RFC1644: T/TCP -- TCP Extensions for Transactions Functional Specification
- RFC2018: TCP Selective Acknowledgement Options
- RFC2140: TCP Control Block Interdependence
- RFC2398: Some Testing Tools for TCP Implementors
- RFC2525: Known TCP Implementation Problems
- RFC2581: TCP Congestion Control
- RFC2582: The NewReno Modification to TCP's Fast Recovery Algorithm
- draft-paxson-tcp-rto-01.txt: Computing TCP's Retransmission Timer
- draft-handley-tcp-cwv-02.txt: TCP Congestion Window Validation
- draft-floyd-sack-00.txt: An Extension to the Selective Acknowledgement (SACK) Option for TCP
- draft-allman-tcp-lossrec-00.txt: Enhancing TCP's Loss Recovery Using Early Duplicate Acknowledgment Response
- draft-ietf-sigtran-sctp-10.txt: Stream Control Transmission Protocol
- Pilc Working Group Charter: This includes references to several good works in progress on TCP protocol behavior under various conditions. http://www.ietf.org/html.charters/pilc-charter.html
TCP Design and Behavior:
- J.H Saltzer, D.P. Reed, and D.D. Clark. End-to-End Arguments in System Design. ACM Transactions on Computer Systems, 2(4):195-206, 1984.
- Floyd, S., Connections with Multiple Congested Gateways in Packet-Switched Networks Part 1: One-way Traffic. Computer Communication Review, Vol.21, No.5, October 1991, p. 30-47. ftp://ftp.ee.lbl.gov/papers/gates1.ps.Z
- L. Zhang, S. Shenker, and D.D. Clark. Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic. Proc. of ACM SIGCOMM '91, pages 133-147, Sep. 1991.
- Fall, K., and Floyd, S., Simulation-based Comparisons of Tahoe, Reno, and SACK TCP. Computer Communication Review, V. 26 N. 3, July 1996, pp. 5-21. This is a revised version of Comparisons of Tahoe, Reno, and Sack TCP. Technical report, December 1995. http://www.aciri.org/floyd/papers/sacks.ps.Z
- K. Fall and S. Floyd. Simulation-based Comparisons of Tahoe, Reno, and SACK TCP. ACM Computer Communication Review, 26(3):5-21, Jul. 96.
- M. Mathis, J. Semke, J. Mahdavi, T. Ott, The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm,Computer Communication Review, volume 27, number 3, pp. 67-82, July 1997. http://www.psc.edu/networking/papers/model_ccr97.ps
- V. Paxson. End-to-End Internet Packet Dynamics. Proc. of ACM SIGCOMM '97, Sep. 1997.
- Hari Balakrishnan, Venkata N. Padmanabhan and Randy H. Katz, The Effects of Asymmetry on TCP Performance, in Proc. of 3rd ACM/IEEE Intl. Conference on Mobile Computing and Networking (MobiCom), (Budapest, Hungary), Sep. 1997.
- Stefan Savage, Neal Cardwell, David Wetherall and Tom Anderson, TCP Congestion Control with a Misbehaving Receiver, ACM Computer Communication Review, vol. 29, no. 3, Oct. 1999.
- R. Ludwig, B. Rathonyi, A. Konrad, K. Oden, and A. Joseph, Multi-layer Tracing of TCP over a Reliable Wireless Link. In Proceedings of ACM SIGMETRICS 1999 (Atlanta, GA, May 1999).
- Neal Cardwell, Stefan Savage and Thomas Anderson, Modeling TCP Latency, in Proceedings of the Conference on Computer Communications (IEEE Infocom), (Tel Aviv, Israel), Mar. 2000.
Derivations of TCP Performance:
- Teunis J.Ott, J.H.B. Kemperman and Matt Mathis, Window Size Behavior in TCP/IP with Constant Loss Probability, November 1996. This paper is a revision of The Stationary Behavior of Ideal TCP Congestion Avoidance by the same authors. ftp://ftp.bellcore.com/pub/tjo/TCPwindow.ps
- Padhye, J., Firoiu, V., Towsley, D., and Kurose, J., Modeling TCP Throughput: a Simple Model and its Empirical Validation, UMASS CMPSCI Tech Report TR98-008, Feb. 1998. ftp://gaia.cs.umass.edu/pub/Padhye-Firoiu98:TCP-throughput.ps.Z
- J. Padhye, V. Firoiu and D. Towsley, A Stochastic Model of TCP Reno Congestion Avoidance and Control, Technical Report 99-02, Department of Computer Science, University of Massachusetts, Amherst. ftp://gaia.cs.umass.edu/pub/Padhye99-markov.ps
- Sally Floyd, Mark Handley, Jitendra Padhye, and Joerg Widmer, Equation-Based Congestion Control for Unicast Applications, May 2000. To appear in SIGCOMM 2000.
- The TCP Friendly Website: http://www.psc.edu/networking/tcp_friendly.html
Other TCP Algorithms:
- Jacobson, V., Congestion Avoidance and Control. Proceedings of SIGCOMM '88 (Palo Alto, CA, Aug. 1988) (The pointers are to a slightly-revised 1992 version of the 1988 paper.) ftp://ftp.ee.lbl.gov/papers/congavoid.ps.Z
- Floyd, S., and Jacobson, V., Random Early Detection gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413. http://www.aciri.org/floyd/papers/red/red.html
- Floyd, S., TCP and Explicit Congestion Notification. ACM Computer Communication Review, V. 24 N. 5, October 1994, p. 10-23. [This issue of CCR incorrectly has "1995" on the cover instead of "1994".] ftp://ftp.ee.lbl.gov/papers/tcp_ecn.4.ps.Z
- L. S. Brakmo and L. L. Peterson, TCP Vegas: End to End Congestion Avoidance on a Global Internet. IEEE Journal of Selected Areas in Communication, Vol. 13, No. 8, pp. 1465-1480, October 1995.
- J.C. Hoe. Improving the Start-up Behavior of a Congestion Control Scheme for TCP, Proc. of ACM SIGCOMM '96, pages 270-280, Aug. 1996.
- J. Semke, J. Mahdavi, M. Mathis, Automatic TCP Buffer Tuning, ACM SIGCOMM '98/ Computer Communication Review, volume 28, number 4, October 1998. http://www.psc.edu/networking/ftp/papers/autotune_sigcomm98.ps
- Mark Allman, On the Generation and Use of TCP Acknowledgments, ACM Computer Communication Review, vol. 28, no. 5, pp. 4--21, Oct. 1998.
- Mark Allman, TCP Byte Counting Refinements, ACM Computer Communication Review, vol. 29, no. 3, Jul. 1999.
- G. Minshall, A Suggested Modification to Nagle's Algorithm, Internet Engineering Task Force, Jun. 1999. http://www.ietf.org/internet-drafts/draft-minshall-nagle-01.txt (expired)
- Shrikrishna Karandikar, Shivkumar Kalyanaraman, Prasad Bagal and Bob Packer, TCP Rate Control, ACM Computer Communication Review, vol. 30, no. 1, Jan. 2000.
- Deepak Bansal and Hari Balakrishnan, TCP-friendly Congestion Control for Real-time Streaming Applications, MIT, Cambridge, Massachusetts, no. MIT-LCS-TR-806, May 2000.
- M. Mathis, J. Semke, J. Mahdavi, The Rate-Halving Algorithm for TCP Congestion Control, under development. http://www.psc.edu/networking/rate-halving/
- The Perf_Tune Page: http://www.psc.edu/networking/perf_tune.html
RED:
- S. Floyd and V. Jacobson. Random Early Detection Gateways for Congestion Avoidance. ACM/IEEE Transactions on Networking, 1(4):397-413, Aug. 1993.
- B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski and L. Zhang, Recommendations on Queue Management and Congestion Avoidance in the Internet, Internet Engineering Task Force, RFC 2309, Apr. 1998.
- S. Floyd and K. Fall, Promoting the Use of End-to-End Congestion Control in the Internet, IEEE/ACM Trans. on Networking, 7(4), August 1999, pp. 458-472.
TCP Implementation:
- D. Clark, V. Jacobson, J. Romkey, and H. Salwen, An Analysis of TCP Processing Overhead, IEEE Communication Magazine, June 1989, pp 23-29.