SECOND EDITION
`
`COMPUTER
`NETWORKS
`
`------------------------(cid:173)
`
`~·.
`
`ANDREW S. TANENBAUM
`
`Ex.1067.001
`
`DELL
`
`

`

`

`

`COMPUTER NETWORKS
`
`SECOND EDITION
`
`ANDREW S. TANENBAUM
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`PRENTICE HALL
`
`ENGLEWOOD CLIFFS, NEW JERSEY 07632
`
`Ex.1067.003
`
`DELL
`
`

`

`Library of Congress Cataloging-in-Publication Data
`Tanenbaum, Andrew S.
`Computer networks I Andrew S. Tanenbaum.-2nd ed.
`p.
`cm.
`Bibliography: p.
`Includes index.
`ISBN 0-13-162959-X
`1. Computer networks.
`TK5!05.5.T36 1988
`004.6-dcl9
`
`I. Title.
`
`·
`
`88-16937
`CIP
`
`Editorial/production supervision: Lisa Schulz Garboski
`Manufacturing buyer: Mary Ann Gloriande
`
`Prentice Hall Software Series
`Brian W. Kernighan, Advisor
`
`The publisher offers discounts on this book when ordered in bulk
`quantities. For more information, write:
`
`Special Sales/College Marketing
`Prentice Hall
`College Technical and Reference Division
`Englewood Cliffs, NJ 07632
`
`© 1989 by Prentice-Hall, Inc.
`A Division of Simon & Schuster
`Englewood Cliffs, New Jersey 07632
`
`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.
`
`Printed in the United States of America
`
`10 9
`
`ISBN
`
`0-13-162959-X
`
`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.1067.004
`
`DELL
`
`

`

`To Suzanne, Barbara, Marvin, Muis, and the memory of Sweetie 7t
`
`Ex.1067.005
`
`DELL
`
`

`

`CONTENTS
`
`1
`
`INTRODUCTION
`
`1
`
`1.1 THE USES OF COMPUTER NETWORKS 3
`1.1.1 Network Goals 3
`1.1.2 Applications of Networks 4
`
`1.2 NETWORK STRUCTURE 6
`
`1.3 NETWORK ARCHITECTURES 9
`1.3.1 Protocol Hierarchies 9
`1.3.2 Design Issues for the Layers 13
`
`1.4 THE OSI 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 The Transp01t Layer 17
`l.4.5 The Session Layer 18
`l.4.6 The Presentation Layer 18
`1.4. 7 The Application Layer 19
`1.4.8 Data Transmission in the OSI Model 19
`
`1.5 SERVICES 21
`1.5.1 OSI Terminology 21
`1.5.2 Connection-Oriented and Connectionless Services 22
`1.5.3 Service Primitives 24
`1.5.4 The Relationship of Services to Protocols 26
`
`1.6 NETWORK STANDARDIZATION 27
`1.6.l Who's Who in the Telecommunication World 28
`1.6.2 Who's Who in the Standards World 29
`1.6.3 Discussion of the Standardization of the OSI model 30
`
`1.7 EXAMPLE NETWORKS 32
`1.7.1 Public Networks 32
`1.7.2 The ARPANET 35
`1.7.3 MAP and TOP 36
`1. 7.4 USENET 40
`1.7.5 CSNET 41
`1.7.6 BITNET 42
`1.7.7 SNA 43
`
`1.8 OUTLINE OF THE REST OF THE BOOK 47
`
`1.9 SUMMARY 48
`
`v
`
`Ex.1067.006
`
`DELL
`
`

`

`vi
`2
`
`CONTENf S
`
`THE PHYSICAL LA YER
`
`52
`
`2.1 THE THEORETICAL BASIS FOR DATA COMMUNICATION 52
`2.1.1 Fourier Analysis 52
`2.1.2 Bandwidth-Limited Signals 53
`2.1.3 The Maximum Data Rate of a Channel 56
`
`2.2 TRANSMISSION MEDIA 57
`2.2.1 Magnetic Media 57
`2.2.2 Twisted Pair 57
`2.2.3 Baseband Coaxial Cable 58
`2.2.4 Broadband Coaxial Cable 59
`2.2.5 Fiber Optics 62
`2.2.6 Line-of-Sight Transmission 65
`2.2.7 Communication Satellites 66
`
`2.3 ANALOG TRANSMISSION 70
`2.3. l The Telephone System 70
`2.3.2 Modems 72
`2.3.3 RS-232-C and RS-449 76
`
`2.4 DIGIT AL TRANSMISSION 77
`2.4.1 Pulse Code Modulation 79
`2.4.2 Encoding Systems 81
`2.4.3 The X.21 Digital Interface 82
`
`2.5 TRANSMISSION AND SWITCHING 84
`2.5.1 Frequency Division and Time Division Multiplexing 84
`2.5.2 Circuit Switching 86
`2.5.3 Packet Switching 88
`2.5.4 Hybrid Switching 89
`
`2.6
`
`ISDN-INTEGRATED SERVICES DIGITAL NETWORK 90
`2.6.1
`ISDN Services 91
`2.6.2 Evolution of ISDN 93
`2.6.3 ISDN System Architecture 95
`2.6.4 The Digital PBX g9
`2.6.5 The ISDN Interface 102
`2.6.6 ISDN Signaling-SS #7 106
`2.6.7 Perspective on ISDN 107
`
`2.7 TERMINAL HANDLING 109
`2.7.1 Polling 110
`2. 7 .2 Multiplexing versus Concentration 111
`
`2.8 SUMMARY 113
`
`Ex.1067.007
`
`DELL
`
`

`

`3
`
`THE MEDIUM ACCESS SUBLAYER
`
`CONTENTS
`
`vii
`
`116
`
`3.1 LOCAL AND METROPOLITAN AREA NETWORKS 116
`3.1.1 Static Channel Allocation in LANs and MANs 118
`3.1.2 Dynamic Channel Allocation in LANs and MANs 119
`
`3.2 THE ALOHA PROTOCOLS 121
`3.2.1 Pure ALOHA and Slotted ALOHA 121
`3.2.2 Finite Population ALOHA 124
`
`3.3 LOCAL AREA NETWORK PROTOCOLS 127
`3.3.1 Persistent and Nonpersistent CSMA 127
`3.3.2 CSMA with Collision Detection 128
`3.3.3 Collision-Free Protocols 130
`3.3.4 BRAP-Broadcast Recognition with Alternating Priorities 131
`3.3.5 MLMA-The Multi-Level Multi-Access Protocol 132
`3.3.6 Binary Countdown 134
`3.3.7 Limited-Contention Protocols 135
`3.3.8 The Adaptive Tree Walk Protocol 136
`3.3.9 The Um Protocol 138
`IEEE STANDARD 802 FOR LOCAL AREA NETWORKS 141
`3.4.1 IEEE Standard 802.2 and Ethernet 141
`3.4.2 IEEE Standard 802.4: Token Bus 148
`3.4.3 IEEE Standard 802.5: Token Ring 153
`3.4.4 Comparison of Local Area Networks 163
`
`3.4
`
`3.5 FIBER OPTIC NETWORKS 165
`3.5.1 FDDI 166
`3.5.2 Fibemet II 168
`3.5.3 S/NET 170
`3.5.4 FASNET AND EXPRESSNET 171
`3.5.5 DATAKIT 173
`
`3.6 SATELLITE NETWORKS 175
`3.6.1 SPADE 176
`3.6.2 ALOHA Revisited 177
`3.6.3 Reservation ALOHA 179
`
`3.7 PACKET RADIO NETWORKS 182
`3.7.1 The University of Hawaii ALOHA System 182
`3.7.2 Design Issues for Packet Radio Networks 183
`
`3.8 EXAMPLES OF THE MAC SUBLAYER 188
`3.8.1 The MAC Sublayer in Public Networks 189
`3.8.2 The MAC Sublayer in the ARPANET 189
`3.8.3 The MAC Sublayer in MAP and TOP 189
`3.8.4 The MAC Sublayer in USENET 190
`
`3.9 SUMMARY 190
`
`Ex.1067.008
`
`DELL
`
`

`

`viii
`4
`
`CONTENTS
`
`THE DATA LINK LAYER
`
`196
`
`4.1 DATA LINK LAYER DESIGN ISSUES 197
`4.1.1 Services Provided to the Network Layer 197
`4.1.2 Framing 199
`4.1.3 Error Control 202
`4.1.4 Flow Control 203
`4.1.5 Link management 204
`
`4.2 ERROR DETECTION AND CORRECTION 204
`4.2.1 Error-Correcting Codes 206
`4.2.2 Error-Detecting Codes 208
`
`4.3 ELEMENTARY DATA LINK PROTOCOLS 212
`4.3.1 An Unrestricted Simplex Protocol 216
`4.3.2 A Simplex Stop-and-Wait Protocol 217
`4.3.3 A Simplex Protocol for a Noisy Channel 219
`
`4.4 SLIDING WINDOW PROTOCOLS 223
`4.4.1 A One Bit Sliding Window Protocol 225
`4.4.2 A Protocol Using Go Back n 228
`4.4.3 A Protocol Using Selective Repeat 234
`
`4.5 PROTOCOL PERFORMANCE 239
`4.5.1 Performance of the Stop-and-Wait Protocol 239
`4.5.2 Performance of the Sliding Window Protocol 242
`
`4.6 PROTOCOL SPECIFICATION AND VERIFICATION 244
`4.6.1 Finite State Machine Models 245
`4.6.2 The Estelle Protocol Specification Language 251
`4.6.3 Petri Net Models 252
`
`4.7 EXAMPLES OF THE DATA LINK LA YER 253
`4.7.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
`
`4.7 SUMMARY 267
`
`5
`
`THE NETWORK LA YER
`
`271
`
`5.1 NETWORK LA YER DESIGN ISSUES 271
`5.1.1 Services Provided to the Transport Layer 271
`5.1.2 Internal Organization of the Network Layer 280
`5.1.3 Routing 284
`5.1.4 Congestion 287
`5.1.5 Internetworking 288
`
`Ex.1067.009
`
`DELL
`
`

`

`CONTENTS
`
`ix
`
`5.2 ROUTING ALGORITHMS 289
`5.2.1 Shortest Path Routing 289
`5.2.2 Multipath Routing 291
`5.2.3 Centralized Routing 294
`5.2.4 Isolated Routing 296
`5.2.5 Flooding 298
`5.2.6 Distributed Routing 299
`5.2. 7 Optimal Routing 300
`5.2.8 Flow-Bf!Sed Routing 303
`5.2.9 Hierarchical Routing 305
`5.2.10 Broadcast Routing 306
`
`5.3 CONGESTION CONTROL ALGORITHMS
`5.3.1 Preallocation of Buffers 309
`5.3.2 Packet Discarding 310
`5.3.3 Isarithmic Congestion Control
`5.3.4 Flow Control 313
`5.3.5 Choke Packets 314
`5.3.6 Deadlocks 315
`
`312
`
`309
`
`5.4
`
`INTERNETWORKING 320
`5.4.1 OSI and Intemetworking 321
`5.4.2 Bridges 325
`5.4.3 Gateways 337
`5.4.4 Comparison of Connection-Oriented and Connectionless Gateways 345
`5.4.5 Bridge and Gateway Software 346
`
`5.5 EXAMPLES OF THE NETWORK LA YER 350
`5.5.1 The Network Layer in Public Networks 350
`5.5.2 The Network Layer in the ARPANET (IP) 358
`5.5.3 The Network Layer in MAP and TOP 362
`5.5.4 The Network Layer in USENET 363
`
`5.6 SUMMARY 365
`
`6
`
`THE TRANSPORT LAYER
`
`370
`
`6.1 TRANSPORT LA YER DESIGN ISSUES 371
`6.1.1 Services Provided to the Session Layer 371
`6.1.2 Quality of Service 373
`6.1.3 The OSI Transport Service Primitives 375
`6.1.4 Transport Protocols 381
`6.1.5 Elements of Transport Protocols 384
`
`Ex.1067.010
`
`DELL
`
`

`

`x
`
`CONTENTS
`
`6.2 CONNECTION MANAGEMENT 387
`6.2.1 Addressing 388
`6.2.2 Establishing a Connection 391
`6.2.3 Releasing a Connection 397
`6.2.4 Timer-Based Connection Management 401
`6.2.5 Flow Control and Buffering 403
`6.2.6 Multiplexing 407
`6.2. 7 Crash Recovery 409
`
`6.3 A SIMPLE TRANSPORT PROTOCOL ON TOP OF X.25 411
`6.3.1 The Example Service Primitives 411
`6.3.2 The Example Transport Entity 413
`6.3.3 The Example as a Finite State Machine 420
`
`6.4 EXAMPLES OF THE TRANSPORT LA YER 422
`6.4.1 The Transport Layer in Public Networks 422
`6.4.2 The Transport Layer in the ARP ANET (TCP) 429
`6.4.3 The Transport Layer in MAP and TOP 435
`6.4.4 The Transport Layer in USENET 436
`
`6.5 SUMMARY 436
`
`7
`
`THE SESSION LAYER
`
`440
`
`7.1 SESSION LA YER 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.7 The OSI Session Service Primitives 451
`
`7 .2 REMOTE PROCEDURE CALL 454
`7.2.1 The Client-Server Model 455
`7 .2.2 Implemehtation 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 OF THE SESSION LA YER 465
`7.3.1 The Session Layer in Public Networks 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 The Session Layer in USENET 469
`
`7.4 SUMMARY 469
`
`Ex.1067.011
`
`DELL
`
`

`

`8
`
`THE PRESENTATION LA YER
`
`CONTENTS
`
`xi
`
`471
`
`8.1 PRESENTATION LAYER DESIGN ISSUES 472
`8.1.1 Data Representation 472
`8.1.2 Data Compression 473
`8.1.3 Network Security and Privacy 473
`8.1.4 The OSI Presentation Service Primitives 475
`
`8.2 ABSTRACT SYNTAX NOTATION 1 (ASN.1) 475
`8.2.1 Data Structures 476
`8.2.2 Abstract Syntax 481
`8.2.3 Transfer Syntax 487
`
`8.3 DATA COMPRESSION TECHNIQUES 490
`8.3.1 Encoding a Finite Set of Equally Likely Symbols 491
`8.3.2 Frequency Dependent Coding 491
`8.3.3 Context Dependent Encoding 494
`
`8.4 CRYPTOGRAPHY 496
`8.4.1 Traditional Cryptography 496
`8.4.2 The Data Encryption Standard 503
`8.4.3 The Key Distribution Problem 510
`8.4.4 Public Key Cryptography 513
`8.4.5 Authentication and Digital Signatures 516
`
`8.5 EXAMPLES OF THE PRESENT A TI ON LA YER 520
`8.5.1 The Presentation Layer in Public Networks 521
`8.5.2 The Presentation Layer in the ARPANET 523
`8.5.3 The Presentation Layer in MAP and TOP 524
`8.5.4 The Presentation Layer in USENET 524
`
`8.6 SUMMARY 524
`
`9
`
`THE APPLICATION LAYER
`
`528
`
`9.1 APPLICATION LAYER DESIGN ISSUES 528
`9.1.1 File Transfer, Access, and Management 529
`9.1.2 Electronic Mail 530
`9.1.3 Virtual Terminals 531
`9.1.4 Other Applications 531
`9.1.5 OSI Service Elements-ACSE and CCR 532
`
`9.2 FILE TRANSFER, ACCESS, AND MANAGEMENT 535
`9.2.1 File Servers 535
`9.2.2 Concurrency Control 539
`
`Ex.1067.012
`
`DELL
`
`

`

`xii
`
`CONTENTS
`
`9.2.3 Replicated Files 540
`9.2.4 Implementation Issues 542
`
`9.3 ELECTRONIC MAIL 546
`9.3.1 Architecture and Services of MOTIS and X.400 547
`9.3.2 The User Agent 551
`9.3.3 The Message Transfer Agent 555
`
`9.4 VIRTUAL TERMINALS 558
`9.4.1 Scroll Mode Terminals 559
`9.4.2 Page Mode Terminals 561
`9.4.3 Form Mode Terminals 562
`
`9.5 OTHER APPLICATIONS 569
`9.5.1 Directory Service 569
`9.5.2 Job Transfer and Management 571
`9.5.3 Picture Storage and Transfer 573
`9.5.4 Teletext and Videotex 574
`
`9.6 EXAMPLES OF THE 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 READING LIST AND BIBLIOGRAPHY
`
`608
`
`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 611
`10.1.4 The Data Link Layer 611
`10.1.5 The Network Layer 612
`10.1.6 The Transport 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
`
`631
`
`642
`
`Ex.1067.013
`
`DELL
`
`

`

`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(cid:173)
`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(cid:173)
`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 art. Every computer manufacturer had its own network architecture, no two
`of which were compatible. All that has changed now. Virtually the entire com(cid:173)
`puter industry has now agreed to a series of International 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(cid:173)
`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
`
`Ex.1067.014
`
`DELL
`
`

`

`xiv
`
`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, LAN s, fiber optics,
`and bridges. The treatment of the upper OSI layers has been completely rewritten
`and expanded by over a hundred pages to include important topics such as the OSI
`transport protocols, ASN.1, FfAM, and VTP. New networks, including MAP,
`TOP, 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 OSI 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(cid:173)
`sport, which collectively are the providers of the transport service. Chapter 2 cov(cid:173)
`ers physical media, analog and digital transmission, the telephone system and
`ISDN. Chapter 3 looks at the MAC sublayer and local area networks, including
`IEEE standard 802. Chapter 4 is about the data link layer and its protocols: also(cid:173)
`rithms for reliably transmitting data over umeliable lines. Chapter 5 treats the net(cid:173)
`work layer, especially routing, congestion control, and internetworking. 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(cid:173)
`vice. Chapter 7 is about the session layer, which is concerned with providing reli(cid:173)
`able service, even in the face of umeliable hardware. Chapter 8 covers the presen(cid:173)
`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, virtual 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 the benefit of readers not familiar
`with this subject.
`The book can be used as a text for undergraduates or beginning graduate stu(cid:173)
`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 examples 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(cid:173)
`ing on the level of the students, I have made a serious attempt to· make each chapter
`relatively independent of the other ones. In this way an instructor 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
`
`Ex.1067.015
`
`DELL
`
`

`

`PREFACE
`
`xv
`
`networking. For this reason, I have attempted to limit the amount of mathematics
`used, and have included numerous practical examples instead of providing niany
`pages of abstract derivations. Even programmers or technical managers who are
`not network specialists should be able to follow a considerable amount of the book.
`Many people have helped me during the preparation of the second edition. I
`would especially like to thank Imrich Chlamtac Bdale Garbee, John Henshall,
`Brian Kernighan, John Limb, Chris Makemson, Daniel Pitt, Sandy Shaw, Jennifer
`Steiner and my editor, John Wait. I would also like to thank my students for help(cid:173)
`ing to debug the text. Special thanks go to Jeroen Belien, Berend Jan Beugel,
`Remco Feenstra, Anneth de Gee, Comelis Kroon, Roemer Lievaart, Maarten Lit(cid:173)
`maath, Paul Polderman, Rob van Swinderen, Luuk 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.
`
`ANDREWS. TANENBAUM
`
`Ex.1067.016
`
`DELL
`
`

`

`1
`
`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(cid:173)
`ing the Industrial Revolution. The nineteenth century was the age of the steam
`engine. During the twentieth 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 televi(cid:173)
`sion, the birth and unprecedented growth of the computer industry, and the launch(cid:173)
`ing of communication satellites.
`As we move toward the final years of this century, these areas are rapidly con(cid:173)
`verging, and the differences between collecting, transporting, storing, and process(cid:173)
`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 information 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 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.1067.017
`
`DELL
`
`

`

`2
`
`INTRODUCTION
`
`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 processing is
`rapidly becoming obsolete. This model has not one, but at least two flaws: the con(cid:173)
`cept of a single large computer doing all the work, and the idea of users bringing
`work to the computer instead of bringing the computer to the users.
`The old model of a single computer serving all of the organization's computa(cid:173)
`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(cid:173)
`works. The design and analysis 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
`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 master/slave 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 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. Het can type a command to run a program, and it runs. It is up to the operat(cid:173)
`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(cid:173)
`ple processors; it looks like a virtual uniprocessor. Allocation of jobs to processors
`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, a user 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 user's knowledge.
`In effect, a distributed system is a special case of a network, one whose ,
`software gives it a high degree of cohesiveness and transparency. Thus the distinc(cid:173)
`tion between a network and a distributed system lies with the software (especially
`the operating system), rather than with the hardware.
`
`t "He" should be read as "he or she" throughout this book.
`
`Ex.1067.018
`
`DELL
`
`

`

`SEC. 1.1
`
`USES OF COMPUTER 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(cid:173)
`buted systems. For more information about distributed systems, see Crichlow
`(1988), Sloman and Kramer (1987), and Tanenbaum and van Renesse (1985).
`
`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. Network Goals
`
`Many organizations already have a substantial number of computers in opera(cid:173)
`tion, 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 iso(cid:173)
`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 form, the issue here is resource sharing, and the
`goal is to make all programs, data, and equipment available to anyone on the net(cid:173)
`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 traffic control, and many other applications, the ability to con(cid:173)
`tinue operating in the face of hardware problems is of great importance.
`Another goal is saving money. Small computers have a much better
`price/performance 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(cid:173)
`ing 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.
`
`Ex.1067.019
`
`DELL
`
`

`

`4
`
`INTRODUCTION
`
`CHAP. 1
`
`Such a network is called a LAN (local area network) to contrast it with the far(cid:173)
`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(cid:173)
`ogy at all. A computer network can provide a powerful communication medium
`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 far-flung 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. 1-1 we give a classification of multiple processor systems arranged by
`physical size. At the top are data flow machines, highly parallel computers with
`many functional units all working on the same program. Next come the multi(cid:173)
`processors, systems that communicate via shared memory. Beyond the multipro(cid:173)
`cessors are the true networks, computers that communicate by exchanging mes(cid:173)
`sages. Finally, the connection of two or more networks is called internetworking.
`
`Interprocessor Processors located
`distance
`in same
`
`Example
`
`0.1 m
`
`1m
`
`10 m
`
`100 m
`
`1 km
`
`10 km
`
`Circuit board
`
`System
`
`Room
`
`Building
`
`Campus
`
`City
`
`100 km
`
`Country
`
`1000 km
`
`Continent
`
`10,000 km
`
`Planet
`
`} Data flow machine
`
`} Multiprocessor
`
`l Local netwock
`
`} Long haul netwock
`
`}
`
`lntecconnection of long haul netwock•
`
`Fig. 1-1. Classification of interconnected processors by scale.
`
`1.1.2. Applications of Networks
`
`Replacing a single mainframe by workstations on a LAN does not make many
`new applications possible, although it may improve the reliability and performance.
`In contrast, the availability of a (public) WAN makes many new applications
`
`Ex.1067.020
`
`DELL
`
`

`

`SEC. 1.2
`
`USES OF COMPUTER NETWORKS
`
`5
`
`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(cid:173)
`cially if the model is constantly being adjusted or requires an extremely large main(cid:173)
`frame computer to run.
`Another major area of network use is access to remote databases. It may soon
`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(cid:173)
`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(cid:173)
`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(cid:173)
`tain digitized voice, still pictures and possibly even 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 meisje.
`Electronic bulletin board systems already exist, but these tend to be used by
`computer experts, are oriented towards technical topics, and are often limited in
`geographic scope. Future systems will be national or international, be used by mil(cid:173)
`lions of nontechnical people, and cover a much broader range of subjects. Using a
`bulletin board may be as common as reading a magazine.
`It is sometimes said that there is a