Computer Networks
`
`Fourth Edition
`
`Andrew S. Tanenbaum
`
`Vrije Universiteit
`Amsterdam, The Netherlands
`
`PH
`PTR
`
`
`Prentice Hall PTR
`
`Upper Saddle RN63 NJ 07458
`WWW'phptr‘°°m
`
`SIMPLEAIR EXHIBIT 2035
`Google v. Simp|eAir
`|PR2015-00180
`
`

`
`Library of Congress Cataloging-in-Publication Data
`
`Tanenbaum, Andrew S.
`Computer networks /Andrew S. Tanenbaum.——4th ed.
`p. cm.
`Includes bibliographical references.
`ISBN 0-13-066102—3
`1. Computer networks. I. Title.
`TK5l05.5 .T36 2002
`004.6——dc2l
`
`2002029263
`
`Editorial/production supervision: Patti Guerrieri
`Cover design director: Jerry Volta
`Cover designer: Anthony Gemmellaro
`Cover design: Andrew S. Tanenbaum
`Art director: Gail Cocker-Bogusz
`Interior Design: Andrew S. Tanenbtmm
`Interior graphics: Hadel Studio
`Typesetting: Andrew S. Tcmenbaiim
`Manufacturing buyer: Maura Zaldivar
`Executive editor: Mary Franz
`Editorial assistant: Noreen Regina
`Marketing manager: Dan DePasqua.le
`
`PH
`PTR
`
`
`© 2003 Pearson Education, Inc.
`Publishing as Prentice Hall PTR
`Upper Saddle River, New Jersey 07458
`
`Prentice Hall books are widely used by corporations and government agencies for training,
`marketing, and resale.
`
`For information regarding corporate and government bulk discounts please contact:
`Corporate and Government Sales (800) 382-3419 or corpsales@pearsontechgroup.com
`
`All products or services mentioned in this book are the trademarks or service marks of their
`respective companies or organizations.
`"
`
`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 8
`
`ISBN O-13-066102-3
`
`Pearson Education LTD.
`Pearson Education Australia PTY, Limited
`Pearson Education Singapore, Pte. Ltd.
`Pearson Education North Asia Ltd.
`Pearson Education Canada, Ltd.
`Pearson Educacion de Mexico, S.A. de C.V.
`Pearson Education — Japan
`Pearson Education Malaysia, Pte. Ltd.
`
`
`
`

`
`16
`
`INTRODUCTION
`
`CHAP.
`
`1
`
`lnterprocessor
`distance
`
`Processors
`located in same
`
`Example
`
`1 m
`
`10 m
`
`100 m
`
`1 km
`
`10 km
`
`100 km
`
`Square meter
`
`Personal area network
`
`Room
`
`Building
`
`Campus
`
`City
`
`Country
`
`Local area network
`
`Metropolitan area network
`
`Wide area network
`
`1000 km
`
`1
`
`Continent
`
`10,000 km
`
`Planet
`
`The Internet
`
`Figure 1-6. Classification of interconnected processors by scale.
`
`The worldwide Internet is a well—known example of an internetwork. Distance is
`important as a classification metric because different techniques are used at dif~
`ferent scales.
`In this book we will be concerned with networks at all these scales.
`Below we give a brief introduction to 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-
`fies network management.
`LANS may use a transmission technology consisting of a 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 Mbps to 100 Mbps, have low
`delay (microseconds or nanoseconds), and make Very few errors. Newer LANS
`operate at up to 10 Gbps.
`In this book, we will adhere to tradition and measure
`line speeds in megabits/sec (1 Mbps is 1,000,000 bits/sec) and gigabits/sec (1
`Gbps is 1,000,000,000 bits/sec).
`Various topologies are possible for broadcast LANS. Figure 1-7 shows two of
`them. In a bus (i.e., a linear cable) network, at any instant at most one machine is
`
`

`
`SEC. 1.2
`
`NETWORK HARDWARE
`
`17
`
`the 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, usually
`operating at 10 Mbps to l0 Gbps. Computers on an Ethernet can transmit when-
`ever they want to; if two or more packets collide, each computer just waits a ran-
`dom time and tries again later.
`
`/
`
`Computer
`
`(b)
`
`Computer
`
`Illll
`
`I
`
`Cable
`
`\ (
`
`8)
`
`Figure 1-7. Two broadcast networks. (a) Bus. (b) Ring.
`
`In a ring, each bit propagates
`A second type of broadcast system is the ring.
`around on its own, not waiting for the rest of the packet to which it belongs. Typi-
`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. As with all
`other broadcast systems, some rule is needed for arbitrating simultaneous accesses
`to the ring. Various methods, such as having the machines take turns, are in use.
`IEEE 802.5 (the IBM token ring),
`is a ring—based LAN operating at 4 and 16
`Mbps. FDDI is another example of a ring network.
`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
`time into discrete intervals and use a round—robin algorithm, allowing each ma-
`chine 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 en-
`tity, 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
`algfuithm.
`In the decentralized channel allocation method, there is no central
`Emmy; each machine must decide for itself whether to transmit. You might think
`that this always leads to chaos, but it does not. Later we will study many algo-
`rithms designed to bring order out of the potential chaos.
`
`

`
`42
`
`INTRODUCTION
`
`CHAP.
`
`1
`
`remain intact as long as the source and destination machines were functioning,
`even if some of the machines or transmission lines in between were suddenly put
`out of operation. Furthermore, a flexible architecture was needed since applica-
`tions with divergent requirements were envisioned, ranging from transferring files
`to real—time speech transmission.
`
`The Internet Layer
`
`All these requirements led to the choice of a packet—switching network based
`on a connectionless internetwork layer. This layer, called the internet layer, is
`the linchpin that holds the whole architecture together.
`Its job is to permit hosts to
`inject packets into any network and have them travel independently to the destina-
`tion (potentially on a different network). They may even arrive in a different
`order than they were sent, in which case it is the job of higher layers to rearrange
`them, if in—order delivery is desired. Note that “internet” is used here in a generic
`sense, even though this layer is present in the Internet.
`The analogy here is with the (snail) mail system. A person can drop a
`sequence of international letters into a mail box in one country, and with a little
`luck, most of them will be delivered to the correct address in the destination coun-
`try. Probably the letters will travel through one or more international mail gate-
`ways along the way, but this is transparent to the users. Furthermore, that each
`country (i.e., each network) has its own stamps, preferred envelope sizes, and
`delivery rules is hidden from the users.
`The internet layer defines an official packet format and protocol called IP
`(Internet Protocol). The job of the internet layer is to deliver IP packets where
`they are supposed to go. Packet routing is clearly the major issue here, as is
`avoiding congestion. For these reasons, it is reasonable to say that the TCP/IP
`internet layer is similar in functionality to the OSI network layer. Figure 1-21
`shows this correspondence.
`
`The Transport Layer
`
`The layer above the internet layer in the TCP/IP model is now usually called
`the transport layer.
`It is designed to allow peer entities on the source and desti-
`nation hosts to carry on a conversation, just as in the OSI transport layer. Two
`end—to—end transport protocols have been defined here. The first one, TCP
`(Transmission Control Protocol), is a reliable connection—oriented protocol that
`allows a byte stream originating on one machine to be delivered without error on
`any. other machine in the internet.
`It fragments the incoming byte stream into
`discrete messages and passes each one on to the internet layer. At the destination,
`the receiving TCP process reassembles the received messages into the output
`stream. TCP also handles flow control to make sure a fast sender cannot swamp a
`slow receiver with more messages than it can handle.
`
`

`
`SEC. 1.4
`
`REFERENCE MODELS
`
`43
`
`7
`
`6
`5
`
`4
`
`3
`
`2
`
`1
`
`OSI
`
`TCP/IP
`
`Application
`
`Application
`
`Presentation
`Session
`
`Transport
`
`Network
`
`Data link
`
`Physical
`
`Not present
`/ in the model
`
`Transport
`
`Internet
`
`Host-to-network
`
`Figure 1-21. The TCP/IP reference model.
`
`The second protocol in this layer, UDP (User Datagram Protocol), is an un-
`reliable, connectionless protocol for applications that do not want TCP’s sequenc-
`ing or flow control and wish to provide their own.
`It is also widely used for one-
`shot, client—server—type request—reply queries and applications in which prompt
`delivery is more important than accurate delivery, such as transmitting speech or
`video. The relation of IP, TCP, and UDP is shown in Fig. 1-22. Since the model
`was developed, IP has been implemented on many other networks.
`
`TELNEL‘
`
`I
`
`FTP
`
`I
`
`i
`
`SMTP
`
`i
`
`DNS
`
`i
`
`Application
`
`Layer (OSI names)
`
`Protocols
`
`TCP
`
`‘
`
`UDP
`
`Transport
`
`Networks{
`
`ARPANETi
`
`H SATNET I
`
`Packet
`
`F radio J
`
`LAN
`
`‘I
`
`Physical +
`
`datannk
`
`Figure 1-22. Protocols and networks in the TCP/IP model initially.
`
`The Application Layer
`
`The TCP/IP model does not have session or presentation layers. No need for
`ilhem was perceived, so they were not included. Experience with the OSI model
`33 Droven this View correct: they are of little use to most applications.
`hmoll top of the transport layer is the application layer.
`It contains all the
`D 1e1—level protocols. The early ones included virtual terminal (TELNET), file
`
`

`
`44
`
`INTRODUCTION
`
`CHAP.
`
`I
`
`l—22. The virtual
`transfer (FTP), and electronic mail (SMTP), as shown in Fig.
`terminal protocol allows a user on one machine to log onto a distant machine and
`work there. The file transfer protocol provides a way to move data efficiently
`from one machine to another. Electronic mail was originally just a kind of file
`transfer, but later a specialized protocol (SMTP) was developed for it. Many
`other protocols have been added to these over the years: the Domain Name Sys-
`tem (DNS) for mapping host names onto their network addresses, NNTP, the pro-
`tocol for moving USENET news articles around, and HTTP,
`the protocol for
`fetching pages on the World Wide Web, and many others.
`
`The Host-to-Network Layer
`
`Below the internet layer is a great void. The TCP/IP reference model does
`not really say much about what happens here, except to point out that the host has
`to connect to the network using some protocol so it can send IP packets to it. This
`protocol is not defined and varies from host to host and network to network.
`Books and papers about the TCP/IP model rarely discuss it.
`
`1.4.3 A Comparison of the OSI and TCP/IP Reference Models
`
`The OSI and TCP/IP reference models have much in common. Both are
`based on the concept of a stack of independent protocols. Also, the functionality
`of the layers is roughly similar. For example,
`in both models the layers up
`through and including the transport layer are there to provide an end—to—end,
`network—independent
`transport service to processes wishing to communicate.
`These layers form the transport provider. Again in both models, the layers above
`transport are application—oriented users of the transport service.
`Despite these fundamental similarities, the two models also have many differ-
`ences.
`In this section we will focus on the key differences between the two refer-
`ence models.
`It is important to note that we are comparing the reference models
`here, not the corresponding protocol stacks. The protocols themselves will be dis-
`cussed later. For an entire book comparing and contrasting TCP/IP and OSI, see
`(Piscitello and Chapin, I993).
`Three concepts are central to the OSI model:
`
`1. Services.
`
`2.
`
`Interfaces.
`
`3. Protocols.
`
`Probably the biggest contribution of the OSI model is to make the distinction
`between these three concepts explicit. Each layer performs some services for the
`layer above it. The service definition tells what the layer does, not how entities
`above it access it or how the layer works. It defines the layer’s semantics.
`
`
`
`

`
`56
`
`INTRODUCTION
`
`CHAP.
`
`1
`
`network operators to establish a NAP (Network Access Point). These operators
`were PacBell (San Francisco), Ameritech (Chicago), MFS (Washington, D.C.),
`and Sprint (New York City, where for NAP purposes, Pennsauken, New Jersey
`counts as New York City). Every network operator that wanted to provide back-
`bone service to the NSF regional networks had to connect to all the NAPS.
`This arrangement meant that a packet originating on any regional network had
`a choice of backbone carriers to get from its NAP to the destination’s NAP. Con-
`sequently,
`the backbone carriers were forced to compete for the regional net-
`works’ business on the basis of service and price, which was the idea, of course.
`As a result, the concept of a single default backbone was replaced by a commer—
`cially—driven competitive infrastructure. Many people like to criticize the Federal
`Government for not being innovative, but in the area of networking, it was DoD
`and NSF that created the infrastructure that formed the basis for the Internet and
`then handed it over to industry to operate.
`During the 1990s, many other countries and regions also built national re-
`search networks, often patterned on the ARPANET and NSFNET. These in-
`cluded EuropaNET and EBONE in Europe, which started out with 2—Mbps lines
`and then upgraded to 34—Mbps lines. Eventually, the network infrastructure in
`Europe was handed over to industry as well.
`
`Internet Usage
`
`The number of networks, machines, and users connected to the ARPANET
`grew rapidly after TCP/IP became the only official protocol on January 1, 1983.
`When NSFNET and the ARPANET were interconnected, the growth became exp-
`onential. Many regional networks joined up, and connections were made to net-
`works in Canada, Europe, and the Pacific’.
`Sometime in the mid—l980s, people began viewing the collection of networks
`as an internet, and later as the Internetjalthough there was no official dedication
`with some politician breaking a bottle of champagne over a fuzzball.
`The glue that holds the Internet together is the TCP/IP reference model and
`TCP/IP protocol stack. TCP/IP makes universal service possible and can be com-
`pared to the adoption of standard gauge by the railroads in the 19th century or the
`adoption of common signaling protocols by all the telephone companies.
`What does it actually mean to be on the Internet? Our definition is that a
`machine is on the Internet if it runs the TCP/IP protocol stack, has an IP address,
`and can send IP packets to all the other machines on the Internet. The mere abil-
`ity to send and receive electronic mail is not enough, since e—mail is gatewayed to
`many networks outside the Internet. However, the issue is clouded somewhat by
`the fact that millions of personal computers can call up an Internet service pro-
`vider using a modem, be assigned a temporary IP address, and send IP packets to
`other Internet hosts. It makes sense to regard such machines as being on the Inter—
`net for as long as they are connected to the service provider’s router.
`
`

`
`58
`
`INTRODUCTION
`
`CHAP.
`
`l
`
`the WW, and other Internet services. These com-
`gaining access to e—mail,
`panies signed up tens of millions of new users a year during the late 1990s, com-
`pletely changing the character of the network from an academic and military play-
`ground to a public utility, much like the telephone system. The number of Inter-
`net users now is unknown, but is certainly hundreds of millions worldwide and
`will probably hit 1 billion fairly soon.
`
`Architecture of the Internet
`
`In this section we will attempt to give a brief overview of the Internet today.
`Due to the many mergers between telephone companies (telcos) and ISPs, the
`waters have become muddied and it is often hard to tell who is doing what. Con-
`sequently,
`this description will be of necessity somewhat simpler than reality.
`The big picture is shown in Fig. 1-29. Let us examine this figure piece by piece
`now.
`
`Regional ISP
`
`\ Backbone
`
`
`
`Corporate
`LAN
`
`Figure 1-29. Overview of the Internet.
`A good place to start is with a client at home. Let us assume our client calls
`his or her ISP over a dial—up telephone line, as shown in Fig. l—29. The modem is
`a card within the PC that converts the digital signals the computer produces to
`analog signals that can pass unhindered over the telephone system. These signals
`are transferred to the ISP’s POP (Point of Presence), where they are removed
`from the telephone system and injected into the ISP’s regional network. From this
`point on, the system is fully digital and packet switched.
`If the ISP is the local
`
`

`
`SEC. 1.5
`
`EXAMPLE NETWORKS
`
`61
`
`as the basic concept, but it was not, due in part to the expense of billing (and giv-
`en the quality of most television, the embarrassment factor cannot be totally dis-
`counted either). Also, many theme parks charge a daily admission fee for unlim-
`ited rides, in contrast to traveling carnivals, which charge by the ride.
`That said, it should come as no surprise that all networks designed by the tele-
`phone industry have had connection—oriented subnets. What is perhaps surprising,
`is that the Internet is also drifting in that direction,
`in order to provide a better
`quality of service for audio and video, a subject we will return to in Chap. 5. But
`now let us examine some connection—oriented networks.
`
`X.25 and Frame Relay
`
`Our first example of a connection—oriented network is X.25, which was the
`first public data network.
`It was deployed in the 1970s at a time when telephone
`service was a monopoly everywhere and the telephone company in each country
`expected there to be one data network per country—theirs. To use X.25, a com-
`puter first established a connection to the remote computer, that is, placed a tele-
`phone call. This connection was given a connection number to be used in data
`transfer packets (because multiple connections could be open at the same time).
`Data packets were very simple, consisting of a 3—byte header and up to 128 bytes
`of data. The header consisted of a 12-bit connection number, a packet sequence
`number, an acknowledgement number, and a few miscellaneous bits. X.25 net-
`works operated for about a decade with mixed success.
`In the 1980s, the X.25 networks were largely replaced by a new kind of net-
`work called frame relay. The essence of frame relay is that it is a connection-
`oriented network with no error control and no flow control. Because it was
`
`connection—oriented, packets were delivered in order (if they were delivered at
`all). The properties of in—order delivery, no error control, and no flow control
`make frame relay akin to a wide area LAN.
`Its most important application is
`interconnecting LANs at multiple company offices. Frame relay enjoyed a mod-
`est success and is still in use in places today.
`
`Asynchronous Transfer Mode
`
`Yet another, and far more important, connection—oriented network is ATM
`(Asynchronous Transfer Mode). The reason for the somewhat strange name is
`that in the telephone system, most transmission is synchronous (closely tied to a
`Clock), and ATM is not.
`ATM was designed in the early 1990s and launched amid truly incredible
`hype (Ginsburg, 1996; Goralski, 1995; Ibe, 1997; Kim et al., 1994; and Stallings,
`2000) ATM was going to solve all the world’s networking and telecommunica-
`“QHS problems by merging voice, data, cable television, telex, telegraph, carrier
`P‘g€0n,
`tin cans connected by strings, tom—toms, smoke signals, and everything
`
`

`
`SEC. 2.5
`
`THE PUBLIC SWITCHED TELEPHONE NETWORK
`
`147
`
`which are inside the switching offices. We have just looked at the outside plant.
`Now it is time to examine the inside plant.
`Two different switching techniques are used nowadays: circuit switching and
`packet switching. We will give a brief introduction to each of them below. Then
`we will go into circuit switching in detail because that is how the telephone sys-
`tem works. We will study packet switching in detail in subsequent chapters.
`
`Circuit Switching
`
`When you or your computer places a telephone call, the switching equipment
`within the telephone system seeks out a physical path all the way from your tele-
`phone to the receiver’s telephone. This technique is called circuit switching and
`is shown schematically in Fig. 2—38(a). Each of the six rectangles represents a
`carrier switching office (end office, toll office, etc.).
`In this example, each office
`has three incoming lines and three outgoing lines. When a call passes through a
`switching office, a physical connection is (conceptually) established between the
`line on which the call came in and one of the output lines, as shown by the dotted
`lines.
`-
`
`L—Q
`__O
`.—o
`
`Q—.——Q
`O_fi
`r__O
`o
`o
`
`O— ‘
`x o
`‘0—
`—'?1—<}——— — 0-
`i—o
`o
`-—O
`O \
`
`-
`
`r
`
`(8)
`
`—i
`
`1-
`
`—I
`
`I-F“.
`i—
`
`Ii-El
`It
`
`Physical (copper)
`Q——J
`connection set up
`O__,
`when call is made
`-0 I /
`" \\
`O
`——o
`\ 0-;
`_Lj——o
`\—o
`
`El
`
`__
`——
`
`/'
`
`Switching office
`
`Packets queued
`for subsequent
`transmission
`
`T
`
`I
`/’
`Computer
`
`i—-"
`
`I i
`
`—I
`
`_L
`
`(b)
`
`l
`
`Figure 2-38.
`
`(21) Circuit switching. (b) Packet switching.
`
`

`
`148
`
`THE PHYSICAL LAYER
`
`CHAP. 2
`
`In the early days of the telephone, the connection was made by the operator
`plugging a jumper cable into the input and output sockets. In fact, a surprising lit-
`tle story is associated with the invention of automatic circuit switching equipment.
`It was invented by a l9th century Missouri undertaker named Almon B. Strowger.
`Shortly after the telephone was invented, when someone died, one of the survivors
`would call the town operator and say “Please connect me to an undertaker.”
`Unfortunately for Mr. Strowger, there were two undertakers in his town, and the
`other one’s wife was the town telephone operator. He quickly saw that either he
`was going to have to invent automatic telephone switching equipment or he was
`going to go out of business. He chose the first option. For nearly 100 years, the
`circuit—switching equipment used worldwide was known as Strowger gear.
`(His-
`tory does not record whether the now—unemployed switchboard operator got a job
`as an information operator, answering questions such as “What is the phone num-
`ber of an undertaker?”)
`The model shown in Fig. 2—39(a) is highly simplified, of course, because parts
`of the physical path between the two telephones may, in fact, be microwave or
`fiber links onto which thousands of calls are multiplexed. Nevertheless, the basic
`idea is valid: once a call has been set up, a dedicated path between both ends
`exists and will continue to exist until the call is finished.
`The alternative to circuit switching is packet switching, shown in Fig. 2—38(b).
`With this technology, individual packets are sent as need be, with no dedicated
`path being set up in advance. It is up to each packet to find its way to the destina-
`tion on its own.
`An important property of circuit switching is the need to set up an end—to—end
`J
`path before any data can be sent. The_ elapsed time between the end of dialing and
`the start of ringing can easily be 10 sec, more on long—d1stance or international
`calls. During this time interval, the telephone system is hunting for a path, as
`shown in Fig. 2—39(a). Note that before data transmission can even begin, the call
`request signal must propagate all the way to the destination and be acknowledged.
`For many computer applications (e.g., point—of—sale credit verification), long setup
`times are undesirable.
`As a consequence of the reserved path between the calling parties, once the
`setup has been completed, the only delay for data is the propagation time for the
`electromagnetic signal, about 5 msec per 1000 km. Also as a consequence of the
`established path, there is no danger of congestion~that is, once the call has been
`put through, you never get busy signals. Of course, you might get one before the
`connection has been established due to lack of switching or trunk capacity.
`
`Message Switching
`
`An alternative switching strategy is message switching, illustrated in Fig. 2-
`39(b). When this form of switching is used, no physical path is established in
`advance between sender and receiver.
`Instead, when the sender has a block of
`
`

`
`
`
`432
`
`THE NETWORK LAYER
`
`CHAP. 5
`
`
`
`
`
`w.;.w.r.r..»wa..a.;'—.W;,.;;..;w.,n.o.a%¢e.e.../N.a.....W.;:,w;w.w;s
`
`-i
`
`
`
`7. Look for a good design; it need not be perfect. Often the design-
`ers have a good design but it cannot handle some weird special case.
`Rather than messing up the design, the designers should go with the
`good design and put the burden of working around it on the people
`with the strange requirements.
`
`In other
`8. Be strict when sending and tolerant when receiving.
`words, only send packets that rigorously comply with the standards,
`but expect incoming packets that may not be fully conformant and
`try to deal with them.
`
`9. Think about scalability. If the system is to handle millions of hosts
`and billions of users effectively, no centralized databases of any kind
`are tolerable and load must be spread as evenly as possible over the
`available resources.
`
`If a network has poor perfor-
`10. Consider performance and cost.
`mance or outrageous costs, nobody will use it.
`
`Let us now leave the general principles and start looking at the details of the
`Internet’s network layer. At the network layer, the Internet can be viewed as a
`collection of subnetworks or Autonomous Systems (ASes) that are intercon-
`nected. There is no real structure, but several major backbones exist. These are
`constructed from high—bandwidth lines and fast routers. Attached to the back-
`bones are regional (midlevel) networks, and attached to these regional networks
`are the LANs at many universities, companies, and Internet service providers. A
`sketch of this quasi-hierarchical organization is given in Fig. 5-52.
`The glue that holds the whole Internet together is the network layer protocol,
`IP (Internet Protocol). Unlike» most older network layer protocols,
`it was
`designed from the beginning with internetworking in mind. A good way to think
`of the network layer is this.
`Its job is to provide a best—efforts (i.e., not guar-
`anteed) way to transport datagrams from source to destination, without regard to
`whether these machines are on the same network or whether there are other net-
`works in between them.
`
`Communication in the Internet works as follows. The transport layer takes
`data streams and breaks them up into datagrams.
`In theory, datagrams can be up
`to 64 Kbytes each, but in practice they are usually not more than 1500 bytes (so
`they fit in one Ethernet frame). Each datagram is transmitted through the Internet,
`possibly being fragmented into smaller units as it goes. When all the pieces
`finally get to the destination machine, they are reassembled by the network layer
`into the original datagram. This datagram is then handed to the transport layer,
`which inserts it into the receiving process’ input stream. As can be seen from
`Fig. 5-52, a packet originating at host 1 has to traverse six networks to get to host
`2. In practice, it is often much more than six.
`
`

`
`
`
`582
`
`THE APPLICATION LAYER
`
`CHAP_ 7
`
`Relative names have to be interpreted in some context to uniquely determine their
`true meaning.
`In both cases, a named domain refers to a specific node in the tree
`and all the nodes under it.
`
`Domain names are case insensitive, so edu, Edit, and EDU mean the same
`thing. Component names can be up to 63 characters long, and full path names
`must not exceed 255 characters.
`
`In principle, domains can be inserted into the tree in two different ways. F01-
`example, cs.yale.edu could equally well be listed under the us country domain as
`cs.yczle.ct.us.
`In practice, however, most organizations in the United States are
`under a generic domain, and most outside the United States are under the domain
`of their country. There is no rule against registering under two top—level domains,
`but few organizations except multinationals do it (e. g., sony.c0m and s0ny.nl).
`Each domain controls how it allocates the domains under it. For example,
`Japan has domains ac.jp and c0.jp that mirror edu and com. The Netherlands does
`not make this distinction and puts all organizations directly under nl. Thus, an
`three of the following are university computer science departments:
`
`1.
`
`cs.yale.edu (Yale University, in the United States)
`
`2. cs.vu.nl (Vrije Universiteit, in The Netherlands)
`
`3. cs.kei0.ac.jp (Keio University, in Japan)
`
`To create a new domain, permission is required of the domain in which it will
`be included. For example, if a VLSI group is started at Yale and wants to be
`known as vlsi.cs.yale.edu,
`it has to get permission from whoever manages
`cs.yale.edu. Similarly,
`if a new university is chartered, say,
`the University of
`Northern South Dakota, it must ask the manager of the edu domain to assign it
`Lmsd.edu.
`In this way, name conflicts are avoided and each domain can keep
`track of all its subdomains. Once a new domain has been created and registered,
`it can create subdomains, such as cs.Lmsd.edu, without getting permission from
`anybody higher up the tree.
`Naming follows organizational boundaries, not physical networks. For exam»
`ple, if the computer science and electrical engineering departments are located in
`the same building and share the same LAN, they can nevertheless have distinct
`domains. Similarly, even if computer science is split over Babbage Hall and Tur-
`ing Hall, the hosts in both buildings will normally belong to the same domain.
`
`7.1.2 Resource Records
`
`Every domain, whether it is a single host or a top—level domain, can have a set
`of resource records associated with it. For a single host, the most common re-
`source record is just its IP address, but many other kinds of resource records alS0
`exist. When a resolver gives a domain name to DNS, what it gets back are the