Network Protocols
`
`ANDREW S. TANENBAUM
`
`Wiskundig Seminormflc, I/‘rye Universiteit, Amsterdam, The Netherlands
`
`During the last ten years, many computer networks have been designed, ‘implemented,
`and put into service in the United States, Canada, Europe, Japan, and elsewhere. From
`the experience obtained with these networks, certain key design principles have begun to
`emerge, principles that can be used to design new computer networks in a more
`structured way than has traditionally been the case. Chief among these principles is the
`notion of structuring a network as a hierarchy of layers, each one built upon the previous
`one. This paper is a tutorial about such network hierarchies, using the Reference Model
`of Open Systems Interconnection developed by the International Organization for
`Standardization as a guide. Numerous examples are given to illustrate the principles.
`
`Key Words and Phrases: computer network, data communication, ISO OSI Reference
`Model. layered architecture, network. protocol
`
`CR Categories‘ 1.3, 4.9, 6.9
`
`INTRODUCTION
`
`Ten years ago, only a handful of computer
`networks existed, mostly experimental net-
`works built by research organizations. To-
`day dozens of national and international
`networks and innumerable local networks
`
`operate on a commercial basis around the
`clock. From the beginning, many networks
`were designed hierarchically, as a series of
`layers, each one building on the one below.
`At first, each network design team started
`out by choosing its own set of layers. How-
`ever, in the past few years, a consensus has
`begun to develop among network designers,
`a consensus embodied in the International
`
`Organization for Standard_ization’s Refer-
`ence Model of Open Systems Interconnec-
`tion (ISO OSI). In this paper we present an
`informal
`introduction to computer net-
`working using this model as a guide. A more
`thorough treatment of the ISO OSI model
`itself can be found in ZIMMSO.
`Before getting into the subject of network
`protocols, it is worth saying a few words
`
`about what we mean by a computer net-
`work. A computer network is a collection of
`computers, called hosts, that communicate
`with one another. The hosts may be large
`multiprograrnmed mainframes or small
`personal computers. Networks can be clas-
`sified as local! networks or long-haul net-
`works. The hosts on a local network are
`
`typically contained in a single building or
`campus and are connected by a high-band-
`width cable or other communication me-
`
`dium specifically designed for this purpose.
`Long-haul networks, in contrast, typically
`connect hosts in different cities using the
`public telephone network, an earth satel-
`lite, or both.
`Local networks are nearly always com-
`pletely owned by a single organization,
`whereas long-haul networks normally in-
`volve at least two organizations: the carrier,
`which operates the communication facility
`(telephone lines, microwave dishes, satel-
`lite, etc.}, and the users, who own the hosts.
`This division of labor into (1) the provider
`of the communication facility and (2) the
`
`Permission to copy without fee all or part of this material is granted provided that the copies are not made or
`distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its
`date appear, and notice is given that copying IS by permission of the Association for Computing Machinery. To
`copy otherwise, or to republish, requires a fee and/or specific permission.
`© 1981 ACM 0010-4892/81/1200-0453 $00 75
`
`Computing Surveys, Vol. 13, No. -1, December 1981
`
`EMC 1013
`
`EMC 1013
`
`

`
`454
`
`-
`
`Andrew S. Tanenbaum
`
`CONTENTS
`
`INTRODUCTION
`Protocols
`Overview of the ISO OS] Layers
`1. THE PHYSICAL LAYER
`1 I The Telephone System
`I 2 Cornrnumcataon Satellites
`1 3 Local Networks
`1.4 An Example Physical Layer Protocol X 21
`2 THE DATA LINK LAYER
`2 1 Stop-and-Walt Protocols
`2.2 Shdang—W:ndow Protocols
`2 3 An Example Data Link Layer Protocol HDLC
`24 Channel Allocation in Satellite Networks
`2 5 Channel Allocation in Local Networks
`3 THE NETWORK LAYER
`3 I Routing In Point-to-Point Networks
`3 2 Congestion Control in Po:.nt.—r.o-Pomt Networks
`3.3 An Example Network Layer Protocol X 25
`4 THE TRANSPOR"I‘ LAYER
`4 I The Transport Station
`4 2 Establishing and Closing Connections
`4 3 Flow Control and Buffering
`4 4 Connection Multlpiexlng
`5 THE SESSION LAYER
`6 THE PRESENTATION LAYER
`6.! Text Compression
`6 2 Encryption Protocols
`6 3 \I"artual—'I‘e1-rnmzial Protocols
`6 4 File Transfer Protocols
`7 SUMMARY
`ACKNOWLEDGMENTS
`REFERENCES
`
`_._.._—_j--_.:_
`
`users of the communication facility has im-
`portant ramifications for network architec-
`tures, as we shall see later.
`The communication facility in a long-
`haul network is called the (communication)
`subnet, and often consists of a collection of
`minicomputers variously called IMPS (in-
`terface message processors), nodes, or
`switches connected by high-bandwidth
`leased telephone lines or a satellite. Figure
`1 shows a network using telephone lines.
`Such a network is called a point-to~point or
`store-and forward network, as opposed to
`a broadcast network, such as a satellite
`network. The terms “host,” “IMP,” and
`“communication subnet” come from the
`
`U.S. Department of Defense's ARPANET,
`one of
`the first
`large-scale networks
`[MCQU77]. We use this terminology gener-
`
`Computing Surveys, Vol. 13, No 4, December 1981
`
`ically because no consensus on nomencla-
`ture exists.
`
`When the IMPs are connected by tele-
`phone lines, they are normally located on
`the carrier’s premises, with each IMP serv-
`icing multiple hosts. To save on long-dis-
`tance leased—1ine line charges, hosts and
`terminals are often funneled through re-
`mote concentrators. When the IMPs are
`
`connected by a satellite, the IMPs may be
`located on the customer's premises (e.g., on
`the roof). Local networks do not have
`IMPS; instead, each host has an interface
`card inserted into its backplane to control
`access to the network. This card is attached
`to the communication subnet, which is typ-
`ically just a cable.
`Although the ISO Reference Model can
`be used for both long-haul and local net-
`works, it was designed primarily with the
`former in mind. Accordingly, in this paper
`we also treat both kinds of networks, but
`we emphasize slightly the long-haul variety,
`since issues such as routing and congestion
`control play a more prominent role in long-
`haul networks than in local networks.
`In passing, we note that the subject of
`connecting distinct networks together is an
`increasingly important one, although it lies
`beyond the scope of this article. For an
`introduction to this subject see BoccS0 and
`Posr80.
`
`Protocols
`
`As mentioned above, networks are almost
`always organized as a hierarchy of layers.
`Each layer performs a small set of closely
`related functions. The ISO Reference
`Model has seven layers:
`
`(1) the physical layer,
`(2) the data link layer,
`(3) the network layer,
`(4) the transport layer,
`(5) the session layer,
`(6) the presentation layer,
`(7) the application layer,
`
`as shown in Figure 2. All layers are present
`on the hosts, but only layers 1, 2, and 3 are
`present on the IMPS.
`Each layer should be thought of as a
`program or process (possibly embedded in
`a hardware device) that communicates with
`
`

`
`Network Protocols
`
`°
`
`455
`
`O
`
`IMP
`
`Host
`
`Concentrator
`
`Terminal
`
`Submzt boundary
`
`
`
`High bandwidth t runl-<
`
`Figure 1 .
`
`A typical point-to—point long-haul network.
`
`the layers of the sending machine and up
`the layers of the receiving machine. Only in
`layer 1 does actual intermachine commu-
`nication occur. When an application pro-
`gram, running in layer 7 on host A, wants
`to send a message to the application in
`layer 7 on host .3, it passes the message
`down to the presentation layer on its own
`machine. The presentation layer
`trans-
`forms the data, adds a layer 6 header con-
`taining control
`information used by the
`layer 6 protocol, and passes the resulting
`message down to the session layer. The
`session layer then adds its own header and
`passes the new message down to the trans-
`port layer. The complete path from layer 7
`on host A to layer 7 on host B is shown in
`Figure 2 by the solid line. The boundary
`between adjacent layers is called an inter-
`face. The layers, interfaces, and protocols
`in a network form the network architec-
`ture.
`
`No layer is aware of the header formats
`or protocols used by other layers. Layer k
`on the sending machine regards its job as
`getting the bits that come in from layer
`k + 1 over to the receiving machine some-
`how (using the services of the lower layers).
`It neither knows nor cares what the bits
`mean.
`
`A three-layer analogy may be helpful in
`understanding how multilayer communi-
`cation works. Consider the problem of the
`
`Computing Surveys. Vol 13, No. 4, December 1981
`
`anal-su1_-on ‘era r=r2t°_w|
`
`
`
`f!’°_-"EtE*E"_' ‘3.¥'3L P_"°L° E L
`
`_5.S5_5'2“_ '£Y£"_9L°E"_‘"_ _
`
`HC|5‘l. A
`
`IMP
`
`Host 3
`
`Figure 2. The seven-layer ISO Reference Model.
`
`the corresponding process on another ma-
`chine. In Figure 2, host layers 1, 2, and 3
`think that they are communicating with
`their corresponding layers on the IMP,
`called peers. (In this example, hosts A and
`B are serviced by a common IMP; in gen-
`eral, multiple lMPs may intervene.) Layers
`4-7, in contrast, communicate directly with
`their peer layers on the other host. The
`rules governing the layer k conversation are
`called the layer It protocol. The ISO model
`thus has seven protocols.
`In reality, data are not transmitted hori-
`zontally, from machine to machine within
`a given layer, but are passed vertically down
`
`

`
`456
`
`-
`
`Andrew S. Tanenbaum
`
`1
`two talking philosophers. Philosopher
`lives in an ivory tower in Kenya and speaks
`only Swahili. Philosopher 2 lives in a cave
`in India and speaks only Telugu. Neverthe-
`less, Philosopher 1 wishes to convey his
`affection for Oryctolagus cuniculus to his
`Indian colleague (the philosophers are layer
`3 peers). Since the philosophers speak dif-
`ferent languages, each engages the services
`of a translator (layer 2 process) and an
`engineer {layer 1 process).
`To convey his thoughts, Philosopher 1
`passes his message, in Swahili, to his trans-
`lator, across the 3/2 interface. The trans-
`lator may convert it to English, French,
`Dutch, or some other language, depending
`only on the layer 2 protocol. The translator
`then hands his output to his engineer across
`the 2/1 interface for transmission. The
`physical mode of transmission may be tel-
`egram,
`telephone, computer network, or
`something else, depending only on the layer
`1 protocol. When the Indian engineer re-
`ceives the message, he passes it to his trans-
`lator for rendition into Telugu. Finally, the
`Indian translator gives the message, in Te-
`lugu, to his philosopher.
`This analogy illustrates three points.
`First, each person thinks of his communi-
`cation as being primarily horizontal, with
`his peer (although in reality it is vertical,
`except in layer 1). For example, Philosopher
`1 regards himself as conversing with Phi-
`losopher 2, even though his only physical
`cornrnunication is with translator 1. Sec-
`ond, actual communication is vertical, not
`horizontal, except
`in layer 1. Third,
`the
`three protocols are completely independ-
`ent. The philosophers can switch the sub-
`ject from rabbits to guinea pigs at will; the
`translators can switch from English to
`Dutch at will; the engineers can switch from
`telegram to telephone at will. The peers in
`any layer can change their protocol without
`affecting the other layers. It is for precisely
`this reason that networks are designed as a
`series of layers—to prevent changes in one
`part of the design (e.g., caused by techno-
`logical advances) from requiring changes in
`other parts.
`
`Overview of the ISO ()5! Layers
`The remainder of this article concerns the
`
`various layers in the ISO Reference Model,
`
`Computing Surveys, Vol. 13, No 4. December 1981
`
`one section per layer. Before looking at the
`layers in detail, we first present a brief
`overview of each layer, to put the hierarchy
`in perspective.
`The physical layer protocol is concerned
`with the transmission of a raw bit stream.
`Its protocol designers must decide how to
`represent 0’s and 1’s, how many microsec-
`onds a bit will last, whether transmission is
`full- or half-duplex, how the connection is
`set up and torn down, how many pins the
`network connector has, what each pin is
`used for, and other electrical, mechanical,
`and procedural details.
`The data link layer converts an unrelia-
`ble transmission channel into a reliable one
`for use by the network layer. The technique
`for doing so is to break up the raw bit
`stream into frames, each containing a
`checksum for detecting errors. (A checksum
`is a short integer that depends on all the
`bits in the frame so that a transmission
`error will probably change it and thus be
`detectable.) The data link protocol usually
`ensures that the sender of a data frame will
`
`repeatedly transmit the frame until it re-
`ceives an acknowledgment frame from the
`receiver.
`The network layer in a point-to-point
`network is primarily concerned with rout-
`ing and the effects of poor routing, namely,
`congestion. In a broadcast network, routing
`is not an issue, since only one channel ex-
`ists.
`The task of the transport layer is to pro-
`vide reliable host-to-host communication
`for use by the session layer. It must hide all
`the details of the communication subnet
`from the session layer, so that, for example,
`a point—to-point subnet can be replaced by
`a satellite link without affecting the session,
`presentation, or application layers. In ef-
`fect, the transport layer shields the cus-
`torner’s portion of the network (layers 5-7)
`from the carrier’s portion (layers 1-3).
`The session layer is responsible for set-
`ting up, managing, and tearing down pro-
`cess-to-process connections, using the host-
`to-host service provided by the transport
`layer. It also handles certain aspects of
`synchronization and recovery.
`The presentation layer performs gener-
`ally useful transformations on the data to
`be sent, such as text compression. It also
`
`

`
`performs the conversions required to allow
`an interactive program to converse with
`any one of a set of incompatible intelligent
`terminals.
`
`The content of the application layer is up
`to the users. Nevertheless, standard proto-
`cols for specific industries, such as airlines
`and banking, are likely to develop, although
`few exist now. For this reason we say no
`more about the application layer in this
`paper.
`Although the ISO OSI Reference Model
`says nothing about how the layers are to be
`implemented, one possible configuration
`might have the physical layer in hardware,
`the data link layer in a special protocol
`chip, the network layer in a device driver,
`the transport and session layers in the op-
`erating system proper,
`the presentation
`layer in a set of library routines in the user’s
`address space, and the application layer be
`the user’s program.
`At this point we have covered enough
`background material to say a little bit about
`the ISO OSI Reference Model itself. Basi-
`
`cally, it is a framework for describing lay-
`ered networks. It discusses the concept of
`layering in considerable detail, and intro-
`duces a uniform terminology for naming
`the various entities involved. Finally,
`it
`specifies the seven layers mentioned thus
`far, and for each layer gives its purpose, the
`services provided to the next higher layer,
`and a description of the functions that the
`layer must perform. The value of the model
`is that it provides a uniform nomenclature
`and a generally agreed upon way to split
`the various network activities into layers.
`However, the ISO OSI Reference Model
`is not a protocol standard. By breaking a
`network's functions up into layers, it sug-
`gests places where protocol standards could
`be developed (physical layer protocols, data
`link layer protocols, and so on), but these
`standards themselves fall outside the do-
`main of the model. With the model in hand,
`other organizations such as the Consulta-
`tive Committee for
`International Tele-
`
`phony and Telegraphy (CCITTJ, the Inter-
`national Federation for Information Proc-
`
`essing (IFIP), and the American National
`Standards Institute {ANSI} may develop
`specific protocol standards for the various
`layers. Although these standards may even-
`
`Network Protocols
`
`-
`
`457
`
`tually be officially approved by ISO, such
`work is still in progress and, in any event,
`falls far outside the scope of the model.
`As a final note, before plunging into the
`details of the various layers, we would like
`to point out that this article is about net-
`work protocols, with the ISO OSI Refer-
`ence Model used as a guide; it is not an
`article about the model itself. We empha-
`size the communication algorithms and
`protocols themselves, a subject about which
`the Reference Model says nothing.
`
`1. THE PHYSICAL LAYER
`
`In this section we look at a variety of as-
`pects related to the physical layer. Our
`emphasis is on the conceptual organization
`of the physical transmission facilities, not
`on the hardware details themselves. Point-
`
`to-point, satellite, and local networks are
`discussed. We conclude with a brief discus-
`sion of the X.21 physical layer protocol.
`The function of the physical layer is to
`allow a host to send a raw bit stream into
`
`the network. The physical layer is in no
`way concerned with the way the bits are
`grouped into larger units, or what they
`mean. Nor does it rectify the problem of
`some bits being garbled by transmission
`errors. Recovery from such errors is up to
`the data link layer.
`The communication subnet can be orga-
`nized in one of two ways. In circuit switch-
`ing, a fixed amount of transmission capac-
`ity (bandwidth) is reserved when the source
`initiates a conversation and released only
`when the conversation is over. The tele-
`phone system uses circuit switching. When
`someone calls a time-sharing service in a
`distant city, the connection is established
`after dialing and remains in force until one
`end hangs up. If the user goes out to lunch
`while still logged in, the connection remains
`intact and the charges continue to accu-
`mulate, even though the connection is ac-
`tually idle.
`With packet switching, in contrast, the
`user initially sets up a connection between
`his terminal or host and the nearest IMP,
`not the destination host. (We assume that
`the destination host also is connected to
`some IMP.) Whenever the user has data to
`send, he sends them to the IMP as a series
`of pockets,
`typically 10-1000 bytes long.
`
`Computing Surveys, Vol. 13, No. 4, December 1981
`
`

`
`458
`
`-
`
`Andrew S. Tanenbaum
`
`Packets are routed from IMP to IMP
`within the subnet, until they get to the IMP
`which services the destination host. No cir-
`cuits are reserved in advance within the
`subnet for the terminal-to-host connection
`
`(except the terminal-to-IMP and IMP-to-
`host circuits). Instead, the high-bandwidth
`IMP—IMP lines are dynamically shared
`among all the users on a demand basis;
`IMP—IMP bandwidth is only tied up when
`data are actually being transmitted.
`Although the above discussion is cast in
`terms of a point-to-point network, the same
`considerations apply to broadcast channels.
`If a portion of the channel {e.g., one fre-
`quency band} is dedicated to a given con-
`versation throughout its duration, without
`regard to actual usage, the network is cir-
`cuit switched. If, however, the channel is
`dynamically requested, used, and released
`for every packet, the network is packet
`switched.
`Circuit-switched networks are best suited
`to communication whose bandwidth re-
`
`quirements do not change much over time.
`Transmission of human speech is such an
`application, so it makes sense for the tele-
`phone network to be circuit switched. Ter-
`minal~to-computer and computer-to-com-
`puter traffic, however,
`is usually bursty.
`Most of the time there are no data to send,
`but once in a while a burst of data must be
`transmitted. For this reason, most com-
`puter networks use packet switching to
`avoid tying up expensive transmission fa-
`cilities when they are not needed. However,
`in the future, all digital transmission sys-
`tems will allow computers to dial a call,
`send the data, and hang up, all within a few
`milliseconds. If such systems become wide-
`spread, circuit switching may come back
`into favor.
`
`1.1 The Telephone System
`
`Since most existing long-haul networks use
`the telephone system for their transmission
`facilities, we shall briefly describe how the
`latter is organized. Most
`telephones are
`connected to a nearby telephone company
`switching office by a pair of copper wires
`known as a local loop. The switching offices
`themselves are connected by high-band-
`width trunks onto which thousands of un-
`related calls are multiplexed. Although
`
`Computing Surveys, Vol 13, No 4. December 1931
`
`some trunks utilize copper wire, many uti-
`lize microwave relays, fiber optics, or wave
`guides as the transmission medium.
`Because the bandwidth of the local loop
`is artificially limited to about 3000 Hz
`(hertz), it is difficult to transmit informa-
`tion over it by using, for example, +5 volts
`for a binary one and 0 volts for a binary
`zero. Such square wave signaling depends
`on high-frequency harmonics that are well
`above the 3000-Hz cutoff frequency. Only
`with very low date rates might enough in-
`formation be below 3000 Hz to be intelligi-
`ble. Instead, a device called a modem is
`inserted between the host and the tele-
`
`phone line. The input to the modem is pure
`digital data, but the output is a modulated
`sine wave with a base frequency of gener-
`ally between 1000 and 2000 Hz. Since the
`modulated sine wave has fewer high-fre-
`quency components
`than the original
`square wave, it is affected less by the lim-
`ited bandwidth.
`A sine wave has three properties that can
`be modulated to transmit information: an
`
`amplitude, a frequency, and a phase. In
`amplitude modulation, two different ampli-
`tude values are used to represent 0 and 1.
`In frequency modulation, different frequen-
`cies are used for 0 and 1, but the amplitude
`is never varied. In phase modulation, nei-
`ther the amplitude nor the frequency is
`varied, but the phase of the sine wave is
`abruptly switched to send data. In the most
`common encoding scheme, phase shifts of
`45, 135, 225, and 315 degrees are used to
`send 00, 01, 10, and 11, respectively. In
`other words, each phase shift sends two
`bits. The three methods can be combined
`
`to increase the transmission capacity.
`Many such transmission systems have
`been standardized and form an important
`class of physical layer protocols. Unfortu-
`nately, in many cases, the standards in the
`United States and Canada differ from those
`
`used by the rest of the world. For example,
`those ubiquitous 300-bit-per-second fre-
`quency modulation modems found near ter-
`Ininals around the world use different sig-
`naling frequencies in North America and
`Europe.
`Probably the best known physical layer
`standard at present is RS-232-C, which
`specifies the meaning of each of the 25 pins
`
`

`
`on a terminal connector and the protocol
`governing their use. However, a new stan-
`dard, RS-449, has been developed to re-
`place this aging workhorse. RS-449 is up-
`ward compatible with RS-232-C but uses a
`37-pin connector to accommodate the new
`signals. Unfortunately, 37 pins are insuffi-
`cient, so users wishing to take advantage of
`all the features of RS-449 (notably the sec-
`ondary channel) need a second 9-pin con-
`nector as well.
`
`The transmission technology and proto-
`cols used on the interoffice trunks are dif-
`
`ferent from those used on the local loop. In
`particular, digital rather than analog tech-
`niques are becoming increasingly wide-
`spread. The most common digital system is
`pulse code modulation (PCM),
`in which
`the analog signal coming in from the local
`loop is digitised by sampling it 8000 times
`per second. Eight bits (seven data and one
`control} are transmitted during each 125-
`ps (microsecond) sampling period. In North
`America,
`24 such PCM channels are
`grouped together into 193-bit frames, with
`the last bit being used for synchronization.
`With 8000 193-bit frames per second, the
`gross data rate of this system, known as T1,
`is 1.544 Mbits/s (megabits per second). In
`Europe, the 1.544-Mbit/s PCM standard
`uses all 8 bits for data, with the 193rd bit
`(which is attached to the front rather than
`rear of the frame) used for signaling. Two
`different
`(and incompatible) 32-channel
`PCM standards running at 2.048 Mbits/s
`are also widely used outside North Amer-
`ica. For more information about the tele-
`
`phone system see DAVI73 and DDLL78.
`
`1.2 Communication Satellites
`
`Although most existing long-haul networks
`use leased telephone circuits to connect the
`lMPs, satellite-based networks are becom-
`ing increasingly common. A communica-
`tion satellite is a big repeater in the sky.
`Incoming signals are amplified and re-
`broadcast by a transponder on the satellite.
`The upward and downward signals use dif-
`ferent frequencies to avoid interference. A
`typical communication satellite has 5-10
`independent transponders, each with a ca-
`pacity of about 50 Mbits/s.
`Communication satellites are put into
`
`Network Protocols
`
`-
`
`459
`
`geosynchronous equatorial orbit at an alti-
`tude of 36,000 kilometers to make them
`appear stationary in the sky when viewed
`from the earth. Consequently, the ground
`station antenna can be pointed at the sat-
`ellite when the antenna is installed and
`never moved. A moving satellite would re-
`quire a much more expensive steerable an-
`tenna and would also have the disadvan-
`
`tage of being on the other side of the earth
`half the time. On the other hand, the great
`altitude required to achieve a 24-hour pe-
`riod implies an up-and-down propagation
`delay of 270 ms (milliseconds), which seri-
`ously affects the data link layer protocols
`and response time.
`To avoid mutual interference, communi-
`cation satellites using the 4/6-GHZ (giga-
`hertz) frequency band must be separated
`by an angle of 4 degrees as viewed from the
`earth. Since some orbit slots have been
`allocated by international agreement
`to
`television, military, and other use, the num-
`ber of equatorial orbit slots available to
`data communication is limited.
`(As an
`aside, the allocation of orbit slots has been
`a political battleground, with every coun-
`try, especially those in the Third World,
`asking for its fair share of slots for the
`purpose of renting them back to those coun-
`tries able to launch satellites.) The 12/ 14-
`GHz band has also been allocated to data
`
`communication. At these frequencies, an
`orbit spacing of 1 degree is sufficient, pro-
`viding four times as many slots. Unfortu-
`nately, because water is an excellent ab-
`sorber of these short microwaves, multiple
`ground stations and elaborate switching are
`needed in order to avoid rain.
`
`Three modes of operation have been pro-
`posed for satellite users. The most direct
`but most expensive mode is to put a com-
`plete ground station with antenna on the
`user’s roof. This approach is already feasi-
`ble for large multinational corporations and
`will become feasible for medium-sized ones
`as costs decline. The second approach is to
`put a small, cheap antenna on the user’s
`roof to communicate with a shared satellite
`ground station on a nearby hill. The third
`approach is to access the ground station via
`a cable (e.g., a leased telephone circuit or
`even the same cable used for cable televi-
`sion).
`
`Computing Surveys. Vol. 13, No. 4. December 1981
`
`

`
`Andrew S. Tanenbaum
`
`
`
`
`
`(cl
`(bl
`Figure 3. Local network topologies. (a) Linea: cable with four hosts. {b} Segmented cable with repeaters and
`hosts. (cl Ring.
`
`Physical layer satellite protocols typi-
`cally have many PCM channels multi-
`plexed on each transponder beam. Some-
`times they are dedicated (circuit switched);
`at other times they are dynamically as-
`signed as needed (packet switched). For
`more information about communication
`satellites see MART78.
`
`1 .3 Local Networks
`
`In most local networks, the hosts are con-
`nected by a linear, tree-shaped, or ring-
`shaped cable, as shown in Figure 3. In Fig-
`ure 3a, all hosts tap onto a common cable.
`In Figure 3b, multiple cables are used (e.g.,
`one per floor of an oifice building), with
`repeaters connecting the segments. In Fig-
`ure 3c, all hosts tap onto a unidirectional
`ring.
`A widely imitated linear or tree-shaped
`local network is the Ethernetfl” network
`[METC76]. The proper term for this kind of
`network is CSMA/CD (Carrier Sense Mul-
`tiple Access/Collision Detect), although
`many people incorrectly use the term “Eth-
`ernet” (which is a trademark of the Xerox.
`Corporation} in a generic sense. In these
`networks, only one packet may be on the
`cable at any instant. The cable is known as
`the ether, after
`the lurniniferous ether
`through which electromagnetic radiation
`was once alleged to propagate. The princi-
`ple behind CSMA/CD is simple: when a
`
`Computing Suweys. Vol. 13, No 4. December 1931
`
`host wishes to send a packet, it first listens
`to the ether to see if the ether is being used.
`If it is, the host waits until the current
`transmission finishes; if not, the host begins
`transmitting immediately.
`The interface hardware must detect col-
`lisions caused by two hosts simultaneously
`starting a transmission. Collision detection
`is done using analog circuitry, in essence
`monitoring the ether to see if it agrees with
`the signal being transmitted. When a host
`interface (the analog of an IMP in this
`system, since the ether itself is totally pas-
`sive) detects a collision, it informs the data
`link layer. The collision recovery action
`consists of aborting the current transmis-
`sion, broadcasting a noise burst to make
`sure that everyone else detects the collision
`as well, waiting a random length of time,
`and then trying again. Collision detection is
`only feasible if the round-trip propagation
`delay is short compared to the packet trans-
`mission time, a condition that can be met
`with cable networks, but not, for example,
`with satellite networks.
`Cable networks similar to the Xerox Eth-
`ernet network, but without the collision
`detect feature, also exist. Network design-
`ers can trade off the cost of collision detec-
`
`tion circuitry against the time lost by not
`aborting colliding packets quickly.
`in
`Ring nets use a different principle:
`effect, the whole ring is a giant circular shift
`
`

`
`Network Protocols
`
`-
`
`461
`
`To see how X21 works, let us examine
`how a DTE calls another DTE, talks to it,
`and then hangs up. When the interface is
`idle, T, R, C, and I are all 1. The series of
`events is as follows (with a telephone anal-
`ogy in parentheses):
`
`(1) DTE drops T and C (DTE picks up
`phone)
`(2) DCE sends “++++++ - - - +++” on
`R (DCE sends dial tone).
`(3) DTE sends cal]ee’s address on T
`(DTE dials number).
`(4) DCE sends call progress signals on R
`(phone rings).
`(5) DCE drops I to 0 (callee answers
`phonel
`(6) Full duplex data exchange on T and
`R (talk).
`(7) DTE raises 0 to 1 (DTE says good-
`bye).
`(8) DCE raises I to 1 (DCE says good-
`bye).
`(9) DCE raises R to 1 (DCE hangs up).
`(10) DTE raises T to 1 (DTE hangs up).
`
`The call progress signals in Step 4 tell
`whether the call has been put through, and
`if not, why not. The shutdown procedure in
`Steps 7-10 operates in two phases. After
`either party has said goodbye, that party
`may not send more data but it must con-
`tinue listening for incoming data. When
`both sides have said goodbye, they then
`hang up, returning the interface to idle
`state, with 1’s on all four lines. RS-449 and
`X21 are described in more detail in BERT30
`and FOLT30.
`
`2. THE DATA LINK LAYER
`
`As we have seen, neither X21, RS-232-C,
`nor any other physical layer protocol makes
`any attempt to detect or correct transmis-
`sion errors. Nor do these protocols recog-
`nize the possibility that the receiver cannot
`accept data as fast as the sender can trans-
`mit them. Both of these problems are han-
`dled in the data link layer. In the following
`sections we first discuss the relevant prin-
`ciples and then we give an example of a
`widely used data link protocol, HDLC
`(High-Level Data Link Control). Following
`the HDLC example, we look at some data
`link protocols for satellite and local net-
`works.
`
`Computing Surveys. Vol. 13, No. 4. December 1931
`
`T
`
`(Transmit)
`
`(Ground)
`
`Ga (Common return)
`
`G
`
`Figure 4. The DTE/DCE interface tn X 21.
`
`register. After each shift, the host interface
`can read or write the bit just shifted into it.
`Several different kinds of rings have been
`proposed [CLAR78, FARB72, FRAS75, LIUTS,
`WILK79], differing primarily in their layer
`2 organizations, which we describe later.
`Both CSMA/CD networks and rings typi-
`cally operate at data rates of 1-10 Mbits/s.
`A substantial bibliography about local net-
`works can be found in FREE80 and SHoC81.
`
`1.4 An Example Physical Layer Protocol:
`X.21
`
`At present, most physical layer standards,
`like RS-232-C and RS-449, utilize analog