THIRD EDITION
`
`._-u
`I
`
`OMPUTER NETWRKS
`
`.-.
`
`ANDREW S. TANENBAUM
`
`.::..i‘*
`
`‘''—s_.
`
`$2?‘
`
`____
`
`_
`
`3;“ ‘JV
`
`‘,r "—,__
`
`Broadcasting
`
`'
`
`SHALL I COMPARE THEE
`TO A SUMMERS DAY’?
`
`_I.
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 1
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 1
`
`

`
`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, AndrewS. 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
`
`Editorial/production manager: Camille Trentacoste
`Interior design and composition: Andrew S. Tanenbaum
`Cover design director: Jerry Votta
`Cover designer: Don Martinetti, DM Graphics, Inc.
`Cover concept: AndrewS. 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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 2
`
`

`
`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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 3
`
`

`
`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 WIRELESS TRANSMISSION 94
`2.3.1 The Ele~tromagnetic 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
`
`2.4 THE TELEPHONE SYSTEM 102
`2.4.1 Structure of the Telephone System 103
`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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 4
`
`

`
`viii
`
`CONTENTS
`
`2.5 NARROWBAND ISDN 139
`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
`
`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 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.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 176
`3 .1.2 Framing 179
`· 3.1.3 Error Control 182
`3.1.4 Flow Control 183
`
`3.2 ERROR DETECTION AND CORRECTION 183
`3.2.1 Error-Correcting Codes 184
`3 .2.2 Error-Detecting Codes 186
`
`3.3 ELEMENTARY DATA LINK PROTOCOLS 190
`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 197
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 5
`
`

`
`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 Mode~ 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 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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 6
`
`

`
`X
`
`CONTENTS
`
`4.4 BRIDGES 304
`4.4.1 Bridges from 802.x to 802.y 307
`4.4.2 Transpar~nt 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 CDMA 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.1 0 Multicast Routing 372
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 7
`
`

`
`CONTENTS
`
`xi
`
`5.3 CONGESTION CONTROL ALGORITHMS 374
`5.3 .1 General Principles of Congestion Control 37 6
`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 Firewalls 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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 8
`
`

`
`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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 9
`
`

`
`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 60 I
`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 ofUSENET 670
`7.5.2 How USENET is Implemented 675
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 10
`
`

`
`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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 11
`
`

`
`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 pro-
`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
`ntunber 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 nutononious 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-
`tion. If one computer can forcibly start, stop, or control another one, the comput-
`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' 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
`m«ltiple processors; it looks like a virtual uniprocessor. Allocation of jobs to pro-
`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
`jabs remotely, explicitly move files around and generally handle all the network
`management personally. With a distributed system, nothing has to be done expli-
`citly; it is all automatically done by the system without the 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.
`f "He" should be read as "he or she" throughout this book.
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 12
`
`

`
``~
`
`~^-,y
`~ ,~
`~ $'_
`-~~>
`r.~
`.f
`
`i
`
`s.
`_-~-
`-
`
`~{
`
`SEC. 11
`
`U~E~ CC~F 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; Mullender, 1993; and Tanenbaum, 1995).
`
`11. 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-
`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 fiom
`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-
`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-l.
`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.
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 13
`
`

`
`4
`
`INTRODUCTION
`
`CHAP. I
`
`Client machine
`
`Server machine
`
`Client
`process
`
`0
`
`Server
`process
`
`0
`
`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
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 14
`
`

`
`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 electronicaliy.
`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 meetings, called videoconference, among far-flung people. It is
`sometimes said that transportation and communication are having a race, and
`whichever wins will make the other obsolete. Virtual meetings could be used for
`remote school, getting medical opinions from distant specialists, and numerous
`other applications.
`Worldwide newsgroups, with discussions on every conceivable topic are
`already commonplace among a select group of people, and this will grow to
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 15
`
`

`
`6
`
`INTRODUCTION
`
`CHAP. 1
`
`include the population at large. These discussions, in which one person posts a
`message and all the other subscribers to the newsgroup can read it, run the gamut
`from humorous to impassioned.
`Our third category is entertainment, which is a huge and growing industry.
`The killer application here (the one that may drive all the rest) is video on
`demand. A decade or so hence, it may be possible to select any movie or televi(cid:173)
`sion program ever made, in any country, and have it displayed on your screen
`instantly. New films may become interactive, where the user is occasionally
`prompted for the story direction (should Macbeth murder Duncan or just bide his
`time?) with alternative scenarios provided for all cases. Live television may also
`become interactive, with the audience participating in quiz shows, choosing
`among contestants, and so on.
`On the other hand, maybe the killer application will not be video on demand.
`Maybe it will be game playing. Already we have multiperson real-time simula(cid:173)
`tion games, like hide-and-seek in a virtual dungeon, and flight simulators with the
`players on one team trying to shoot down the players on the opposing team. If
`done with goggles and 3-dimensional real-time, photographic-quality moving
`images, we have a kind of worldwide shared virtual reality.
`In short, the ability to merge information, communication, and entertainment
`will surely give rise to a massive new industry based on computer networking.
`
`1.1.3. Social Issues
`
`The widespread introduction of networking will introduce new social, ethical,
`political problems (Laudon, 1995). Let us just briefly mention a few of them; a
`thorough study would require a full book, at least. A popular feature of many net(cid:173)
`works are newsgroups or bulletin boards where people can exchange messages
`with like-minded individuals. As long as the subjects are restricted to technical
`topics or hobbies like gardening, not too many problems will arise.
`The trouble comes when newsgroups are set up on topics that people actually
`care. about, like politics, religion, or sex. Views posted to such groups may be
`deGpJy offensive to some people. Furthermore, messages need not be limited to
`text. High-resolution color photographs and even short video clips can now easily
`be transmitted over computer networks. Some people take a live-and-let-live
`view, but others feel that posting certain material (e.g., child pornography) is sim(cid:173)
`ply unacceptable. Thus the debate rages.
`People have sued network operators, claiming that they are responsible for the
`contents of what they carry, just as newspapers and magazines are. The inevitable
`response is that a network is like a telephone company or the post office and can(cid:173)
`not be expected to police what its users say. Stronger yet, having network opera(cid:173)
`tors censor messages would probably cause them to delete everything with even
`the slightest possibility of their being sued, and thus violate their users' rights to
`free speech. It is probably safe to say that this debate will go on for a while.
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 16
`
`

`
`SEC. 1.1
`
`USES OF COMPUTER NETWORKS
`
`7
`
`Another fun area is employee rights versus employer rights. Many people
`read and write email at work. Some employers have claimed the right to read and
`possibly censor employee messages, including messages sent from a home termi(cid:173)
`nal after work. Not all employees agree with this (Sipior and Ward, 1995).
`Even if employers have power over employees, does this relationship also
`govern universities and students? How about high schools and students? In 1994,
`Carnegie-Mellon University decided to fum off the incoming message stream for
`several newsgroups dealing with sex because the university felt the material was
`inappropriate for minors (i.e., those few students under 18). The fallout from this
`event will take years to settle.
`Computer networks offer the potential for sending anonymous messages. 'In
`some situations, this capability may be desirable. For example, it provides a way
`for students, soldiers, employees, and citizens to blow the whistle on illegal
`behavior on the part of professors, officers, superiors, and politicians without fear
`of reprisals. On the other hand, in the United States and most other democracies,
`the law specifically permits an accused person the right to confront and challenge
`his accuser in court. Anonymous accusations cannot be used as evidence.
`In short, computer networks, like the printing press 500 years ago, allow ordi(cid:173)
`nary citizens to distribute their views in different ways and to different audiences
`than were previously possible. This new-found freedom brings with it many
`unsolved social, political, and moral issues. The solution to these problems is left
`as an exercise for the reader.
`
`1.2. NETWORK HARDWARE
`
`It is now time to turn our attention from the applications and social aspects of
`networking to the technical issues involved in network design. There is no gen(cid:173)
`erally accepted taxonomy into which all computer networks fit, but two dimen(cid:173)
`sions stand out as important: transmission technology and scale. We will now
`examine each of these in turn.
`Broadly speaking, there are two types of transmission technology:
`
`1. Broadcast networks.
`
`2. Point-to-point networks.
`
`Broadcast networks have a single communication channel that is shared by all
`the machines on the network. Short messages, called packets in certain contexts,
`sent by any machine are received by all the others. An address field within the
`packet specifies for whom it is intended. Upon receiving a packet, a machine
`checks the address field. If the packet is intended for itself, it processes the
`packet; if the packet is intended for some other machine, it is just ignored.
`As an analogy, consider someone standing at the end of a corridor with many
`rooms off it and shouting "Watson, come here. I want you." Although the packet
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 17
`
`

`
`28
`
`INTRODUCTION
`
`CHAP. 1
`
`are free to change their protocols at will, provided they do not change the service
`visible to their users. In this way, the service and the protocol are completely
`decoupled.
`An analogy with programming languages is worth making. A service is like
`an abstract data type or an object in an object-oriented language. It defines opera-
`tions that can be performed on an object but does not specify how these operations
`are implemented. A protocol relates to the implementation of the service and as
`such is not visible to the user of the service.
`Many older protocols did not distinguish the service from the protocol. In
`effect, a typical layer might have had a service primitive SEND PACKET with the
`user providing a pointer to a fully assembled packet. This arrangement meant that
`all changes to the protocol were immediately visible to the users. Most network
`designers now regard such a design as a serious blunder.
`
`1.4. REFERENCE MODELS
`
`Now that we have discussed layered networks in the abstract, it is time to look
`at some examples. In the next two sections we will discuss two important net-
`work architectures, the OSI reference model and the TCP/IP reference model.
`
`1.4.1. The OSI Reference Model
`
`The OSI model is shown in Fig. 1-16 (minus the physical medium). This
`model is based on a proposal developed by the International Standards Organiza-
`tion (ISO) as a first step toward international standardization of the protocols used
`in the various layers (Day and Zimmermann, 1983). The model is called the ISO
`OSI (Open Systems Interconnection) Reference Model because it deals with
`connecting open systems—that is, systems that are open for communication with
`other systems. We will usually just call it the OSI model for short.
`The OSI model has seven layers. The principles that were applied to arrive at
`the seven layers are as follows:
`
`1. A layer should be created where a different level of abstraction is
`needed.
`
`2. Each layer should perform a well defined function.
`
`The function of each layer should be chosen with an eye toward
`defining internationally standardized protocols.
`
`4. The layer boundaries should be chosen to minimize the information
`flow across the interfaces.
`
`5. The number of layers should be large enough that distinct functions
`need not be thrown together in the same layer out of necessity, and
`small enough that the architecture does not become unwieldy.
`
`CISCO SYSTEMS, INC. Ex. 1111 Page 18
`
`

`
`;~
`
`~
`
`~-- ~.
`~ s~`
`~r~~
`~
`
`ci
`
`~
`~
`
`t
`
`u
`
`I
`~.
`
```
`
`~';r
`
`,,
`
`REFERENCE MODELS
`
`SEC. 1.4
`Below we will discuss each layer of the model in turn, starting at the bottom
`layer.