Internet Protocol Design

Internet Protocol Design and Implementation

My goal with this page is to document the design and implementation of TCP/IP with some important highlights from news, mailing lists, and papers. As I have worked on IP issues, I've found this personal list of links useful and wanted to make sure that this archive survives. Some of these documents have become difficult to obtain. There is a lot of sage advice here as well as humor. The best way to prove someone wrong is to do what they say is impossible.

All papers and talks are compressed with gzip. To view the postscript files, print them out or use ghostview.

Some of the impetus for this work came from Greg Chesson's statement at the Phoenix USENIX that `the way TCP and IP are designed, it's impossible to make them go fast'. On hearing this, I lept to my feet to protest but decided that saying "I think you're wrong" wasn't going to change anybody's mind about anything.

-- Van Jacobson

RFCs

817 - Important protocol implementation considerations including checksum and copy and minimal layering.
998 - NETBLT, uses rate-based flow control
2525 - Doh! Known TCP implementation problems

Papers

Savage, S., Cardwell, N., Wetherall, D., Anderson, T.; TCP Congestion Control with a Misbehaving Receiver; 10/1999 - Three ways to trick a sender into using any window size you wish
Savage, S.; Sting: a TCP-based Network Measurement Tool; 10/1999 - Finds sending and return packet loss rates, source code
Willinger, W. and Paxson, V.; Where Mathematics meets the Internet; 8/1998 - Goodbye, Poisson; Hello, Fractals
Proebsting, T. and Watterson, S.; Filter Fusion; 1996 - An optimizing compiler for filters
Floyd, S. and Jacobson, V.; The Synchronization of Periodic Routing Messages; 4/1994 - Avoidance of synchronization for route updates, injecting randomness
Bachmann, D., Honeyman, P., Huston, L.B.; The Rx Hex; 4/1994 - Better throughput on poor links for AFS RPC
Floyd, S. and Jacobson, V.; Random Early Detection (RED) gateways for Congestion Avoidance; 8/1993 - Extra information can be found here
McCanne, S. and Jacobson, V.; The BSD Packet Filter: A New Architecture for User-level Packet Capture; 1/1993 - High-performance, portable, versatile packet filter
Floyd, S. and Jacobson, V.; On Traffic Phase Effects in Packet-Switched Gateways; 9/1992 - Periodicity in queuing and RED
Jacobson, V.; Congestion Avoidance and Control; 11/1988 - The seminal paper on the now-common estimators
Kent, C. and Mogul, J.; Fragmentation Considered Harmful; 12/1987 - Reducing fragmentation to help performance and prevent failure
Jain, R.; A Timeout Based Congestion Control Scheme for Window Flow-Controlled Networks; 10/1986 - Predecessor to VJ congestion control
Lampson, B.; Hints for Computer System Design; 10/1983 - The Xerox PARC computer designer gives many hints which assist anyone doing systems work
Saltzer, J.H., Reed, D.P., and Clark, D.D.; End-to-End Arguments in System Design; 4/1981 - Design principles for putting together distributed systems

Talks

Jacobson, V.; Pathchar - a tool to infer characteristics of Internet paths; 4/1997 - Calculate bandwidth and delay on a per-hop basis
Jacobson, V.; How to Kill the Internet; 8/1995 - Multicast and caching as a solution to the web's poor application protocol
Jacobson, V.; Things that IP got right and ATM got wrong; 8/1994 - End-to-end versus hop-by-hop flow control, network guarantees
Jacobson, V.; Some Design Issues for High Speed Networks; 11/1993 - Similar to the previous talk, plus some discussion of queuing.
Jacobson, V.; Design Changes to the Kernel Network Architecture for 4.4BSD; 5/1992 - Despite the title, many performance changes here (like pbufs) never made it into 4.4BSD.

end2end mailing list archives (1984-current)

1987/10/5 - Network timers and turbulent flows
1987/10/6 - Router queuing and packet clumping
1987/11/2 - IETF announcement of congestion avoidance
1987/11/2 - TOS Routing and bw/delay bounds
1987/11/24 - Network Computing Forum through a sarcasm filter
1987/12/5 - TCP vs. NETBLT
1987/12/6 - Initial thoughts on window scaling
1987/12/8 - Task force meeting, especially SATNET and differential equations
1987/12/16 - TCP echos, other WS proposals
1988/1/18 - Problems with echo testing
1988/1/27 - WS in SYN TCP options, proto overhead
1988/1/31 - Analyzing traces, ftp trace script
1988/2/3 - Xtcp dies but not telnet?
1988/2/16 - "Are you simulating the bugs...?", clumping in physics and its relation to gateways. Original, Diagram
1988/2/18 - Randomness and order in networks
1988/2/22 - 4.2 retransmit bug
1988/2/25 - Multicast and multiple network interfaces
1988/3/2 - Congestion control and SACK, more damping for networks where ack speed >> data speed
1988/3/7 - Buffering, error rate, and large bw-delay products
1988/7/18 - Sniffing language, ether2ip
1988/8/9 - Source quench, gateway drops
1988/8/10 - Implementing mtu changes, path mtu discovery problems
1988/9/16 - Self-organization of multiple TCPs
1988/10/21 - Tcpdump initial release, NIT flame
1988/11/17 - More NIT flame
1988/11/30 - E2E Task force meeting notes for April 11-12, August 16, November 3-4
1988/12/12 - NIT bugs, NFS bugs
1988/12/20 - Traceroute initial release
1989/3/25 - ISO TP4 >> TCP
1989/3/30 - Buffering and RTT
1989/4/9 - Comments on queuing and random drop
1989/5/12 - Sun Corp. packet size, MIT packet size
1989/5/16 - Problem when MTU allows MSS larger than snd_cwnd, response
1989/5/24 - E2E Video Meeting
1989/6/21 - Src/Dest pair fair queuing, more comments
1989/10/24 - Long control delays in feedback algorithms
1990/4/30 - Modified congestion avoidance for large bw*delay
1994/3/14 - Retransmission problems in Vegas, diagram
1994/6/27 - BSD and deferred accept()

Email

1987/6/15 - Analysis of rtt estimators
1987/11/16 - Congestion window and slow start
1988/2/11 - Conservation of packets and congestion avoidance
1988/10/24 - Sun3 ethernet performance numbers
1993/9/7 - Details on pbufs, 30 Sparc instructions for TCP recv

comp.protocols.tcp-ip

1988/2/23 - Analysis of TCP congestion control
1988/3/10 - Header prediction, "impetus for this work came from ... statement ... `the way TCP and IP are designed, it's impossible to make them go fast'"
1988/7/20 - Kernel mods to Suns and aggregate performance increase
1988/11/23 - "Is there anybody has better 'ftp' performance than mine ???"
1995/6/5 - "I agree with your conclusion that STREAMS stink"
1995/6/9 - Performance analysis of STREAMS buffer strategy
1995/9/29 - 30% of Internet routes are asymmetric
1996/3/23 - Detailed design notes for optimized stack
1997/3/27 - Multicast and pbufs
1998/7/8 - TCP SACK development history
1999/2/8 - ICMP vs. UDP in traceroute

ucb.digital-video

1995/6/21 - Dynamic allocation of multicast ports
1995/6/22 - Put predictor in header or first sample?
1995/6/27 - Microsoft/Henning's DVI coder
1995/7/20 - Socket close and SIOCDELMULTI

Rules of Thumb

Moore's Law (1965) - The processor power and number of transistors on a chip doubles every 18-24 months (Graph)
- Machrone's Law - The machine you always want costs $5,000 (no longer true)
- Rock's Law - The cost of capital equipment to build semiconductors will double every four years
Amdahl's Law (1967) - When the fraction of serial work in a given problem is small, say s, the maximum speedup obtainable from even an infinite number of parallel processors is only 1/s (disproven and again)
Amdahl's Law - For every clock cycle, a CPU requires 1 bit of IO
Wirth's Law - Software gets slower more quickly than hardware gets faster

Humor

Dictionary of Research Phrases - Next time you have to read a research paper, use this handy reference