`
`INFORMATION
`SUPER
`HIGHWAY
`
`DELL Ex.1006.001
`Ex.1006.001
`
`DELL
`
`

`

`Computer Networks
`Third Edition
`
`Ex.1006.002
`
`DELL
`
`

`

`Other bestselling titles by Andrew S. Tanenbaum:
`
`Operating Systems: Design and Implementation, 2nd edition
`This now-classic text on operating systems is the only book covering both the principles of
`operating systems and their appli;,alion to a real system. All the traditional operating
`systems topics are covered in detail. ln addition, the principles are carefully illustrated by
`MINIX, a free UNIX-like operating system for personal computers. The second edition,
`which is expected in late 1996. will deal with the new POSlX-based MINIX 2.0 system. As
`with the first edition, the book will include a listing of the MINIX source code. New to the
`second edition is a free CD-ROM in each book containing the complete MINIX system
`(binary and source code).
`
`Modern Operating Systems
`This bestselling text presents the basics of both single processor and distributed computer
`systems. Tanenbaum covers traditional topics including processes, memory management,
`and files systems as well as key issues in distributed systems including the client-server
`model, remote procedure call, threads and distributed files servers. This practical guide uses
`UNIX, MS-DOS, Mach and Amoeba to illustrate operating system concepts.
`
`Distributed Operating Systems
`This text covers the fundamental concepts of distributed operating systems. Key topics
`include communication and synchronization, processes and processors, distributed shared
`memory, distributed tile systems, and distributed real-time systems. The principles of
`distributed computing are illustrated in four detailed case studies using Mach, Amoeba,
`Chorus and DCE operating environments.
`
`Structured Computer Organization, 3rd edition
`This leading text looks at computer architecture as a series of levels. At the bottom is the
`hardware:
`transistors, gates, registers, adders, and other circuits. Then comes the
`microprogramming level. After that is the conventional machine level, with its ADD,
`MOVE, JUMP, and other instructions. On top of that is the operating system, which adds
`new facilities such as tile management and virtual memory. The final chapter deals with two
`advanced topics: parallel computers and the design of RISC machines.
`
`Ex.1006.003
`
`DELL
`
`

`

`

`

`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, Andrew S. 1944-.
`Computer networks I Andrew S. Tanenbaum. -- 3rd ed.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0-13-349945-6
`I.Computer networks.
`TK5105.5.T36 1996
`004.6--dc20
`
`I. Title.
`
`96-4121
`CIP
`
`Editorial/production manager: Camille Trentacoste
`Interior design and composition: Andrew S. Tanenbaum
`Cover design director: Jerry Votta
`Cover designer: Don Martinetti, DM Grnphics, 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 hook when ordered in hnlk quantities. For more information,
`contact:
`Corporate Sales Department, Prentice Hall PTR, One Lake Street, Upper Saddle River, NJ 07458.
`Phone: (800) 382-3419; Fax: (20 I) 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 3 2
`
`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
`
`Ex.1006.005
`
`DELL
`
`

`

`To Suzanne, Barbara, Marvin, and Little Bram
`
`Ex.1006.006
`
`DELL
`
`

`

`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 Intemetworks 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. l 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
`
`Ex.1006.007
`
`DELL
`
`

`

`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 ATM 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 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
`
`2.3
`
`2.4
`
`WIRELESS TRANSMISSION 94
`2.3.1 The Electromagnetic Spectrum
`2.3.2 Radio Transmission 97
`2.3.3 Microwave Transmission 98
`2.3.4 Infrared and Millimeter Waves
`2.3.5 Lightwave Transmission 100
`
`94
`
`100
`
`THE TELEPHONE SYSTEM 102
`2.4.1 Structure of the Telephone System
`2.4.2 The Politics of Telephones 106
`2.4.3 The Local Loop 108
`2.4.4 Trunks and Multiplexing 118
`2.4.5 Switching 130
`
`103
`
`Ex.1006.008
`
`DELL
`
`

`

`viii
`
`CONTENTS
`
`l 39
`2.5 NARROWBAND ISDN
`2.5.1
`ISDN Services 140
`2.5.2 ISDN System Architecture 140
`2.5.3 The ISDN Interface 142
`2.5.4 Perspective on N-ISDN 143
`
`l44
`2.6 BROADBAND ISDN AND ATM
`2.6.J Virtual Circuits versus Circuit Switching 145
`2.6.2 Transmission in ATM Networks 146
`2.6.3 ATM Switches
`l47
`
`2.7 CELLULAR RADIO 155
`2.7.l Paging Systems 155
`2.7.2 Cordless Telephones 157
`2.7.3 Analog Cellular Telephones 157
`2.7.4 Digital Cellular Telephones 162
`2.7.5 Personal Communications Services 162
`
`2.8 COMMUNICATION SATELLITES 163
`2.8. l 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
`
`Ex.1006.009
`
`DELL
`
`

`

`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.l Finite State Machine Models 219
`3.5.2 Petri Net Models 223
`
`3.6 EXAMPLE DATA LINK PROTOCOLS 225
`3.6.1 HDLC-High-level 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 SUBLAYER
`
`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
`
`Ex.1006.010
`
`DELL
`
`

`

`x
`
`CONTENTS
`
`4.4 BRIDGES 304
`4.4.l 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 3 [ 7
`
`4.5 HIGH-SPEED LANS 318
`4.5.l 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 TOM 330
`4.6.5 CDMA 333
`
`4.7 SUMMARY 333
`
`5 THE NETWORK LA YER
`
`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
`
`Ex.1006.011
`
`DELL
`
`

`

`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 Coltltrol 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 Firewalls 410
`
`5.5 THE NETWORK LA YER 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 LA YER IN A TM 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
`
`Ex.1006.012
`
`DELL
`
`

`

`xii
`CONTENTS
`6 THE TRANSPORT LA YER
`
`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 LA YER PROTOCOLS 545
`6.5. l Structure of the ATM Adaptation Layer 546
`6.5.2 AAL I 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. J Performance Problems in Computer Networks 556
`6.6.2 Measuring Network Performance 559
`
`Ex.1006.013
`
`DELL
`
`

`

`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
`
`Ex.1006.014
`
`DELL
`
`

`

`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
`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
`8.1.5 The Network Layer 771
`8.1.6 The Transport Layer 772
`8.1.7 The Application Layer 772
`
`767
`
`770
`
`8.2 ALPHABETICAL BIBLIOGRAPHY 775
`
`INDEX 795
`
`Ex.1006.015
`
`DELL
`
`

`

`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. 1 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
`
`Ex.1006.016
`
`DELL
`
`

`

`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, ATM, 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, IAB, ICMP, IDEA, IETF,
`1Pv6, !SO, 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, WARC, WDM, WWV, and
`WWW. But don't worry. Each one will be carefully defined before it is used.
`
`Ex.1006.017
`
`DELL
`
`

`

`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 Wide Web.
`To get them, please see the author's home page: http://www.cs.vu.nl/-astl.
`The book was typeset in Times Roman using Troff, 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 fillm 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. I 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 ways, small, medium, large, and jumbo. My production editor,
`Camille Trentacoste, taught me about people of snow, 8-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
`
`Ex.1006.018
`
`DELL
`
`

`

`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 technologicall 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
`
`1
`
`Ex.1006.019
`
`DELL
`
`

`

`2
`
`INTRODUCTJON
`
`CHAP. 1
`
`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 autonmnous computers. Two computers are said to
`be interconnected if they are able to exchange information. The connection need
`not be 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
`It is up to the
`user. He i" can type a command to run a program, and it runs.
`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 cohesiveuess 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.
`i" "He" should be read as "he or she" throughout this book.
`
`Ex.1006.020
`
`DELL
`
`

`

`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 distributed systems,
`see (Coulouris et al., 1994; Mulllender, 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 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 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.
`
`Ex.1006.021
`
`DELL
`
`

`

`

`

`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:
`
`1. 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 bank 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
`name.
`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 bit 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
`have virtual meeti