Computer Networks
`Third Edition
`
`Andrew S. Tanenbaum
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`For book and bookstore information
`
`http://www.prenhall.com
`
`g
`
`Prentice Hall PTR
`Upper Saddle River, New Jersey 07458
`
`REMBRANDT EXHIBIT 2304
`
`

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

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

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

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

`
`REMBRANDT EXHIBIT 2304
`
`REMBRANDT EXHIBIT 2304
`
`

`
`1
`
`INTRODUCTION
`
`Each of the past three centuries has been dominated by a single technology.
`The 18th Century was the time of the great mechanical systems accompanying the
`Industrial Revolution. The 19th Century was the age of the steam engine. During
`the 20th Century, the key technology has been information gathering. processing,
`and distribution. Among other developments, we have seen the installation of
`worldwide telephone networks, the invention of radio and television, the birth and
`unprecedented growth of the computer industry, and the launching of communica(cid:173)
`tion satellites.
`Due to rapid technological progress, these areas are rapidly converging, and
`the differences between collecting, transporting. storing. and processing informa(cid:173)
`tion are quickly disappearing. Organizations with hundreds of offices spread over
`a wide geographical area routinely expect to be able to examine the current status
`of even their most remote outpost at the push of a button. As our ability to gather,
`process, and distribute information grows. the demand for even more sophisti(cid:173)
`cated information processing grows even faster.
`Although the computer industry is young compared to other industries (e.g ..
`automobiles and air transportation), computers have made spectacular progress in
`a short time. During the first two decades of their existence, computer systems
`were highly centralized, usually within a single large room. Not infrequently, this
`room had glass walls, through which visitors could gawk at the great electronic
`wonder inside. A medium-size company or university might have had one or two
`
`REMBRANDT EXHIBIT 2304
`
`

`
`2
`
`INTRODUCTION
`
`CHAP. I
`
`computers, while large institutions had at most a few dozen. The idea that within
`20 years equally powerful computers smaller than postage stamps would be mass
`produced by the millions was pure science fiction.
`The merging of computers and communications has had a profound influence
`on the way computer systems are organized. The concept of the "computer
`center" as a room with a large computer to which users bring their work for pro(cid:173)
`cessing is now totally obsolete. The old model of a single computer serving all of
`the organization· s computational needs has been replaced by one in which a large
`number of separate but interconnected computers do the job. These systems are
`called computer networks. The design and organization of these networks are
`the subjects of this book.
`Throughout the book we will use the term "computer network" to mean an
`interconnected collection of autonomous computers. Two computers are said to
`be interconnected if they are able to exchange information. The connection need
`not he via a copper wire; fiber optics, microwaves, and communication satellites
`can also be used. By requiring the computers to be autonomous, we wish to
`exclude from our definition systems in which there is a clear master/slave rela(cid:173)
`tion. If one computer can forcibly start, stop, or control another one, the comput(cid:173)
`ers are not autonomous. A system with one control unit and many slaves is not a
`network; nor is a large computer with remote printers and terminals.
`There is considerable confusion in the literature between a computer network
`and a distributed system. The key distinction is that in a distributed system, the
`existence of multiple autonomous computers is transparent (i.e., not visible) to the
`user. He t can type a command to run a program, and it runs. It is up to the
`operating system to select the best processor, find and transport all the input files
`to that processor, and put the results in the appropriate place.
`In other words, the user of a distributed system is not aware that there are
`multiple processors; it looks like a virtual uniprocessor. Allocation of jobs to pro(cid:173)
`cessors and files to disks, movement of files between where they are stored and
`where they are needed, and all other system functions must be automatic.
`With a network, users must explicitly log onto one machine, explicitly submit
`jobs remotely. explicitly move files around and generally handle all the network
`management personally. With a distributed system, nothing has to be done expli(cid:173)
`citly; it is all automatically done by the system without the users' knowledge.
`In effect, a distributed system is a software system built on top of a network.
`The software gives it a high degree of cohesiveness and transparency. Thus the
`distinction between a network and a distributed system lies with the software
`(especially the operating system), rather than with the hardware.
`Nevertheless, there is considerable overlap between the two subjects. For
`example, both distributed systems and computer networks need to move files
`around. The difference lies in who invokes the movement, the system or the user.
`·;· ""He·· 'hould be read as "he or she'" throughout this book.
`
`REMBRANDT EXHIBIT 2304
`
`

`
`SEC. 1.1
`
`USES OF COMPUTER NETWORKS
`
`3
`
`Although this book primarily focuses on networks, many of the topics are also
`important in distributed systems. For more information about distrihuted systems,
`see (Coulouris et al., 1994; Mullender. 1993; and Tanenbaum, 1995 ).
`
`1.1. USES OF COMPUTER NETWORKS
`
`Before we start to examine the technical issues in detail, it is worth devoting
`some time to pointing out why people are interested in computer networks and
`what they can be used for.
`
`1.1.1. Networks for Companies
`
`Many organizations have a substantial number of computers in operation,
`often located far apart. For example, a company with many factories may have a
`computer at each location to keep track of inventories. monitor productivity, and
`do the local payroll. Initially, each of these computers may have worked in isola(cid:173)
`tion from the others, but at some point, management may have decided to connect
`them to be able to extract and correlate information about the entire company.
`Put in slightly more general form, the issue here is resource sharing, and the
`goal is to make all programs, equipment, and especially data available to anyone
`on the network without regard to the physical location of the resource and the
`user. In other words, the mere fact that a user happens to be 1000 km away from
`his data should not prevent him from using the data as though they were local.
`This goal may be summarized by saying that it is an attempt to end the "tyranny
`of geography."
`A second goal is to provide high reliability by having alternative sources of
`supply. For example. all files could be replicated on two or three machines, so if
`one of them is unavailable (due to a hardware failure), the other copies could be
`used. In addition, the presence of multiple CPU s means that if one goes down, the
`others may be able to take over its work, although at reduced performance. For
`military, banking, air traffic control, nuclear reactor safety, and many other appli(cid:173)
`cations, the ability to continue operating in the face of hardware problems is of
`utmost importance.
`Another goal
`is saving money. Small computers have a much better
`price/performance ratio than large ones. Mainframes (room-size computers) are
`roughly a factor of ten faster than personal computers, but they cost a thousand
`times more. This imbalance has caused many systems designers to build systems
`consisting of personal computers, one per user, with data kept on one or more
`shared file server machines. In this model, the users are called clients, and the
`whole arrangement is called the client-server model. It is illustrated in Fig. 1-1.
`In the client-server model, communication generally takes the form of a
`request message from the client to the server asking for some work to be done.
`
`REMBRANDT EXHIBIT 2304
`
`

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

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

`
`6
`
`INTRODUCTION
`
`CHAP. I
`
`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'J) 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 he 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-dimcnsional 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
`deeply 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.
`
`REMBRANDT EXHIBIT 2304
`
`

`
`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 turn 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
`
`REMBRANDT EXHIBIT 2304
`
`

`
`8
`
`INTRODUCTION
`
`CHAP. I
`
`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.
`I address bits can hold a group number. Each machine can
`The remaining n -
`"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 arc 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.
`
`lnterprocessor
`distance
`
`0.1 m
`
`1m
`
`10m
`
`100m
`
`1 km
`
`10 km
`
`100 km
`
`Processors
`located in same
`· -
`Circuit board
`
`System
`
`Room
`
`Building
`
`Campus
`
`City
`
`Country
`
`Example
`
`Data flow machine
`
`Multicomputer
`
`Local area network
`
`Metropolitan area network
`
`1,000 km
`
`Continent
`
`Wide area network
`
`10,000 km
`
`Planet
`
`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 aiTanged 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
`
`REMBRANDT EXHIBIT 2304
`
`

`
`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, general!; called LANs, arc privately-owned networks
`within a single building or campus of up to a few kilometers in size. They arc
`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 net\vorks by three characteristics: (I) 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
`usc certain kinds of designs that would not otherwise be possible. It also simpli(cid:173)
`fies network management.
`LANs often use a tra