INTRODUCTION TO COMPUTER NETWORKS

INTRODUCTION TO COMPUTER NETWORKS

1.2.1 Local Area Networks

ocal 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 inadvance.

Knowing this bound makes it possible to use certain kinds of designs that would not otherwise be

possible. It also simplifies 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 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 10 Gbps. 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.

Figure 1-7. Two broadcast networks. (a) Bus. (b) Ring.

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. Typically, 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 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 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.

1.2.2 Metropolitan Area Networks

A metropolitan area network, or MAN, covers a city. The best-known example of a MAN is the cable television

network available in many cities. This system grew from earlier community antenna systems used in areas with

poor over-the-air television reception. In these early systems, a large antenna was placed on top of a nearby hill

and signal was then piped to the subscribers’ houses.

At first, these were locally-designed, ad hoc systems. Then companies began jumping into the business, getting

contracts from city governments to wire up an entire city. The next step was television programming and even

entire channels designed for cable only. Often these channels were highly specialized, such as all news, all

sports, all cooking, all gardening, and so on. But from their inception until the late 1990s, they were intended for

television reception only.

Starting when the Internet attracted a mass audience, the cable TV network operators began to realize that with

some changes to the system, they could provide two-way Internet service in unused parts of the spectrum. At

that point, the cable TV system began to morph from a way to distribute television to a metropolitan area

network. To a first approximation, a MAN might look something like the system shown in Fig. 1-8. In this figure

we see both television signals and Internet being fed into the centralized head end for subsequent distribution to

people’s homes. We will come back to this subject in detail in Chap. 2.

Figure 1-8. A metropolitan area network based on cable TV.

Cable television is not the only MAN. Recent developments in high-speed wireless Internet access resulted in

another MAN, which has been standardized as IEEE 802.16. We will look at this area in Chap. 2.

1.2.3 Wide Area Networks

A wide area network, or WAN, spans a large geographical area, often a country or continent. It contains a

collection of machines intended for running user (i.e., application) programs. We will follow traditional usage and

call these machines hosts. The hosts are connected by a communication subnet, or just subnet for short. The

hosts are owned by the customers (e.g., people’s personal computers), whereas the communication subnet is

typically owned and operated by a telephone company or Internet service provider. The job of the subnet is to

carry messages from host to host, just as the telephone system carries words from speaker to listener.

Separation of the pure communication aspects of the network (the subnet) from the application aspects (the

hosts), greatly simplifies the complete network design.

In most wide area networks, the subnet consists of two distinct components: transmission lines and switching

elements. Transmission lines move bits between machines. They can be made of copper wire, optical fiber, or

even radio links. Switching elements are specialized computers that connect three or more transmission lines.

When data arrive on an incoming line, the switching element must choose an outgoing line on which to forward

them. These switching computers have been called by various names in the past; the name router is now most

commonly used. Unfortunately, some people pronounce it ”rooter” and others have it rhyme with ”doubter.”

Determining the correct pronunciation will be left as an exercise for the reader. (Note: the perceived correct

answer may depend on where you live.)

In this model, shown in Fig. 1-9, each host is frequently connected to a LAN on which a router is present,

although in some cases a host can be connected directly to a router. The collection of communication lines and

routers (but not the hosts) form the subnet.

Figure 1-9. Relation between hosts on LANs and the subnet.

A short comment about the term ”subnet” is in order here. Originally, its only meaning was the collection of

routers and communication lines that moved packets from the source host to the destination host. However,

some years later, it also acquired a second meaning in conjunction with network addressing (which we will

discuss in Chap. 5). Unfortunately, no widely-used alternative exists for its initial meaning, so with some

hesitation we will use it in both senses. From the context, it will always be clear which is meant.

In most WANs, the network contains numerous transmission lines, each one connecting a pair of routers. If two

routers that do not share a transmission line wish to communicate, they must do this indirectly, via other routers.

When a packet is sent from one router to another via one or more intermediate routers, the packet is received at

each intermediate router in its entirety, stored there until the required output line is free, and then forwarded. A

subnet organized according to this principle is called a store-and-forward or packet-switched subnet. Nearly all

wide area networks (except those using satellites) have store-and-forward subnets. When the packets are small

and all the same size, they are often called cells.

The principle of a packet-switched WAN is so important that it is worth devoting a few more words to it.

Generally, when a process on some host has a message to be sent to a process on some other host, the

sending host first cuts the message into packets, each one bearing its number in the sequence. These packets

are then injected into the network one at a time in quick succession. The packets are transported individually

over the network and deposited at the receiving host, where they are reassembled into the original message and

delivered to the receiving process. A stream of packets resulting from some initial message is illustrated in Fig.

1-10.

Figure 1-10. A stream of packets from sender to receiver.

In this figure, all the packets follow the route ACE, rather than ABDE or ACDE. In some networks all packets

from a given message must follow the same route; in others each packet is routed separately. Of course, if ACE

is the best route, all packets may be sent along it, even if each packet is individually routed.

Routing decisions are made locally. When a packet arrives at router A,itis up to A to decide if this packet should

be sent on the line to B or the line to C. How A makes that decision is called the routing algorithm. Many of them

exist. We will study some of them in detail in Chap. 5.

Not all WANs are packet switched. A second possibility for a WAN is a satellite system. Each router has an

antenna through which it can send and receive. All routers can hear the output from the satellite, and in some

cases they can also hear the upward transmissions of their fellow routers to the satellite as well. Sometimes the

routers are connected to a substantial point-to-point subnet, with only some of them having a satellite antenna.

Satellite networks are inherently broadcast and are most useful when the broadcast property is important.

1.1.2 Home Applications

In 1977, Ken Olsen was president of the Digital Equipment Corporation, then the number two computer vendor

in the world (after IBM). When asked why Digital was not going after the personal computer market in a big way,

he said: ”There is no reason for any individual to have a computer in his home.” History showed otherwise and

Digital no longer exists. Why do people buy computers for home use? Initially, for word processing and games,

but in recent years that picture has changed radically. Probably the biggest reason now is for Internet access.

Some of the more popular uses of the Internet for home users are as follows:

1. Access to remote information.

2. Person-to-person communication.

3. Interactive entertainment.

4. Electronic commerce.

Access to remote information comes in many forms. It can be surfing the World Wide Web for information or just

for fun. Information available includes the arts, business, cooking, government, health, history, hobbies,

recreation, science, sports, travel, and many others. Fun comes in too many ways to mention, plus some ways

that are better left unmentioned.

Many newspapers have gone on-line and can be personalized. For example, it is sometimes possible to tell a

newspaper that you want everything about corrupt politicians, big fires, scandals involving celebrities, and

epidemics, but no football, thank you. Sometimes it is even possible to have the selected articles downloaded to

your hard disk while you sleep or printed on your printer just before breakfast. As this trend continues, it will

cause massive unemployment among 12-year-old paperboys, but newspapers like it because distribution has

always been the weakest link in the whole production chain.

The next step beyond newspapers (plus magazines and scientific journals) is the on-line digital library. Many

professional organizations, such as the ACM (www.acm.org) and the IEEE Computer Society

(www.computer.org), already have many journals and conference proceedings on-line. Other groups are

following rapidly. Depending on the cost, size, and weight of book-sized notebook computers, printed books may

become obsolete. Skeptics should take note of the effect the printing press had on the medieval illuminated

manuscript.

All of the above applications involve interactions between a person and a remote database full of information.

The second broad category of network use is person-to-person communication, basically the 21st century’s

answer to the 19th century’s telephone. E-mail is already used on a daily basis by millions of people all over the

world and its use is growing rapidly. It already routinely contains audio and video as well as text and pictures.

Smell may take a while.

Any teenager worth his or her salt is addicted to instant messaging. This facility, derived from the UNIX talk

program in use since around 1970, allows two people to type messages at each other in real time. A multiperson

version of this idea is the chat room, in which a group of people can type messages for all to see.

Worldwide newsgroups, with discussions on every conceivable topic, are already commonplace among a select

group of people, and this phenomenon will grow to 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. Unlike chat rooms, newsgroups are not real time and messages are saved so that

when someone comes back from vacation, all messages that have been posted in the meanwhile are patiently

waiting for reading.

Another type of person-to-person communication often goes by the name of peer-to-peer communication, to

distinguish it from the client-server model (Parameswaran et al., 2001). In this form, individuals who form a loose

group can communicate with others in the group, as shown in Fig. 1-3. Every person can, in principle,

communicate with one or more other people; there is no fixed division into clients and servers.

Figure 1-3. In a peer-to-peer system there are no fixed clients and servers.

Peer-to-peer communication really hit the big time around 2000 with a service called Napster, which at its peak

had over 50 million music fans swapping music, in what was probably the biggest copyright infringement in all of

recorded history (Lam and Tan, 2001; and Macedonia, 2000). The idea was fairly simple. Members registered

the music they had on their hard disks in a central database maintained on the Napster server. If a member

wanted a song, he checked the database to see who had it and went directly there to get it. By not actually

keeping any music on its machines, Napster argued that it was not infringing anyone’s copyright. The courts did

not agree and shut it down.

However, the next generation of peer-to-peer systems eliminates the central database by having each user

maintain his own database locally, as well as providing a list of other nearby people who are members of the

system. A new user can then go to any existing member to see what he has and get a list of other members to

inspect for more music and more names. This lookup process can be repeated indefinitely to build up a large

local database of what is out there. It is an activity that would get tedious for people but is one at which

computers excel.

Legal applications for peer-to-peer communication also exist. For example, fans sharing public domain music or

sample tracks that new bands have released for publicity purposes, families sharing photos, movies, and

genealogical information, and teenagers playing multiperson on-line games. In fact, one of the most popular

Internet applications of all, e-mail, is inherently peer-to-peer. This form of communication is expected to grow

considerably in the future.

Electronic crime is not restricted to copyright law. Another hot area is electronic gambling. Computers have been

simulating things for decades. Why not simulate slot machines, roulette wheels, blackjack dealers, and more

gambling equipment? Well, because it is illegal in a lot of places. The trouble is, gambling is legal in a lot of other

places (England, for example) and casino owners there have grasped the potential for Internet gambling. What

happens if the gambler and the casino are in different countries, with conflicting laws? Good question.

Other communication-oriented applications include using the Internet to carry telephone calls, video phone, and

Internet radio, three rapidly growing areas. Another application is telelearning, meaning attending 8 A.M. classes

without the inconvenience of having to get out of bed first. In the long run, the use of networks to enhance

human-to-human communication may prove more important than any of the others.

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

television 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 simulation 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 games are

played with goggles and three-dimensional real-time, photographic-quality moving images, we have a kind of

worldwide shared virtual reality.

Our fourth category is electronic commerce in the broadest sense of the term. Home shopping is already popular

and enables users 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. After the

customer buys a product electronically but cannot figure out how to use it, on-line technical support may be

consulted.

Another area in which e-commerce is already happening is access to financial institutions. Many people already

pay their bills, manage their bank accounts, and handle their investments electronically. This will surely grow as

networks become more secure.

One area that virtually nobody foresaw is electronic flea markets (e-flea?). On-line auctions of second-hand

goods have become a massive industry. Unlike traditional e-commerce, which follows the client-server model,

on-line auctions are more of a peer-to-peer system, sort of consumer-to-consumer. Some of these forms of ecommerce

have acquired cute little tags based on the fact that ”to” and ”2” are pronounced the same. The most

popular ones are listed in Fig. 1-4.

Figure 1-4. Some forms of e-commerce.

No doubt the range of uses of computer networks will grow rapidly in the future, and probably in ways no one

can now foresee. After all, how many people in 1990 predicted that teenagers tediously typing short text

messages on mobile phones while riding buses would be an immense money maker for telephone companies in

10 years? But short message service is very profitable.

Computer networks may become hugely important to people who are geographically challenged, giving them the

same access to services as people living in the middle of a big city. Telelearning may radically affect education;

universities may go national or international. Telemedicine is only now starting to catch on (e.g., remote patient

monitoring) but may become much more important. But the killer application may be something mundane, like

using the webcam in your refrigerator to see if you have to buy milk on the way home from work.

1.1.3 Mobile Users

Mobile computers, such as notebook computers and personal digital assistants (PDAs), are one of the fastestgrowing

segments of the computer industry. Many owners of these computers have desktop machines back at

the office and want to be connected to their home base even when away from home or en route. Since having a

wired connection is impossible in cars and airplanes, there is a lot of interest in wireless networks. In this section

we will briefly look at some of the uses of wireless networks.

Why would anyone want one? A common reason is the portable office. People on the road often want to use

their portable electronic equipment to send and receive telephone calls, faxes, and electronic mail, surf the Web,

access remote files, and log on to remote machines. And they want to do this from anywhere on land, sea, or air.

For example, at computer conferences these days, the organizers often set up a wireless network in the

conference area. Anyone with a notebook computer and a wireless modem can just turn the computer on and be

connected to the Internet, as though the computer were plugged into a wired network. Similarly, some

universities have installed wireless networks on campus so students can sit under the trees and consult the

library’s card catalog or read their e-mail.

Wireless networks are of great value to fleets of trucks, taxis, delivery vehicles, and repairpersons for keeping in

contact with home. For example, in many cities, taxi drivers are independent businessmen, rather than being

employees of a taxi company. In some of these cities, the taxis have a display the driver can see. When a

customer calls up, a central dispatcher types in the pickup and destination points. This information is displayed

on the drivers’ displays and a beep sounds. The first driver to hit a button on the display gets the call.

Wireless networks are also important to the military. If you have to be able to fight a war anywhere on earth on

short notice, counting on using the local networking infrastructure is probably not a good idea. It is better to bring

your own.

Although wireless networking and mobile computing are often related, they are not identical, as Fig. 1-5 shows.

Here we see a distinction between fixed wireless and mobile wireless. Even notebook computers are sometimes

wired. For example, if a traveler plugs a notebook computer into the telephone jack in a hotel room, he has

mobility without a wireless network.

Figure 1-5. Combinations of wireless networks and mobile computing.

On the other hand, some wireless computers are not mobile. An important example is a company that owns an

older building lacking network cabling, and which wants to connect its computers. Installing a wireless network

may require little more than buying a small box with some electronics, unpacking it, and plugging it in. This

solution may be far cheaper than having workmen put in cable ducts to wire the building.

But of course, there are also the true mobile, wireless applications, ranging from the portable office to people

walking around a store with a PDA doing inventory. At many busy airports, car rental return clerks work in the

parking lot with wireless portable computers. They type in the license plate number of returning cars, and their

portable, which has a built-in printer, calls the main computer,

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 network architectures, the OSI reference model and the TCP/IP

reference model. Although the protocols associated with the OSI model are rarely used any more, the model

itself is actually quite general and still valid, and the features discussed at each layer are still very important. The

TCP/IP model has the opposite properties: the model itself is not of much use but the protocols are widely used.

For this reason we will look at both of them in detail. Also, sometimes you can learn more from failures than from

successes.

1.4.1 The OSI Reference Model

The OSI model (minus the physical medium) is shown in Fig. 1-20. This model is based on a proposal developed

by the International Standards Organization (ISO) as a first step toward international standardization of the

protocols used in the various layers (Day and Zimmermann, 1983). It was revised in 1995 (Day, 1995). 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 just call it the OSI

model for short.

Figure 1-20. The OSI reference model.

The OSI model has seven layers. The principles that were applied to arrive at the seven layers can be briefly

summarized as follows:

1. A layer should be created where a different abstraction is needed.

2. Each layer should perform a well-defined function.

3. 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.

Below we will discuss each layer of the model in turn, starting at the bottom layer. Note that the OSI model itself

is not a network architecture because it does not specify the exact services and protocols to be used in each

layer. It just tells what each layer should do. However, ISO has also produced standards for all the layers,

although these are not part of the reference model itself. Each one has been published as a separate

international standard.

The Physical Layer

The physical layer is concerned with transmitting raw bits over a communication channel. The design issues

have to do with making sure that when one side sends a 1 bit, it is received by the other side as a 1 bit, not as a

0 bit. Typical questions here are how many volts should be used to represent a 1 and how many for a 0, how

many nanoseconds a bit lasts, whether transmission may proceed simultaneously in both directions, how the

initial connection is established and how it is torn down when both sides are finished, and how many pins the

network connector has and what each pin is used for. The design issues here largely deal with mechanical,

electrical, and timing interfaces, and the physical transmission medium, which lies below the physical layer.

The Data Link Layer

The main task of the data link layer is to transform a raw transmission facility into a line that appears free of

undetected transmission errors to the network layer. It accomplishes this task by having the sender break up the

input data into data frames (typically a few hundred or a few thousand bytes) and transmit the frames

sequentially. If the service is reliable, the receiver confirms correct receipt of each frame by sending back an

acknowledgement frame.

Another issue that arises in the data link layer (and most of the higher layers as well) is how to keep a fast

transmitter from drowning a slow receiver in data. Some traffic regulation mechanism is often needed to let the

transmitter know how much buffer space the receiver has at the moment. Frequently, this flow regulation and the

error handling are integrated.

Broadcast networks have an additional issue in the data link layer: how to control access to the shared channel.

A special sublayer of the data link layer, the medium access control sublayer, deals with this problem.

The Network Layer

The network layer controls the operation of the subnet. A key design issue is determining how packets are

routed from source to destination. Routes can be based on static tables that are ”wired into” the network and

rarely changed. They can also be determined at the start of each conversation, for example, a terminal session

(e.g., a login to a remote machine). Finally, they can be highly dynamic, being determined anew for each packet,

to reflect the current network load.

If too many packets are present in the subnet at the same time, they will get in one another’s way, forming

bottlenecks. The control of such congestion also belongs to the network layer. More generally, the quality of

service provided (delay, transit time, jitter, etc.) is also a network layer issue.

When a packet has to travel from one network to another to get to its destination, many problems can arise. The

addressing used by the second network may be different from the first one. The second one may not accept the

packet at all because it is too large. The protocols may differ, and so on. It is up to the network layer to overcome

all these problems to allow heterogeneous networks to be interconnected.

In broadcast networks, the routing problem is simple, so the network layer is often thin or even nonexistent.

The Transport Layer

The basic function of the transport layer is to accept data from above, split it up into smaller units if need be,

pass these to the network layer, and ensure that the pieces all arrive correctly at the other end. Furthermore, all

this must be done efficiently and in a way that isolates the upper layers from the inevitable changes in the

hardware technology.

The transport layer also determines what type of service to provide to the session layer, and, ultimately, to the

users of the network. The most popular type of transport connection is an error-free point-to-point channel that

delivers messages or bytes in the order in which they were sent. However, other possible kinds of transport

service are the transporting of isolated messages, with no guarantee about the order of delivery, and the

broadcasting of messages to multiple destinations. The type of service is determined when the connection is

established. (As an aside, an error-free channel is impossible to achieve; what people really mean by this term is

that the error rate is low enough to ignore in practice.)

The transport layer is a true end-to-end layer, all the way from the source to the destination. In other words, a

program on the source machine carries on a conversation with a similar program on the destination machine,

using the message headers and control messages. In the lower layers, the protocols are between each machine

and its immediate neighbors, and not between the ultimate source and destination machines, which may be

separated by many routers. The difference between layers 1 through 3, which are chained, and layers 4 through

7, which are end-to-end, is illustrated in Fig. 1-20.

The Session Layer

The session layer allows users on different machines to establish sessions between them. Sessions offer

various services, including dialog control (keeping track of whose turn it is to transmit), token management

(preventing two parties from attempting the same critical operation at the same time), and synchronization

(checkpointing long transmissions to allow them to continue from where they were after a crash).

The Presentation Layer

Unlike lower layers, which are mostly concerned with moving bits around, the presentation layer is concerned

with the syntax and semantics of the information transmitted. In order to make it possible for computers with

different data representations to communicate, the data structures to be exchanged can be defined in an

abstract way, along with a standard encoding to be used ”on the wire.” The presentation layer manages these

abstract data structures and allows higher-level data structures (e.g., banking records), to be defined and

exchanged.

The Application Layer

The application layer contains a variety of protocols that are commonly needed by users. One widely-used

application protocol is HTTP (HyperText Transfer Protocol), which is the basis for the World Wide Web. When a

browser wants a Web page, it sends the name of the page it wants to the server using HTTP. The server then

sends the page back. Other application protocols are used for file transfer, electronic mail, and network news.

1.4.2 The TCP/IP Reference Model

Let us now turn from the OSI reference model to the reference model used in the grandparent of all wide area

computer networks, the ARPANET, and its successor, the worldwide Internet. Although we will give a brief

history of the ARPANET later, it is useful to mention a few key aspects of it now. The ARPANET was a research

network sponsored by the DoD (U.S. Department of Defense). It eventually connected hundreds of universities

and government installations, using leased telephone lines. When satellite and radio networks were added later,

the existing protocols had trouble interworking with them, so a new reference architecture was needed. Thus,

the ability to connect multiple networks in a seamless way was one of the major design goals from the very

beginning. This architecture later became known as the TCP/IP Reference Model, after its two primary protocols.

It was first defined in (Cerf and Kahn, 1974). A later perspective is given in (Leiner et al., 1985). The design

philosophy behind the model is discussed in (Clark, 1988).

Given the DoD’s worry that some of its precious hosts, routers, and internetwork gateways might get blown to

pieces at a moment’s notice, another major goal was that the network be able to survive loss of subnet

hardware, with existing conversations not being broken off. In other words, DoD wanted connections to 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 applications with divergent requirements were envisioned, ranging from transferring files to realtime

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 destination (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 country. Probably the letters will travel through one or more international mail gateways 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.

Figure 1-21. The TCP/IP reference model.

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 destination 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.

The second protocol in this layer, UDP (User Datagram Protocol), is an unreliable, connectionless protocol for

applications that do not want TCP’s sequencing 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.

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 them was perceived, so they were

not included. Experience with the OSI model has proven this view correct: they are of little use to most

applications.

On top of the transport layer is the application layer. It contains all the higher-level protocols. The early ones

included virtual terminal (TELNET), file transfer (FTP), and electronic mail (SMTP), as shown in Fig. 1-22. The

virtual 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 System (DNS) for mapping host names

onto their network addresses, NNTP, the protocol 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 differences. In this section we will focus

on the key differences between the two reference models. It is important to note that we are comparing the

reference models here, not the corresponding protocol stacks. The protocols themselves will be discussed later.

For an entire book comparing and contrasting TCP/IP and OSI, see (Piscitello and Chapin, 1993).

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.

A layer’s interface tells the processes above it how to access it. It specifies what the parameters are and what

results to expect. It, too, says nothing about how the layer works inside.

Finally, the peer protocols used in a layer are the layer’s own business. It can use any protocols it wants to, as

long as it gets the job done (i.e., provides the offered services). It can also change them at will without affecting

software in higher layers.

These ideas fit very nicely with modern ideas about object-oriented programming. An object, like a layer, has a

set of methods (operations) that processes outside the object can invoke. The semantics of these methods

define the set of services that the object offers. The methods’ parameters and results form the object’s interface.

The code internal to the object is its protocol and is not visible or of any concern outside the object.

The TCP/IP model did not originally clearly distinguish between service, interface, and protocol, although people

have tried to retrofit it after the fact to make it more OSI-like. For example, the only real services offered by the

internet layer are SEND IP PACKET and RECEIVE IP PACKET.

As a consequence, the protocols in the OSI model are better hidden than in the TCP/IP model and can be

replaced relatively easily as the technology changes. Being able to make such changes is one of the main

purposes of having layered protocols in the first place.

The OSI reference model was devised before the corresponding protocols were invented. This ordering means

that the model was not biased toward one particular set of protocols, a fact that made it quite general. The

downside of this ordering is that the designers did not have much experience with the subject and did not have a

good idea of which functionality to put in which layer.

For example, the data link layer originally dealt only with point-to-point networks. When broadcast networks

came around, a new sublayer had to be hacked into the model. When people started to build real networks using

the OSI model and existing protocols, it was discovered that these networks did not match the required service

specifications (wonder of wonders), so convergence sublayers had to be grafted onto the model to provide a

place for papering over the differences. Finally, the committee originally expected that each country would have

one network, run by the government and using the OSI protocols, so no thought was given to internetworking.

To make a long story short, things did not turn out that way.

With TCP/IP the reverse was true: the protocols came first, and the model was really just a description of the

existing protocols. There was no problem with the protocols fitting the model. They fit perfectly. The only trouble

was that the model did not fit any other protocol stacks. Consequently, it was not especially useful for describing

other, non-TCP/IP networks.

Turning from philosophical matters to more specific ones, an obvious difference between the two models is the

number of layers: the OSI model has seven layers and the TCP/IP has four layers. Both have (inter)network,

transport, and application layers, but the other layers are different.

Another difference is in the area of connectionless versus connection-oriented communication. The OSI model

supports both connectionless and connection-oriented communication in the network layer, but only connectionoriented

communication in the transport layer, where it counts (because the transport service is visible to the

users). The TCP/IP model has only one mode in the network layer (connectionless) but supports both modes in

the transport layer, giving the users a choice. This choice is especially important for simple request-response

protocols.

1.5 Example Networks

The subject of computer networking covers many different kinds of networks, large and small, well known and

less well known. They have different goals, scales, and technologies. In the following sections, we will look at

some examples, to get an idea of the variety one finds in the area of computer networking.

We will start with the Internet, probably the best known network, and look at its history, evolution, and

technology. Then we will consider ATM, which is often used within the core of large (telephone) networks.

Technically, it is quite different from the Internet, contrasting nicely with it. Next we will introduce Ethernet, the

dominant local area network. Finally, we will look at IEEE 802.11, the standard for wireless LANs.

1.5.1 The Internet

The Internet is not a network at all, but a vast collection of different networks that use certain common protocols

and provide certain common services. It is an unusual system in that it was not planned by anyone and is not

controlled by anyone. To better understand it, let us start from the beginning and see how it has developed and

why. For a wonderful history of the Internet, John Naughton’s (2000) book is highly recommended. It is one of

those rare books that is not only fun to read, but also has 20 pages of ibid.’s and op. cit.’s for the serious

historian. Some of the material below is based on this book.

Of course, countless technical books have been written about the Internet and its protocols as well. For more

information, see, for example, (Maufer, 1999).

The ARPANET

The story begins in the late 1950s. At the height of the Cold War, the DoD wanted a command-and-control

network that could survive a nuclear war. At that time, all military communications used the public telephone

network, which was considered vulnerable. The reason for this belief can be gleaned from Fig. 1-25(a). Here the

black dots represent telephone switching offices, each of which was connected to thousands of telephones.

These switching offices were, in turn, connected to higher-level switching offices (toll offices), to form a national

hierarchy with only a small amount of redundancy. The vulnerability of the system was that the destruction of a

few key toll offices could fragment the system into many isolated islands.

Figure 1-25. (a) Structure of the telephone system. (b) Baran’s proposed distributed switching system.

Around 1960, the DoD awarded a contract to the RAND Corporation to find a solution. One of its employees,

Paul Baran, came up with the highly distributed and fault-tolerant design of Fig. 1-25(b). Since the paths

between any two switching offices were now much longer than analog signals could travel without distortion,

Baran proposed using digital packet-switching technology throughout the system. Baran wrote several reports

for the DoD describing his ideas in detail. Officials at the Pentagon liked the concept and asked AT&T, then the

U.S. national telephone monopoly, to build a prototype. AT&T dismissed Baran’s ideas out of hand. The biggest

and richest corporation in the world was not about to allow some young whippersnapper tell it how to build a

telephone system. They said Baran’s network could not be built and the idea was killed.

Several years went by and still the DoD did not have a better command-and-control system. To understand what

happened next, we have to go back to October 1957, when the Soviet Union beat the U.S. into space with the

launch of the first artificial satellite, Sputnik. When President Eisenhower tried to find out who was asleep at the

switch, he was appalled to find the Army, Navy, and Air Force squabbling over the Pentagon’s research budget.

His immediate response was to create a single defense research organization, ARPA, the Advanced Research

Projects Agency. ARPA had no scientists or laboratories; in fact, it had nothing more than an office and a small

(by Pentagon standards) budget. It did its work by issuing grants and contracts to universities and companies

whose ideas looked promising to it.

For the first few years, ARPA tried to figure out what its mission should be, but in 1967, the attention of ARPA’s

then director, Larry Roberts, turned to networking. He contacted various experts to decide what to do. One of

them, Wesley Clark, suggested building a packet-switched subnet, giving each host its own router, as illustrated

in Fig. 1-10.

After some initial skepticism, Roberts bought the idea and presented a somewhat vague paper about it at the

ACM SIGOPS Symposium on Operating System Principles held in Gatlinburg, Tennessee in late 1967 (Roberts,

1967). Much to Roberts’ surprise, another paper at the conference described a similar system that had not only

been designed but actually implemented under the direction of Donald Davies at the National Physical

Laboratory in England. The NPL system was not a national system (it just connected several computers on the

NPL campus), but it demonstrated that packet switching could be made to work. Furthermore, it cited Baran’s

now discarded earlier work. Roberts came away from Gatlinburg determined to build what later became known

as the ARPANET.

The subnet would consist of minicomputers called IMPs (Interface Message Processors) connected by 56-kbps

transmission lines. For high reliability, each IMP would be connected to at least two other IMPs. The subnet was

to be a datagram subnet, so if some lines and IMPs were destroyed, messages could be automatically rerouted

along alternative paths.

Each node of the network was to consist of an IMP and a host, in the same room, connected by a short wire. A

host could send messages of up to 8063 bits to its IMP, which would then break these up into packets of at most

1008 bits and forward them independently toward the destination. Each packet was received in its entirety

before being forwarded, so the subnet was the first electronic store-and-forward packet-switching network.

ARPA then put out a tender for building the subnet. Twelve companies bid for it. After evaluating all the

proposals, ARPA selected BBN, a consulting firm in Cambridge, Massachusetts, and in December 1968,

awarded it a contract to build the subnet and write the subnet software. BBN chose to use specially modified

Honeywell DDP-316 minicomputers with 12K 16-bit words of core memory as the IMPs. The IMPs did not have

disks, since moving parts were considered unreliable. The IMPs were interconnected by 56-kbps lines leased

from telephone companies. Although 56 kbps is now the choice of teenagers who cannot afford ADSL or cable,

it was then the best money could buy.

The software was split into two parts: subnet and host. The subnet software consisted of the IMP end of the

host-IMP connection, the IMP-IMP protocol, and a source IMP to destination IMP protocol designed to improve

reliability. The original ARPANET design is shown in Fig. 1-26.

Figure 1-26. The original ARPANET design.

Outside the subnet, software was also needed, namely, the host end of the host-IMP connection, the host-host

protocol, and the application software. It soon became clear that BBN felt that when it had accepted a message

on a host-IMP wire and placed it on the host-IMP wire at the destination, its job was done.

Roberts had a problem: the hosts needed software too. To deal with it, he convened a meeting of network

researchers, mostly graduate students, at Snowbird, Utah, in the summer of 1969. The graduate students

expected some network expert to explain the grand design of the network and its software to them and then to

assign each of them the job of writing part of it. They were astounded when there was no network expert and no

grand design. They had to figure out what to do on their own.

Nevertheless, somehow an experimental network went on the air in December 1969 with four nodes: at UCLA,

UCSB, SRI, and the University of Utah. These four were chosen because all had a large number of ARPA

contracts, and all had different and completely incompatible host computers (just to make it more fun). The

network grew quickly as more IMPs were delivered and installed; it soon spanned the United States. Figure 1-27

shows how rapidly the ARPANET grew in the first 3 years.

Figure 1-27. Growth of the ARPANET. (a) December 1969. (b) July 1970. (c) March 1971. (d) April 1972. (e)

September 1972.

In addition to helping the fledgling ARPANET grow, ARPA also funded research on the use of satellite networks

and mobile packet radio networks. In one now famous demonstration, a truck driving around in California used

the packet radio network to send messages to SRI, which were then forwarded over the ARPANET to the East

Coast, where they were shipped to University College in London over the satellite network. This allowed a

researcher in the truck to use a computer in London while driving around in California.

This experiment also demonstrated that the existing ARPANET protocols were not suitable for running over

multiple networks. This observation led to more research on protocols, culminating with the invention of the

TCP/IP model and protocols (Cerf and Kahn, 1974). TCP/IP was specifically designed to handle communication

over internetworks, something becoming increasingly important as more and more networks were being hooked

up to the ARPANET.

To encourage adoption of these new protocols, ARPA awarded several contracts to BBN and the University of

California at Berkeley to integrate them into Berkeley UNIX. Researchers at Berkeley developed a convenient

program interface to the network (sockets) and wrote many application, utility, and management programs to

make networking easier.

The timing was perfect. Many universities had just acquired a second or third VAX computer and a LAN to

connect them, but they had no networking software. When 4.2BSD came along, with TCP/IP, sockets, and many

network utilities, the complete package was adopted immediately. Furthermore, with TCP/IP, it was easy for the

LANs to connect to the ARPANET, and many did.

During the 1980s, additional networks, especially LANs, were connected to the ARPANET. As the scale

increased, finding hosts became increasingly expensive, so DNS (Domain Name System) was created to

organize machines into domains and map host names onto IP addresses. Since then, DNS has become a

generalized, distributed database system for storing a variety of information related to naming. We will study it in

detail in Chap. 7.

NSFNET

By the late 1970s, NSF (the U.S. National Science Foundation) saw the enormous impact the ARPANET was

having on university research, allowing scientists across the country to share data and collaborate on research

projects. However, to get on the ARPANET, a university had to have a research contract with the DoD, which

many did not have. NSF’s response was to design a successor to the ARPANET that would be open to all

university research groups. To have something concrete to start with, NSF decided to build a backbone network

to connect its six supercomputer centers, in San Diego, Boulder, Champaign, Pittsburgh, Ithaca, and Princeton.

Each supercomputer was given a little brother, consisting of an LSI-11 microcomputer called a fuzzball. The

fuzzballs were connected with 56-kbps leased lines and formed the subnet, the same hardware technology as

the ARPANET used. The software technology was different however: the fuzzballs spoke TCP/IP right from the

start, making it the first TCP/IP WAN.

NSF also funded some (eventually about 20) regional networks that connected to the backbone to allow users at

thousands of universities, research labs, libraries, and museums to access any of the supercomputers and to

communicate with one another. The complete network, including the backbone and the regional networks, was

called NSFNET. It connected to the ARPANET through a link between an IMP and a fuzzball in the Carnegie-

Mellon machine room. The first NSFNET backbone is illustrated in Fig. 1-28.

Figure 1-28. The NSFNET backbone in 1988.

NSFNET was an instantaneous success and was overloaded from the word go. NSF immediately began

planning its successor and awarded a contract to the Michigan-based MERIT consortium to run it. Fiber optic

channels at 448 kbps were leased from MCI (since merged with WorldCom) to provide the version 2 backbone.

IBM PC-RTs were used as routers. This, too, was soon overwhelmed, and by 1990, the second backbone was

upgraded to 1.5 Mbps.

As growth continued, NSF realized that the government could not continue financing networking forever.

Furthermore, commercial organizations wanted to join but were forbidden by NSF’s charter from using networks

NSF paid for. Consequently, NSF encouraged MERIT, MCI, and IBM to form a nonprofit corporation, ANS

(Advanced Networks and Services), as the first step along the road to commercialization. In 1990, ANS took

over NSFNET and upgraded the 1.5-Mbps links to 45 Mbps to form ANSNET. This network operated for 5 years

and was then sold to America Online. But by then, various companies were offering commercial IP service and it

was clear the government should now get out of the networking business.

To ease the transition and make sure every regional network could communicate with every other regional

network, NSF awarded contracts to four different 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 backbone 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. Consequently, the backbone carriers were forced to compete for the

regional networks’ 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 commercially-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 research networks, often patterned on the

ARPANET and NSFNET. These included 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 exponential. Many regional networks joined up, and connections were made to networks in Canada,

Europe, and the Pacific.

Sometime in the mid-1980s, people began viewing the collection of networks as an internet, and later as the

Internet, although 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 compared 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 ability 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 provider 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 Internet for as long as they are

connected to the service provider’s router.

Traditionally (meaning 1970 to about 1990), the Internet and its predecessors had four main applications:

1. E-mail. The ability to compose, send, and receive electronic mail has been around since the early days

of the ARPANET and is enormously popular. Many people get dozens of messages a day and consider

it their primary way of interacting with the outside world, far outdistancing the telephone and snail mail.

E-mail programs are available on virtually every kind of computer these days.

2. News. Newsgroups are specialized forums in which users with a common interest can exchange

messages. Thousands of newsgroups exist, devoted to technical and nontechnical topics, including

computers, science, recreation, and politics. Each newsgroup has its own etiquette, style, and customs,

and woe betide anyone violating them.

3. Remote login. Using the telnet, rlogin, or ssh programs, users anywhere on the Internet can log on to

any other machine on which they have an account.

4. File transfer. Using the FTP program, users can copy files from one machine on the Internet to another.

Vast numbers of articles, databases, and other information are available this way.

Up until the early 1990s, the Internet was largely populated by academic, government, and industrial

researchers. One new application, the WWW (World Wide Web) changed all that and brought millions of new,

nonacademic users to the net. This application, invented by CERN physicist Tim Berners-Lee, did not change

any of the underlying facilities but made them easier to use. Together with the Mosaic browser, written by Marc

Andreessen at the National Center for Supercomputer Applications in Urbana, Illinois, the WWW made it

possible for a site to set up a number of pages of information containing text, pictures, sound, and even video,

with embedded links to other pages. By clicking on a link, the user is suddenly transported to the page pointed to

by that link. For example, many companies have a home page with entries pointing to other pages for product

information, price lists, sales, technical support, communication with employees, stockholder information, and

more.

Numerous other kinds of pages have come into existence in a very short time, including maps, stock market

tables, library card catalogs, recorded radio programs, and even a page pointing to the complete text of many

books whose copyrights have expired (Mark Twain, Charles Dickens, etc.). Many people also have personal

pages (home pages).

Much of this growth during the 1990s was fueled by companies called ISPs (Internet Service Providers). These

are companies that offer individual users at home the ability to call up one of their machines and connect to the

Internet, thus gaining access to e-mail, the WWW, and other Internet services. These companies signed up tens

of millions of new users a year during the late 1990s, completely changing the character of the network from an

academic and military playground to a public utility, much like the telephone system. The number of Internet

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. Consequently, 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.

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. 1-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 telco, the POP will probably be located in the telephone switching office where the telephone

wire from the client terminates. If the ISP is not the local telco, the POP may be a few switching offices down the

road.

The ISP’s regional network consists of interconnected routers in the various cities the ISP serves. If the packet is

destined for a host served directly by the ISP, the packet is delivered to the host. Otherwise, it is handed over to

the ISP’s backbone operator.

At the top of the food chain are the major backbone operators, companies like AT&T and Sprint. They operate

large international backbone networks, with thousands of routers connected by high-bandwidth fiber optics.

Large corporations and hosting services that run server farms (machines that can serve thousands of Web

pages per second) often connect directly to the backbone. Backbone operators encourage this direct connection

by renting space in what are called carrier hotels, basically equipment racks in the same room as the router to

allow short, fast connections between server farms and the backbone.

If a packet given to the backbone is destined for an ISP or company served by the backbone, it is sent to the

closest router and handed off there. However, many backbones, of varying sizes, exist in the world, so a packet

may have to go to a competing backbone. To allow packets to hop between backbones, all the major backbones

connect at the NAPs discussed earlier. Basically, a NAP is a room full of routers, at least one per backbone. A

LAN in the room connects all the routers, so packets can be forwarded from any backbone to any other

backbone. In addition to being interconnected at NAPs, the larger backbones have numerous direct connections

between their routers, a technique known as private peering. One of the many paradoxes of the Internet is that

ISPs who publicly compete with one another for customers often privately cooperate to do private peering (Metz,

2001).

This ends our quick tour of the Internet. We will have a great deal to say about the individual components and

their design, algorithms, and protocols in subsequent chapters. Also worth mentioning in passing is that some

companies have interconnected all their existing internal networks, often using the same technology as the

Internet. These intranets are typically accessible only within the company but otherwise work the same way as

the Internet.

1.5.2 Connection-Oriented Networks: X.25, Frame Relay, and ATM

Since the beginning of networking, a war has been going on between the people who support connectionless

(i.e., datagram) subnets and the people who support connection-oriented subnets. The main proponents of the

connectionless subnets come from the ARPANET/Internet community. Remember that DoD’s original desire in

funding and building the ARPANET was to have a network that would continue functioning even after multiple

direct hits by nuclear weapons wiped out numerous routers and transmission lines. Thus, fault tolerance was

high on their priority list; billing customers was not. This approach led to a connectionless design in which every

packet is routed independently of every other packet. As a consequence, if some routers go down during a

session, no harm is done as long as the system can reconfigure itself dynamically so that subsequent packets

can find some route to the destination, even if it is different from that which previous packets used.

The connection-oriented camp comes from the world of telephone companies. In the telephone system, a caller

must dial the called party’s number and wait for a connection before talking or sending data. This connection

setup establishes a route through the telephone system that is maintained until the call is terminated. All words

or packets follow the same route. If a line or switch on the path goes down, the call is aborted. This property is

precisely what the DoD did not like about it.

Why do the telephone companies like it then? There are two reasons:

1. Quality of service.

2. Billing.

By setting up a connection in advance, the subnet can reserve resources such as buffer space and router CPU

capacity. If an attempt is made to set up a call and insufficient resources are available, the call is rejected and

the caller gets a kind of busy signal. In this way, once a connection has been set up, the connection will get good

service. With a connectionless network, if too many packets arrive at the same router at the same moment, the

router will choke and probably lose packets. The sender will eventually notice this and resend them, but the

quality of service will be jerky and unsuitable for audio or video unless the network is very lightly loaded.

Needless to say, providing adequate audio quality is something telephone companies care about very much,

hence their preference for connections.

The second reason the telephone companies like connection-oriented service is that they are accustomed to

charging for connect time. When you make a long distance call (or even a local call outside North America) you

are charged by the minute. When networks came around, they just automatically gravitated toward a model in

which charging by the minute was easy to do. If you have to set up a connection before sending data, that is

when the billing clock starts running. If there is no connection, they cannot charge for it.

Ironically, maintaining billing records is very expensive. If a telephone company were to adopt a flat monthly rate

with unlimited calling and no billing or record keeping, it would probably save a huge amount of money, despite

the increased calling this policy would generate. Political, regulatory, and other factors weigh against doing this,

however. Interestingly enough, flat rate service exists in other sectors. For example, cable TV is billed at a flat

rate per month, no matter how many programs you watch. It could have been designed with pay-per-view as the

basic concept, but it was not, due in part to the expense of billing (and given the quality of most television, the

embarrassment factor cannot be totally discounted either). Also, many theme parks charge a daily admission fee

for unlimited 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 telephone 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 computer

first established a connection to the remote computer, that is, placed a telephone 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 networks operated for about a decade with mixed success.

In the 1980s, the X.25 networks were largely replaced by a new kind of network 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 modest 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

telecommunications problems by merging voice, data, cable television, telex, telegraph, carrier pigeon, tin cans

connected by strings, tom-toms, smoke signals, and everything else into a single integrated system that could do

everything for everyone. It did not happen. In large part, the problems were similar to those we described earlier

concerning OSI, that is, bad timing, technology, implementation, and politics. Having just beaten back the

telephone companies in round 1, many in the Internet community saw ATM as Internet versus the Telcos: the

Sequel. But it really was not, and this time around even diehard datagram fanatics were aware that the Internet’s

quality of service left a lot to be desired. To make a long story short, ATM was much more successful than OSI,

and it is now widely used deep within the telephone system, often for moving IP packets. Because it is now

mostly used by carriers for internal transport, users are often unaware of its existence, but it is definitely alive

and well.

ATM Virtual Circuits

Since ATM networks are connection-oriented, sending data requires first sending a packet to set up the

connection. As the setup packet wends its way through the subnet, all the routers on the path make an entry in

their internal tables noting the existence of the connection and reserving whatever resources are needed for it.

Connections are often called virtual circuits, in analogy with the physical circuits used within the telephone

system. Most ATM networks also support permanent virtual circuits, which are permanent connections between

two (distant) hosts. They are similar to leased lines in the telephone world. Each connection, temporary or

permanent, has a unique connection identifier. A virtual circuit is illustrated in Fig. 1-30.

Figure 1-30. A virtual circuit.

Once a connection has been established, either side can begin transmitting data. The basic idea behind ATM is

to transmit all information in small, fixed-size packets called cells. The cells are 53 bytes long, of which 5 bytes

are header and 48 bytes are payload, as shown in Fig. 1-31. Part of the header is the connection identifier, so

the sending and receiving hosts and all the intermediate routers can tell which cells belong to which connections.

This information allows each router to know how to route each incoming cell. Cell routing is done in hardware, at

high speed. In fact, the main argument for having fixed-size cells is that it is easy to build hardware routers to

handle short, fixed-length cells. Variable-length IP packets have to be routed by software, which is a slower

process. Another plus of ATM is that the hardware can be set up to copy one incoming cell to multiple output

lines, a property that is required for handling a television program that is being broadcast to many receivers.

Finally, small cells do not block any line for very long, which makes guaranteeing quality of service easier.

Figure 1-31. An ATM cell.

All cells follow the same route to the destination. Cell delivery is not guaranteed, but their order is. If cells 1 and 2

are sent in that order, then if both arrive, they will arrive in that order, never first 2 then 1. But either or both of

them can be lost along the way. It is up to higher protocol levels to recover from lost cells. Note that although this

guarantee is not perfect, it is better than what the Internet provides. There packets can not only be lost, but

delivered out of order as well. ATM, in contrast, guarantees never to deliver cells out of order.

ATM networks are organized like traditional WANs, with lines and switches (routers). The most common speeds

for ATM networks are 155 Mbps and 622 Mbps, although higher speeds are also supported. The 155-Mbps

speed was chosen because this is about what is needed to transmit high definition television. The exact choice

of 155.52 Mbps was made for compatibility with AT&T’s SONET transmission system, something we will study in

Chap. 2. The 622 Mbps speed was chosen so that four 155-Mbps channels could be sent over it.

The ATM Reference Model

ATM has its own reference model, different from the OSI model and also different from the TCP/IP model. This

model is shown in Fig. 1-32. It consists of three layers, the physical, ATM, and ATM adaptation layers, plus

whatever users want to put on top of that.

Figure 1-32. The ATM reference model.

The physical layer deals with the physical medium: voltages, bit timing, and various other issues. ATM does not

prescribe a particular set of rules but instead says that ATM cells can be sent on a wire or fiber by themselves,

but they can also be packaged inside the payload of other carrier systems. In other words, ATM has been

designed to be independent of the transmission medium.

The ATM layer deals with cells and cell transport. It defines the layout of a cell and tells what the header fields

mean. It also deals with establishment and release of virtual circuits. Congestion control is also located here.

Because most applications do not want to work directly with cells (although some may), a layer above the ATM

layer has been defined to allow users to send packets larger than a cell. The ATM interface segments these

packets, transmits the cells individually, and reassembles them at the other end. This layer is the AAL (ATM

Adaptation Layer).

Unlike the earlier two-dimensional reference models, the ATM model is defined as being three-dimensional, as

shown in Fig. 1-32. The user plane deals with data transport, flow control, error correction, and other user

functions. In contrast, the control plane is concerned with connection management. The layer and plane

management functions relate to resource management and interlayer coordination.

The physical and AAL layers are each divided into two sublayers, one at the bottom that does the work and a

convergence sublayer on top that provides the proper interface to the layer above it. The functions of the layers

and sublayers are given in Fig. 1-33.

Figure 1-33. The ATM layers and sublayers, and their functions..

The PMD (Physical Medium Dependent) sublayer interfaces to the actual cable. It moves the bits on and off and

handles the bit timing. For different carriers and cables, this layer will be different.

The other sublayer of the physical layer is the TC (Transmission Convergence) sublayer. When cells are

transmitted, the TC layer sends them as a string of bits to the PMD layer. Doing this is easy. At the other end,

the TC sublayer gets a pure incoming bit stream from the PMD sublayer. Its job is to convert this bit stream into

a cell stream for the ATM layer. It handles all the issues related to telling where cells begin and end in the bit

stream. In the ATM model, this functionality is in the physical layer. In the OSI model and in pretty much all other

networks, the job of framing, that is, turning a raw bit stream into a sequence of frames or cells, is the data link

layer’s task.

As we mentioned earlier, the ATM layer manages cells, including their generation and transport. Most of the

interesting aspects of ATM are located here. It is a mixture of the OSI data link and network layers; it is not split

into sublayers.

The AAL layer is split into a SAR (Segmentation And Reassembly) sublayer and a CS (Convergence Sublayer).

The lower sublayer breaks up packets into cells on the transmission side and puts them back together again at

the destination. The upper sublayer makes it possible to have ATM systems offer different kinds of services to

different applications (e.g., file transfer and video on demand have different requirements concerning error

handling, timing, etc.).

As it is probably mostly downhill for ATM from now on, we will not discuss it further in this book. Nevertheless,

since it has a substantial installed base, it will probably be around for at least a few more years. For more

information about ATM, see (Dobrowski and Grise, 2001; and Gadecki and Heckart, 1997).

1.5.3 Ethernet

Both the Internet and ATM were designed for wide area networking. However, many companies, universities,

and other organizations have large numbers of computers that must be connected. This need gave rise to the

local area network. In this section we will say a little bit about the most popular LAN, Ethernet.

The story starts out in pristine Hawaii in the early 1970s. In this case, ”pristine” can be interpreted as ”not having

a working telephone system.” While not being interrupted by the phone all day long makes life more pleasant for

vacationers, it did not make life more pleasant for researcher Norman Abramson and his colleagues at the

University of Hawaii who were trying to connect users on remote islands to the main computer in Honolulu.

Stringing their own cables under the Pacific Ocean was not in the cards, so they looked for a different solution.

The one they found was short-range radios. Each user terminal was equipped with a small radio having two

frequencies: upstream (to the central computer) and downstream (from the central computer). When the user

wanted to contact the computer, it just transmitted a packet containing the data in the upstream channel. If no

one else was transmitting at that instant, the packet probably got through and was acknowledged on the

downstream channel. If there was contention for the upstream channel, the terminal noticed the lack of

acknowledgement and tried again. Since there was only one sender on the downstream channel (the central

computer), there were never collisions there. This system, called ALOHANET, worked fairly well under

conditions of low traffic but bogged down badly when the upstream traffic was heavy.

About the same time, a student named Bob Metcalfe got his bachelor’s degree at M.I.T. and then moved up the

river to get his Ph.D. at Harvard. During his studies, he was exposed to Abramson’s work. He became so

interested in it that after graduating from Harvard, he decided to spend the summer in Hawaii working with

Abramson before starting work at Xerox PARC (Palo Alto Research Center). When he got to PARC, he saw that

the researchers there had designed and built what would later be called personal computers. But the machines

were isolated. Using his knowledge of Abramson’s work, he, together with his colleague David Boggs, designed

and implemented the first local area network (Metcalfe and Boggs, 1976).

They called the system Ethernet after the luminiferous ether, through which electromagnetic radiation was once

thought to propagate. (When the 19th century British physicist James Clerk Maxwell discovered that

electromagnetic radiation could be described by a wave equation, scientists assumed that space must be filled

with some ethereal medium in which the radiation was propagating. Only after the famous Michelson-Morley

experiment in 1887 did physicists discover that electromagnetic radiation could propagate in a vacuum.)

The transmission medium here was not a vacuum, but a thick coaxial cable (the ether) up to 2.5 km long (with

repeaters every 500 meters). Up to 256 machines could be attached to the system via transceivers screwed onto

the cable. A cable with multiple machines attached to it in parallel is called a multidrop cable. The system ran at

2.94 Mbps. A sketch of its architecture is given in Fig. 1-34. Ethernet had a major improvement over

ALOHANET: before transmitting, a computer first listened to the cable to see if someone else was already

transmitting. If so, the computer held back until the current transmission finished. Doing so avoided interfering

with existing transmissions, giving a much higher efficiency. ALOHANET did not work like this because it was

impossible for a terminal on one island to sense the transmission of a terminal on a distant island. With a single

cable, this problem does not exist.

Figure 1-34. Architecture of the original Ethernet..

Despite the computer listening before transmitting, a problem still arises: what happens if two or more computers

all wait until the current transmission completes and then all start at once? The solution is to have each

computer listen during its own transmission and if it detects interference, jam the ether to alert all senders. Then

back off and wait a random time before retrying. If a second collision happens, the random waiting time is

doubled, and so on, to spread out the competing transmissions and give one of them a chance to go first.

The Xerox Ethernet was so successful that DEC, Intel, and Xerox drew up a standard in 1978 for a 10-Mbps

Ethernet, called the DIX standard. With two minor changes, the DIX standard became the IEEE 802.3 standard

in 1983.

Unfortunately for Xerox, it already had a history of making seminal inventions (such as the personal computer)

and then failing to commercialize on them, a story told in Fumbling the Future (Smith and Alexander, 1988).

When Xerox showed little interest in doing anything with Ethernet other than helping standardize it, Metcalfe

formed his own company, 3Com, to sell Ethernet adapters for PCs. It has sold over 100 million of them.

Ethernet continued to develop and is still developing. New versions at 100 Mbps, 1000 Mbps, and still higher

have come out. Also the cabling has improved, and switching and other features have been added. We will

discuss Ethernet in detail in Chap. 4.

In passing, it is worth mentioning that Ethernet (IEEE 802.3) is not the only LAN standard. The committee also

standardized a token bus (802.4) and a token ring (802.5). The need for three more-or-less incompatible

standards has little to do with technology and everything to do with politics. At the time of standardization,

General Motors was pushing a LAN in which the topology was the same as Ethernet (a linear cable) but

computers took turns in transmitting by passing a short packet called a token from computer to computer. A

computer could only send if it possessed the token, thus avoiding collisions. General Motors announced that this

scheme was essential for manufacturing cars and was not prepared to budge from this position. This

announcement notwithstanding, 802.4 has basically vanished from sight.

Similarly, IBM had its own favorite: its proprietary token ring. The token was passed around the ring and

whichever computer held the token was allowed to transmit before putting the token back on the ring. Unlike

802.4, this scheme, standardized as 802.5, is still in use at some IBM sites, but virtually nowhere outside of IBM

sites. However, work is progressing on a gigabit version (802.5v), but it seems unlikely that it will ever catch up

with Ethernet. In short, there was a war between Ethernet, token bus, and token ring, and Ethernet won, mostly

because it was there first and the challengers were not as good.

1.5.4 Wireless LANs: 802.11

Almost as soon as notebook computers appeared, many people had a dream of walking into an office and

magically having their notebook computer be connected to the Internet. Consequently, various groups began

working on ways to accomplish this goal. The most practical approach is to equip both the office and the

notebook computers with short-range radio transmitters and receivers to allow them to communicate. This work

rapidly led to wireless LANs being marketed by a variety of companies.

The trouble was that no two of them were compatible. This proliferation of standards meant that a computer

equipped with a brand X radio would not work in a room equipped with a brand Y base station. Finally, the

industry decided that a wireless LAN standard might be a good idea, so the IEEE committee that standardized

the wired LANs was given the task of drawing up a wireless LAN standard. The standard it came up with was

named 802.11. A common slang name for it is WiFi. It is an important standard and deserves respect, so we will

call it by its proper name, 802.11.

The proposed standard had to work in two modes:

1. In the presence of a base station.

2. In the absence of a base station.

In the former case, all communication was to go through the base station, called an access point in 802.11

terminology. In the latter case, the computers would just send to one another directly. This mode is now

sometimes called ad hoc networking. A typical example is two or more people sitting down together in a room

not equipped with a wireless LAN and having their computers just communicate directly. The two modes are

illustrated in Fig. 1-35.

Figure 1-35. (a) Wireless networking with a base station. (b) Ad hoc networking.

The first decision was the easiest: what to call it. All the other LAN standards had numbers like 802.1, 802.2,

802.3, up to 802.10, so the wireless LAN standard was dubbed 802.11. The rest was harder.

In particular, some of the many challenges that had to be met were: finding a suitable frequency band that was

available, preferably worldwide; dealing with the fact that radio signals have a finite range; ensuring that users’

privacy was maintained; taking limited battery life into account; worrying about human safety (do radio waves

cause cancer?); understanding the implications of computer mobility; and finally, building a system with enough

bandwidth to be economically viable.

At the time the standardization process started (mid-1990s), Ethernet had already come to dominate local area

networking, so the committee decided to make 802.11 compatible with Ethernet above the data link layer. In

particular, it should be possible to send an IP packet over the wireless LAN the same way a wired computer sent

an IP packet over Ethernet. Nevertheless, in the physical and data link layers, several inherent differences with

Ethernet exist and had to be dealt with by the standard.

First, a computer on Ethernet always listens to the ether before transmitting. Only if the ether is idle does the

computer begin transmitting. With wireless LANs, that idea does not work so well. To see why, examine Fig. 1-

36. Suppose that computer A is transmitting to computer B, but the radio range of A’s transmitter is too short to

reach computer C. If C wants to transmit to B it can listen to the ether before starting, but the fact that it does not

hear anything does not mean that its transmission will succeed. The 802.11 standard had to solve this problem.

Figure 1-36. The range of a single radio may not cover the entire system.

The second problem that had to be solved is that a radio signal can be reflected off solid objects, so it may be

received multiple times (along multiple paths). This interference results in what is called multipath fading.

The third problem is that a great deal of software is not aware of mobility. For example, many word processors

have a list of printers that users can choose from to print a file. When the computer on which the word processor

runs is taken into a new environment, the built-in list of printers becomes invalid.

The fourth problem is that if a notebook computer is moved away from the ceiling-mounted base station it is

using and into the range of a different base station, some way of handing it off is needed. Although this problem

occurs with cellular telephones, it does not occur with Ethernet and needed to be solved. In particular, the

network envisioned consists of multiple cells, each with its own base station, but with the base stations

connected by Ethernet, as shown in Fig. 1-37. From the outside, the entire system should look like a single

Ethernet. The connection between the 802.11 system and the outside world is called a portal.

Figure 1-37. A multicell 802.11 network.

After some work, the committee came up with a standard in 1997 that addressed these and other concerns. The

wireless LAN it described ran at either 1 Mbps or 2 Mbps. Almost immediately, people complained that it was too

slow, so work began on faster standards. A split developed within the committee, resulting in two new standards

in 1999. The 802.11a standard uses a wider frequency band and runs at speeds up to 54 Mbps. The 802.11b

standard uses the same frequency band as 802.11, but uses a different modulation technique to achieve 11

Mbps. Some people see this as psychologically important since 11 Mbps is faster than the original wired

Ethernet. It is likely that the original 1-Mbps 802.11 will die off quickly, but it is not yet clear which of the new

standards will win out.

To make matters even more complicated than they already were, the 802 committee has come up with yet

another variant, 802.11g, which uses the modulation technique of 802.11a but the frequency band of 802.11b.

We will come back to 802.11 in detail in Chap. 4.

Binary Cipher

INTRODUCTION TO COMPUTER NETWORKS

Leave a ReplyCancel Reply

Add Binary Cipher to your Homescreen!

<img class="alignnone wp-image-505" src="/wp-content/uploads/2022/07/logo_nobg-1.png" alt="Binary Cipher" width="69" height="73" />Binary Cipher

Leave a ReplyCancel Reply

Add Binary Cipher to your Homescreen!

Binary Cipher