Middleton W.M. (ed.) Reference Data for Engineers: Radio, Electronics, Computer and Communications
Подождите немного. Документ загружается.
26-26
REFERENCE
DATA
FOR
ENGINEERS
however, other flow control procedures that reside at
other layers of the hierarchy of protocols. Fig. 17
illustrates the various levels at which flow control is
exercised. As will be clear from the following discus-
sion, flow control helps prevent loss of efficiency,
deadlocks, and unfair allocation of the resources.
Hop-Level
Flow
Control-Channel-Queue-Limit
Flow Control: The
direct store-and-forward deadlock
occurs in nonlossy networks when all buffers in some
node
A
are destined to an adjacent node
B
and vice
versa. Channel-queue-limit flow-control techniques are
used to prevent such deadlocks. They consist of parti-
tioning the buffers available at a node among the various
outgoing channels. Complete partitioning is such a
scheme that does not allow any sharing of buffer among
the channels. Sharing with maximum queues, with
minimum queues, or with maximum and minimum
queues are variants. In addition to preventing dead-
locks, these techniques achieve more efficient and fairer
operation of the network by avoiding hogging.
Structured Buffer Pool Flow Control: Given that a
channel-queue-limit flow control is implemented, thus
preventing the direct store-and-forward deadlock,
another type of deadlock, called the
indirect store-
and-forward deadlock,
might still occur. Consider a
closed chain of consecutively adjacent nodes
No,
N,
,
.
.
.
N,l-l,
No.
Assume all buffers on the outgoing
queue from
N,
to
N,-,
are occupied by packets destined
to
Nif2,
fori
=
0,
1,
,
. .
,n
-
1
(addition on indices is
modulo
n).
This situation clearly leads to a deadlock.
A
solution to this problem is given by the structured buffer
pool technique. Packets arriving at an outgoing link
queue are classified according to the number of hops
they have already traveled. With
N
nodes in the net-
work, the maximum number of hops is
N
-
1. The
buffers available for that queue are allocated to the
various classes (either in a fixed fashion or adjustable as
needed).
A
packet of class
k
can use all buffers available
to classes
1
through
k.
It
has been shown that such a
technique avoids completely cycles such as those de-
scribed above that lead to the indirect SIF deadlock.
Hop-Level Flow Control With Virtual Circuits: The
above techniques are used with both datagram and
virtual circuit modes. In virtual circuit modes, it is also
possible to exercise selective flow control on individual
virtual circuit streams. An example consists of setting a
maximum limit,
M,
on the number of packets for each
VC in transit at each intermediate node. Limit
M
may
be fixed or dynamically adjusted. This scheme is
effective in slowing down VCs that directly feed into
congested areas; by backpressure the control is exer-
cised at the source, which in response reduces its input.
In
the absence of this control, congestion is bound to
spread to other areas of the network and affects other
sources originally not responsible for the congestion.
Entry-to-Exit Flow
Control-This level of flow
control is primarily aimed at preventing buffer conges-
tion at the exit node that may be due to conditions of
overload of local lines connecting the exit node to the
host. If the exit node must reassemble the messages
before handing them to the host, then the problem is
hrther complicated by reassembly and resequence
deadlocks. An example illustrating a reassembly buffer
deadlock is shown in Fig.
18.
In this figure,
A,,
i
=
1,
2.
3,
4
are packets belonging to the same message.
Similarly,
B,,
j
=
1,
2,
3,
4
and
Ck,
k
=
1,
2,
3
represent packets of two other messages. Node
3
is the
exit node. It is currently assembling message
A1A2A3A4.
Packet
A2
is missing. The deadlock occurs
because packet
A2
cannot make it through node
2,
where the buffers are full. An example illustrating
resequence deadlocks is given in Fig.
19.
Here
A,
B,
. .
.
,
K
are consecutive packets. The exit node
(node
3)
must deliver packets to host
1
in sequence. The
deadlock takes place because node
3
cannot deliver any
of its packets, and packet
A
cannot reach node
3
via
node
2.
The most common solution to reassembly deadlocks
is to reserve a reassembly buffer for each message
entering the network. The solution to the sequence
deadlock is simply to discard out-of-sequence messages
at the destination. The ARPANET applies this tech-
nique. A logical pipe is assumed to exist for all
messages from some host
A
to some host
B.
Each pipe
is individually flow controlled by a window mechanism
of size
W
=
8.
Messages arriving out-of-range are
discarded. A request for next message (RFNM) is
issued by the destination node to the source node to
permit the source node to issue the next message. Buffer
allocation for message reassembly at the destination is
TRANSPQRT LEVEL
ENTRY TO EXIT LEVEL
'
NETWORK
'
1-
ACCESS
l-NETWoRK-l
ACCESS
I
I
I
I
I
~----(ZJ--(--j-(--J-----@
Fig.
17.
Flow
control
levels.
(From Paul
E.
Green,
Jr.,
Computer Network Architectures
and
Protocols,
0
1982.
Used
by
permission
of
Plenum Publishing Corp.,
New
York.
i
COMPUTER COMMUNICATIONS NETWORKS
26-27
NODE
1
NODE
2
NODE
3
HOST
1
Fig.
18.
Reassembly buffer deadlock.
(From Paul
E.
Green, Jr.,
Computer Network Architectures
and
Protocols,
0
1982.
Used
by
permission
of
Plenum Publishing Corp.,
New
York.)
guaranteed prior to message transmission by the source
node. In GMDNET, a network based on virtual cir-
cuits, entry-to-exit flow control is exercised individually
on each
VC.
A window mechanism is used for each
VC
with the window size large enough to attain efficient
utilization. However, the window size
is
variable: it is
reduced if the destination
is
slow in accepting packets; it
is increased otherwise.
Network Access
Flow Control-Network access
flow control is aimed at throttling the external input to
the network with a view toward preventing overall
internal network congestion. This control
is
based on
measurements of internal network congestion, where
the measures collected may be local (e.g., buffer
occupancy at the entry node), global (e.g., total number
of empty buffers available in the network), or selective
(e.g., some measure of congestion on the path leading
to the destination). Three techniques are described
hereafter.
The Isarithmic Scheme: This scheme consists of
setting an upper limit on the number of packets that can
circulate in the network at any one time. It is based on
the concept of
permits.
A number
of
permits are present
in the network. Each packet offered to the network must
secure a permit at the entry node before being admitted.
Once a permit is
so
secured, it remains in use until the
corresponding packet is delivered to its destination and
hence exits from the network. The permit becoming
free is added to the pool of permits at the node where it
is
freed. This scheme as described functions adequately
if the traffic pattern is uniform and balanced. Other-
wise, one must avoid having a large number of permits
accumulate in certain parts of the network at the
expense
of
other parts. This is accomplished by setting
limits on the number of permits at each node. The
question of how to distribute the permits in the network
then arises. The performance of the network under this
scheme is sensitive to the permit distribution algorithm
in use. A few such algorithms have been investigated
analytically and by simulation.
The Input Buffer Limit Scheme: At each node, a
distinction is made between (external) input traffic and
transit traffic. The input is throttled based on buffer
occupancy data at the entry node. This scheme rests on
the observation that congestion at the entry node is a
good indication of global congestion due to the back-
pressure effect propagating internal network congestion
back
to
the source nodes. Different versions exist. The
structured buffer pool technique discussed previously
falls into this category. Input traffic (which
is
in the
0-hop class) is discarded when all class-zero buffers are
occupied. The number of class-zero buffers has been
shown to have a great effect on the network perform-
ance under heavy load. Another version defines a limit,
N,,
smaller than the total number of buffers,
N,
and new
packets are limited to
N,
while transit packets have no
limitation imposed upon them. The performance here is
sensitive
to
the ratio
N,IN.
Another version yet consists
of discarding an input packet if the total number of
packets in the entry node exceeds a given threshold.
Choke Packet Scheme: In this scheme, a link is said
to be congested if its utilization over some history
window is beyond some threshold. A path is said to be
congested
if
any of its links is congested. Along with
routing information, congestion information
is
propa-
gated in the network. When a packet is received by a
node for some destination whose path
is
congested, then
(1)
if the packet is new external input,
it
is
dropped;
(2)
otherwise, it is forwarded and a choke packet is sent
back to the source, slowing the source. The path to the
destination is unblocked gradually as no choke packets
are received during a specified period of time.
HOST
2
hODE
1
NODE
2
NODE
3
HOST
I
Fig.
19. Resequence deadlock.
(From Paul
E.
Green, Jr.,
Computer Network Architectures and Protocols,
0
1982.
Used
by
permission
of
Plenum Publishing Corp.,
New
York.)
CCITT
Recommendation
X.25
Recommendation X.25 is a widely accepted standard
entitled “Interface Between
a
DTE and a DCE for
Terminals Operating in the Packet Mode on Public Data
Networks.”
It
is a set of three peer protocols: a physical
level. which is the same as in Recommendation X.21
(discussed in the section “The Physical Layer”); a link
control level, which is essentially HDLC: and
a
network
layer. which is discussed in the present subsection.
Recommendation X.25 is based on the concept of
virtual circuits. These virtual circuits can be either
temporary or permanent. A temporary virtual circuit
referred
to
as a virtual call requires three phases: setting
up the call, the data-transfer phase, and disconnecting
the call. In setting up a virtual call, a logical channel
number is assigned
to
the call. With a permanent virtual
call, the numbers are assigned when the customer leases
the facility from the common carrier. In such a case, the
two phases of setting up and disconnecting the circuit
do not exist.
It is important
to
note that Recommendation X.25
describes only the DTEiDCE interface. It is not con-
cerned about how the network operates and how virtual
circuits within the network are implemented. Recom-
mendation X.25 defines the services rendered
to
the
transport layer of the
IS0
model that resides in the
user’s equipment. Thus X.25 is known as a network
access protocol standard. In many cases, the DTE is a
terminal that handles characters rather than packets and
that uses the start-stop asynchronous DLC protocol. In
such cases, common carriers operating X.25 networks
provide interface machines to which these terminals are
connected. These interface machines, called PAD
(Packet AssemblyiDisassembly), are extensions to X.25
but
not
part of it.
The network layer of X.25 defines explicitly the
formats of packets and the operational phases of a
virtual circuit connection. Two types
of
packets exist:
data packets and control packets. A data packet has a
variable-length information field to carry user data. A
control packet can be
of
different types, many of which
are discussed below.
When a DTE sets up a virtual call, it selects a free
logical channel number from the set allocated
to
it.
Such
a
number consists of two parts: a logical channel
group number and a logical channel number. A DTE
has available
to
it up
to
15
logical channel groups
(addressed with
4
bits) and up to 255 logical channels
within each group (addressed with
8
bits). Using a
CALL REQUEST packet, the DTE sends the selected
logical number along with its own address, the address
of the destination, and other facility codes to the DCE
to
which it is attached. (For efficiency purposes, the
CALL REQUEST packet may also carry user data up to
16
bytes.) The request to establish a connection arrives
at the remote DTE from its attached DCE as an
INCOMING CALL packet. The called DTE decides
whether
to
accept or refuse the call. If it accepts it, then
a CALL ACCEPTED packet is sent back to the DCE.
The indication
of
acceptance of the call is achieved via a
CALL CONNECTED packet, which is sent by the local
DCE
to
its calling DTE. The disconnection of a call
follows similar procedures. It uses the control packets
CLEAR REQUEST, CLEAR CONFIRMATION, and
CLEAR INDICATION. Once
a
connection is estab-
lished, the flow of data packets can take place. Data
packets are sequenced, and the flow is regulated accord-
ing
to
a window mechanism as described in the section
“The Data Link Control Layer.” As with ADCCP and
HDLC, the two sequence ranges
of
8
and 128 are
available. The control packets RECEIVE READY and
RECEIVE NOT READY, similar
to
those described for
ADCCP and HDLC, are used in a supervisory mode to
acknowledge data packets. Other packets such
as
IN-
TERRUPT, RESET, RESTART, and their confirma-
tions are used for further control and
to
recover from
certain minor and major problems. The INTERRUPT
packet contains only one byte of user data and has
no
sequence number. It
is
transmitted as quickly as possi-
ble, preempting the queues of normal data packets. It is
delivered (out of sequence) even when data packets are
not being accepted. It is normally used to convey the
fact that a terminal user has hit the break key
to
stop a
flow of data from a distant computer. An INTERRUPT
packet is acknowledged by the local DCE with an
INTERRUPT CONFIRMATION packet. The RESET
commands are used
to
reinitialize the window parame-
ters corresponding
to
a
particular virtual circuit to zero.
Both DTEs and DCEs can initiate
a
reset. Reset packets
contain up
to
two bytes of data explaining the reasons
for the reset. These may be: the remote DTE is
out
of
order, the network is congested or one of its nodes had
failed, etc. Following a reset, the DTE has no knowl-
edge about the status of outstanding (unacknowledged)
packets. Recovery must be accomplished by higher
levels. The
restart
condition provides
a
mechanism
to
recover from major failures. It has the effect of clearing
all the virtual calls that a DTE has connected and
resetting the permanent virtual calls, bringing the
userinetwork interface to the state it was in when the
service was initiated.
Since X.25 is an interface between a DTE and the
local DCE
to
which it is attached, the receipt of an
acknowledgement by a DTE from the DCE means that
the latter has received the packet, but does not imply
that the remote DTE has received it. To provide some
level of end-to-end acknowledgement, a hit called the
delivery confirmation bit, or D-bit, has been provided
in the packet format. The DTE sets
D
to
1
to request
confirmation of delivery to the remote DTE. An ac-
knowledgement for this packet by the DCE would then
have
to
be a guarantee of its delivery
to
the remote DTE.
In addition
to
the standard features of X.25, there are
also some optional features that may be requested by a
user when a call is set up. Examples are: reverse
charging, closed user group (where members
of
a closed
group can communicate only with one another), packet
retransmission (where a DTE can ask its DCE to
retransmit one or several data packets, and this is
accomplished by the use of the REJECT command
as
in
ADCCP), etc.
HIGHER-LEVEL PROTOCOLS
This section is concerned with layers four through
seven of the
IS0
model. The brevity of this section is
due to three factors:
(1)
many of the concepts and
techniques needed at these higher levels, such
as
sequencing, acknowledging, and flow control, are simi-
lar to those used in lower layers and have already been
described and discussed in previous sections;
(2)
many
of the functions residing at these layers have not yet
been well defined, and there are no internationally
accepted standards yet; and
(3)
some of the functions
(especially concerning the presentation and application
layers) are not strictly speaking communication func-
tions, and thus are considered
out
of the scope of this
chapter.
The Transport and Session
Layers
Internally to a host computer, application programs
are represented by processes. Communication between
such processes across a network is accomplished by
means of “reliable connections” called
sessions
be-
tween specific pairs of processes, and it is the role of the
session layer to establish and maintain such connec-
tions. It is possible to imagine that each such connec-
tion is achieved as a virtual circuit that the network layer
provides. In that case, the session layer is trivial, the
transport layer is nonexistent, and most of the work is
done by the network layer. However, there are many
problems with that design. The first problem arises
when the network layer provides only
a
datagram
service; the session layer will then have to be construct-
ed appropriately
so
as to overcome the deficiencies of
the network.
In
such
a
design, the session layer will also
have to interface to the networks differently, depending
on their type. It will have to be concerned with
managing the buffers at the host where the processes
reside, guaranteeing end-to-end reliability between the
end hosts (which the network does not guarantee even
when it is providing the virtual circuit service, since
crashes, resets, and restarts can occur), and controlling
the flow. As the protocols for many of these functions
again differ depending on the network, it is best to
render the session layer independent from network
issues by the introduction of the transport layer. Thus,
while the transport layer provides truly reliable host-to-
host communication, the session layer connects two
processes together in a session without worrying about
any of the implementation details of the actual network.
It merely requests from the transport layer its services.
The functions of a session layer are thus considerably
reduced. At session setup time, it establishes the
conventions necessary for the connection, conventions
relating to the data-transfer mode (half-duplex versus
full-duplex), the character codes, the flow control
window sizes, how to recover from failures at the
transport layer, etc. It
also
allows processes to refer to
destinations using symbolic names by doing itself the
mapping onto transport addresses.
The transport layer within
a
host defines
a
set of
transport addresses
or
sockets
through which connec-
tions are established. A transport address consists of
a
network
number.
a
host
number, and
a
port
number
assigned by the host. A CCITT numbering plan exists
which uses 14-digit numbers. The first three identify the
country; the fourth identifies the network within the
country; the last ten digits are assigned by each network
operator, some to indicate hosts, the remaining ones to
indicate ports. There is a distinct difference between a
transport address and a network layer address (which
defines a virtual circuit), and the mapping need not be
one-to-one. The transport layer uses network addresses
to create transport connections. If the mapping is not
one-to-one. then
multiplexing
is said to be in effect. In
upward multiplexing,
several transport connections are
multiplexed onto the same network virtual circuit con-
nection. In
downward multiplexing,
a single transport
connection uses several virtual circuits. The choice of
one type of multiplexing or the other is
a
function of the
charging procedure used in the public network, the
traffic volume exercised by a transport connection, and
the window size of virtual circuits within the network.
The transport layer functions to establish and close
connections
as
well as to control the flow across each
connection. The techniques are similar to those de-
scribed for lower levels. However, due to the ultimate
end-to-end reliability that is to be guaranteed, several
problems need to be solved. First of all, it is important
to guarantee that old packets that for some reason have
been delayed in the subnet but whose sequence numbers
fall within the current receive window of the destination
are not delivered to the destination. This is done by
limiting the amount of time that
a
packet can exist in the
network and by
using
a
sequence space
so
large (e.g.,
32
bits) that
no
packet can live for
a
complete cycle. For
this method to be successful, however, it is important to
have each connection initialize its sequence numbers to
a value higher than the previous end sequence number
by some margin
so as
to guarantee it is higher than any
existing packet number. The second problem to deal
with is to guarantee synchronization between the source
host and destination host with regard to their respective
initial sequence numbers. The solution
to
this problem
is the
three-way handshake
mechanism. It consists of
the following. The sender sends a CALL REQUEST
packet with initial sequence number
S.
The destination
responds with a CALL ACCEPTED with a sequence
number
A
along with the source sequence number,
S.
Upon receipt
of
this packet, the source sends a packet
with
S
and
A.
Thus, only when source and destination
have confirmation of the combined sequence numbers
would they consider the connection
to
have been
established. The control of flow over
a
connection
between source and destination is achieved by using
a
window mechanism similar to that of lower levels. The
window sizes must be chosen appropriately. To be
effective, it is important in some cases to distinguish
acknowledgements from the destination confirming
correct reception of packets from so-called
credits,
which are sent by the destination to inform the sender
that receive buffers are available. Acknowledgement of
a packet allows the sender to free its own buffer, while
receipt of a credit allows the sender to advance its send
window.
The Presentation Layer
The presentation layer performs transformation on
the data generated by or destined to application pro-
grams before they are sent to or after they arrive from
the session layer, respectively. The objectives and
nature
of
such transformations are diverse. In order to
save on communication bandwidth, the presentation
layer compresses text and reduces the amount to be
transmitted across the network. In order to guarantee
the security of data, the presentation layer encrypts it at
the source and decrypts at the destination. Many
compression and encryption techniques are available.
They are out of the scope
of
this chapter, and thus are
not described here.
Another objective of the presentation layer is to
resolve the differences that exist among the various
equipments connected to the network. Advances of this
nature have been made in two areas: (1) resolving the
differences that exist among the various types of termi-
nals in the networks leading to the so-called
virtual-
terminal protocols,
and
(2)
resolving the differences
that exist among the various hosts
so
that files stored in
one host can be transferred to another host. This has led
to the so-called
file transfer protocols.
Terminals are basically of three types:
scroll-mode
terminals, which have no intelligence and generally use
the start-stop protocol;
page-mode
terminals, which
handle about
25
lines of
80
characters each at a time
and have some local editing capabilities; and
form-
mode
terminals, which are micro-based, have more
intelligence, and handle specific forms that the operator
fills out using local editing facilities. Besides the
differences that exist among the different types of
terminals, many differences exist within each class with
regard to such attributes as the character set, line length,
carriage-return and tab rules, cursor addressing, blink-
ing, local editing capabilities, etc. Virtual-terminal
protocols attempt to hide the differences by mapping
real terminafs onto a hypothetical network virtual
terminal. For
scroll-mode
terminals, such a conversion
is straightforward. Each time a new version of such a
terminal type is to be supported, the corresponding
conversion rules are added to the presentation layer at
the host computer. For the more sophisticated types, a
data structure model
has proven useful and effective.
Each end
of
the session has a data structure representing
the state of the virtual terminal. Every time the applica-
tion program changes the data structure on its machine,
the presentation layer sends a message to the remote
machine telling it how to change its data structure, and
vice versa.
While the terminal conversion problem has been
adequately solved, file transfer has proven to be much
more difficult, and no general solutions exist. In partic-
ular, the concept of a network standard file format is not
attractive due to the great difficulties involved in con-
verting a file from one machine format to another.
There are, however, several ad hoc file-transfer proto-
cols particular to specific networks, e.g., ARPANET’s
FTP (reference
2).
HIGH
SPEED LOCAL AREA
NETWORKS
The advances in technology and the pull of new,
more demanding user applications are stimulating the
development of
Local Area Networks
(LANs)
at speeds
much higher than those available just a few years ago.
High speed LANs in the 100 Mbps range are now
commercially available, and prototypes operating at
speeds of
1
Gbps are being tested. In this section, we
trace the evolution
of
the LAN technology from low to
high speed, identify the technology push and the market
pull, survey the novel high speed LAN products that are
now coming to market, and examine some of the most
recent LAN proposals and prototypes designed to
operate at speeds beyond the Gbps range.
The first LAN products were introduced in the late
’70s
in offices, campuses, and production plants in
order to interconnect with each other and to a growing
number of terminals, workstations, and peripherals.
Typical applications were word processing, interactive
computing, data-base queries, and file transfers-a
predominantly data-oriented environment with peak
data transfer speeds on any user session well below
1
Mbps. Thus, LAN speeds from
1
to 10 Mbps were
adequate for these applications.
In the mid
’80s,
the original LAN environment
underwent an important series of transformations which
forced LAN designers to look ahead for new network
technologies. First, the proliferation of LANs on cam-
puses and industrial plants led to the need
to
intercon-
nect them-via other LANs capable of carrying aggre-
gate traffic several orders of magnitude higher than the
traffic found in an individual LAN. Thus, speeds of up
to
100
Mbps and geographical coverage of several miles
are now required.
In
addition to the data applications,
new applications and services start now to emerge:
voice, video, imaging. For example, in an office we
desire to combine the telephone and the data terminal in
the same multimedia workstation, and to carry both
voice and data on the same cable.
In
a campus
environment, we wish to distribute video lectures and to
support video conferencing.
In
a hospital, we wish to
permit the radiologist to retrieve
X
rays from an image
data base.
New high-speed LAN requirements emerge also in
supercomputer labs. An important application here is
“scientific visualization,” i.e., the ability to visualize,
COMPUTER COMMUNICATIONS
through a high-definition graphics screen, a physical
phenomenon (e.g. the fluid dynamic turbulence of a jet
engine) which is simulated in the supercomputer. Cur-
rently, most of the visualization set-ups are supported
by high-speed dedicated point-to-point connections be-
tween the supercomputer and the graphics workstation.
Data rates of up to 100 Mbps are observed on such
connections. Specialized, high-speed “supercom-
puter” LANs are now proposed to reduce the cost and
increase the flexibility of such interconnections, by
sharing a common network. Many other applications
besides visualization will benefit from the supercom-
puter LAN; examples are memory-to-memory trans-
fers, distributed processing and load sharing among
supercomputers, etc.
Advances in light-wave technology have greatly influ-
enced the development of high-speed LANs. Perform-
ance and cost are the principal advantages of light-wave
technology, as compared to copper-based or radio-
frequency technologies. The improvement in light-wave
technology has been rapid and steady in the areas of
optical fibers, light sources, light detectors, couplers,
amplifiers, connectors, switches, and signal processors.
Advanced research in other areas of light-wave technol-
ogy-such as coherent processing, WDM, and pho-
tonic switching-is also yielding new results that can be
exploited in constructing even higher-performance and
more-cost-effective networks.
Whereas today’s high-speed LANs are based on
simple light-wave technology, the LANs of the future
will rely on more advanced light-wave principles to
achieve higher performance and increased functional-
ity. High-speed LANs such as FDDI and DQDB
employ direct-detection, LED-based transmission over
multimode optical fibers, which can easily accommo-
date data rates in the range of about
100
Mbps. Using
LDs
to
transmit over single-mode optical fibers, higher-
speed networks can reach speeds in the range
of
about
1
Gbps. Research proposals for future LANs and MANs
are often postulated on the emergence of WDM, which
would allow the easy implementation of multichannel
networks. Such proposals therefore depend on the
successful development of the coherent techniques that
multichannel transmission requires, especially in the
areas of modulation, heterodyne and homodyne detec-
tion, and the tunability of lasers and detectors. More
advanced research proposals might even assume that
all-optical transmission
is
to
be used, in which optical
signals are switched by purely photonic means, thereby
eIiminating undesirable electro-optical conversions
within the network. Such advanced proposals thus rely
on technological progress in areas such as photonic
switching and passive optical amplification.
Furthermore, current LANs based on light-wave
technology use simple topologies to distribute optical
signals essentially in a point-to-point manner. These
LANs regenerate the optical signal by means of electro-
optical conversions at every network interface, which
eases considerably the difficulty of meeting the link
budget. Link distances are usually constrained to only a
few kilometers, and network interfaces are typically
connected to or isolated from the optical fiber through
an optical bypass switch. However, such simple point-
to-point topologies limit the designer’s flexibility and
make the implementation of multichannel networks
problematic.. By making effective use of optical cou-
plers and broadband optical amplifiers, one can design
LANs and MANs with nonpoint-to-point topologies,
e.g. trees and stars. Tree-Net, for instance, can be used
as a physical tree topology for distributing optical
signals to a large number of users over a wide geograph-
ical area, using only passive optical couplers and optical
amplification at the root of the tree. The commerciali-
zation of a broadband optical amplifier would be
necessary before tree-like multichannel networks be-
come a reality. All-optical networks could be construct-
ed as arbitrary mesh-connected topologies using linear
combinersidividers or wavelength-selective switches.
These devices are not currently available, but active
research into their design is under way.
Technological progress in light-wave transmission
must be accompanied by progress in digital electronics.
High-speed data transmission relies on fast electronics
that can provide serial data to a transmitter at network
rates. The speed of digital electronic circuits must
therefore grow as rapidly as the speed of light-wave
transmission systems. Given that the bandwidth of a
single-mode optical fiber is in the Tbps range, it is clear
that WDM must be used to allow a serial electronic
interface to tap into this enormous bandwidth. In order
to transmit at Gbps speeds, electronic transceivers must
be clocked at GHz rates, which suggests the use of
high-performance integrated circuitry such as GaAs or
ECL. Since the processing of data-link-layer protocols
is normally hardware-assisted in high-speed LANs, it is
essential to implement state machines as integrated
circuits that can keep up with the transmission system.
Some LANs, such as HPPI, employ complex, large
switching fabrics to operate at very high speeds, which
also implies the need for technological advances in
integrated-circuit technology.
A
Taxonomy
of
Local Area
Networks
In the past LANs have been classified according to
several different criteria (topology, access protocol,
transmission medium, etc). For the purposes
of
this
section, which is focused on high-speed LANs, the
most appropriate criterion for classification is data rate.
..
we define the following four classes:
Low- and Medium-Speed LANs: Data rate up to
10
to
20
Mbps. This class includes the great
majority of conventional LANs (Ethernet, Token
ring, etc.), as well as the recently introduced
wireless LANs.
High-speed LANs: Data rates ranging from
50
to
150
Mbps. Typical entries are FDDI and DQDB.
The most common medium is the fiber.
REFERENCE DATA
FOR
ENGINEERS
Supercomputer LANs: Data rate in the order of
800
Mbps. Typical entries are UltraNet and
Nectar. Due to the limited geographical range,
the most common transmission medium is the
cable (32 or
64
parallel connections).
Ultragigabit LANs: Data rates well above the
Gbps range. Although no commercial offerings
exist in this area, several experimental prototypes
are being developed (e.g., ATT Multihop Net-
work). The medium is the single-mode fiber.
The technology of choice is Wavelength Division
Multiplexing (WDM).
Low-
and Medium-Speed LANs
The appearance of Ethernet in the late
70s
marks the
birth of first generation LANs. Within the next few
years, the Token ring and Token bus LAN architectures
also become well established, and are all eventually
standardized by the IEEE
802
committee.? These first
generation LANs have comparable characteristics in
terms of speed (around 5-10 Mbps), geographical
range (around 1000 feet), and station connectivity (a
few dozen). They offer, however, markedly differently
features
so
as to gain a competitive advantage in
different applications. For example, Ethernet prevails in
office and campus environments because of its low cost,
good fault tolerance, and easy maintenance. Token ring
and Token bus offer guaranteed delay and therefore
better real-time traffic support. In particular, the Token
bus was chosen as the MAC layer for MAP (Manufac-
turing Automation Protocol) because of its suitability
for carrying the real-time control messages common in
manufacturing plants.
A detailed survey of first generation protocols is
clearly beyond the scope of this section; the interested
reader can consult the excellent survey by Tobagi in
reference 5. Rather, we would like to comment on the
ability to scale up the speed of these LANs by one or
two orders of magnitude, from 10 Mbps to the 100-
1000
Mbps range. At the same time, we explore the
possibility of stretching the geographical coverage from
the 1-km range to the 10-km range. These speed and
range upgrades are of interest because of the broadening
of LAN applications in the early
80s.
If we denote by
T
the end-to-end propagation delay on
the bus and by
P
the frame transmission time, we find
that Ethernet performance degrades dramatically when
the ratio
a
=
TIP
becomes
1.
For channel speed
=
100
Mbps, bus length
=
10
miles, and frame length
=
1000
bits, channel utilization becomes
0.03.
The reason for
this dramatic drop is that it takes more time (on the
order of
T)
to ensure that the transmission will not suffer
a collision than to transmit the frame itself
(P
seconds).
The Token bus does not fare much better. The time to
pass the token from one station
to
the next in the polling
sequence can be
as
large as
T
plus the token processing
time. Assuming that a station transmits a single frame
per token visit, the channel utilization is given by the
following expression:
Token bus utilization
5
P/(P
+
T)
=
l/(l
+
rip)
Thus, again, utilization decreases as the product of
bandwidth times length
(B
X
L)
increases.
In contrast with Ethernet and Token bus, the Token
ring does not have any intrinsic limitations imposed by
the hardware. In principle, the ring can be maintained
fully utilized even at very high
B
X
L
products if
stations attach their frames to the token one after the
other forming a “train.” The higherB
X
L,
the larger is
the number of frames simultaneously outstanding on the
ring. However, the IEEE 802.5 standard implementa-
tion requires that only one station be allowed to
maintain one (or more) frames outstanding on the ring
at any one time.? This requirement is dictated by the
particular implementation of priorities in IEEE
802.5.
Namely, stations announce their priority in the header
of a passing frame. Thus, the station currently holding
the token must wait for the header of its frame(s) to
come back before it can reissue the token at the highest
announced priority. Assuming that each station trans-
mits one single frame per token acquisition, and letting
T’
be the ring latency (propagation
+
shift register
delay), the maximum ring utilization is
5
l/(l
+
T’/P).
Again, we find that performance degrades as
B
x
L
increases.
The interested reader can verify that in general first
generation LA architectures do not scale well with
speed and distance.§ This is not to say that such LANs
are obsolete; they are simply designed to satisfy require-
ments of the 10-Mbps, 1000-feet type.
High-speed LANs
In the early
O OS,
two separate developments contrib-
uted to the start of a new generation of LANs (and
MANS): the rapid advancement of fiber-optic technolo-
gy, and the emergence of very-high-speed local and
metropolitan applications. In the former area were the
fabrication of low-cost, low-attenuation fibers and of
high quality optical transmitters, detectors, and passive
components. In the latter area came the proliferation of
private LANs and the need to interconnect them across
metropolitan regions through a high-speed backbone.
We must thus introduce a new version of “stretched”
LAN, called the Metropolitan Area Network (MAN),
which shares many common characteristics with the
LAN, and therefore will be covered along with the
LANs in this survey.
We also note growing interest in videoconferencing
-
t
Reference
2.
t
Reference
2.
§
Reference
5.
26-33
CLASS
A
and in the integration of voice, data, and video commu-
nications in a single network. The integration is moti-
vated both by the desire to reduce network cost (by
sharing facilities) and by the need to support new
applications (e.g., multimedia communications).
To satisfy these requirements, a new family of LANs
is required, with data rates in the order of 100 Mbps and
above, with geographical coverage on the order of 10
km, and with the ability to support a large number of
stations (in the hundreds).
Also,
good fault recovery
properties are required, since metropolitan networks
span areas outside of the customer and network operator
control, and are therefore more vulnerable to link
failures.
The most natural way to meet the new challenge is to
start from first generation LAN architectures, replacing
the cable with fiber and modifying the protocols
so
as to
remove the
B
X
L
limitations observed in previous
schemes. This is exactly what happens in the case of the
ring.
Rings-FDDI (Fiber Distributed Data Interface) is
a 100 Mbps, multimode fiber ring which implements a
“multitoken” protocol (Le. several stations can simul-
taneously maintain outstanding frames on the ring). See
Fig. 20. The multitoken variant removes the inefficien-
cies of the 802.5 token ring protocol and makes it
possible to operate the ring at high speed over large
distances (up to
200
km). Priorities can, of course, no
longer be handled with header reservations. Thus, new
priority mechanisms based on maximum token rotation
time are implemented. Fault tolerance to link failures is
achieved by using a double-counter rotating ring topolo-
I
’.I
,
‘-.
WIRING CONNECTOR
:
.-.
’
,e
\8
STATION
4
CLASS A
STATION
CLASS
A
I
’.I
,
‘-.
WIRING CONNECTOR
:
.-.
’
,e
\8
STATION
1
STATION
2
STATION
6
gy. Isochronous traffic support is provided by a variant
of FDDI (called FDDI-11). In FDDI-II the ring is
slotted. Each slot corresponds to a channel that can be
reserved by isochronous traffic. The asynchronous traf-
fic is still managed by the token protocol through the
use of unreserved slots.
In FDDI and FDDI-11, each frame is removed by the
origin, after a full rotation around the ring. Efficiency
can be improved (by as much as
4
times on average) if
the destination removes the frame, thus allowing spatial
reuse of portions of the ring. A recently proposed buffer
insertion ring, the Meta Ring, does in fact offer
destination removal and spatial reuse, upgrading the
FDDI speed to 800 Mbps (using a 2-counter rotating
ring).
Linear
Buses-The linear bus topology was also
investigated for possible fiber-optic upgrade. It was
found that the fiber bus cannot be used effectively in a
bidirectional mode (such as in Ethernet), because of the
optical coupler implementation. Thus, two candidate
configurations emerged: twin parallel unidirectional
buses, and a single, unidirectional folded bus.$ Since
CSMA-CD and token bus protocols do not scale up to
high speeds, a new access protocol, called “implicit”
token (or “ordered access”) was introduced. Basically,
the implicit token is a burst of carrier issued by a
designated end station. Backlogged stations append
their frames in sequence after the token, forming a
train. Upon completion of a cycle, the end station starts
the next cycle. Good efficiency at high
B
x
L
speeds is
achieved by virtue of the fact that no time
is
wasted in
passing the token from one station to the next (in
contrast to what was happening in IEEE 802.4). In fact,
stations are automatically “polled” in sequence, based
on their position on the bus. Furthermore, no token
processing is required. One drawback of linear fiber
buses, however, is fiber and coupler attenuation. This
problem is corrected by regenerating and amplifying the
signal at each interface. Fault tolerance to link failures
is achieved by coiling the topology in a pseudo loop.
Real-time (isochronous) traffic is carried in reserved
slots, or in alternating cycles. A large number of
implicit token fiber-bus architectures were proposed and
implemented in the ’80s. Among them were Express-
Net, U-Net, and FasNet.$
An alternative approach to multiple access in linear
buses is reservation. This scheme differs drastically
from the implicit token approach in that stations are
given the opportunity to place reservations in a separate
logical channel (implemented by using special fields in
the data packet headers, or dedicated portions
of
a
cycle). Thus, the order of packet transmissions is first
come first served, as opposed to the round robin order
in token schemes.
The best known implementation of a reservation
strategy is DQDB (Distributed Queue Dual Bus), a
150-Mbps twin bus in which each station records and
-
$
Reference
6.
Fig.
20.
FDDI
topology
maintains the reservations in a local queue. In ideal
situations, all local queues are perfectly consistent with
each other, thus yielding an exact FCFS schedule. The
strong points of DQDB are simplicity and extreme
efficiency of the distributed reservation mechanism.
Reservations are piggybacked on data packets, thus
avoiding cycle latency and providing channel efficiency
close to unity for a single sending station. As in
previous protocol proposals, the bus is slotted to
provide isochronous traffic support. The bus is installed
as a pseudoloop topology to permit recovery from
single link failures (Fig.
21).
DQDB
has encountered
rapid and broad acceptance, and has been chosen as the
MAN standard by the
IEEE
802.6
committee.
Trees-During the
%Os,
new LAN and MAN
topologies such as the tree and the mesh also emerged.
Trees are particularly desirable for the efficient coverage
of metropolitan areas. A well known fiber-optics tree
architecture is Hubnet. Hubnet implements a random-
access protocol with capture (i.e., if there is a collision,
one of the contendents prevails and captures the chan-
nel). Contention resolution is implemented at the nodes
(which, therefore, include an active processing ele-
ment).
Another tree architecture with random access and
capture is CAMB (Collision Avoidance Multiple Broad-
cast). In CAMB, tree nodes have the ability to route
frames on-the-fly within subtrees (instead of sending all
frames
to
the root of the tree as in Hubnet). Subtree
routing yields spatial reuse, and therefore better overall
throughput, at the cost of additional processing in the
nodes.
A general limitation of the above tree architectures is
the inability to guarantee delays and, therefore, to
support real-time traffic.
It
will be shown later that this
limitation can be overcome by using tree topologies
with passive nodes and token or reservation access
schemes.
Grids-Spatial reuse is also the driving force behind
mesh architectures. The best known mesh architecture
is MSN (Manhattan Street Network), organized
as
a
square grid. To avoid store and forward buffering and
therefore improve efficiency at high speeds, a very
simple routing scheme, deflection routing,
is
imple-
mented at the nodes (i.e., grid crosspoints). Recall that
in
a grid each node has exactly two inputs and two
U
SLOT
GENERATOR
HEAD
OF
BUS
B
HEAD
OF
BUS
A
Fig.
21.
DQDB
topology
outputs, and consider the case of both inputs competing
for the same output. One packet
is
sent to the correct
output. The other, instead of being buffered, is sent to
the “wrong” output, and is thus forced to take a
“round-the-block” detour. This feature, albeit some-
what wasteful in terms of delivered throughput, makes it
possible to avoid nodal buffering,
thus
speeding up the
operation. The positive aspects of MSN are the good
metropolitan coverage, the simplicity of protocols and
nodal implementations, and the potentially unlimited
throughput offered by a topology with multiple concur-
rently available paths. In this sense, MSN is a major
step forward with respect to more traditional LAN and
MAN architectures, where a single broadcast channel
(bus, tree, or ring) inevitably becomes the bottleneck.
The drawback of the mesh topology, however, is the
inability to provide efficient broadcast and isochronous
traffic support, properties in which the bus, tree, and
ring topologies excel. It will be seen later how the path
concurrency of MSN and the broadcast and isochronous
support features of more conventional MANS can be
combined in a single architecture, the WON (Wave-
length division Optical Network).
Supercomputer Networks
Another important development in the area of high-
speed local and campus-wide networking
is
the emer-
gence of the networks especially designed to connect
supercomputers, massive storage devices, frame buff-
ers, and high-end graphics workstations. Typical appli-
cations are scientific visualization, load sharing among
supercomputers, and, more generally, distribution of
tasks among supercomputers and workstations. Very
high data rates (in the order
of
Gbps) are required to
support real-time applications and an interactive mode.
A high-speed interface for such “supercomputer” net-
works has been proposed, namely HPPI (previously
known as High Speed Channel), and is evaluated by an
ANSI committee. We will mention two network archi-
tectures which have been developed to interface with
HPPI and to satisfy the above needs. One is Ultranet,
basically a datagram network, consisting of high per-
formance ultrabus switches interconnected by intelli-
gent, high throughput bridges. In contrast, the CP*
network, developed by the
Los
Alamos National Labo-
ratory, is
a
fast circuit switched network. It features
crossbar switches and basically sets up a circuit for each
message exchanged across the network. Both Ultranet
and CP* operate at near Gbps speed. They have been
designed for
a
specific application and therefore cannot
be easily extended to satisfy the general requirements of
a metropolitan network. On the other hand, a challeng-
ing question for network designers is whether the future
LAN and MAN architectures will be sufficiently power-
ful and flexible to satisfy HPPI users.
26-35
U
ltragiga
bit
Networks
Many of the above architectures have been success-
fully demonstrated at speeds ranging between
100
and
200
Mbps, and some have been pushed up to Gbps
speeds. These speeds are quite adequate for introducto-
ry
LAN and MAN solutions. Traffic projections for the
mid
O OS,
however, show that a single MAN will be
required to carry simultaneously a large number of very
high speed connections (e.g., scientific visualization,
high-quality videoconferencing
,
multimedia communi-
cation, etc.) along with the support of a large population
of
more conventional users. The statistical aggregation
of these traffic components in a large metropolitan area
will probably require an overall network capacity in the
order of hundreds of Gbps. Clearly, current LANs and
MANs cannot deliver such performance. First, the
presence of active processing elements along the net-
work path poses a limitation on speed. In fact, interme-
diate station interfaces along the DQDB bus or the
FDDI ring must process in real time, at line speed (as
part of the access protocol) some of the incoming
information (as opposed to buffering it and processing it
later). For example, in DBDQ the Busy and Reservation
bits must be read and set “on the fly” in the packet
headers. Likewise in FDDI, the header of a packet must
be inspected at channel speed while it transits through
the shift register at each interface.
Another limitation common to most of the above
architectures stems from the fact that loops and rings
cannot be easily (and effectively) configured to cover a
distributed metropolitan area. The common solution is
to resort to a multilayer architecture with a backbone
loop at the top of the hierarchy and several layers of
distribution loops. The weak point of the multilayer
configuration, however, is the bridge that connects the
layers. The bridge is basically a store-and-forward
processor which buffers packets, inspects the headers,
and performs some simple flow control and traffic
filtering functions. But, simple as these functions may
be, they still pose a practical limit on the throughput
that can be handled by a bridge, probably in the order of
lOOK
packetsisecond (state of the art bridges today can
forward at most
20K
packetsisecond). Furthermore, it
will be difficult to satisfy the tight delay constraints of
voice and video connections across several bridges.
Manhattan Street Networks can potentially yield the
desired throughput (by exploiting parallelism, spacial
reuse, and locality) and can provide efficient metropoli-
tan coverage. However, they cannot efficiently support
broadcast and real time services. Also, they require
fairly sophisticated controls in order to avoid unfairness
and congestion.
Finally, none of the above architectures are well
suited to exploiting WDM (Wavelength Division Multi-
plexing). WDM makes it possible to maintain multiple
channels in a fiber and can, in principle, expand the
effective data rate of a single fiber from the Gbps to the
Tbps range. In order to implement WDM, an FDDI or
DQDB network requires a splitter,
a
filter, and a
combiner at each interface, plus a wideband amplifier to
make up for the power loss-a very expensive proposi-
tion!
The above considerations suggest that in order to
achieve ultragigabit speeds, the network must be totally
“transparent” to WDM, and thus must avoid any
processing components (e.g., shift registers, busy-bit
manipulators, bridges, etc.) along the communications
path between source and destination. This has led to the
development of a new generation
of
LANs and MANs,
based on passive optical components and WDM tech-
niques.
The key components of a wavelength division optical
network are:
Passive optical network, including couplers, split-
ters, combiners, and optical amplifiers. Electrical-
ly controllable couplers and switches are also
required for some proposed architectures.
Wavelength division gear, namely: tunable lasers,
detectors (conventional and coherent), and filters.
For some architectures, wavelength switches are
also required.
Network management, to control wavelength allo-
cation and dynamically reconfigure the virtual
topologies according to traffic patterns and user
demands.
Several wavelength division proposals and prototypes
have been reported in the literature. The most common
architecture consists of a passive optic broadcast medi-
um (star, tree, bus)-the so-called “mass of glass”-
on which several wavelengths (a few dozen with conven-
tional, coarse WDM; thousands with coherent, dense
WDM) can be multiplexed. The multiplexing and
switching are done at the perifery
of
the “mass of
glass.” Indeed, the main challenge is how to use this
abundance of bandwidth efficiently (Le., channel access
control).
Two main approaches have been proposed. The first
approach is the timeifrequency division approach. A
global, time-slotted reference frame is defined
(as
on a
satellite multiple access channel). A source/destination
pair must reserve in advance a slot in the frame for the
transmission of each packet and must agree
on
the
frequency (Le., wavelength) to be used. This system
can achieve high efficiency, but it involves high over-
head for sourceidestination coordination and high cost
(and technology
risk)
due
to
the
quickly
retunable
transmitters and receivers.
The second approach assigns a limited number
of
fixed wavelengths to each user station (say two for
transmission and two for reception). By means of these
wavelengths, users can interconnect with each other
with a “virtual” topology (as opposed to the “physi-
cal” topology-e.g., a star or a tree-corresponding to
the fiber layout). Fig.
22
shows a virtual topology. in
this case a “perfect shuffle” topology, mapped on a