e
`
`Ga
`
`I
`
`i£net~addrs:
`
`INTEL Ex.1013.001
`
`

`

`starting point
`~ CLOSED
`
`appl: passive open !
`send: <nothing> I!
`
`LISTEN
`open
`
`timeou~
`send: RST
`
`JYN_RCVD
`
`"~
`%
`
`recv: SYN
`send: SYN, ACK
`simultaneous open
`
`SYN_SENT
`active open
`
`apph close
`or timeout
`
`recv: FIN
`send: ACK ~,~..CLOSE_WAIT~
`
`!!
`
`data transfer state
`
`appl" close
`sendi" FIN
`
`appl: ! close
`send: ! FIN
`
`II
`
`( LAST_ACK
`
`recv:ACK.-~
`send: <nothing>
`
`passive close
`
`~ ,
`
`J
`-~
`/
`..FIN WAIT 1 ~
`
`recv: FIN
`
`simultaneous close
`
`recv:l ACK
`send <nothing>
`
`send:
`
`~FIN WAIT 2~
`
`re : N _’~.r~ ’~^~rT-’~
`send:ACK .\TIME WAIT)
`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.
`
`INTEL Ex.1013.002
`
`

`

`Structure Definitions
`80
`mrt
`682
`mrtctl
`msghdr
`
`arpcom
`arphdr
`
`bpf_d
`bpf_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
`In_ifaddr
`in_multi
`inpcb
`lovec
`~p
`ipasfrag
`ip_moptions
`ip_mreq
`ipoption
`ipovly
`~Pq
`ip_srcrt
`~p_timestamp
`
`le_softc
`igrplctl
`linger
`llinfo_arp
`
`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
`
`8O
`411
`542
`682
`
`osockaddr
`
`pdevinit
`protosw
`
`radix mask
`radix_node
`radix_node_head
`rawcb
`route
`route_cb
`rt_addrinfo
`rtentry
`rt_metrics
`r t_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
`
`vi f
`vifctl
`
`mbuf
`
`38
`
`walkarg
`
`419
`420
`482
`
`75
`
`78
`188
`
`578
`575
`574
`647
`220
`625
`623
`579
`580
`622
`
`531
`83
`75
`87
`160
`70]
`476
`438
`444
`626
`443
`
`804
`916
`801
`803
`106
`
`759
`759
`485
`
`406
`407
`
`632
`
`INTEL Ex.1013.003
`
`

`

`
`
`INTEL Ex.1013.004
`INTEL Ex.11 .4
`
`

`

`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."
`
`-- Walter Zintz, Unix World, 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
`
`INTEL Ex.1013.005
`
`

`

`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), F-FP (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, lnternet WorM, 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
`
`INTEL Ex.1013.006
`
`

`

`TCP/IP Illustrated, Volume 2
`
`INTEL Ex.1013.007
`
`

`

`Addison-Wesley Professional Computing Series
`Brian W. Kernighan, Consulting Editor
`
`Matthew H. Austern, Generic Programming and the STL: Using and Extending the C ++ Standard Template Library
`David R. Butenhof, Programming with POSIX® Threads
`Brent Callaghan, NFS Illustrated
`Tom Cargill, C++ Programming Style
`William R. Cheswick/Steven M. Bellovin/Aviel D. Rubin, FirewalIs and Internet Security, Second Edition: Repelling
`the Wily Hacker
`David A. Curry, UNIX~ System Security: A Guide for Users and System Administrators
`Stephen C. Dewhurst, C++ Gotchas: Avoiding Common Problems in Coding and Design
`Dan Farmer/Wietse Venema, Forensic Discovery
`Erich Gamma/Richard Helm/Ralph Johnson/John Vlissides, Design Patterns: Elements of Reusable Object-
`Oriented Software
`Erich Gamma/Richard Helm/Ralph Johnson/John VJissides, Design Patterns CD: Elements of Reusable Object-
`Oriented Software
`Peter Haggar, Practical JavaTM Programming Language Guide
`David R. Hanson, C Interfaces and Implementations: Techniques for Creating Reusable Software
`Mark Harrison/Michael McLennan, Effective Tcl/Tk Programming: Writing Better Programs with Tcl and Tk
`Michi Henning/Steve Vinoski, Advanced CORBA® Programming with C++
`Brian W. Kernighan/Rob Pike, The Practice of Programming
`S. Keshav, An Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network
`Jotm Lakos, Large-Scale C ++ Software Design
`Scott Meyers, Effective C++ CD: 85 Specific Ways to hnprove Your Programs and Designs
`Scott Meyers, Effective C++, Third Edition: 55 Specific Ways to Improve Your Programs and Designs
`Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs
`Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library
`Robert B. Murray, C++ Strategies and Tactics
`David R. Musser/Gillmer J. Derge/Atul Saini, STL Tutorial and Reference Guide, Second Edition:
`C++ Programming with the Standard Template Librat~j
`John K. Ousterhout, Tcl and the Tk Toolkit
`Craig Partridge, Gigabit Networking
`Radia Perlman, Interconnections, Second Edition: Bridges, Routers, Switches, and Internetworking Protocols
`Stephen A. Rago, UNIX® System V Network Programming
`Eric S. Raymond, The Art of UNIX Programming
`Marc J. Rochkind, Advanced UNIX Programming, Second Edition
`Curt Schimmel, UNIX® Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers
`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
`W. Richard Stevens/Bill Fenner/Andrew M. Rudoff, UNIX Network Programming Volume 1, Third Edition: The
`Sockets Networking API
`W. Richard Stevens/Stephen A. Rago, Advanced Programming in the UNIX~ Environment, Second Edition
`W. Richard Stevens/Gary R. Wright, TCP/IP Illustrated Volumes 1-3 Boxed Set
`John Viega/Gary McGraw, Building Secure Software: How to Avoid Security Problems the Right Way
`Gary R. Wright/W. Richard Stevens, TCP/IP Illustrated, Volume 2: The Implementation
`Ruixi Yuan/W. Timothy Strayer, Virtual Private Networks: Technologies and Solutions
`
`Visit www.awprofessional.com/series/professionalcomputing for more information about these titles.
`
`INTEL Ex.1013.008
`
`

`

`TCP/IP Illustrated, Volume 2
`The Implementation
`
`Gary R. Wright
`W. Richard Stevens
`
`¯
`
`ADDISON-WESLEY
`Boston ¯ San Francisco ° New York ° Toronto ° Montreal
`London ¯ Munich ° Paris ¯ Madrid
`Capetown ° Sydney ¯ Tokyo ¯ Singapore ¯ Mexico City
`
`INTEL Ex.1013.009
`
`

`

`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 we were aware of a trademark claim, the designations have been
`printed in initial capital letters or in all capitals.
`
`The programs and applications presented in this book have been included for their instructional value. They have been
`tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or rep-
`resentations, nor does it accept any liabilities 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:
`
`Pearson Education Corporate Sales Division
`201 W. 103rd Street
`Indianapolis, IN 46290
`(800) 428-5331
`corpsales@pearsoned.com
`Visit AW on the Web: www.awl.com/cseng/
`
`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)
`
`9340000
`
`The BSD Daemon used on the cover of this book is reproduced with the permission of
`Marshall Kirk McKusick.
`
`Copyright © 1995 by Addison-Wesley
`
`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, photocopying, recording, or other-wise, without the
`prior consent of the publisher. Printed in the United States of America. Published
`simultaneously in Canada.
`
`ISBN 0-201-63354-X
`Text printed in the United States on recycled paper at Courier Westford in Westford, Massachusetts.
`24th Printing September 2010
`
`INTEL Ex.1013.010
`
`

`

`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.
`
`INTEL Ex.1013.011
`
`

`

`
`
`INTEL Ex.1013.012
`INTEL Ex.1 1
`.12
`
`

`

`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
`Introduction 1
`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
`Code Introduction
`36
`Mbuf Definitions
`37
`mbuf Structure
`38
`Simple Mbuf Macros and Functions
`m_devget and m_pullup Functions
`
`4O
`44
`
`15
`
`xix
`
`1
`
`31
`
`ix
`
`INTEL Ex.1013.013
`
`

`

`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.1o
`
`76
`
`77
`
`Interface Layer
`Introduction
`63
`Code Introduction
`64
`ifneL Structure
`65
`73
`i faddr Structure
`74
`sockaddr Structure
`ifneL and ifaddrSpecialization
`Network Initialization Overview
`Ethernet Initialization
`80
`82
`SLIP Initialization
`Loopback Initialization
`i f_atLach Function
`ifiniL Function
`Summary 94
`
`85
`85
`
`93
`
`Interfaces: Ethernet
`Introduction
`95
`Code Introduction
`Ethernet Interface
`JoeL1 System Call
`Summary
`125
`
`96
`98
`114
`
`Interfaces: SLIP and Loopback
`Introduction
`127
`Code Introduction
`128
`SLIP Interface
`Loopback Interface
`Summary 153
`
`150
`
`127
`
`IP Addressing
`Introduction
`155
`Code Introduction 158
`Interface and Address Summary
`sockaddr_in Structure
`160
`in_i faddr Structure
`161
`Address Assignment
`161
`Interface ±ocL1 Processing
`Internet Utility Functions
`±fneL Utility Functions
`Summary 183
`
`181
`182
`
`177
`
`63
`
`95
`
`127
`
`155
`
`158
`
`INTEL Ex.1013.014
`
`

`

`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
`Code Introduction
`186
`domain Structure
`187
`188
`#roLosw Structure
`IP doma±n and #rot.osw Structures 191
`pffindproto and pffindtype Functions
`p[cLlin#uL Function 198
`IP Initialization 199
`syscL1 System Call 201
`Summary 204
`
`196
`
`IP: Internet Protocol
`Introduction
`205
`Code Introduction 206
`IP Packets
`210
`Input Processing: ipintr Function
`212
`220
`Forwarding: i#_forward Function
`Output Processing: ip_outpuL Function
`Internet Checksum: in_cksum Function
`setsockopt and getsockopt System Calls
`ip_sysct 1 Function 244
`Summary 245
`
`228
`234
`
`239
`
`IP Option Processing
`Introduction
`247
`247
`Code Introduction
`Option Format
`248
`±#_doopt_ ±ons Function 249
`Record Route Option 252
`Source and Record Route Options
`Timestamp Option 261
`ip_insertoptions Function 265
`ip_pcbopL s Function 269
`Limitations
`272
`Summary
`272
`
`254
`
`IP Fragmentation and Reassembly
`Introduction
`275
`277
`Code Introduction
`278
`Fragmentation
`ip_opLcopy Function 282
`Reassembly 283
`ip_reass Function
`ip_slowLimo Function
`Summary 300
`
`286
`
`298
`
`185
`
`205
`
`247
`
`275
`
`INTEL Ex.1013.015
`
`

`

`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
`305
`Code Introduction
`icmp Structure
`308
`ICMP protosw Structure 309
`Input Processing: letup_input Function 310
`Error Processing
`313
`316
`Request Processing
`Redirect Processing
`321
`Reply Processing
`323
`324
`Output Processing
`icmp_error Function 324
`icmp_reflecL Function 328
`icmp_send Function 333
`icmp_syscL1 Function 334
`Summary 335
`
`341
`
`344
`
`347
`348
`
`IP Multicasting
`Introduction
`337
`Code Introduction 340
`Ethernet Multicast Addresses
`ether_multi Structure 342
`Ethernet Multicast Reception
`345
`in_mulLi Structure
`ip_mopLions Structure
`Multicast Socket Options
`348
`Multicast TTL Values
`ip_seLmopLions Function
`Joining an IP Multicast Group
`Leaving an IP Multicast Group
`371
`ip_geLmopLions Function
`Multicast Input Processing: ipintr Function 373
`Multicast Output Processing: ip_ouLpuL Function
`Performance Considerations 379
`Summary 379
`
`351
`355
`366
`
`Contents
`
`301
`
`337
`
`381
`
`375
`
`IGMP: Internet Group Management Protocol
`Introduction
`381
`382
`Code Introduction
`igmp Structure
`384
`IGMP protosw Structure 384
`Joining a Group: igmp_joingroup Function
`igmp_fasLLimo Function 387
`Input Processing: igmp_inpuL Function 391
`Leaving a Group: igmp_leavegroup Function
`Summary 396
`
`386
`
`395
`
`INTEL Ex.1013.016
`
`

`

`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
`
`IP Multicast Routing
`Introduction
`397
`Code Introduction 398
`Multicast Output Processing Revisited 399
`mrouted Daemon
`401
`Virtual Interfaces
`404
`IGMP Revisited
`411
`Multicast Routing
`416
`Multicast Forwarding: ip_mforward Function
`Cleanup: ip_mrouLer_done Function 433
`Summary 434
`
`Socket Layer
`435
`Introduction
`Code Introduction
`socket Structure
`System Calls
`441
`Processes, Descriptors, and Sockets
`socket System Call 447
`getsock and sockargs Functions
`bind System Call
`453
`listen System Call
`455
`tsleep and wakeup Functions 456
`accept System Call 457
`sonewconn and soisconnected Functions
`connect System call
`464
`shutdown System Call
`468
`close System Call
`Summary 474
`
`436
`437
`
`471
`
`445
`
`451
`
`424
`
`461
`
`397
`
`435
`
`475
`
`INTEL Ex.1013.017
`
`Socket I/0
`Introduction
`475
`Code Introduction
`475
`Socket Buffers
`476
`write, writev, sendto, and sendmsg System Calls
`sendmsg System Call
`483
`sendit Function 485
`sosend Function
`489
`read, readv, recvfrom, and recvmsg System Calls
`recvmsg System Call
`501
`recviL Function
`503
`soreceive Function
`505
`soreceive Code
`510
`select_ System Call
`524
`Summary 534
`
`480
`
`500
`
`

`

`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
`
`Chapter 20.
`20.1
`20.2
`20.3
`
`Socket Options
`537
`Introduction
`538
`Code Introduction
`539
`seLsockopt System Call
`545
`geLsockopL System Call
`fcnL1 and iocL1 System Calls
`554
`geLsockname System Call
`554
`geLpeername System Call
`Summary 557
`
`548
`
`Radix Tree Routing Tables
`Introduction
`559
`Routing Table Structure 560
`Routing Sockets
`569
`570
`Code Introduction
`Radix Node Data Structures 573
`Routing Structures 578
`Initialization: route_iniL and rtable_init Functions
`Initialization: rn_init and rn_iniLhead Functions
`587
`Duplicate Keys and Mask Lists
`rn_maLch Function 591
`rn_search Function 599
`Summary 599
`
`581
`
`584
`
`Routing Requests and Routing Messages
`Introduction
`601
`rLalloc and rLallocl Functions 601
`RTFREE Macro and rtfree Function 604
`607
`rLrequesL Function
`612
`rL_seLgaLe Function
`rL iiq.± L Function
`615
`rLredirecL Function 617
`Routing Message Structures
`625
`rL_missmsg Function
`627
`rL_± fmsg Function
`r t_newaddrmsg Function 628
`630
`rL_rasgl Function
`632
`rL_msg2 Function
`sysc L l_rLab]-e Function 635
`sysc L l_dumpenL ry Function
`syscL ]__i f ]_isL Function 642
`Summary 644
`
`640
`
`621
`
`Routing Sockets
`645
`Introduction
`routedomain and protosw Structures
`Routing Control Blocks 647
`
`646
`
`Contents
`
`537
`
`559
`
`601
`
`645
`
`INTEL Ex.1013.018
`
`

`

`ARP: Address Resolution Protocol
`Introduction
`675
`ARP and the Routing Table 675
`Code Introduction
`678
`ARP Structures
`681
`arpwhohas Function
`683
`arpreques L Function 684
`arpintr Function 687
`in_arpinput Function
`ARP Timer Functions
`arpresolve Function
`arplookup Function
`Proxy ARP 703
`arp_rtrequest Function
`ARP and Multicasting
`Summary 711
`
`704
`
`710
`
`688
`694
`696
`701
`
`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
`
`Protocol Control Blocks
`Introduction
`713
`715
`Code Introduction
`inpcb Structure
`716
`in_pcballoc and in_pcbdeLach Functions 717
`Binding, Connecting, and Demultiplexing 719
`in_pcblookup Function
`724
`in_pcbbind Function
`728
`in_pcbconnecL Function
`735
`in_pcbdisconnect Function 741
`in_seLsockaddr and in_seLpeeraddr 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 proLosw Structure 758
`
`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
`rt_xaddrs Function 660
`rL_seLmeLrics Function 661
`raw_input Function
`662
`664
`rouLe_usrreq Function
`raw_usrreq Function
`666
`raw_attach, raw_detach, and raw_disconnect Functions
`Summary 672
`
`671
`
`675
`
`713
`
`742
`
`755
`
`INTEL Ex.1013.019
`
`

`

`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
`
`UDP Header 759
`udp_ini r_ Function
`760
`udp_output Function
`760
`udp_input Function
`769
`udp_saveopL Function
`781
`udp_cL ]_inpuL Function
`782
`udp_usrreq Function
`784
`udp_syscL1 Function
`790
`Implementation Refinements
`Summary
`793
`
`791
`
`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
`Code Introduction 795
`TCP protosw Structure
`TCP Header 801
`TCP Control Block 803
`TCP State Transition Diagram
`TCP Sequence Numbers
`807
`tcp_init Function 812
`Summary 815
`
`805
`
`801
`
`TCP Timers
`Introduction 817
`Code Introduction 819
`tcp_canceltimers Function 821
`Lcp_fasL Limo Function
`821
`Lcp_slowLimo Function
`822
`Lcp_Limers Function
`824
`Retransmission Timer Calculations 831
`Lcp_newLcpcb Function
`833
`Lcp_seLpersisL Function
`835
`Lcp_xmiL_L imer Function
`836
`Retransmission Timeout: Lcp_Limers Function
`An R]-I- Example 846
`Summary 848
`
`TCP Output
`Introduction
`851
`tcp_output Overview 852
`Determine if a Segment Should be Sent
`TCP Options 864
`Window Scale Option
`866
`Timestamp Option
`866
`Send a Segment
`871
`Lcp_LemplaLe Function
`Lcp_respond Function
`Summary 888
`
`884
`885
`
`852
`
`841
`
`795
`
`817
`
`851
`
`INTEL Ex.1013.020
`
`

`

`TCP/IP Illustrated
`
`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
`
`TCP Functions
`Introduction
`891
`Lcp_drain Function
`892
`Lc#_dro# Function
`892
`Lcp_close Function
`893
`Lc#_ms s Function
`897
`tcp_ct linput Function
`904
`Lcp_noLi fy Function
`904
`Lcp_quench Function
`906
`TCP_REASS Macro and Lcp_reass Function
`Lcp_Lrace Function
`916
`Summary 920
`
`906
`
`TCP Input
`Introduction
`923
`Preliminary Processing
`925
`tcp_dooptions Function
`933
`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
`Update Window Information
`Urgent Mode Processing
`tcp_pul louto fband Function
`Processing of Received Data
`FIN Processing
`990
`Final Processing
`992
`Implementation Refinements
`Header Compression 995
`Summary 1004
`
`994
`
`981
`983
`
`986
`988
`
`Chapter 30.
`30.1
`30.2
`30.3
`30.4
`
`TCP User Requests
`Int~duction 1007
`Lcp_usrreq Function
`1007
`Lcp_aLLach Function
`1018
`Lcp_disconnecL Function
`
`1019
`
`Contents
`
`xvii
`
`891
`
`942
`951
`
`967
`
`923
`
`967
`
`1007
`
`INTEL Ex.1013.021
`
`

`

`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
`Code Introduction
`bpf_i f Structure
`bpf_d Structure
`BPF Input
`1040
`BPF Output
`1046
`Summary
`1047
`
`1028
`1029
`1032
`
`Raw IP
`Introduction 1049
`Code Introduction 1050
`Raw IP proLosw Structure 1051
`rip_init Function
`1053
`rip_input Function
`1053
`rip_ouLpuL Function
`1056
`rip_usrreq Function
`1058
`rip_cLlouLpuL Function 1063
`Summary 1065
`
`Appendix A.
`
`Solutions to Selected Exercises
`
`Appendix B.
`
`Source Code Availability
`
`1097
`
`RFC 1122 Compliance
`Link-Layer Requirements
`IP Requirements
`1098
`1102
`I P Options Requirements
`IP Fragmentation and Reassembly Requirements
`ICMP Requirements 1105
`Multicasting Requirements 1110
`1111
`IGMP Requirements
`Routing Requirements
`1111
`1113
`ARP Requirements
`1113
`UDP Requirements
`1115
`TCP Requirements
`
`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
`
`INTEL Ex.1013.022
`
`

`

`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 4o4BSD-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
`4o4BSD 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
`
`INTEL Ex.1013.023
`
`

`

`xx
`
`TCP/IP Illustrated
`
`Organization of the Book
`
`Preface
`
`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.
`22
`Chap. 2
`7
`15, 16, 17
`
`24, 25, 26
`27, 28, 29, 30
`
`32
`
`23
`
`18, 19, 20
`
`14
`
`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
`
`INTEL Ex.1013.024
`
`

`

`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
`4.4BSD-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
`* AIqY 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.
`*/
`
`INTEL Ex.1013.025
`
`

`

`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.
`Kernighan, 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