COMPUTER NETWORKS
`
`SECOND EDITION
`
`ANDREW S. TANENBAUM
`
`Vrijt Universileil
`Amsterdam. The Netherlands
`
`5
`PRENTICE HALL
`£uaLr.wooocuns.Nswaensev men
`
`Math
`
`3 A
`('_>(’ 2 s
`‘I
`I
`I L“
`I 9 (5 ,1
`
`'
`
`Petitioner Microsoft — Ex. 1005, Cover
`
`

`
`laum r-if l'mu.;n- n (‘.u..(,.,...,.,,...¢..auhr.I\-'1 I“-4"‘
`lam-rvluuunu. Aggy‘... 5
`nmpum mtwuqtg; .n\..;,..,. 5 -rgnh-I-I -100 H1
`5:
`an
`p_
`n.n.n..,,..,..,
`IlI.IuII¢\ |Iu.|u.-a
`ISBN l'|.1\_|&z.,s9_”
`'
`‘Vtlqaulcr nnmsulu
`IKfiIlI5.5 11310“
`mg 3. uh".
`
`I 1'5"‘
`
`I3 Ill-ll.”HP
`
`Edilnrialfpmduction supervision: Lisa Schulz Glrboalti
`Manufacluring buygg: Mil‘! Ann Glvllfilllllfl
`
`Prentice Hall Stine-w'e Sarita‘
`Brian W. K:-rnignan. MI'is:rr
`
`The publisher offers discuunis on this haul: when urdclud in hull
`quaniilies. For rmre information, write:
`Special Salestflullegt Marketing
`Prenlicc Hall
`Cullcge Technical and Rcfcmnce Division
`El'|L"|=Wood Cliffs. N] am:
`
`
`
`tonto.l'..l-I/EH
`
`-u-
`
`._-.-o1-.,9-
`
`
`
`0 I939 by Prentice-Hall. Inc.
`_ A Division Of Simnn & Schuuler
`_ Englcwood Cliffs. New Jersey M632
`
`All rights reserved. No part of this book may be
`reproduced. in any form or by any mcans.
`wilhoul pumission in wriling Fmm Ihc: publislazr.
`
`Printed in the Uniled Slams oi America
`
`I098‘:-'6
`
`ISBN I]']-3-I-h.3_“15‘|-X
`
`Pmmicc-Hall lniamalionnl {UK} Limited. hinder:
`Prcnlice-Hull of Mlszralia Pty. Lil'I1i1ed.Syd‘r:r]r
`Pltnlict.-Hall Canada Inc.. Tarontu
`Prentice-Hall Hispannarncricana. S.A_. Mexico
`Pmnticc-Hail of India Private Lirnilcd. New Delhi
`PrctItiv.‘e—HzIll of Japan. InC.. Tolryu
`Simon & Schusher Ania Pie. Ll:l.. Sfngapart
`Edilunl Pr¢:nIic:—HlII dn Brasil, Lida. . Rio 0': begin:
`
`Petitioner Microsoft - Ex. 1005, p. ii
`
`Petitioner Microsoft - Ex. 1005, p. ii
`
`

`
`To Suzanne. Barbara. Marvin. Mm‘.-I. and fire memory afsweelie 1:
`
`Petitioner Microsoft - Ex. 1005, p. iii
`
`Petitioner Microsoft - Ex. 1005, p. iii
`
`

`
`
`
`ZOFEIOLN/SW
`
`
`
`,...—._—_,_..__.—.._.___—._._.
`
`Petitioner Microsoft - Ex. 1005, p. iv
`
`Petitioner Microsoft - Ex. 1005, p. iv
`
`

`
`
`
`
`
`__.—.——,—___._-_.___..._._._.,7;-_-__--—-—.:.._.._...-.-_.__-_..
`
`CONTENTS
`
`INTRODUCTION
`
`I
`
`1.I THE USES OF COMPUTER NETWORKS 3
`1. LI Network Goals
`3
`1.1.2 Applications of Networks
`1.2 NEIWORKSTRUCFURE 6
`
`4
`
`1.3 NETWORK ARCHITECTURES 9
`1.3.1 Protocol HiE1’llI'l:|‘Ii¢5
`9
`13
`1.3.2 Design Issues for the Layers
`1.4 THE 08! REFERENCE MODEL 14
`1.4.1 The Physical Layer
`15
`1.4.2 The Data Link Layer 16
`1.4.3 The Network Layer 16
`1.4.4 'IheTransport Layer
`17
`1.4.5 The Session Layer
`13
`1!!
`1.4.6 The Presentation Layer
`1.4.? The Application Layer 19
`1.4.8 Data Transmission in the 031 Model
`
`I‘)
`
`1.5
`
`SERVICES 21
`1.5.1 OSITertninoIogy 21
`1.5.2 Connection-Otiented and Cottrtectionless Services 22
`1.5.3 Service Primitives 24
`1.5.4 111: Relationship of Services to Protocols 26
`1.6 NETWORK STANDARDIZATION 2'1’
`1.6.1 W110‘: Who in the Telecommunication would 28
`1.6.2 Who's Who in the Standards World 29
`1.6.3 Discussion of the Slnndattlization of the 031 model 30
`
`1.? EXAMPLE NETWORKS 32
`1.7.1 Public Networks 32
`1.7.2 T|'1eARPANE'[' 35
`1.13 MAPa.nd'FOP 36
`1.14 USENET 40
`1.7.5 CSNET 41
`1.7.6 BITNET 42
`1.7.? SNA 43
`
`;o—o-—...
`
`L8 OUTLINE OF THE REST OF THE BOOK 4'}
`
`1.9 SUMMARY 43
`
`Petitioner Microsoft - Ex. 1005, p. V
`
`Petitioner Microsoft - Ex. 1005, p. v
`
`

`
`vi
`
`CONTENTS
`
`THE PHYSICAL LAYER
`
`51
`
`II
`
`THE THEORETICAL BASIS FOR DATA COMMUNICATION 52
`2.1.1 Fourier Analysis 52
`2.1.2 BItndwidth—Limi1ed Signals 53
`2.1.3 The Maximum Data Rate of a Channel 56
`
`
`
`sotrtto-LN/SW
`
`2.2 TRANSMISSION MEDIA 5?
`2.2.1 Magnetic Media 5'!
`2.2.2 TwistedPair 57
`2.2.3 Baseba.ndConJtia1Cable 58
`2.2.4 Broadband Coaxial Cable 59
`2.2.5 fiber Optics 62
`2.2.6 Line-of-Sight Transmission 65
`2.2.? Communication Satellites 66
`
`2.3 ANALOG TRANSMISSION 70
`2.3.] The Telephone System ‘ID
`2.3.2 Modems 72
`2.3.3 RS-232-C and RS449 76
`
`2.4 DIGITAL TRANSMISSION 77
`2.4.] Pulse Code Modulation 79
`2.4.2 Encoding Systems 8]
`2.4.3 TIleX.."-El Digital Interface 32
`
`2.5 TRANSMISSION ANDSWITCHING B4
`2.5.l Frequency Division and Time Division Multiplexing 34
`2.5.2 Cireuitswitching 36
`2.5.3 Packet Switching 88
`2.5.4 Hybrid Switching B9
`
`2.6
`
`lSDN—INTEGRATED SERVICES DIGITAL NETWORK 90
`2.6.]
`ISDN Services 9|
`2.6.2 Evolution of[SDN 93
`2.6.3 ISDN System Architecture 95
`2.6.4 ‘I11: Digital PBX 99
`I02
`2.6.5 ThelSDN Interface
`2.6.6 ISDN Signa.ling—SS #7 106
`2.6.7 Perspoe-tiveonlSDN I07
`
`2.? TERMINALHANDLING 109
`2.7.l Polling IID
`2.7.2 Multiplexing versus Concentration
`
`III
`
`2.8 SUMMARY I I3
`
`Petitioner Microsoft - Ex. 1005, p. Vi
`
`Petitioner Microsoft - Ex. 1005, p. vi
`
`

`
`LUNll.‘.1\l.)
`
`Tl-IE MEDIUM ACCESS SUBLAYER
`
`I16
`
`3.]
`
`LOCAL AND METROPOLITAN AREA NETWORKS 116
`3.1.! Static Channel Allocation in LAN; and MAN: H8
`3.1.2 Dynalnic Channel Allocation in LAN; anti MARS 119
`3.2 THE ALOHA PROTOCOLS 121
`3.2.1 Plm: ALOHA and Slotted ALOHA 121
`3.2.2 Finite Population ALOHA 124
`3.3 DOCAL AREA NETWORK PROTOCOLS 127
`13.1 Persistent and Nonpemistent CSMA 127
`3.3.2 CSMA with Collision Detection
`I28
`3.3.3 Collision-Free Protocols
`I30
`3.3.4 BRAP——Broadcast Rnoognition with Alternating Priorities
`3.3.5 MLMA——Tl'le Multi—LA:vel Molti-Access Protocol 132
`3.3.6 Binary Countdown I34
`135
`13.? Limilnd-Contention Protocols
`3.3.8 The Adaptive Tie: Walk Protocol 136
`3.3.9 The Um Plntocol 138
`
`3.4
`
`IEEE STANDARD 802 FOR LOCAL AREA NETWORKS 161
`3.4.1
`IEEE Stnrtt|a.rd 302.2 and Ethernet
`141
`3.4.2 IEEE Standard 302.4: Token Bus 143
`3.4.3 IEEE Standard 802.5: Token King 153
`3.4.4 Comparison of Local Area Networks
`163
`3.5 FIBER OPTIC NETWORKS I65
`3.5.] FDDI
`I66
`3.5.2 Fibernetll 163
`3.5.3 SINET ITO
`3.5.4 FASNET AND EXPRESSNET I'll
`3.5.5 DATAKIT I13
`
`131
`
`3.6 SATELLITE NETWORKS ITS
`3.6.! SPADE I76
`3.6.2 ALOHA Revisited 177
`3.6.3 Reservation ALOHA 1.79
`
`3.1‘
`
`PACKET RADIO NETWORKS 182
`3.7.] The University of Hawaii ALOHA System [82
`3.7.2 Design Issues for Packet Radio Nctworks
`183
`3.3 EXAMPLES OF THE MAC SUBLAYER 138
`I89
`3.8.1 The MAC Sublayer in Public Networks
`3.8.2 Tlte MAC Sublayer in the ARPANET 189
`3.3.3 The MAC Sublayer in MAP and TOP I89
`3,3,4 The MAC Sublayer in USENET 190
`3.9 SUMMRRY l90
`
`Petitioner Microsoft - Ex. 1005, p. Vii
`
`Petitioner Microsoft - Ex. 1005, p. vii
`
`

`
`!
`i
`
`1
`i1
`
`IlI 1
`
`vlll
`
`CDNTE NTS
`
`THE DATA LINK LAYER
`
`196
`
`4.! DATA LINK LAYER DESIGN ISSUES I97
`4. LI Services Provided to me Network Layer
`4.1.2 Framing I99
`4.1.3 En“or Control 202
`4.1.4 Flow Control 203
`4.l.5 Link management 204
`
`19'?
`
`4.2 ERROR DE'I'ECl'lON AND CORRECTION 204
`4.2.] Error-Correcting Codes 206
`4.2.2 Enor-Detecting Codes 205
`4.3 ELEMENTARY DATA LINK PROTOCOLS 212
`4.3.] An Unrestricted Simple: Protocol 216
`4.3.2 A Simple: Stop-and-Wait Protocol 21'!
`4.3.3 A Simple: Protocol for a Noisy Channel 219
`SLIDING WINDOW PROTOCOLS 223
`4.4.1 A One Bil Sliding Window Protocol 225
`4.4.2 A Protocol Using Go Back It 223
`4.4.3 A Protocol Using Selective Repeat 234
`PROTOCOL PERFORMANCE 239
`4.5.] Perfonrtance of the Stop-and-Wait Protocol 239
`4.5.2 Perfonttance of the Sliding window Protocol 242
`
`4.4
`
`4.5
`
`4.6 PROTOCOL SPECIHCATION AND VERIFICATION 244
`
`4.6.] Finite State Machine Models 245
`4.6.2 The Estelle Protocol Specification Language 25]
`4.6.3 Petri Net Models 252
`4.7 EXAMPLES OF THE DATA LINK LAYER 253
`4.1.1 The Data Link Layer in Public Networks 254
`4.7.2 The Data Link Layer in the ARPANET 257
`4.7.3 The Data Link Layer in MAP and TOP 262
`4.7.4 The Data Link Layer in USENET 265
`SUMMARY 26?
`
`4.?
`
`THE NETWORK LAYER
`
`2'71
`
`5.1 NETWORK. LAYER DESIGN ISSUES 211
`5.1.! Services Provided to tlte Transport Layer 271
`5.1.2 lnlernal Organization of the Network Layer 280
`5.1.3 Routing 234
`5.1.4 Congestion 287
`5.I.5 lntemetworlting 288
`
`Petitioner Microsoft - Ex. 1005, p. Viii
`
`
`
`'PDfiI‘IIO.I.K/sn
`
`Petitioner Microsoft - Ex. 1005, p. viii
`
`

`
`5.2 ROUTING ALGORITHMS 289
`5.2.1 Sltot1.estPa.'Ih Routing 289
`5.2.2 Multipalh Routing 291
`5.2.3 Centrnliud Routing 294
`5.2.4 Isolated Routing 296
`5.2.5 Flooding 298
`5.2.6 Distributed Routing 299
`5.2.7 Optimal Routing 3120
`5.2.8 Flow-Based Routing 303
`5.2.9 Hieramhical Routing 305
`5.2.10 Broadcast Routing 3%
`
`5.3 CONGESTION CONTROL ALGORITHMS 309
`5.3.1 Preallocation of Buffers 309
`5.3.2 I-"ncke1Discarding 310
`5.3.3 Isarilhmic Congestion Control 312
`5.3.4 Flow Control 313
`5.3.5 Choke Packets 314
`5.3.6 Deedlocks 315
`
`5 ,4
`
`INTERNETWORKING 320
`5.4.1 OS] and Internetworking 321
`5.4.2 Bridger.
`325
`5.4.3 Gntcw ays 337
`5.4.4 Comparison of Connection-Oriented and Connectionlcss Gateways 345
`5.4.5 Bridge and Gateway Software 346
`
`5.5 EXAMPLES OF THE NETWORK LAYER 350
`5.5.] The Network Layer in Public Networks 350
`5.5.2 The Network Layer in the ARPANET (IF) 358
`5.5.3 The Nelwork Layer in MAP and TOP 362
`5.5.4 The Network Layer in USENET 363
`SUMMARY 365
`
`5.6
`
`THE TRANSPORT LAYER
`
`370
`
`6.l TRANSPORT LAYER DESIGN ISSUES 37]
`6.1.]. Services Provided to the Session Layer 3?!
`6.1.2 Quality of Service 373
`6.1.3 The OS! Transport Service Primitives
`6.I.-I Tu-anspon Protocols
`311!
`6.1.5 Elements of Transpon Protocols 384
`
`3'15
`
`Petitioner Microsoft - Ex. 1005, p. ix
`
`Petitioner Microsoft - Ex. 1005, p. ix
`
`

`
`
`
`SOPIIO{LN/SW
`
`CONTENTS
`
`6.2 CONNECHON MANAGEMENT 38'?
`6.2.1 Addressing 388
`62.2 Establishing nconoection 391
`6.2.3 Releasingaconnection 397
`6.2.4 Timer-Based Connection Management 401
`6.2.5 Flow Cootml and Buffering 403
`6.2.6 Multiplexing 4-U7
`6.2.7 Crash Recovery 409
`6.3 A SIMPLE TRANSPORT PRUIDCOL ON TOP OF X25 41 1
`6.3.1 The Example Service Primitives 411
`6.3.2 The Example Transpon Entity 413
`6.3.3 The Example as a Finite State Machine 420
`
`6.4 EXAMPLES OF '11-l.[-ITRANSPDRT LAYER 422
`6.4.1 The Transport Layer in Public Networks 122
`6.4.2 The Transport Layer in the ARPANET {TCP) 429
`6.4.3 The Transpon Layer in MAP and TOP 435
`6.4.4 The "l‘ranspDn. Layer in USENET 436
`6.5 SUMMARY 436
`
`THE SESSION LAYER
`
`440
`
`7.1
`
`SESSION LAYER DESIGN ISSUES 441
`7.1.1 Services Provided to the Presentation Layer 441
`7.1.2 Data Exchange 443
`7.1.3 Dialog Management. 444
`7.1.4 Synchronization 446
`7.1.5 Activity Management 448
`7.1.6 Exception Reporting 451
`7.1.? The 031 Session Service Primitives 451
`
`7.2 REMOTE PROCEDURE CALL 454
`7.2.1 111: Client-Server Model 455
`7.2.2 Implementation of Remote Procedure Call 456
`7.2.3 Semantics of Remote Procedure Call 460
`7.2.4 Orphans 462
`7.2.5 Discussion of RPC 464
`
`7.3 EXAMPLES OFTHE SESSION LAYER 46.5
`7.3.1 The Session Layer in Public Network: 465
`7.3.2 ‘The Session Layer in the ARPANET 469
`7.3.3 The Session Layer in MAP and TOP 469
`7.3.4 Thesession Layer in USENET 469
`7.4 SUMMARY 469
`
`.
`
`'
`
`..__--
`
`Petitioner Microsoft - Ex. 1005, p. x
`
`Petitioner Microsoft - Ex. 1005, p. x
`
`

`
`CONTENTS
`
`THE PRESENTATION LAYER
`
`Ll
`
`471
`
`8.1
`
`PRESENTATION LAYER DESIGN ISSUES H2
`8.1.1 Data Representation 472
`3.1.2 Data Compression 473
`8.1.3 Network Security and Privacy 473
`8.1.4 The OS] Presentation Service Primitives 475
`
`8.2 ABSTRACT SYNTAX NOTATION I (ASN.1) 475
`8.2] Dalastructures 476
`8.2.2 Abstract Syntax 481
`8.2.3 Transfer Syntax 481'
`
`8.3 DATA COMPRESSION 'I"E-‘CI-INIQUES 490
`8.3.1 Encoding I Finite Set of Equally Likely Symbols 49!
`8.3.2 Frequency Dependent Coding 491
`3.3.3 Context Dependent Encoding 494
`8.4 CRYFIUGRAPHY 496
`8.4.1 ‘Traditional Cryptography 496
`8.4.2 The Data Encryption Standard 503
`8.4.3 The Key Distribution Problem 510
`3.4.4 Public Key Cryptography 513
`8.4.5 Authentication and Digital Signatures SIG
`8.5 EXAMPLES OF THE PRESENTATION LAYER S20
`8.5.! The Presentation Layer in Public Networks 52]
`8.5.2 The Presentation Layer In the ARPANET 523
`8.5.3 1113 Presentation Layer in MAP and TOP 524
`8.5.4 The Presentation Layer in USENET 524
`8.6 SUMMARY 524
`
`THE APPLICATION LAYER
`
`528
`
`9.] APPLICATION LAYER DESIGN ISSUES 528
`9.1.1 File Transfer. Access. and Matnagentenl 529
`9.1.2 Electronic Mail 530
`9.1.3 Virtual Terminals 53I
`‘J.l.4 Other Applications 531
`9.1.5 051 Service Elernents-—-ACSE. and CCR 532
`
`9.2
`
`FILE TRANSFER. ACCESS. AND MANAGEMENT 535
`9.2.l File Servers 535
`9.2.2 Concurrency Control 539
`
`Petitioner Microsoft - Ex. 1005, p. xi
`
`Petitioner Microsoft - Ex. 1005, p. xi
`
`

`
`xii
`
`cuun-gm 5
`
`
`
`90fT'l.’0,3”/SH
`
`9.2.3 Replicaled files 540
`9.2.4 lmplementationlssues 542
`9.3 ELECTRONIC MAIL 546
`9.3.1 Architecture and Services of M0118 and X41!) 541
`9.3.2 The User Agent 551
`9.3.1 The Message Transfer Agent 555
`9.4 VIRTUALTERMINALS 538
`9.4.1 Scroll ModeTerm'nta1s 559
`9.4.2 Page Mode Terminals 561
`9.4.3 Form ModeTermina1s 562
`
`0.5 UTHER APPLICATIONS 569
`9.5.1 Directory Service 569
`9.5.2 lobTransfer and Management 571
`9.5.3 Picture Storage and Transfer 573
`9.5.4 Teletext and Videolex S74
`
`9.6 EXAMPLES OFTI-IE APPLICATION LAYER 576
`9.6.1 The Application Layer in Public Networks 576
`9.6.2 The Application Layer in the ARPANET 587
`9.6.3 The Application Layer in MAP and TOP 593
`9.6.4 The Application Layer in USENET 598
`9.7 SUMMARY 604
`
`10 ruaanmc us'r AND BIBLIOGRAPHY
`
`soc
`
`10.1
`
`SUGGESTIONS FOR FURTHER READING 608
`10.1.1
`Introduction and General Works 609
`10.1.2 The Physical Layer 610
`10.1.3 The Medium Access Control Sublayer 61 1
`10.1.4 The Data Link Layer 611
`10.1.5 The Network Layer 612
`10.1.6 The Transpon Layer 612
`10.1.7 The Session Layer 613
`10.1.8 The Presentation Layer 614
`10.1.9 The Application Layer 615
`10.2 ALPHABETICAL BIBLIOGRAPHY 615
`
`A APPENDIX: QUEUEING THEORY
`
`INDEX
`
`63]
`
`642
`
`Petitioner Microsoft - Ex. 1005, p. xii
`
`

`
`PREFACE
`
`Computer networking has changed enormously over the past decade. and this
`book has changed along with it. Ten years ago. computer networks were exotic
`research tools used only by few specialists. Today. computers ranging from per-
`sonal computers to supercomputers are more likely to be part of a network than not.
`Most organizations that use computers either already have. or are soon planning to
`install. one or more local area networks. Worldwide electronic mail is a daily real-
`ity for millions of people.
`In short. networks have evolved from an academic
`curiosity to an essential tool for users in business. government. and universities.
`Only a few short years ago. the design of a computer network was something of
`a black an. Every computer manufacturer had its own network architecture. no two
`of which were compatible. All that has changed now. Virtually the entire com-
`puter industry has now agreed to a series of lntemational Standards for describing
`network architectures. These standards are known as the OSI Reference Model. In
`the near future. almost all other network architectures will disappear. and comput-
`ers from one vendor will be able to communicate effortlessly with computers from
`another vendor. thus stimulating network usage even more.
`This book uses the OSI Reference Model as a framework. The model is based
`on a principle first enunciated by Julius Caesar: Divide and Conquer. The idea is to
`design networks as a sequence of layers. one based upon the previous one. By
`reducing the study of the whole to the study of its parts. the entire process becomes
`more manageable.
`
`xiii
`
`Petitioner Microsoft - Ex. 1005, p. xiii
`
`

`
`[IV
`
`PREFACE
`
`Because networking has changed so much since the first edition, this second
`edition is almost a completely new book. Over half of the material is completely
`new. and much of the remainder has also been heavily updated and improved.
`Whole new areas are now discussed in detail. including ISDN. LANs. fiber optics.
`and bridges. The treatment of the upper OS] layers has been completely rewritten
`and expanded by over a hundred pages to include important topics such as the OS]
`transport protocols, ASNJ. FTAM. and VTP. New networks.
`including MAP.
`“FOP. and USENET are now examined in some detail and network software is also
`given more coverage.
`The idea of organizing the book around the seven O51 layers has proved very
`successful and has been retained in this second edition. Chapter 1 provides an
`introduction to the subject of computer networks in general and layered protocols in
`particular. The next five chapters deal with the lower layers. physical through tran-
`spon. which collectively are the providers of the transport service. Chapter 2 cov-
`ers physical media. analog and digital
`transmission.
`the telephone system and
`ISDN. Chapter 3 Ioolts at the MAC sublayer and local area ruttworlts, including
`IEEE standard 302. Chapter 4 is about the data link layer and its protocols: algo-
`rithms for reliably transmitting data over unreliable lines. Chapter 5 treats the net-
`work layer, especially routing. congestion control. and intcrnetworking. Finally.
`chapter 6 studies the transport layer.
`in particular. connection management and
`end-to-end protocols.
`The last three chapters deal with the upper layers. the users of the transport ser-
`vice. Chapter 7 is about the session layer. which is concerned with providing reli-
`able service. even in the face of unreliable hardware. Chapter 8 covers the presen-
`tation layer.
`including the OSI abstract syntax notation, data compression, and
`cryptography. Chapter 9 provides an introduction to some application layer issues.
`including file transfer. electronic mail. vinual
`terminals. remote job entry, and
`directory services. Chapter 10 contains a reading list and bibliography.
`Queueing theory is a basic mathematical tool that is used to analyze computer
`networks. so an appendix is provided on it for die benefit of readers not familiar
`with this subject.
`The book can be used as a text for undergraduates or beginning graduate stu-
`dents in computer science. electrical engineering. and related disciplines. The only
`prerequisites are a general familiarity with computer systems and programming,
`although a little knowledge of elementary calculus and probability theory is useful
`in a few places. but is not essential. Some of the exarnples are given in Pascal. so
`some knowledge of this. or a similar programming language is a plus. Since the
`amount of material in the book may be too much for a one semester course. depend-
`ing on the level of the students. 1 have made a serious attempt to make each chapter
`relatively independent of the other ones.
`In this way an insuuctor could choose to
`emphasize, for example. data communication and the lower layers. or alternatively.
`software and the upper layers.
`The book can also be used by computer professionals who are interested in
`
`
`
`LUVETOLN/SH
`
`Petitioner Microsoft - Ex. 1005, p. xiv
`
`Petitioner Microsoft - Ex. 1005, p. xiv
`
`

`
`Hllril-'.M.£l.i
`
`IV
`
`networking. For this reason. I lave attempted to limit the amount of mathematics
`used. and have included numerous practical examples instead of providing many
`pages of abstract tbrivations. Even programmers or technical managers who an:
`not ntuwork specialists should be able to follow a considerable amount of the book.
`Many people have helped rne during the preparation of the second edition.
`I
`would especially like to thank ltrtrich Chlamtac Bdale Garbee. Jol'u1 Henshall.
`Brian Kernighan. John Limb. Chris Makemson. Daniel Pilt. Sandy Shaw. Jennifer
`Steiner and my editor. John Wait.
`I would also like to thank my students for help-
`ing to debug the text. Special
`thanks go to Jeroen Belien. Berend Jan Beugel.
`Remco Feenslra. Anneth tle Gee. Cornelia Kroon. Roemer Lievaart. Maarten Lit-
`maath. Paul Poldemtan. Rob van Swinderen, Luult Uljee. and Felix Yap-
`Last but not least. I would like to thank Suzanne. Barbara. Marvin. and Muis.
`Suzanne for still being so understanding after all these years‘. Barbara and Marvin
`for using their computer instead of mine. thus making this book possible; and and
`Muis for being as quiet as a mouse while I was writing.
`
`ANDREW S. TANENBAUM
`
`Petitioner Microsoft - Ex. 1005, p. xv
`
`Petitioner Microsoft - Ex. 1005, p. xv
`
`

`
`
`
`sonztom/SH
`
`Petitioner Microsoft - Ex. 1005, p. xvi
`
`Petitioner Microsoft - Ex. 1005, p. xvi
`
`

`
`INTRODUCTION
`
`Each of the past three centuries has been dominated by a single technology.
`The eighteenth century was the time of the great mechanical systems accompany-
`ing the Industrial Revolution. The nineteenth century was the age of the steam
`engine. During the twentieth century. the key technology has been infonnation
`gathering. processing. and distribution. Among other developments. we have seen
`the installation of worldwide telephone networks. the invention of radio and televi-
`sion. the birth and unprecedented growth of the computer industry. and the launch-
`ing of communication satellites.
`As we move toward the final years of this century. these areas are rapidly eon-
`verging. and the differences between collecting. transporting. storing. and process-
`ing information are quickly disappearing. Organizations with hundreds of offices
`spread over a wide geographical area routinely expect to be able to examine the
`current status of even their most remote outpost at the push of a button. As our
`ability to gather. process. and distribute infomtation grows. the demand for even
`more sophisticated information processing grows even faster.
`Although the computer industry is young compared to other industries (e.g..
`automobiles and air transportation). computers have made spectacular progress in a
`short time. During the Iirst two decades of their existence. computer systems were
`highly centralized. usually within :1 single large room. Not infrequently. this room
`had glass walls. through which visitors could gawk at the great electronic wonder
`inside. A medium—sizc company or university might have had one or
`two
`
`Petitioner Microsoft - Ex. 1005, p. 1
`
`Petitioner Microsoft - Ex. 1005, p. 1
`
`

`
`2
`
`INTRODUCTION
`
`CHM’.
`
`I
`
`computers. while large institutions had at most a few dozen. The idea that within
`20 years equally powerful computers smaller than postage stamps would be mass
`produced by the millions was pure science flction.
`The merging of computers and communications has had a profound influence
`on the way computer systems are organized. Tire concept of the “computer center"
`as a room with It large computer to which users bring their work for processing is
`rapidly becoming obsolete. This model has not one, but at least two flaws: the con-
`cept of a single large computer doing all the work. and the idea of users bringing
`worlt to the computer instead of bringing the computer to tlte users.
`The old model of a single computer serving all of the organization‘: computa-
`tional needs. is rapidly being replaced by one in which a large number of separate
`but interconnected computers do the job. These systems are called computer net-
`worlts. The design and analysis of these networks are the subjects of this book.
`Tl'trottghDut the book we will use the tenrt "computer network" to mean an
`interconnected collection of atttottomotts computers. Two computers are said to be
`interconnected if they are able to exchange information. The connection need not
`be via a copper wire: lasers. microwaves. and communication satellites can also be
`used. By requiring the computers to be autonomous. we wish to exclude from our
`definition systems in which there is a clear masterfslavc relation.
`If one computer
`can forcibly start. stop. or control another one. the computers are not autonomous.
`A system with one control unit and many slaves is not a network; nor is a large
`computer with remote card readers, printers. and terminals.
`There is considerable confusion in the literature between at computer network
`and a distributed system. The key distinction is that in a distributed system. the
`existence of multiple autonomous computers is transparent {'t.e.. not visible) to the
`user. He? can type a command to run a program. and it runs. it is up to the operat-
`ing system to select the best processor. find and transport all the input files to that
`processor. and put the results in the appropriate place.
`in other words, the user of a distributed system is not aware that there are multi-
`ple processors: it looks like a virtual urtiprocessor. Allocation of jobs to processors
`and files to disks. movement of tiles between where they are stored and where they
`are needed. and all other system functions must be automatic.
`With it network, a user must explicitly log onto one machine. explicitly submit
`jobs remotely. e-.rptr'rr'rly more files around and generally handle all the network
`management personally. With a distributed system. nothing has to be done expli-
`citly: it is all automatically done by the system without the user's knowledge.
`In effect, a distributed system is a special case of It network. one whose
`software gives it a high degree of cohesiveness and transparency. Thus the distinc-
`tion between a network and a distributed system lies with the software (especially
`the operating system}. rather than with the hardware.
`
`1‘ "He" sl'tot.t1r.'l be read its "he or air" throughout this bctot.
`
`sastroan/so
`
`Petitioner Microsoft - Ex. 1005, p. 2
`
`Petitioner Microsoft - Ex. 1005, p. 2
`
`

`
`SEC.
`
`l.l
`
`USES OF COMPU'l'ER NETWORKS
`
`3
`
`Nevertheless. there is a lot of overlap between the two subjects. For example.
`both distributed systems and computer networks need to move files around. The
`difference lies in who invokes the movement. the system or the user. Although this
`book primarily focuses on networks. many of the topics are also important in distri-
`buted systems. For more information about distributed systems. see Crichlow
`(I988). Sloman and Kramer (1987), and Tancnbaurn and van Renesse (I985).
`
`1.1. USES OF COMPUTER NETWORKS
`
`it is worth devoting
`Before we start to examine the technical issues in detail.
`some tirrte to pointing out why people are interested in computer networks and what
`they can be used for.
`
`1.1.1. Network Goals
`
`Many organizations already have a substantial number of computers in opera-
`tion. often located far apan. For example. a company with many factories may
`have a computer at each location to keep track of inventories. monitor productivity.
`and do the local payroll. Initially. each of these computers may have worked in iso-
`lation from the others. but at some point. management may have decided to connect
`them to be able to extract and correlate information about the entire company.
`Put in slightly more general l'om1. the issue here is resource sharing. and the
`goal is to make all programs. data. and equipment available to anyone on the net-
`work without regard to the physical location of the resource and the user.
`In other
`words. the mere fact that a user happens to be 1000 km away from his data should
`not prevent him from using the data as though they were local. Load sharing is
`another aspect of resource sharing. This goal may be summarized by saying that it
`is an attempt to end the "tyranny of geography."
`A second goal is to provide high reliability by having alternative sources of
`supply. For example. all files could be replicated on two or three machines. so if
`one of them is unavailable (due to a hardware failure). the other copies could be
`used.
`in addition. the presence of multiple CPUs means that if one goes down. the
`others may be able to take over its work. although at reduced performance. For
`military. banking. air traflic control. and many other applications. the ability to con-
`tinue operating in the face of hardware problems is of great importance.
`Another goal
`is saving money. Small computers have a much better
`pricelperformancc ratio than large ones. Mainframes are roughly a factor of ten
`faster than the fastest single chip microprocessors. but they cost a thousand times
`more. This imbalance has caused many systems designers to build systems consist-
`log of powerful personal computers. one per user. with data kept on one or more
`shared file server machines.
`
`This goal leads to networks with many computers located in the same building.
`
`Petitioner Microsoft - Ex. 1005, p. 3
`
`Petitioner Microsoft - Ex. 1005, p. 3
`
`

`
`II
`
`INTRODUCTION
`
`CHAP.
`
`1
`
`Such a network is called it LAN (local area network) to contrast it with the far-
`flung WAN (wide area network). which is also called a long haul network.
`A closely related point is the ability to increase system performance gradually
`as the workload grows just by adding more processors. With central mainframes.
`when the system is full. it must be replaced by a larger one. usually at great expense
`and with even greater disruption to the users.
`Yet another goal of setting up a computer network has little to do with technol-
`ogy at all. A computer network can provide a powerful cotnmttttictttioll Iltetliuttl
`among widely separated people. Using a network, it is easy for two or more people
`who live far apart to write a report together. when one author makes a change to
`the document. which is kept online. the others can see the change immediately.
`instead of waiting several days for a letter. Such a speedup makes cooperation
`among lanflung groups of people easy where it previously had been impossible.
`In
`the long run. the use of networks to enhance human-to-human communication may
`prove more important than technical goals such as improved reliability.
`In Fig. l-l we give at classification of multiple processor systems arranged by
`physical size. At the top are data How machines. highly parallel computers with
`many functional units all working on the same program. Next come the multi-
`processors. systems that communicate via shared memory. Beyond the multipro-
`cessors are the true networks, computers that communicate by exchanging mes~
`sages. Finally. the connection of two or more networks is called lnternetworking.
`Into-rprocr--ssor Processors located
`E :<;mtnlt-
`distance
`in same
`
`fi }°v*- "ow
`5 3fl1Hi9
`System
`gr;
`
`Local network
`
`
`
`@m
`
`ince km } Innerconni.-ct-on ol long haul networks
`
`Fig. I-I. Classification of interconnected processors by scale.
`
`l.l.2. Applications of Networks
`
`Replacing a single rnairtframe by workstations on a LAN does not make many
`new applications possible. although it may improve the reliability and perfonttanoe.
`In contrast.
`the availability of a (public) WAN makes many new applications
`
`Petitioner Microsoft - Ex. 1005, p. 4
`
`
`
`01:‘!-‘I210.r.n/st»:
`
`Petitioner Microsoft - Ex. 1005, p. 4
`
`

`
`SEC. L2
`
`USES OF CUMPUTL-LR 1NlE'l'WUR.KS
`
`3
`
`feasible. Some of these new applications may have important effects on society as
`a whole. To give an idea about some important uses of computer networks. we will
`now briefly look at just three examples: access to remote programs. access to
`remote databases. and value-added communication facilities.
`A company that has produced a model simulating the world economy may
`allow its clients to log in over the network and run the program to see how various
`projected inflation rates. interest rates. and currency fluctuations might affect their
`businesses. This approach is often preferable to selling the program outright, espe-
`cially if the model is constantly being adjusted or requires an extremely large main-
`frame computer to run.
`It may soon
`Another major area of network use is access to remote databases.
`be easy for the average person sitting at home to make reservations for airplanes.
`trains. buses. boats, hotels, restaurants. theaters. and so on. anywhere in the world
`with instant confirmation. Home banking and the automated newspaper also fall in
`this category. Present newspapers offer a little bit of everything. but electronic
`ones can be easily tailored to each reader's personal taste. for example. everything
`about computers. the major stories about politics and epidemics. but no football.
`thank you.
`The next step beyond automated newspapers (plus magazines and scientific
`journals) is the fully automated library. Depending on the cost. size. and weight of
`the terminal. the printed word may become obsolete. Skeptics should take note of
`the effect the printing press had on the medieval illuminated manuscript.
`All these applications use networking for economic reasons: calling up a distant
`computer via a network is cheaper than calling it directly. The lower rate is possi~
`ble because a normal telephone call ties up an expensive. dedicated circuit for the
`duration of the call. whereas access via a network ties up long-distance lines only
`while data are actually being transmitted.
`A third category of potential widespread network use is as a communication
`medium. Computer scientists already take it for granted that they can send elec-
`tronic mail from their terminals to their colleagues anywhere in the world.
`In the
`future. it will be possible for everyone. not just people in the computer business. to
`send and receive electronic mail. Furthermore. this mail will also be able to con-
`
`tain digitized voicc. still pictures and possibly cvcn moving television and video
`images. One can easily imagine children in different countries trying to learn each
`other's languages by drawing a picture of a child on a shared screen and labeling it
`girl. jeune fille. or meisjc.
`Electronic bulletin board systems already exist. but these tend to be used by
`comput