THIRD EDIT I ON
`
`COMPUTER NETWORKS
`
`ANDREW S. TANENBAUM
`
`Broadcasting
`
`WELCOME
`TO THE
`INFORMATION
`SUPER
`HIGHWAY
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page A
`
`

`
`Computer Networks
`Third Edition
`
`Andrew S. Tanenbaum
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`For book and bookstore information
`
`http://www.prenhall.com
`
`It
`
`Prentice Hall PTR
`Upper Saddle River, New Jersey 07 458
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page B
`
`

`
`Library of Congress Cataloging in Publication Data
`
`Tanenbaum, AndrewS. 1944-.
`Computer networks I Andrew S. Tanenbaum. - 3rd ed.
`em.
`p.
`Includes bibliographical references and index.
`ISBN 0-13-349945-6
`!.Computer networks. I. Title.
`TK5105.5.T36 1996
`004.6--dc20
`
`96-4121
`CIP
`
`Editorial/production manager: Camille Trentacoste
`Interior design and composition: AndrewS. 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
`
`ISBN 0-13-349945-6
`
`Prentice-Hall International (UK) Limited, London
`Prentice-Hall of Australia Pty. Limited, Sydney
`Prentice-Hall Canada Inc., Toronto
`Prentice-Hail Hispanoamericana, SA., Mexico
`Prentice-HaJJ of India Private Limited, New Delhi
`Prentice-Hall of Japan, Inc., Tokyo
`Simon & Schuster Asia Pte. Ltd., Singapore
`EditoraPrentice-Hall do Brasil, Ltda., Rio de Janeiro
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page C
`
`

`
`XV
`
`1
`
`\
`
`CONTENTS
`
`PREFACE
`
`1 INTRODUCTION
`1.1 USES OF COMPUTER NETWORKS 3
`1.1.1 Networks for Companies 3
`1.1.2 Networks for People 4
`1.1.3 Sociallssues 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 lntemetworks 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
`
`·r.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
`
`,. ..
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page vi
`
`

`
`CONTENTS
`
`vii
`
`1.6 EXAMPLE DATA COMMUNICATION SERVICES 56
`1.6.1 SMDS-Switched Multimegabit Data Service 57
`1.q.2 X.25 Networks 59
`1.6.3 Frame Relay 60
`1.6.4 Broadband ISDN and A TM 61
`1.6.5 Comparison of Services 66
`
`1.7 NETWORK STANDARDIZATION 66
`1.7.1 Who's Who in the Tel~communications 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
`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
`
`77
`
`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 Electromagnetic Spectrum 94
`2.3.2 Radio Transmission 97
`2.3.3 Microwave Transmission 98
`2.3.4 Infrared and Millimeter Waves 100
`2.3.5 Lightwave Transmission 100
`
`2.4
`
`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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page vii
`
`

`
`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 A TM 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
`
`176
`
`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
`3.2 ERROR DETECTION AND CORRECTION
`3.2.1 Error-Correcting Codes 184
`3.2.2 Error-Detecting Codes 186
`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
`
`183
`
`190
`
`197
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page viii
`
`

`
`C I
`
`CONTENTS
`
`ix
`
`3.4 SLIDING WINDOW PROTOCOLS 202
`3.4.1 A One Bit Sliding Window Protocol 206
`3.4.2 A Protocol Using Go Back n 207
`3.4.3 A Protocol Using Selective Repeat 213
`3.5 PROTOCOL SPECIFICATION AND VERIFICATION 219
`3.5.1 Finite State Machine Models 219
`3.5.2 Petri Net Models 223
`3.6 EXAMPLE DATA LINK PROTOCOLS 225
`3.6.1 HDLC-High-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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page ix
`
`

`
`X
`
`CONTENTS
`
`4.4 BRIDGES 304
`4.4.1 Bridges from 802.x to 802.y 307
`4.4.2 Transparent Bridges 310
`4.4.3 Source Routing Bridges 314
`4.4.4 Comparison of 802 Bridges 316
`4.4.5 Remote Bridges 317
`4.5 HIGH-SPEED LANS 318
`4.5.1 FDDI 319
`4.5.2 Fast Ethernet 322
`4.5.3 HIPPI- High-Performance Parallel Interface 325
`4.5.4 Fibre Channel 326
`4.6 SATELLITE NETWORKS 327
`4.6.1 Polling 328
`4.6.2 ALOHA 329
`4.6.3 FDM 330
`4.6.4 TDM 330
`4.6.5 CDMA 333
`4.7 SUMMARY 333
`
`- .
`
`5 THENETWORKLAYER
`
`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
`
`. l
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page x
`
`

`
`CONTENTS
`
`xi
`
`5.3 CONGESTION CONTROL ALGORITHMS 374
`5.3.1 General Principles of Congestion Control 376
`5.3.2 Congestion Prevention Policies 378
`5.3.3 Traffic Shaping 379
`5.3.4 Flow Specifications 384
`5.3.5 Congestion Control in Virtual Circuit Subnets 386
`5.3.6 Choke Packets 387
`5.3.7 Load Shedding 390
`5.3.8 Jitter Control 392
`5.3.9 Congestion Control for Multicasting 393
`5.4 INTERNETWORKING 396
`5.4.1 How Networks Differ 399
`5.4.2 Concatenated Virtual Circuits 401
`5.4.3 Connectionless Internetworking 402
`5.4.4 Tunneling 404
`5.4.5 Internetwork Routing 405
`5.4.6 Fragmentation 406
`5.4.7 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 1Pv6 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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page xi
`
`

`
`xii
`6
`
`CONTENTS
`
`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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page xii
`
`

`
`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 NETWORKSECURITY 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 DigitalSignatures 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-Abstracl 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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page xiii
`
`

`
`~ • . ,
`
`'
`
`'·
`
`xiv
`
`CONTENTS
`
`7.6 THE WORLD WIDE WEB 681
`7 .6.1 The C]jent 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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page xiv
`
`

`
`7
`
`USES OF COMPUTER NETWORKS
`
`SEC. 1.1
`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 turn off the incoming message stream for
`several newsgroups dealing with sex because the university felt the tp.aterial 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 tum.
`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
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page 7
`
`

`
`8
`
`INTRODUCTION
`
`CHAP. 1
`
`may actually be received (heard) by many people, only Watson responds. The
`others just ignore it. Another example is an airport announcement asking all flight
`644 passengers to report to gate 12.
`Broadcast systems generally also allow the possibility of addressing a packet
`to all destinations by using a special code in the address field. When a packet
`with this code is transmitted, it is received and processed by every machine on the
`network. This mode of operation is called broadcasting. Some broadcast sys(cid:173)
`tems also support transmission to a subset of the machines, something known as
`multicasting. One possible scheme is to reserve one bit to indicate multicasting.
`The remaining n - 1 address bits can hold a group number. Each machine can
`"subscribe" to any or all of the groups. When a packet is sent to a certain group,
`it is delivered to all machines subscribing to that group.
`In contrast, point-to-point networks consist of many connections between
`individual pairs of machines. To go from the source to the destination, a packet
`on this type of network may have to first visit one or more intermediate machines.
`Often multiple routes, of different lengths are possible, so routing algorithms play
`an important role in point-to-point networks. As a general rule (although there are
`many exceptions), smaller, geographically localized networks tend to use broad(cid:173)
`casting, whereas larger networks usually are point-to-point.
`
`I nterprocessor
`distance
`
`Processors
`located in same
`
`Example
`
`0.1 m
`
`1m
`
`10m
`
`100m
`
`1 km
`
`10km
`
`100 km
`
`1,000 km
`
`10,000 km
`
`Circuit board
`
`Data flow machine
`
`System
`
`Room
`
`Building
`
`Campus
`
`Cjty
`
`Country
`
`Continent
`
`Planet
`
`Multicomputer
`
`} Looal 8'68 oatwo<k
`
`Metropolitan area network
`
`} Wide a<ea ootwo~
`
`The Internet
`
`Fig. 1-2. Classification of interconnected processors by scale.
`An alternative criterion for classifying networks is their scale. In Fig. 1-2 we
`give a classification of multiple processor systems arranged by their physical size.
`At the top are data flow machines, highly parallel computers with many func(cid:173)
`tional units all working on the same program. Next come the multicomputers,
`systems that communicate by sending messages over very short, very fast buses.
`Beyond the multicomputers are the true networks, computers that communicate
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page 8
`
`

`
`.J •
`
`SEC. 1.2
`
`NETWORK HARDWARE
`
`9
`
`by exchanging messages over longer cables. These can be divided into local,
`metropolitan, and wide area networks. Finally, the connection of two or more
`networks is called an internetwork. The worldwide Internet is a well-known
`example of an internetwork. Distance is important as a classification metric
`because different techniques are used at different scales. In this book we will be
`concerned with only the true networks and their interconnection. Below we give
`a brief introduction to the subject of network hardware.
`
`1.2.1. Local Area Networks
`
`Local area networks , generally called LANs, are privately-owned networks
`within a single building or campus of up to a few kilometers in size. They are
`widely used to connect personal computers and workstations in company offices
`and factories to share resources (e.g., printers) and exchange information. LANs
`are distinguished from other kinds of networks by three characteristics: (1) their
`size, (2) their transmission technology, and (3) their topology.
`LANs are restricted in size, which means that the worst-case transmission
`time is bounded and known in advance. Knowing this bound makes it possible to
`use certain kinds of designs that would not otherwise be possible. It also simpli(cid:173)
`fies network management.
`LANs often use a transmission technology consisting of a single cable to
`which all the machines are attached, like the telephone company party lines once
`used in rural areas. Traditional LANs run at speeds of 10 to 100 Mbps, have low
`delay (tens of microseconds), and make very few errors. Newer LANs may
`operate at higher speeds, up to hundreds of megabits/sec. In this book, we will
`adhere to tradition and measure line speeds in megabits/sec (Mbps), not
`megabytes/sec (MB/sec). A megabit is 1,000,000 bits, not 1,048,576 (220) bits.
`
`(a)
`
`(b)
`
`Fig. 1-3. Two broadcast networks. (a) Bus. (b) Ring.
`
`Various topologies are possible for broadcast LANs. Figure 1-3 shows two of
`them. In a bus (i.e., a linear cable) network, at any instant one machine is the
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page 9
`
`

`
`10
`
`INTRODUCTION
`
`CHAP. 1
`
`master and is allowed to transmit. All other machines are required to refrain from
`sending. An arbitration mechanism is needed to resolve conflicts when two or
`more machines want to transmit simultaneously. The arbitration mechanism may
`be centralized or distributed. IEEE 802.3, popularly called Ethernet ™, for
`example, is a bus-based broadcast network with decentralized control operating at
`10 or 100 Mbps. Computers on an Ethernet can transmit whenever they want to;
`if two or more packets collide, each computer just waits a random time and tries
`again later.
`A second type of broadcast system is the ring. In a ring, each bit propagates
`around on its own, not waiting for the rest of the packet to which it belongs. Typi(cid:173)
`cally, each bit circumnavigates the entire ring in the time it takes to transmit a few
`bits, often before the complete packet has even been transmitted. Like all other
`broadcast systems, some rule is needed for arbitrating simultaneous accesses to
`the ring. Various methods are in use and will be discussed later in this book.
`IEEE 802.5 (the IBM token ring), is a popular ring-based LAN operating at 4 and
`16 Mbps.
`Broadcast networks can be further divided into static and dynamic, depending
`on how the channel is allocated. A typical static allocation would be to divide up
`time into discrete intervals and run a round robin algorithm, allowing each
`machine to broadcast only when its time slot comes up. Static allocation wastes
`channel capacity when a machine has nothing to say during its allocated slot, so
`most systems attempt to allocate the channel dynamically (i.e., on demand).
`Dynamic allocation methods for a common channel are either centralized or
`decentralized. In the centralized channel allocation method, there is a single
`entity, for example a bus arbitration unit, which determines who goes next. It
`might do this by accepting requests and making a decision according to some
`internal algorithm. In the decentralized channel allocation method, there is no
`central entity; each machine must decide for itself whether or not to transmit.
`You might think that this always leads to chaos, but it does not. Later we will
`study many algorithms designed to bring order out of the potential chaos.
`The other kind of LAN is built using point-to-point lines. Individual lines
`connect a specific machine with another specific machine. Such a LAN is really a
`miniature wide area network. We will look at these later.
`
`1.2.2. Metropolitan Area Networks
`
`A metropolitan area network, or MAN (plural: MANs, not MEN) is basi(cid:173)
`cally a bigger version of a LAN and normally uses similar technology. It might
`cover a group of nearby corporate offices or a city and might be either private or
`public. A MAN can support both data and voice, and might even be related to the
`local cable television network. A MAN just has one or two cables and does not
`contain switching elements, which shunt packets over one of several potential out(cid:173)
`put lines. Not having to switch simplifies the design.
`
`j
`
`LENOVO ET AL. EXHIBIT 1009
`
`Page 10