TCP/IP
`
`The
`
`Oa
`
`I
`
`ifnet_addrs:
`
`t
`.evens
`
`DELL EX.1095.001
`
`

`

`starting point
`~ CLOSED
`
`appl: passive open
`send: <nothing>
`
`LISTEN
`open
`
`recv: SYN
`send: SYN, ACK
`simultaneous open
`
`SYN_SENT
`
`active open
`
`apph close
`or timeout
`
`recv: FIN
`send: ACK
`
`data transfer state
`
`IIII
`
`apph I close
`send: ~ FIN
`
`~ LAST_ACK .)~ send: <nothing>
`
`"xl recv:ACK
`
`passive close
`
`timeout
`send: RST
`
`SYN_RCVD
`
`appl" close
`
`~FIN_WAIT_I~
`
`....simultaneous close
`
`~.-
`
`IN
`
`recv" FIN
`s;~Vdf ~A~K
`
`recv: ACK ~ ~ recv: ACK
`
`-~
`"
`~FIN_WAIT_2~
`
`recv: FIN
`sendl ACK ~\ TIME_ ’AIT)
`2MSL timeout
`
`active close
`
`~ normal transitions for client
`
`normal transitions for server
`state transitions taken when application issues operation
`state transitions taken when segment received
`what is sent for this transition
`
`recv:
`send:
`
`TCP state transition diagram.
`
`DELL EX.1095.002
`
`

`

`Structure Definitions
`80
`mrt
`682
`mrtctl
`msghdr
`
`1033
`1029
`1029
`
`482
`
`187
`
`682
`102
`342
`
`308
`73
`622
`117
`622
`67
`71
`117
`384
`160
`174
`161
`345
`716
`481
`211
`287
`347
`356
`265
`760
`286
`258
`262
`
`80
`411
`542
`682
`
`osockaddr
`
`pdevinit
`protosw
`
`radix_mask
`radix_node
`radix_node_head
`rawcb
`route
`route_cb
`rt_addrinfo
`rtentry
`rt_metrics
`rt_msghdr
`
`selinfo
`sl_softc
`sockaddr
`sockaddr_dl
`sockaddr_in
`sockaddr_inarp
`sockbuf
`socket
`socket_args
`sockproto
`sysent
`
`tcpcb
`tcp_debug
`tcphdr
`tcpiphdr
`timeval
`
`udphdr
`udpiphdr
`uio
`
`vif
`vifctl
`
`arpcom
`arphdr
`
`bp f_d
`bp f_hdr
`bpf_if
`
`cmsghdr
`
`domain
`
`ether_arp
`ether_header
`ether_multi
`
`icmp
`ifaddr
`ifa_msghdr
`ifconf
`if_msghdr
`ifnet
`ifqueue
`ifreq
`igmp
`in_addr
`In_aliasreq
`ln_ifaddr
`in_multi
`inpcb
`lovec
`~p
`ipasfrag
`~p_moptions
`~p_mreq
`~poption
`ipovly
`ipq
`ip_srcrt
`ip_timestamp
`
`le_softc
`igrplctl
`linger
`llinfo_arp
`
`mbuf
`
`38
`
`walkarg
`
`419
`420
`482
`
`75
`
`78
`188
`
`578
`575
`574
`647
`220
`625
`623
`579
`580
`622
`
`531
`83
`75
`87
`160
`701
`476
`438
`444
`626
`443
`
`804
`916
`801
`803
`106
`
`759
`759
`485
`
`406
`407
`
`632
`
`DELL EX.1095.003
`
`

`

`Praise for
`TCP/IP Illustrated, Volume 1: The Protocols
`
`"TCP/IP Illustrated has already become my most-likely-to-have-the-answer reference book, the first resource I turn
`to with a networking question. The book is, all publisher hype aside, an instant classic, and I, for one, am thrilled
`that something like this is now available."
`
`-- Vern Paxson, ;login:, March/April 1994
`
`"This is sure to be the bible for TCP/IP developers and users."
`
`-- Robert A. Ciampa, Network Engineer, Synernetics, division of 3COM
`
`"... the difference is that Stevens wants to show as well as tell about the protocols. His principal teaching tools are
`straight-forward explanations, exercises at the ends of chapters, byte-by-byte diagrams of headers and the like, and
`listings of actual traffic as examples."
`
`m Waiter Zintz, Unix WorM, December 1993
`
`"TCP/IP Illustrated, Volume 1 is based on practical examples that reinforce the theory -- distinguishing
`
`this book from others on the subject, and making it both readable and informative."
`
`-- Peter M. Haverlock, Consultant, IBM TCP/IP Development
`
`"While all of Stevens’ books are excellent, this new opus is awesome. Although many books describe the TCP/IP
`protocols, the author provides a level of depth and real-world detail lacking from the competition."
`
`-- Steven Baker, Unix Review, March 1994
`
`"TCP/IP Illustrated, Volume 1 is an excellent reference for developers, network administrators or anyone who needs
`
`to understand TCP/IP technology."
`
`-- Bob Williams, V.P. Marketing, NetManage, Inc.
`
`"W. Richard Stevens has produced a fine text and reference work."
`
`-- Scott Bradner, Consultant, Harvard University OIT/NSD
`
`"Even marketing weenies (of a technical bent) will appreciate this book, as it is clearly written, and uses lots of
`diagrams. I especially like the author’s thoughtful use of asides--set in smaller type and indented--to explain this
`or that concept. "
`
`
`
`~ Ron Jeffries, ATM USER, January 1994
`
`"Stevens takes a subject that has been written about rather prolifically, TCP/IP, and does something fresh and useful
`with it."
`
`Jason Levitt, Open Systems Today, March 7, 1994
`
`DELL EX.1095.004
`
`

`

`More Praise for
`TCP/IP Illustrated, Volume 1: The Protocols
`
`"This book is a stone jewel .... Written by W. Richard Stevens, this book probably provides the most comprehensive
`view of TCP/IP available today in print."
`
`~ Boardwatch, April/May
`
`1994
`
`"...you can’t get a better understanding of the workings of TCP/IP anywhere."
`
`-- Tom Nolle, Netwatcher, January
`
`1994
`
`"The book covers all the basic TCP/IP applications, including Telnet, NFS (Network File System), FTP (file transfer
`protocol) and TFTP (trivial FTP)."
`
`
`
`~ Data Communications, January 21, 1994
`
`"The diagrams he uses are excellent and his writing style is clear and readable. Please read it and keep it on your
`bookshelf."
`
`-- Elizabeth Zinkann, Sys Admin, November
`
`1993
`
`"Stevens’ Unix-oriented investigations will be invaluable to the network programmer or specialist who wishes to
`really understand how the TCP/IP stack is put together."
`
`
`
`-- Joel Snyder, Internet World, March/April 1994 issue
`
`"All aspects of the transmission control protocol/Internet protocol (TCP/IP) are covered here, from link layer and
`static/dynamic routing implementations to applications such as SNMP and Telnet."
`
`
`
`~ Telecommunications, March 1994
`
`"The author of TCP/IP Illustrated has succeeded in creating another indispensable tome of networking knowledge.
`This is the most comprehensible and complete book I have read on TCP/IP. It takes a different slant than other
`books, by presenting not only details of TCP, IP, ARP, ICMP, routing, etc., but actually shows these protocols (and
`common Internet tools) in action."
`
`~ Eli Charne, ConneXions, July 1994
`
`"The word ’illustrated’ distinguishes this book from its many rivals."
`
`~ Stan Kelly-Bootie, Unix Review, December 1993
`
`DELL EX.1095.005
`
`

`

`TCP/IP Illustrated, Volume 2
`
`DELL EX.1095.006
`
`

`

`Addison-Wesley Professional Computing Series
`
`Brian W. Kernighan, Consulting Editor
`
`Ken Arnold/John Peyton, A C User’s Guide to ANSI C
`Tom Cargill, C++ Programming Style
`William R. Cheswick/Steven M. Bellovin, Firewalls and Internet Security: Repelling the Wily Hacker
`
`David A. Curry, UNIX® System Security: A Guide for Users and System Administrators
`Erich Gamma/Richard Helm/Ralph Johnson/John Vlissides, Design Patterns: Elements of Reusable
`Object-Oriented Software
`John Lakos, Large-Scale C ++ Software Design
`Scott Meyers, Effective C++: 50 Specific Ways to Improve Your Programs and Designs
`Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs
`Robert B. Murray, C++ Strategies and Tactics
`David R. Musser/Atul Saini, STL Tutorial and Reference Guide: C++ Programming with the Standard
`Template Library
`John K. Ousterhout, Tcl and the Tk Toolkit
`Craig Partridge, Gigabit Networking
`J. Stephen Pendergrast Jr., Desktop KornShell Graphical Programming
`Radia Perlman, Interconnections: Bridges and Routers
`David Mo Piscitello/A. Lyman Chapin, Open Systems Networking: TCP/IP and OSI
`Stephen A. Rago, UNIX® System V Network Programming
`
`Curt Schimmel, UNIX® Systems for Modern Architectures: Symmetric Multiprocessing and
`Caching for Kernel Programmers
`W. Richard Stevens, Advanced Programming in the UNIX® Environment
`W. Richard Stevens, TCP/IP Illustrated, Volume 1: The Protocols
`W. Richard Stevens, TCP/IP Illustrated, Volume 3: TCP for Transactions, HTTP, NNTP, and the
`UNIX Domain Protocols
`Gary R. Wright/W. Richard Stevens, TCP/IP Illustrated, Volume 2: The Implementation
`
`DELL EX.1095.007
`
`

`

`TCP/IP Illustrated, Volume 2
`The Implementation
`
`Gary R. Wright
`W, Richard Stevens
`
`¯V
`
`V
`
`ADDISON-WESLEY PUBLISHING COMPANY
`Reading, Massachusetts Menlo Park, California New York
`Don Mills, Ontario Wokingham, England Amsterdam
`Bonn Sydney Singapore Tokyo Madrid San Juan
`Seoul Milan Mexico City Taipei
`
`DELL EX.1095.008
`
`

`

`Many of the designations used by manufacturers and sellers to distinguish their products
`are claimed as trademarks. Where those designations appear in this book and Addison-
`Wesley was aware of a trademark claim, the designations have been printed in initial caps
`or all caps.
`
`The programs and applications presented in this book have been included for their instruc-
`tional value. They have been tested with care, but are not guaranteed for any particular pur-
`pose. The publisher does not offer any warranties or representations, nor does it accept any
`liablities with respect to the programs or applications..
`
`The publisher offers discounts on this book when ordered in quantity for special sales. For
`more information please contact:
`Corporate & Professional Publishing Group
`Addison-Wesley Publishing Company
`One Jacob Way
`Reading, Massachusetts 01867
`
`Library of Congress Cataloging-in-Publication Data
`(Revised for vol. 2)
`
`Stevens, W. Richard.
`TCP/IP illustrated.
`
`(Addison-Wesley professional computing series)
`Vol. 2 by Gary R. Wright, W. Richard Stevens.
`Includes bibliographical references and indexes.
`Contents: v. 1. The protocols -- v. 2. The
`implementation
`1. TCP]IP (Computer network protocol) I. Wright,
`Gary R. II. Title. III. Series.
`TK5105.55.$74 1994
`004.6’2
`ISBN 0-201-63346-9 (v. 1)
`ISBN 0-201-63354-X (v. 2)
`
`93-40000
`
`The BSD Daemon used on the cover of this book is reproduced with the permission of
`Marshall Kirk McKusick.
`
`Copyright © 1995 by Addison-Wesley Publishing Company, Inc.
`
`All rights reserved. No part of this publication may be reproduced, stored in a retrieval
`system, or transmitted, in any form, or by any means, electronic, mechanical, photo-
`copying, recording, or otherwise, without the prior consent of the publisher. Printed in
`the United States of America. Published simultaneously in Canada.
`
`Text printed on recycled and acid-free paper
`
`ISBN 0-201-63354-X
`3 4 5 6 7 8 9 10 11-CRW-99989796
`Third printing, March 1996
`
`DELL EX.1095.009
`
`

`

`To my parents and my sister,
`for their love and support.
`--G.R. W.
`
`To my parents,
`for the gift of an education,
`and the example of a work ethic.
`--W.R.S.
`
`DELL EX.1095.010
`
`

`

`DELL EX.1095.01 1
`
`DELL EX.1095.011
`
`

`

`Contents
`
`Preface
`
`Chapter 1.
`1.1
`1.2
`1.3
`1.4
`1.5
`1.6
`1,7
`1.8
`1.9
`1.10
`1.11
`1.12
`1.13
`1.14
`1.15
`
`Chapter 2.
`2,1
`2,2
`2.3
`2.4
`2.5
`2.6
`
`Introduction
`1
`Introduction
`Source Code Presentation 1
`History 3
`Application Programming Interfaces 5
`Example Program 5
`System Calls and Library Functions
`Network Implementation Overview 9
`Descriptors 10
`Mbufs (Memory Buffers) and Output Processing
`Input Processing 19
`Network Implementation Overview Revisited
`Interrupt Levels and Concurrency 23
`Source Code Organization 26
`Test Network
`28
`Summary
`
`7
`
`22
`
`29
`
`Mbufs: Memory Buffers
`Introduction
`31
`36
`Code Introduction
`37
`Mbuf Definitions
`38
`mbu~ Structure
`Simple Mbuf Macros and Functions
`~_devgeL and ~_pu~_~_up Functions
`
`40
`44
`
`15
`
`xix
`
`1
`
`31
`
`Jx
`
`DELL EX.1095.012
`
`

`

`x
`
`TCP/IP Illustrated
`
`Contents
`
`2.7
`2.8
`2.9
`2.10
`2.11
`
`Summary of Mbuf Macros and Functions 51
`Summary of Net/3 Networking Data Structures
`re_copy and Cluster Reference Counts 56
`Alternatives
`60
`Summary
`60
`
`54
`
`Chapter 3.
`3.1
`3.2
`3.3
`3.4
`3.5
`3.6
`3.7
`3.8
`3.9
`3.10
`3.11
`3,12
`3.13
`
`Chapter 4.
`4.1
`4.2
`4.3
`4.4
`4.5
`
`Chapter 5.
`5.1
`5.2
`5.3
`5.4
`5.5
`
`Chapter 6.
`6.1
`6.2
`6.3
`6.4
`6.5
`6.6
`6.7
`6.8
`6.9
`6.10
`
`Interface Layer
`63
`Introduction
`64
`Code Introduction
`65
`±fn÷~ Structure
`73
`ifaddr Structure
`74
`sockaddr Structure
`ifneL and ifaddrSpecialization
`Network Initialization Overview
`Ethemet Initialization
`80
`SLIP Initialization
`82
`Loopback Initialization
`i f_aLLach Function
`4. finit Function
`Summary 94
`
`85
`85
`
`93
`
`76
`
`77
`
`Interfaces: Ethernet
`Introduction
`95
`Code Introduction
`Ethernet Interface
`ioctl System Call
`Summary
`125
`
`96
`98
`114
`
`Interfaces: SLIP and Loopback
`Introduction
`127
`Code Introduction
`SLIP Interface
`Loopback Interface
`Summary 153
`
`127
`128
`
`150
`
`IP Addressing
`Introduction
`155
`158
`Code Introduction
`Interface and Address Summary
`160
`sockaddr_in Structure
`161
`±n_± faddr Structure
`Address Assignment
`161
`Interface ±ocL1 Processing
`Internet Utility Functions
`ifneL Utility Functions
`Summary 183
`
`181
`182
`
`177
`
`158
`
`63
`
`95
`
`127
`
`155
`
`DELL EX.1095.013
`
`

`

`TCP/IP Illustrated
`
`Contents xi
`
`Chapter 7.
`7.1
`7.2
`7.3
`7.4
`7.5
`7.6
`7.7
`7.8
`7.9
`7.10
`
`Chapter 8.
`8.1
`8.2
`8.3
`8.4
`8.5
`8.6
`8.7
`8.8
`8.9
`8.10
`
`Chapter 9.
`9.1
`9.2
`9.3
`9.4
`9.5
`9.6
`9.7
`9.8
`9.9
`9.10
`9.11
`
`Chapter 10.
`10.1
`10.2
`10.3
`10.4
`10.5
`10.6
`10.7
`10.8
`
`Domains and Protocols
`Introduction
`185
`186
`Code Introduction
`187
`doma±n Structure
`188
`proLosw Structure
`IP doraa±n and proLosw Structures 191
`pff±nd#roLo and #ff±ndLy#÷ Functions
`#fcLl±~puL Function 198
`IP Initialization 199
`syscr_l System Call 201
`Summary 204
`
`196
`
`IP: Internet Protocol
`Introduction
`205
`Code Introduction 206
`IP Packets
`210
`212
`Input Processing: ±~i~L~ Function
`220
`Forwarding: ±~_~o~ward Function
`228
`Output Processing: ±#_ouLpuL Function
`234
`Internet Checksum: ±~_cksum Function
`seLsockopL and getsockopt System Calls
`i~_syscL1 Function 244
`Summary 245
`
`239
`
`IP Option Processing
`Introduction
`247
`247
`Code Introduction
`248
`Option Format
`±p_doopL±ons Function 249
`Record Route Option 252
`Source and Record Route Options
`Timestamp Option 261
`ip_inserLopLioms Function 265
`ip_pcbopL s Function 269
`Limitations
`272
`Summary
`272
`
`254
`
`277
`
`IP Fragmentation and Reassembly
`Introduction
`275
`Code Introduction
`278
`Fragmentation
`ip_opt copy Function 282
`Reassembly 283
`i#_reass Function
`ip_slowLimo Function
`Summary 300
`
`286
`
`298
`
`185
`
`205
`
`247
`
`275
`
`DELL EX.1095.014
`
`

`

`xii
`
`TCP/IP Illustrated
`
`Chapter 11
`11.1
`11.2
`11.3
`11.4
`11.5
`11.6
`11.7.
`11.8
`11.9
`11.10
`11.11
`11.12
`11.13
`11.14
`11.15
`
`Chapter 12.
`12.1
`12.2
`12.3
`12.4
`12.5
`12.6
`12.7
`12.8
`12.9
`12.10
`12.11
`12.12
`12.13
`12.14
`12.15
`12.16
`12.17
`
`Chapter 13.
`13.1
`13.2
`13.3
`13.4
`13.5
`13.6
`13.7
`13.8
`13.9
`
`ICMP: Internet Control Message Protocol
`Introduction
`301
`Code Introduction
`305
`±crop Structure
`308
`ICMP protosw Structure 309
`Input Processing: ±cm~_±n~ut Function
`Error Processing 313
`Request Processing
`316
`Redirect Processing
`321
`Reply Processing
`323
`Output Processing
`324
`icmp_error Function
`324
`icmp_ref lect Function 328
`icmp_send Function 333
`icmp_sysct l Function 334
`Summary 335
`
`310
`
`341
`
`344
`
`IP Multicasting
`Introduction
`337
`340
`Code Introduction
`Ethernet Multicast Addresses
`ether_multi Structure 342
`Ethernet Multicast Reception
`in_multi Structure 345
`i~_mopt ions Structure
`347
`Multicast Socket Options
`348
`Multicast TTL Values
`348
`ip_seLmopLions Function
`Joining an IP Multicast Group
`Leaving an IP Multicast Group
`371
`ip_geLmopLions Function
`Multicast Input Processing: i~intr Function 373
`Multicast Output Processing:
`ip_ouLpuL Function
`Performance Considerations 379
`Summary 379
`
`351
`355
`366
`
`375
`
`IGMP: Internet Group Management Protocol
`Introduction
`381
`382
`Code Introduction
`384
`igmp Structure
`IGMP #rotosw Structure 384
`Joining a Group: ±gm~_joingrou# Function
`igmp_fasL Limo Function 387
`Function391
`
`Input Processing:
`igmp_input
`Leaving a Group: igmp_leavegroup Function
`395
`Summary 396
`
`386
`
`Contents
`
`301
`
`337
`
`381
`
`DELL EX.1095.015
`
`

`

`TCP/IP Illustrated
`
`Contents xiii
`
`Chapter 14.
`14.1
`14.2
`14.3
`14.4
`14.5
`14.6
`14.7
`14.8
`14.9
`14.10
`
`Chapter 15.
`15.1
`15.2
`15.3
`15.4
`15.5
`15.6
`15.7
`15.8
`15.9
`15.10
`15.11
`15.12
`15.13
`15.14
`15.15
`15.16
`
`Chapter 16.
`16.1
`16.2
`16.3
`16.4
`16.5
`16.6
`16.7
`16.8
`16.9
`16.10
`16.11
`16.12
`16.13
`16.14
`
`397
`
`435
`
`475
`
`IP Multicast Routing
`Introduction
`397
`398
`Code Introduction
`Multicast Output Processing Revisited 399
`mrouted Daemon
`401
`Virtual Interfaces
`404
`IGMP Revisited
`411
`Multicast Routing
`416
`Multicast Forwarding: ±p_m£orward Function
`Cleanup: ip_mroute~_done Function 433
`Summary 434
`
`424
`
`Socket Layer
`435
`Introduction
`Code Introduction
`soek÷L Structure
`System Calls
`441
`Processes, Descriptors, and Sockets
`soekeL System Call 447
`getsock and
`sockargs Functions
`bind System Call
`453
`!±sLen System Call
`455
`Lsleep and wakeup Functions 456
`accept System Call 457
`sonewconn and soisconnecLed Functions
`connect System call
`464
`shutdown System Call
`468
`close System Call
`Summary 474
`
`436
`437
`
`471
`
`445
`
`451
`
`461
`
`and sendmsg
`
`
`
`System Calls480
`
`483
`
`Socket I/0
`475
`Introduction
`475
`Code Introduction
`476
`Socket Buffers
`write, writev, sendto,
`sendmsg System Call
`sendit Function
`485
`sosend Function
`489
`read, readv, recvfrom, and recvmsg System Calls
`recvmsg System Call
`501
`recvit Function 503
`soreceive Function
`505
`soreceive Code
`510
`select System Call
`524
`Summary 534
`
`5OO
`
`DELL EX.1095.016
`
`

`

`xiv
`
`TCP/IP Illustrated
`
`Chapter 17.
`17.1
`17.2
`17.3
`17.4
`17.5
`17.6
`17.7
`17.8
`
`Chapter 18.
`18.1
`18.2
`18.3
`18.4
`18.5
`18.6
`18.7
`18.8
`18.9
`18.10
`18,11
`18.12
`
`Chapter 19.
`19,1
`19,2
`19.3
`19,4
`19.5
`19,6
`19.7
`19.8
`19.9
`19.10
`19.11
`19.12
`19.13
`19.14
`19.15
`19.16
`19.17
`
`Socket Options
`Introduction
`537
`538
`Code Introduction
`539
`s÷LsockopL System Call
`545
`g÷LsockopL System Call
`fcnL1 and ±ceLl System Calls
`geLsockname System Call
`554
`g÷Lpeername System Call
`554
`Summary 557
`
`548
`
`Radix Tree Routing Tables
`Introduction
`559
`Routing Table Structure 560
`Routing Sockets
`569
`Code Introduction
`570
`Radix Node Data Structures 573
`Routing Structures 578
`rtable_init Functions
`and
`Initialization: route_init
`
`Initialization: rn_init and rn_inithead Functions
`Duplicate Keys and Mask Lists 587
`rn_maL ch Function
`591
`rn_search Function
`599
`Summary 599
`
`581
`
`584
`
`Routing Requests and Routing Messages
`Introduction
`601
`Functions 601
`rtalloc and rtallocl
`RTFRSE Macro and rLfree Function 604
`rLrequesL Function
`607
`rL_seLgaLe Function
`612
`rLiniL Function
`615
`rLredirecL Function 617
`Routing Message Structures
`rt_missmsg Function
`625
`rt_ifmsg Function
`627
`rt_newaddrmsg Function 628
`rt_msgl Function 630
`rL_msg2 Function 632
`syscL !_rLable Function 635
`sysct l_dumpentry Function 640
`sysctl_iflist Function 642
`Summary 644
`
`621
`
`Chapter 20.
`20,1
`20.2
`20.3
`
`Routing Sockets
`Introduction
`645
`rouLedomain and protosw Structures
`Routing Control Blocks 647
`
`646
`
`Contents
`
`537
`
`559
`
`601
`
`645
`
`DELL EX.1095.017
`
`

`

`TCP/IP Illustrated
`
`Contents xv
`
`20.4
`20.5
`20.6
`20.7
`20.8
`20.9
`20.10
`20.11
`20.12
`
`raw_init Function 647
`route_output Function 648
`r t_xaddrs Function 660
`rt_setmetrics Function 661
`raw_input Function
`662
`route_usrreq Function
`664
`raw_usrreq Function
`666
`raw_disconnect Functions
`raw_attach, raw_detach, and
`Summary 672
`
`Chapter 21.
`21.1
`21.2
`21.3
`21.4
`21.5
`21.6
`21.7
`21.8
`21.9
`21.10
`21.11
`21.12
`21.13
`21.14
`21.15
`
`Chapter 22.
`22.1
`22.2
`22.3
`22.4
`22.5
`22.6
`22.7
`22.8
`22.9
`22.10
`22.11
`22.12
`22.13
`
`ARP: Address Resolution Protocol
`Introduction
`675
`ARP and the Routing Table 675
`Code Introduction
`678
`ARP Structures
`681
`arpwhohas Function 683
`arprequest Function 684
`arpintr Function 687
`in_arpinput Function
`ARP Timer Functions
`arpresolve Function
`arplookup Function
`Proxy ARP 703
`arp_rtrequest Function
`ARP and Multicasting
`710
`Summary 711
`
`688
`694
`696
`701
`
`704
`
`Protocol Control Blocks
`Introduction
`713
`715
`Code Introduction
`inpcb Structure
`716
`in_pcballoc and in~cbdeLach Functions 717
`Binding, Connecting, and Demultipiexing 719
`in_pcblookup Function
`724
`in_pcbbind Function
`728
`735
`in_pcbconnecL Function
`in_pcbdisconnecL Function 741
`in_setsockaddr and in_setpeeraddr Functions 741
`in_pcbnotify, in_rtchange, and in_losing Functions
`Implementation Refinements 750
`Summary 751
`
`Chapter 23.
`23.1
`23.2
`23.3
`
`UDP: User Datagram Protocol
`Introduction
`755
`755
`Code Introduction
`UDP protosw Structure 758
`
`671
`
`675
`
`713
`
`742
`
`755
`
`DELL EX.1095.018
`
`

`

`xvi
`
`TCP/IP Illustrated
`
`Contents
`
`23.4
`23.5
`23.6
`23.7
`23.8
`23.9
`23.10
`23.11
`23.12
`23.13
`
`759
`UDP Header
`udp_init Function
`760
`760
`udp_output Function
`udp_input Function
`769
`781
`udp_saveopt Function
`782
`udp_cL linpuL Function
`784
`udp_usrreq Function
`790
`ud~)_sysct 1 Function
`Implementation Refinements 791
`Summary 793
`
`Chapter 24.
`24.1
`24.2
`24.3
`24.4
`24.5
`24.6
`24.7
`24.8
`24.9
`
`Chapter 25.
`25.1
`25.2
`25.3
`25.4
`25.5
`25.6
`25.7
`25.8
`25.9
`25.10
`25.11
`25.12
`25.13
`
`Chapter 26.
`26.1
`26.2
`26.3
`26.4
`26.5
`26.6
`26.7
`26.8
`26.9
`26.10
`
`TCP: Transmission Control Protocol
`Introduction
`795
`795
`Code Introduction
`TCP toroLosw Structure 801
`TCP Header 801
`TCP Control Block 803
`TCP State Transition Diagram
`TCP Sequence Numbers
`807
`tcp_init Function 812
`Summary 815
`
`805
`
`TCP Timers
`817
`Introduction
`819
`Code Introduction
`tcp_cancelLimers Function 821
`Lcp_fasLLimo Function
`821
`tcm_slowLimo Function
`822
`Lcp_Limers Function
`824.
`Retransmission Timer Calculations 831
`tcp_newt cpcb Function
`833
`tcp_setpersist Function
`835
`L cp_xmiL_L imer Function
`836
`Retransmission Timeout: top_timers Function
`An RTT Example 846
`Summary 848
`
`TCP Output
`851
`Introduction
`tc~_ouLput Overview 852
`Determine if a Segment Should be Sent
`TCP Qptions 864
`866
`Window Scale Option
`Timestamp Option
`866
`871
`Send a Segment
`Lcp_LemplaLe Function 884
`tcp_respond Function 885
`Summary 888
`
`852
`
`841
`
`795
`
`817
`
`851
`
`DELL EX.1095.019
`
`

`

`TCP/IP Illustrated
`
`Contents xvii
`
`Chapter 27.
`27.1
`27.2
`27.3
`27.4
`27.5
`27.6
`27.7
`27.8
`27.9
`27.10
`27.11
`
`Chapter 28.
`28.1
`28.2
`28.3
`28.4
`28.5
`28.6
`28.7
`28.8
`28.9
`28.10
`28.11
`28.12
`
`Chapter 29.
`29.1
`29.2
`29.3
`29.4
`29.5
`29.6
`29.7
`29.8
`29.9
`29.10
`29.11
`29.12
`29.13
`29.14
`
`Chapter 30.
`30.1
`30.2
`30.3
`30.4
`
`892
`892
`893
`897
`
`TCP Functions
`Introduction
`891
`Lcp_d~:a±n Function
`Lcp_d~:o;) Function
`Lc]9_c ]_ose Function
`Lc;)_mss Function
`904
`Lclo_C L ]_ ±nlouL Function
`Lclb_noL ± :[y Function
`904
`Leap_quench Function
`906
`<rCP_RSASS Macro and Lcp_z:eass Function
`Lcp_L~-ace Function
`916
`Summary 920
`
`906
`
`925
`933
`
`TCP Input
`923
`Introduction
`Preliminary Processing
`tcp_dooptions Function
`Header Prediction 934
`TCP Input: Slow Path Processing 941
`Initiation of Passive Open, Completion of Active Open
`PAWS: Protection Against Wrapped Sequence Numbers
`Trim Segment so Data is Within Window
`954
`Self-Connects and Simultaneous Opens
`960
`Record Timestamp
`963
`RST Processing
`963
`Summary 965
`
`TCP Input (Continued)
`Introduction
`967
`ACK Processing Overview 967
`Completion of Passive Opens and Simultaneous Opens
`Fast Retransmit and Fast Recovery Algorithms 970
`ACK Processing 974
`981
`Update Window Information
`983
`Urgent Mode Processing
`Lcp_pul louLo fband Function 986
`Processing of Received Data
`988
`FIN Processing
`990
`Final Processing
`992
`Implementation Refinements
`Header Compression 995
`Summary 1004
`
`994
`
`TCP User Requests
`Introduction
`1007
`1007
`tcp_usz:~:eq Function
`1018
`tcp_at Lach Function
`tcp_disconnect Function 1019
`
`942
`951
`
`967
`
`891
`
`923
`
`967
`
`1007
`
`DELL EX.1095.020
`
`

`

`xviii TCP/IP Illustrated
`
`Contents
`
`30.5
`30.6
`30.7
`
`tcp_usrclosed Function
`tcp_ctloutput Function
`Summary 1025
`
`1021
`1022
`
`Chapter 31,
`31.1
`31.2
`31.3
`31.4
`31.5
`31.6
`31.7
`
`Chapter 32.
`32.1
`32.2
`32.3
`32.4
`32.5
`32.6
`32.7
`32.8
`32.9
`
`Epilogue
`
`BPF: BSD Packet Filter
`Introduction 1027
`1028
`Code Introduction
`bpf_i f Structure 1029
`bpf_d Structure
`1032
`BPF Input
`1040
`BPF Output
`1046
`Summary
`1047
`
`Flaw IP
`1049
`Introduction
`Code Introduction 1050
`Raw IP protosw Structure
`rip_init Function
`1053
`rip_input Function
`1053
`rile_out!out Function
`1056
`rip_usrreq Function
`1058
`rip_eL lout#ut: Function
`1063
`Summary
`1065
`
`1051
`
`Appendix A.
`
`Solutions to Selected Exercises
`
`Appendix B.
`
`Source Code Availability
`
`1097
`
`RFC 1122 Compliance
`Link-Layer Requirements
`IP Requirements
`1098
`IP Options Requirements
`1102
`IP Fragmentation and Reassembly Requirements
`ICMP Requirements 1105
`Multicasting Requirements 1110
`IGMP Requirements
`1111
`Routing Requirements
`1111
`ARP Requirements
`1113
`UDP Requirements
`1 t 13
`TCP Requirements
`1115
`
`1104
`
`Appendix C.
`C.1
`C.2
`C.3
`C.4
`C.5
`C.6
`C.7
`C.8
`C.9
`C.10
`C.11
`
`Bibliography
`
`Index
`
`1027
`
`1049
`
`1067
`
`1069
`
`1093
`
`1097
`
`1125
`
`1133
`
`DELL EX.1095.021
`
`

`

`Preface
`
`Introduction
`
`This book describes and presents the source code for the common reference implemen-
`tation of TCP/IP: the implementation from the Computer Systems Research Group
`(CSRG) at the University of California at Berkeley. Historically this has been distributed
`with the 4.x BSD system (Berkeley Software Distribution). This implementation was
`first released in 1982 and has survived many significant changes, much fine tuning, and
`numerous ports to other Unix and non-Unix systems. This is not a toy implementation,
`but the foundation for TCP/IP implementations that are run daily on hundreds of thou-
`sands of systems worldwide. This implementation also provides router functionality,
`letting us show the differences between a host implementation of TCP/IP and a router.
`We describe the implementation and present the entire source code for the kernel
`implementation of TCP/IP, approximately 15,000 lines of C code. The version of the
`Berkeley code described in this text is the 4.4BSD-Lite release. This code was made pub-
`licly available in April 1994, and it contains numerous networking enhancements that
`were added to the 4.3BSD Tahoe release in 1988, the 4.3BSD Reno release in 1990, and
`the 4.4BSD release in 1993. (Appendix B describes how to obtain this source code.) The
`4.4BSD release provides the latest TCP/IP features, such as multicasting and long fat
`pipe support (for high-bandwidth, long-delay paths). Figure 1.1 (p. 4) provides addi-
`tional details of the various releases of the Berkeley networking code.
`This book is intended for anyone wishing to understand how the TCP/IP protocols
`are implemented: programmers writing network applications, system administrators
`responsible for maintaining computer systems and networks utilizing TCP/IP, and any
`programmer interested in understanding how a large body of nontrivial code fits into a
`real operating system.
`
`xix
`
`DELL EX.1095.022
`
`

`

`xx
`
`TCP/IP Illustrated
`
`Preface
`
`Organization of the Book
`
`The following figure shows the various protocols and subsystems that are covered. The
`italic numbers by each box indicate the chapters in which that topic is described.
`
`Chap. 2
`
`7
`
`15, 16, 17
`
`22
`
`24, 25, 26
`27, 28, 29, 30
`
`23
`
`32
`
`18, 19, 20
`
`14
`
`~L~ta~ 3, 4, 5
`
`media
`
`We take a bottom-up approach to the TCP/IP protocol suite, starting at the data-link
`layer, then the network layer (IP, ICMP, IGMP, IP routing, and multicast routing), fol-
`lowed by the socket layer, and finishing with the transport layer (UDP, TCP, and raw
`IP).
`
`Intended Audience
`
`This book assumes a basic understanding of how the TCP/IP protocols work. Readers
`unfamiliar with TCP/IP should consult the first volume in this series, [Stevens 1994],
`for a thorough description of the TCP/IP protocol suite. This earlier volume is referred
`to throughout the current text as Volume 1. The current text also assumes a basic under-
`standing of operating system principles.
`We describe the implementation of the protocols using a data-structures approach.
`That is, in addition to the source code presentation, each chapter contains pictures and
`descriptions of the data structures used and maintained by the source code. We show
`how these data structures fit into the other data structures used by TCP/IP and the ker-
`nel. Heavy .use is made of diagrams throughout the text--there are over 250 diagrams.
`This data-structures approach allows readers to use the book in various ways.
`Those interested in all the implementation details can read the entire text from start to
`finish, following through all the source code. Others might want to understand how the
`
`DELL EX.1095.023
`
`

`

`TCP/IP Illustrated
`
`Preface xxi
`
`protocols are implemented by understanding all the data structures and reading all the
`text, but not following through all the source code.
`We anticipate that many readers are interested in specific portions of the book and
`will want to go directly to those chapters. Therefore many forward and backward refer-
`ences are provided throughout the text, along with a thorough index, to allow individ-
`ual chapters to be studied by themselves. The inside back covers contain an
`alphabetical cross-reference of all the functions and macros described in the book and
`the starting page number of the description. Exercises are provided at the end of the
`chapters; most solutions are in Appendix A to maximize the usefulness of the text as a
`self-study reference.
`
`Source Code Copyright
`
`All of the source code presented in this book, other than Figures 1.2 and 8.27, is from the
`4o4BSD-Lite distribution. This software is publicly available through many sources
`(Appendix B).
`All of this source code contains the following copyright notice.
`
`* Copyright (c) 1982, 1986, 1988, 1990, 1993, 1994
`* The Regents of the University of California. All rights reserved.
`
`* Redistribution and use in source and binary forms, with or without
`* modification, are permitted provided that the following conditions
`* are met:
`* I. Redistributions of source code must retain the above copyright
`
`* notice, this list of conditions and the following disclaimer.
`* 2. Redistributions in binary form must reproduce the above copyright
`
`notice, this list of conditions and the following disclaimer in the
`*
`*
`documentation and/or other materials provided with the distribution.
`
`* 3. All advertising materials mentioning features or use of this software
`must display the following acknowledgement:
`*
`*
`This product includes software developed by the University of
`California, Berkeley and its contributors.
`*
`* 4. Neither the name of the University nor the names of its contributors
`*
`may be used to endorse or promote products derived from this software
`*
`without specific prior written permission.
`
`* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ~’AS IS’’ AND
`* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
`* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
`* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
`* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
`* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
`* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
`* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
`* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
`* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
`* SUCH DAMAGE.
`
`DELL EX.1095.024
`
`

`

`xxii
`
`TCP/IP Illustrated
`
`Acknowledgments
`
`Preface
`
`We thank the technical reviewers who read the manuscript and provided important
`feedback on a tight timetable: Ragnvald Blindheim, Jon Crowcroft, Sally Floyd, Glen
`Glater, John Gulbenkian, Don Hering, Mukesh Kacker, Berry Kercheval, Brian W.
`Kemighan, Ulf Kieber, Mark Laubach, Steven McCanne, Craig Partridge, Vern Paxson,
`Steve Rago, Chakravardhi Ravi, Peter Salus, Doug Schmidt, Keith Sklower, Ian Lance
`Taylor, and G. N. Ananda Vardhana. A special thanks’ to the consulting editor, Brian
`Kernighan, for his rapid, thorough, and helpful reviews throughout the course of the
`project, and for his continued encouragement and support.
`Our thanks (again) to the National Optical Astronomy Observatories (NOAO),
`especially Sidney Wolff, Richard Wolff, and Steve Grandi, for providing access to their
`networks and hosts. Our thanks also to the U.C. Berkeley CSRG: Keith Bostic and Kirk
`McKusick provided access to the latest 4.4BSD system, and Keith Sklower provided the
`modifications to the 4.4BSD-Lite software to run under BSD/386 V1ol.
`G.R.W. wishes to thank John Wait, for several years of gentle prodding; Dave
`Schaller, for his encouragement; and Jim Hogue, for his support during the writing and
`production of this book.
`W.R.S. thanks his family, once again, for enduring another "small" book project.
`Thank you Sally, Bill, Ellen, and David.
`The hardwork, professionalism, and support of the team at Addison-Wesley has
`made the authors’ job that much easier. In particular, we wish to thank John Wait for
`his guidance and Kim Dawley for her creative ideas.
`Camera-ready copy of the book was produced by the authors. It is only fitting that
`a book describing an industrial-strength software system be produced with an indus-
`trial-strength text processing system. Therefore one of the authors chose to use the
`Groff package written by James Clark, and the other author agreed begrudgingly.
`We welcome electronic mail from any readers with comments, suggestions, or bug
`fixes: tcp±p±v2-book@aw, cora. Each author will gladly blame the other for any
`remaining errors.
`
`Gary R. Wright
`http : //www. connix, com/~gwright
`Middletown, Connecticut
`November 1994
`
`W. Richard Stevens
`http : //www. noao. edu/~rstevens
`Tucson, Arizona
`
`DELL EX.1095.025
`
`

`

`Introduction
`
`1.1
`
`Introduction
`
`This chapter provides an introduction to the Berkeley networ