Computer Networks
`Third Edition
`
`Andrew S. Tanenbaum
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`For book and bookstore information
`
`http://www.prenhall.com
`
`g
`
`Prentice Hall PTR
`Upper Saddle River, New Jersey 07458
`
`Page 1 of 92
`
`Mercedes Exhibit 1010
`
`

`
`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, Andrew S. 1944-.
`Computer networks I Andrew S. Tanenbaum. -- 3rd ed.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-13-349945-6
`!.Computer networks.
`TK5105.5.T36 1996
`004.6--dc20
`
`I. Title.
`
`96-4121
`CIP
`
`EditoriaVproduction manager: Camille Trentacoste
`Interior design and composition: Andrew S. Tanenbaum
`Cover design director: Jerry Votta
`Cover designer: Don Martinetti, DM Graphics, Inc.
`Cover concept: Andrew S. Tanenbaum, from an idea by Marilyn Tremaine
`Interior graphics: Hadel Studio
`Manufacturing manager: Alexis R. Heydt
`Acquisitions editor: Mary Franz
`Editorial Assistant: Noreen Regina
`
`© 1996 by Prentice Hall PTR
`Prentice-Hall, Inc.
`A Simon & Schuster Company
`Upper Saddle River, New Jersey 07458
`
`The publisher offers discounts on this book when ordered in bulk quantities. For more information,
`contact:
`Corporate Sales Department, Prentice Hall PTR, One Lake Street, Upper Saddle River, NJ 07458.
`Phone: (800) 382-3419; Fax: (201) 236-7141. E-mail: corpsales@prenhall.com
`
`All rights reserved. No part of this book may be reproduced, in any form or by any means, without
`permission in writing from the publisher.
`
`All product names mentioned herein are the trademarks of their respective owners.
`
`Printed in the United States of America
`10 9 8 7 6 5 4
`
`ISBN 0-13-349945-6
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hall Hispanoamericana, S.A., Mexico
`Prentice-Hall of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Simon & Schuster Asia Pte. Ltd., Singapore
`Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`Page 2 of 92
`
`

`
`To Su;::anne, Barbara, Marvin, and Little Brarn
`
`Page 3 of 92
`
`

`
`CONTENTS
`
`PREFACE
`
`1 INTRODUCTION
`
`XV
`
`1
`
`1.1 USES OF COMPUTER NETWORKS 3
`1.1.1 Networks for Companies 3
`1.1.2 Networks for People 4
`1.1.3 Social Issues 6
`
`1.2 NETWORK HARDWARE 7
`1.2.1 Local Area Networks 9
`1.2.2 Metropolitan Area Networks 10
`1.2.3 Wide Area Networks 11
`1.2.4 Wireless Networks 13
`1.2.5 Internetworks 16
`
`1.3 NETWORK SOFTWARE 16
`1.3.1 Protocol Hierarchies 17
`1.3.2 Design Issues for the Layers 21
`1.3.3 Interfaces and Services 22
`1.3.4 Connection-Oriented and Connectionless Services 23
`1.3.5 Service Primitives 25
`1.3.6 The Relationship of Services to Protocols 27
`
`1.4 REFERENCE MODELS 28
`1.4.1 The OSI Reference Model 28
`1.4.2 The TCP/IP Reference Model 35
`1.4.3 A Comparison of the OSI and TCP Reference Models 38
`1.4.4 A Critique of the OSI Model and Protocols 40
`1.4.5 A Critique of the TCP/IP Reference Model 43
`
`1.5 EXAMPLE NETWORKS 44
`1.5.1 Novell NetWare 45
`1.5.2 The ARPANET 47
`1.5.3 NSFNET 50
`1.5.4 The Internet 52
`1.5.5 Gigabit Testbeds 54
`
`vi
`
`Page 4 of 92
`
`

`
`CONTENTS
`
`vii
`
`1.6 EXAMPLE DATA COMMUNICATION SERVICES 56
`1.6.1 SMDS-Switched Multimegabit Data Service 57
`1.6.2 X.25 Networks 59
`1.6.3 Frame Relay 60
`1.6.4 Broadband ISDN and A TM 61
`1.6.5 Comparison of Services 66
`
`1.7 NETWORK STANDARDIZATION 66
`1.7.1 Who's Who in the Telecommunications World 67
`1.7.2 Who's Who in the International Standards World 69
`1.7.3 Who's Who in the Internet Standards World 70
`
`1.8 OUTLINE OF THE REST OF THE BOOK 72
`
`1.9. SUMMARY 73
`
`2 THE PHYSICAL LAYER
`
`77
`
`2.1 THE THEORETICAL BASIS FOR DATA COMMUNICATION 77
`2.1.1 Fourier Analysis 78
`2.1.2 Bandwidth-Limited Signals 78
`2.1.3 The Maximum Data Rate of a Channel 81
`
`2.2
`
`2.3
`
`2.4
`
`TRANSMISSION MEDIA 82
`2.2.1 Magnetic Media 82
`2.2.2 Twisted Pair 83
`2.2.3 Baseband Coaxial Cable 84
`2.2.4 Broadband Coaxial Cable 85
`2.2.5 Fiber Optics 87
`
`WIRELESS TRANSMISSION 94
`2.3.1 The Electromagnetic Spectrum 94
`2.3.2 Radio Transmission 97
`2.3.3 Microwave Transmission 98
`2.3.4 Infrared and Millimeter Waves 100
`2.3.5 Lightwave Transmission 100
`
`THE TELEPHONE SYSTEM 102
`2.4.1 Structure of the Telephone System
`2.4.2 The Politics of Telephones
`I 06
`2.4.3 The Local Loop 108
`2.4.4 Trunks and Multiplexing 118
`2.4.5 Switching 130
`
`I 03
`
`Page 5 of 92
`
`

`
`viii
`
`CONTENTS
`
`2.5 NARROWBAND ISDN
`I 39
`2.5.1
`ISDNServices 140
`ISDN System Architecture 140
`2.5.2
`2.5.3 The ISDN Interface 142
`2.5.4 Perspective on N-ISDN 143
`
`2.6 BROADBAND ISDN AND ATM 144
`2.6.1 Virtual Circuits versus Circuit Switching 145
`2.6.2 Transmission in ATM Networks 146
`2.6.3 ATM Switches 147
`
`2.7 CELLULAR RADIO 155
`2.7.1 Paging Systems
`ISS
`2.7 .2 Cordless Telephones
`I 57
`2. 7.3 Analog Cellular Telephones 157
`2. 7.4 Digital Cellular Telephones 162
`2.7 .S Personal Communications Services 162
`
`2.8 COMMUNICATION SATELLITES 163
`2.8.1 Geosynchronous Satellites 164
`2.8.2 Low-Orbit Satellites 167
`2.8.3 Satellites versus Fiber 168
`
`2.9 SUMMARY 170
`
`3
`
`THE DATA LINK LAYER
`
`175
`
`3.1 DATA LINK LAYER DESIGN ISSUES 176
`3.1.1 Services Provided to the Network Layer
`3.1.2 Framing 179
`3.1.3 Error Control 182
`3.1.4 Flow Control 183
`
`176
`
`3.2 ERROR DETECTION AND CORRECTION
`3.2.1 Error-Correcting Codes 184
`3.2.2 Error-Detecting Codes 186
`
`183
`
`3.3 ELEMENTARY DATA LINK PROTOCOLS
`3.3.1 An Unrestricted Simplex Protocol 195
`3.3.2 A Simplex Stop-and-Wait Protocol 195
`3.3.3 A Simplex Protocol for a Noisy Channel
`
`190
`
`197
`
`Page 6 of 92
`
`

`
`CONTENTS
`
`ix
`
`3.4 SLIDING WINDOW PROTOCOLS 202
`3.4.1 A One Bit Sliding Window Protocol 206
`3.4.2 A Protocol Using Go Back n 207
`3.4.3 A Protocol Using Selective Repeat 213
`
`3.5 PROTOCOL SPECIFICATION AND VERIFICATION 219
`3.5.1 Finite State Machine Models 219
`3.5.2 Petri Net Models 223
`
`3.6 EXAMPLE DATA LINK PROTOCOLS 225
`3.6.1 HDLC-High-1eve1 Data Link Control 225
`3.6.2 The Data Link Layer in the Internet 229
`3.6.3 The Data Link Layer in ATM 235
`
`3.7. SUMMARY 239
`
`4 THE MEDIUM ACCESS SUBLA YER
`
`243
`
`4.1 THE CHANNEL ALLOCATION PROBLEM 244
`4.1.1 Static Channel Allocation in LANs and MANs 244
`4.1.2 Dynamic Channel Allocation in LANs and MANs 245
`
`4.2 MULTIPLE ACCESS PROTOCOLS 246
`4.2.1 ALOHA 246
`4.2.2 Carrier Sense Multiple Access Protocols 250
`4.2.3 Collision-Free Protocols 254
`4.2.4 Limited-Contention Protocols 256
`4.2.5 Wavelength Division Multiple Access Protocols 260
`4.2.6 Wireless LAN Protocols 262
`4.2.7 Digital Cellular Radio 266
`
`4.3 IEEE STANDARD 802 FOR LANS AND MANS 275
`4.3.1
`IEEE Standard 802.3 and Ethernet 276
`4.3.2 IEEE Standard 802.4: Token Bus 287
`4.3.3 IEEE Standard 802.5: Token Ring 292
`4.3.4 Comparison of 802.3, 802.4, and 802.5 299
`4.3.5 IEEE Standard 802.6: Distributed Queue Dual Bus 301
`4.3.6 IEEE Standard 802.2: Logical Link Control 302
`
`Page 7 of 92
`
`

`
`X
`
`CONTENTS
`
`4.4 BRIDGES 304
`4.4.1 Bridges from 802.x to 802.y 307
`4.4.2 Transparent Bridges 310
`4.4.3 Source Routing Bridges 314
`4.4.4 Comparison of 802 Bridges 316
`4.4.5 Remote Bridges 317
`
`4.5 HIGH-SPEED LANS 318
`4.5.1 FDDI 319
`4.5.2 Fast Ethernet 322
`4.5.3 HIPPI-High-Performance Parallel Interface 325
`4.5.4 Fibre Channel 326
`
`4.6
`
`SATELLITE NETWORKS 327
`4.6.1 Polling 328
`4.6.2 ALOHA 329
`4.6.3 FDM 330
`4.6.4 TDM 330
`4.6.5 COMA 333
`
`4.7 SUMMARY 333
`
`5 THE NETWORK LAYER
`
`339
`
`5.1 NETWORK LAYER DESIGN ISSUES 339
`5.1.1 Services Provided to the Transport Layer 340
`5.1.2 Internal Organization of the Network Layer 342
`5.1.3 Comparison of Virtual Circuit and Datagram Subnets 344
`5.2 ROUTING ALGORITHMS 345
`5.2.1 The Optimality Principle 347
`5.2.2 Shortest Path Routing 349
`5.2.3 Flooding 351
`5.2.4 Flow-Based Routing 353
`5.2.5 Distance Vector Routing 355
`5.2.6 Link State Routing 359
`5.2.7 Hierarchical Routing 365
`5.2.8 Routing for Mobile Hosts 367
`5.2.9 Broadcast Routing 370
`5.2.10 Multicast Routing 372
`
`Page 8 of 92
`
`

`
`CONTENTS
`
`xi
`
`5.3 CONGESTION CONTROL ALGORITHMS 374
`5.3.1 General Principles of Congestion Control 376
`5.3.2 Congestion Prevention Policies 378
`5.3.3 Traffic Shaping 379
`5.3.4 Flow Specifications 384
`5.3.5 Congestion Control in Virtual Circuit Subnets 386
`5.3.6 Choke Packets 387
`5.3.7 Load Shedding 390
`5.3.8 Jitter Control 392
`5.3.9 Congestion Control for Multicasting 393
`
`5.4 INTERNETWORKING 396
`5.4.1 How Networks Differ 399
`5.4.2 Concatenated Virtual Circuits 401
`5.4.3 Connectionless Internetworking 402
`5.4.4 Tunneling 404
`5.4.5 Internetwork Routing 405
`5.4.6 Fragmentation 406
`5 .4. 7 Fire walls 410
`
`5.5 THE NETWORK LAYER IN THE INTERNET 412
`5.5.1 The IP Protocol 413
`5.5.2 IP Addresses 416
`5.5.3 Subnets 417
`5.5.4 Internet Control Protocols 419
`5.5.5 The Interior Gateway Routing Protocol: OSPF 424
`5.5.6 The Exterior Gateway Routing Protocol: BGP 429
`5.5.7 Internet Multicasting 431
`5.5.8 Mobile IP 432
`5.5.9 CIDR-Classless InterDomain Routing 434
`5.5.10 IPv6 437
`
`5.6 THE NETWORK LAYER IN ATM NETWORKS 449
`5.6.1 Cell Formats 450
`5.6.2 Connection Setup 452
`5.6.3 Routing and Switching 455
`5.6.4 Service Categories 458
`5.6.5 Quality of Service 460
`5.6.6 Traffic Shaping and Policing 463
`5.6.7 Congestion Control 467
`5.6.8 ATM LANs 471
`
`5.7 SUMMARY 473
`
`Page 9 of 92
`
`

`
`xii
`CONTENTS
`6 THE TRANSPORT LAYER
`
`479
`
`6.1 THE TRANSPORT SERVICE 479
`6.1.1 Services Provided to the Upper Layers 479
`6.1.2 Quality of Service 481
`6.1.3 Transport Service Primitives 483
`
`6.2 ELEMENTS OF TRANSPORT PROTOCOLS 488
`6.2.1 Addressing 489
`6.2.2 Establishing a Connection 493
`6.2.3 Releasing a Connection 498
`6.2.4 Flow Control and Buffering 502
`6.2.5 Multiplexing 506
`6.2.6 Crash Recovery 508
`
`6.3 A SIMPLE TRANSPORT PROTOCOL 510
`6.3.1 The Example Service Primitives 510
`6.3.2 The Example Transport Entity 512
`6.3.3 The Example as a Finite State Machine 519
`
`6.4 THE INTERNET TRANSPORT PROTOCOLS (TCP AND UDP) 521
`6.4.1 The TCP Service Model 523
`6.4.2 The TCP Protocol 524
`6.4.3 The TCP Segment Header 526
`6.4.4 TCP Connection Management 529
`6.4.5 TCP Transmission Policy 533
`6.4.6 TCP Congestion Control 536
`6.4.7 TCP Timer Management 539
`6.4.8 UDP 542
`6.4.9 Wireless TCP and UDP 543
`
`6.5 THE ATM AAL LAYER PROTOCOLS 545
`6.5.1 Structure of the ATM Adaptation Layer 546
`6.5.2 AAL 1 547
`6.5.3 AAL 2 549
`6.5.4 AAL 3/4 550
`6.5.5 AAL 5 552
`6.5.6 Comparison of AAL Protocols 554
`6.5.7 SSCOP-Service Specific Connection-Oriented Protocol 555
`
`6.6 PERFORMANCE ISSUES 555
`6.6.1 Performance Problems in Computer Networks 556
`6.6.2 Measuring Network Performance 559
`
`Page 10 of 92
`
`

`
`CONTENTS
`
`xiii
`
`6.6.3 System Design for Better Performance 561
`6.6.4 Fast TPDU Processing 565
`6.6.5 Protocols for Gigabit Networks 568
`
`6.7 SUMMARY 572
`
`7 THE APPLICATION LAYER
`
`577
`
`7.1 NETWORK SECURITY 577
`7 .1.1 Traditional Cryptography 580
`7.1.2 Two Fundamental Cryptographic Principles 585
`7.1.3 Secret-Key Algorithms 587
`7.1.4 Public-Key Algorithms 597
`7.1.5 Authentication Protocols 601
`7 .1.6 Digital Signatures 613
`7 .1. 7 Social Issues 620
`
`7.2 DNS-DOMAIN NAME SYSTEM 622
`7.2.1 The DNS Name Space 622
`7.2.2 Resource Records 624
`7.2.3 Name Servers 628
`
`7.3 SNMP-SIMPLE NETWORK MANAGEMENT PROTOCOL 630
`7.3.1 The SNMP Model 631
`7.3.2 ASN.1-Abstract Syntax Notation 1 633
`7.3.3 SMI-Structure of Management Information 639
`7.3.4 The MIB-Management Information Base 641
`7.3.5 The SNMP Protocol 642
`
`7.4 ELECTRONIC MAIL 643
`7 .4.1 Architecture and Services 645
`7.4.2 The User Agent 646
`7.4.3 Message Formats 650
`7 .4.4 Message Transfer 657
`7.4.5 Email Privacy 663
`
`7.5 USENET NEWS 669
`7.5 .1 The User View of USENET 670
`7.5.2 How USENET is Implemented 675
`
`Page 11 of 92
`
`

`
`xiv
`
`CONTENTS
`
`7.6 THE WORLD WIDE WEB 681
`7.6.1 The Client Side 682
`7.6.2 The Server Side 685
`7.6.3 Writing a Web Page in HTML 691
`7.6.4 Java 706
`7.6.5 Locating Information on the Web 720
`
`7.7 MULTIMEDIA 723
`7.7.1 Audio 724
`7.7.2 Video 727
`7. 7.3 Data Compression 730
`7.7.4 Video on Demand 744
`7.7.5 MBone-Multicast Backbone 756
`
`7.8 SUMMARY 760
`
`8 READING LIST AND BIBLIOGRAPHY
`
`767
`
`8.1 SUGGESTIONS FOR FURTHER READING 767
`8.1.1 Introduction and General Works 768
`8.1.2 The Physical Layer 769
`8.1.3 The Data Link Layer 770
`8.1.4 The Medium Access Control Sublayer 770
`8.1.5 The Network Layer 771
`8.1.6 The Transport Layer 772
`8.1.7 The Application Layer 772
`
`8.2 ALPHABETICAL BIBLIOGRAPHY 775
`
`INDEX 795
`
`Page 12 of 92
`
`

`
`PREFACE
`
`This book is now in its third edition. Each edition has corresponded to a dif(cid:173)
`ferent phase in the way computer networks were used. When the first edition
`appeared in 1980, networks were an academic curiosity. When the second edition
`appeared in 1988, networks were used by universities and large businesses. When
`the third edition appeared in 1996, computer networks, especially the worldwide
`Internet, had become a daily reality for millions of people.
`Furthermore, the networking hardware and software have completely changed
`since the second edition appeared. In 1988, nearly all networks were based on
`copper wire. Now, many are based on fiber optics or wireless communication.
`Proprietary networks, such as SNA. have become far less important than public
`networks, especially the Internet. The OSI protocols have quietly vanished, and
`the TCP/IP protocol suite has become dominant. In fact, so much has changed.
`the book has almost been rewritten from scratch.
`Although Chap. I has the same introductory function as it did in the second
`edition, the contents have been completely revised and brought up to date. For
`example, instead of basing the book on the seven-layer OSI modeL a five-layer
`hybrid model (shown in Fig. 1-21) is now used and introduced in Chap. 1. While
`not exactly identical to the TCP/IP modeL it is much closer to the TCP/IP model
`in spirit than it is to the OSI model used in the second edition. Also. the new run(cid:173)
`ning examples used throughout the book-the Internet and A TM networks- are
`introduced here, along with some gigabit networks and other popular networks.
`
`XV
`
`Page 13 of 92
`
`

`
`xvi
`
`PREFACE
`
`In Chap. 2, the focus has moved from copper wire to fiber optics and wireless
`communication, since these are the technologies of the future. The telephone sys(cid:173)
`tem has become almost entirely digital in the past decade, so the material on it has
`been largely rewritten, with new material on broadband ISDN added. The
`material on cellular radio has been greatly expanded, and new material on low(cid:173)
`orbit satellites has been added to the chapter.
`The order of discussion of the data link layer and the MAC sublayer has been
`reversed, since experience with students shows that they understand the MAC
`sublayer better after they have studied the data link layer. The example protocols
`there have been kept, as they have proven very popular, but they have been
`rewritten in C. New material on the Internet and ATM data link layers has been
`added.
`The MAC sublayer principles of Chap. 4. have been revised to reflect new
`protocols, including wavelength division multiplexing, wireless LANs, and digital
`radio. The discussion of bridges has been revised, and new material has been
`added on high-speed LANs.
`Most of the routing algorithms of Chap. 5 have been replaced by more
`modern ones, including distance vector and link state routing. The sections on
`congestion control have been completely redone, and material on the running
`examples, the Internet and ATM is all new.
`Chap. 6 is still about the transport layer, but here, too, major changes have
`occurred, primarily, the addition of a large amount of new material about the
`Internet, A TM, and network performance.
`Chap. 7, on the application layer, is now the longest chapter in the book. The
`material on network security has been doubled in length, and new material has
`been added on DNS, SNMP, email, USENET, the World Wide Web, HTML,
`Java, multimedia, video on demand, and the MBone.
`Of the 395 figures in the third edition, 276 (70 percent) are completely new
`and some of the others have been revised. Of the 371 references to the literature,
`282 (76 percent) are to books and papers that have appeared since the second edi(cid:173)
`tion was published. Of these, over 100 are to works published in 1995 and 1996
`alone. All in all, probably 75 percent of the entire book is brand new, and parts of
`the remaining 25 percent have been heavily revised. Since this is effectively a
`new book, the cover was redesigned to avoid confusion with the second edition.
`Computer books are full of acronyms. This one is no exception. By the time
`you are finished reading this one, all of the following should ring a bell: AAL,
`AMPS, ARP, ASN, ATM, BGP, CDMA, CDPD, CSMA, DQDB, DNS, FAQ,
`FDM, FTP, FTTC, FTTH, GSM, HDLC, HEC, HIPPI, lAB, ICMP, IDEA, IETF,
`IPv6, ISO, ITU, LATA, MAC, MACA, MAN, MIB, MIME, NAP, NNTP, NSA,
`NSAP, OSI, OSPF, PCM, PCN, PCS, PEM, PGP, PPP, PSTN, PTT, PVC, QAM,
`RARP, RFC, RSA, SABME, SAP, SAR, SDH, SDLC, SHA, SMI, SNA, SNMP,
`SNRME, SPX, TCP, UDP, VHF, VLF, VSAT, W ARC, WDM, WWV, and
`WWW. But don't worry. Each one will be carefully defined before it is used.
`
`Page 14 of 92
`
`

`
`PREFACE
`
`xvii
`
`To help instructors using this book as a text for course, the author has
`prepared three teaching aids:
`
`• A problem solutions manual.
`
`• PostScript files containing all the figures (for making overhead sheets).
`
`• A simulator (written in C) for the example protocols of Chap. 3.
`
`The solutions manual is available from Prentice Hall (but only to instructors).
`The file with the figures and the simulator are available via the World Wiele Web.
`To get them, please see the author's home page: http://wlt'w.es. vu.n/1-ast/.
`The book was typeset in Times Roman using TrotT, which, after all these
`years, is still the only way to go. While Troff is not as trendy as WYSIWYG sys(cid:173)
`tems, the reader is invited to compare the typesetting quality of this book with
`books produced by WYSIWYG systems. My only concession to PCs and desktop
`publishing is that for the first time, the art was produced using Adobe Illustrator,
`instead of being drawn on paper. Also for the first time. the book was produced
`entirely electronically. The PostScript output from Troff was sent over the Inter(cid:173)
`net to the printer, where the film for making the offset plates was produced. No
`intermediate paper copy was printed and photographed, as is normally done.
`Many people helped me during the course of the third edition. I would espe(cid:173)
`cially like to thank Chase Bailey, Saniya Ben Hassen. Nathaniel Borenstein, Ron
`Cocchi, Dave Crocker, Wiebren de Jonge, Carl Ellison, M. Rasit Eskicioglu, John
`Evans. Mario Gerla. Mike Goguen, Paul Green, Dick Grune, Wayne Hathaway,
`Franz Hauck, Jack Holtzman, Gerard Holzmann, Philip Homburg, Peter Honey(cid:173)
`man, Raj Jain, Dave Johnson, Charlie Kaufman, Vinay Kumar, Jorg Liebeherr,
`Paul Mockapetris, Carol Orange, Craig Partridge, Charlie Perkins, Thomas
`Powell, Greg Sharp. Anne Steegstra. George Swallow, Mark Taylor, Peter van der
`Linden, Hans van Staveren, Maarten van Steen, Kees Verstoep, Stephen Walters,
`Michael Weintraub . .Joseph Wilkes, and Stephen Wolff. Special thanks go to
`Radia Perlman for many helpful suggestions. My students have also helped in
`many ways. r would like to single out Martijn Bot, Wilbert de Graaf, Flavio del
`Pomo, and Arnold de Wit for their assistance.
`My editor at Prentice Hall, Mary Franz, provided me with more reading
`material than I had consumed in the previous 10 years. She was also helpful in
`numerous other way:--. small, medium. large, and jumbo. My production editor,
`Camille Trentacoste. taught me about people of snow, ~-up flats. fax [sic], and
`other important items, while performing yeoperson's service with a Picky Author
`and a tight schedule.
`Finally, we come to the most important people. Suzanne, Barbara, Marvin,
`and even little Bram, have been through this routine before. They endure it with
`infinite patience and good grace. Thank you.
`
`ANDREWS. TANENBAUM
`
`Page 15 of 92
`
`

`
`Page 16 of 92
`
`Page 16 of 92
`
`

`
`1
`
`INTRODUCTION
`
`Each of the past three centuries has been dominated by a single technology.
`The 18th Century was the time of the great mechanical systems accompanying the
`Industrial Revolution. The 19th Century was the age of the steam engine. During
`the 20th Century, the key technology has been information gathering. processing,
`and distribution. Among other developments, we have seen the installation of
`worldwide telephone networks, the invention of radio and television, the birth and
`unprecedented growth of the computer industry, and the launching of communica(cid:173)
`tion satellites.
`Due to rapid technological progress, these areas are rapidly converging, and
`the differences between collecting, transporting. storing. and processing informa(cid:173)
`tion 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 information grows. the demand for even more sophisti(cid:173)
`cated 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 first two decades of their existence, computer systems
`were highly centralized, usually within a single large room. Not infrequently, this
`room had glass walls, through which visitors could gawk at the great electronic
`wonder inside. A medium-size company or university might have had one or two
`
`Page 17 of 92
`
`

`
`2
`
`INTRODUCTION
`
`CHAP. 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 fiction.
`The merging of computers and communications has had a profound influence
`on the way computer systems are organized. The concept of the "computer
`center" as a room with a large computer to which users bring their work for pro(cid:173)
`cessing is now totally obsolete. The old model of a single computer serving all of
`the organization· s computational needs has been replaced by one in which a large
`number of separate but interconnected computers do the job. These systems are
`called computer networks. The design and organization of these networks are
`the subjects of this book.
`Throughout the book we will use the term "computer network" to mean an
`interconnected collection of autonomous computers. Two computers are said to
`be interconnected if they are able to exchange information. The connection need
`not he via a copper wire; fiber optics, 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 master/slave rela(cid:173)
`tion. If one computer can forcibly start, stop, or control another one, the comput(cid:173)
`ers are not autonomous. A system with one control unit and many slaves is not a
`network; nor is a large computer with remote printers and terminals.
`There is considerable confusion in the literature between a computer network
`and a distributed system. The key distinction is that in a distributed system, the
`existence of multiple autonomous computers is transparent (i.e., not visible) to the
`user. He t can type a command to run a program, and it runs. It is up to the
`operating 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
`multiple processors; it looks like a virtual uniprocessor. Allocation of jobs to pro(cid:173)
`cessors and files to disks, movement of files between where they are stored and
`where they are needed, and all other system functions must be automatic.
`With a network, users must explicitly log onto one machine, explicitly submit
`jobs remotely. explicitly move files around and generally handle all the network
`management personally. With a distributed system, nothing has to be done expli(cid:173)
`citly; it is all automatically done by the system without the users' knowledge.
`In effect, a distributed system is a software system built on top of a network.
`The software gives it a high degree of cohesiveness and transparency. Thus the
`distinction between a network and a distributed system lies with the software
`(especially the operating system), rather than with the hardware.
`Nevertheless, there is considerable 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.
`·;· ""He·· 'hould be read as "he or she'" throughout this book.
`
`Page 18 of 92
`
`

`
`SEC. 1.1
`
`USES OF COMPUTER NETWORKS
`
`3
`
`Although this book primarily focuses on networks, many of the topics are also
`important in distributed systems. For more information about distrihuted systems,
`see (Coulouris et al., 1994; Mullender. 1993; and Tanenbaum, 1995 ).
`
`1.1. USES OF COMPUTER NETWORKS
`
`Before we start to examine the technical issues in detail, it is worth devoting
`some time to pointing out why people are interested in computer networks and
`what they can be used for.
`
`1.1.1. Networks for Companies
`
`Many organizations have a substantial number of computers in operation,
`often located far apart. 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 isola(cid:173)
`tion 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 form, the issue here is resource sharing, and the
`goal is to make all programs, equipment, and especially data available to anyone
`on the network 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.
`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 CPU s means that if one goes down, the
`others may be able to take over its work, although at reduced performance. For
`military, banking, air traffic control, nuclear reactor safety, and many other appli(cid:173)
`cations, the ability to continue operating in the face of hardware problems is of
`utmost importance.
`Another goal
`is saving money. Small computers have a much better
`price/performance ratio than large ones. Mainframes (room-size computers) are
`roughly a factor of ten faster than personal computers, but they cost a thousand
`times more. This imbalance has caused many systems designers to build systems
`consisting of personal computers, one per user, with data kept on one or more
`shared file server machines. In this model, the users are called clients, and the
`whole arrangement is called the client-server model. It is illustrated in Fig. 1-1.
`In the client-server model, communication generally takes the form of a
`request message from the client to the server asking for some work to be done.
`
`Page 19 of 92
`
`

`
`4
`
`INTRODUCTION
`
`CHAP. I
`
`Client machine
`
`Server machine
`
`Client
`process
`
`0
`
`Server
`process
`
`Network
`
`Request
`
`Reply
`
`Fig. 1-1. The client-server model.
`
`The server then does the work and sends back the reply. Usually. there are many
`clients using a small number of servers.
`Another networking goal is scalability, the ability to increase system perfor(cid:173)
`mance gradually as the workload grows just by adding more processors. With
`centralized mainframes, when the system is full, it must be replaced by a larger
`one. usually at great expense and even greater disruption to the users. With the
`client-server model, new clients and new servers can be added as needed.
`Yet another goal of setting up a computer network has little to do with tech(cid:173)
`nology at all. A computer network can provide a powerful communication
`medium among widely separated employees. Using a network. it is easy for two
`or more people who live far apart to write a report together. When one worker
`makes a change to an on-line document, the others can see the change immedi(cid:173)
`ately. instead of waiting several days for a letter. Such a speedup makes coopera(cid:173)
`tion among far-flung groups of people easy where it previously had been impossi(cid:173)
`ble. In the long run, the use of networks to enhance human-to-human communi(cid:173)
`cation will probably prove more important than technical goals such as improved
`reliability.
`
`1.1.2. Networks for People
`
`The motivations given above for building computer networks are all essen(cid:173)
`tially economic and technological in nature. If sufficiently large and powerful
`mainframes were available at acceptable prices, most companies would simply
`choose to keep all their data on them and give employees terminals connected to
`them. In the 1970s and early 1980s, most companies operated this way. Com(cid:173)
`puter networks only became popular when networks of personal computers
`offered a huge price/performance advantage over mainframes.
`Starting in the 1990s, computer networks began to start delivering services to
`private individuals at home. These services and the motivations for using them
`
`Page 20 of 92
`
`

`
`SEC. 1.1
`
`USES OF COMPUTER NETWORKS
`
`5
`
`are quite different than the "corporate efficiency'' model described in the previ(cid:173)
`ous section. Below we will sketch three of the more exciting ones that are starting
`to happen:
`
`I. Access to remote information.
`
`2. Person-to-person communication.
`
`3.
`
`Interactive entertainment.
`
`Access to remote information will come in many forms. One area in which it
`is already happening is access to financial institutions. Many people pay their
`bills, manage their hank accounts, and handle their investments electronically.
`Home shopping is also becoming popular, with the ability to inspect the on-line
`catalogs of thousands of companies, Some of these catalogs will soon provide the
`ability to get an instant video on any product by just clicking on the product's
`murre.
`Newspapers will go on-line and be personalized. It will be possible to tell the
`newspaper that you want everything about corrupt politicians, big fires, scandals
`involving celebrities. and epidemics, but no footbalL thank you. At night while
`you sleep, the newspaper will be downloaded to your computer's disk or printed
`on your laser printer. On a small scale, this service already exists. The next step
`beyond newspapers (plus magazines and scientific journals) is the on-line digital
`library. Depending on the cost size, and weight of book-sized notebook comput(cid:173)
`ers. printed books may become obsolete. Skeptics should take note of the effect
`the printing press had on the medieval illuminated manuscript.
`Another application that falls in this category is access to information systems
`like the current World Wide Web, which contains information about the arts, busi(cid:173)
`ness, cooking, government, health, history, hobbies, recreation, science, sports,
`travel, and too many other topics to even mention.
`All of the above applications involve interactions between a person and a
`remote database. The second broad category of network use will be person-to(cid:173)
`person interactions, basically the 21st Century· s answer to the 19th Century· s tele(cid:173)
`phone. Electronic mail or email is already widely used by millions of people and
`will soon routinely contain audio and video as well as text. Smell in messages
`will take a hit longer to perfect.
`Real-time email will allow remote users to communicate with no delay. possi(cid:173)
`bly seeing and hearing each other as well. This technology makes it possible to
`