Middleton W.M. (ed.) Reference Data for Engineers: Radio, Electronics, Computer and Communications
Подождите немного. Документ загружается.
REFERENCE
DATA
FOR ENGINEERS
26-16
CRC-
CRC-
6
=
x16
+
xI5
+
x2
+
1
CRC-CCITT
=
x16
+
XI’
+
x5
+
la
Of the three techniques (VRC, LRC, and CRC), CRC
offers the best protection against undetected errors.
Error-free transmission of messages is accomplished
by the use of the ACK and NAK control characters in
conjunction with an error-detection procedure and the
retransmission
of
blocks with errors. Moreover, timers
are provided at both the sender and the receiver in order
to
recover from abnormal conditions. The
response
rimer
(typically 2-3 seconds) at the sending station
protects against invalid or missing response, and the
receive timer (about 500
ms)
protects against failure to
receive or recognize ETB or ETX. With these defini-
tions and features, ANSI 3.28 specifies
a
number of
specific protocols, each suitable to
a
particular scenario
(or
situation). For example, “subcategory
2.4”
is for
two-way alternate transmission
on
a
nonswitched multi-
point configuration with centralized operation; “subcat-
egory D1” is for message-independent blocking, with
cyclic checking, alternating acknowledgements, and
transparent heading and text.
Bit-Oriented
DLC
Protocols-A number of defi-
ciencies exist in character-oriented DLC protocols.
First
of
all,
such protocols are best suited for the
two-way alternate transmission mode (Le., half-duplex
transmission) and thus make inefficient use of full-
duplex lines. Secondly, error checking is done only
on
text, leaving control sequences unprotected, and thus
leading to complex recovery procedures. Thirdly,
a
single data link function is performed with each trans-
mission (e.g., either data transmission, or acknowl-
edgement, or polling command, etc.), which leads to
a
larger number of turnarounds and to
an
unsatisfactory
ratio of data transfer exchange to control exchange.
Finally, character-oriented DLC protocols are too rigid
and do not allow for easy expansion.
The new bit-oriented DLC protocols have been
designed
to
overcome all the above limitations. Exam-
ples are ANSI’s Advanced Data Communication Con-
trol Protocols (ADCCP), ISQ’s High-Level Data Link
Control (HDLC), and
IBM’s
Synchronous Data Link
Control (SDLC). The ADCCP and HDLC protocols are
compatible. In this discussion, ADCCP is used to
illustrate hit-oriented DLC protocols.
Bit-oriented DLC protocols have been designed to
support
all
possible environments: point-to-point and
multipoint configurations using two-way alternate or
two-way simultaneous operation over switched and
nonswitched transmission lines, with both terrestrial
and satellite connections. Three data transfer modes
have been defined: the normal response mode (NRM)
and the asynchronous response mode (ARM) for use in
point-to-point and multipoint configurations, and the
asynchronous balanced mode (ABM) for use in point-
to-point configurations. In NRM and ARM,
a
so-called
primary station
controls the operation
of
the data link,
while one
or
more
secondary stations
act
as
subservient
to the primary. The primary issues commands and
receives responses; the secondary station receives com-
mands and issues responses in accordance with the
command received and the mode of operation.
In
NRM,
a
secondary station initiates transmission only
as
a
result of receiving explicit permission to do
so.
This
mode is suitable for polled multipoint operation be-
tween
a
central location and
a
number of outlying
stations. In ARM,
a
secondary station can initiate
transmission without waiting for an explicit permission.
It is suitable for
a
single primary and
a
single activated
secondary wishing to transmit freely to one another
without the overhead of polling. The ABM mode
provides a
balanced
type of data transfer between two
stations referred to
as
logically equal
or
combined
stations. Each station operates
as
a
primary for its data
transfer, and is thus capable of initializing the link,
activating the other combined station, and logically
disconnecting the link. Typically, each combined sta-
tion may be
a
host computer. an intelligent network
node (e.g., a packet-switching node), or
a
highly
intelligent terminal that has the capability
to
control the
data link.
In bit-oriented DLC protocol, the basic transmission
unit is called
a
frame.
In order to achieve enhanced
es over character-oriented DLC protocols,
a
well defined frame format
as
shown
in
Fig.
15
is used,
including
an
address field,
a
control field, and
a
frame
check sequence (FCS).
The flag sequence
(F)
is the unique eight-bit pattern
01111110
used to delimit the start and end of each
frame, and to fill idle time between frames during the
transmission of multiple frames. In order to prohibit the
occurrence of the flag in the address. control, informa-
tion, and FCS fields, and thus achieve transparency,
a
technique called bit-stuffing is used. The transmitter
inserts
a
0
bit following any five contiguous
1
bits
encountered in the above mentioned fields; the receiver
deletes the
0
bit following five contiguous
1
bits
following
a
0
bit anywhere before receiving the closing
flag sequence.
The address field in
a
command frame identifies the
station (secondary or combined) that is to receive the
command; in
a
response frame, it identifies the station
(secondary or combined) that is sending the frame.
Thus in NRM and ARM, the address always identifies
the secondary station; in ABM, it identifies the re-
sponse-generating portion
of
a combined station. There
are two mutually exclusive address-field options: either
a
single octet accommodating up to 256 stations, or
multiple octets recursively extendable by having the first
hit of each octet be
a
1
bit if the octet is the last one in
the address or a
0
bit otherwise. Broadcast addressing is
also possible by using the all-zero address.
The control field identifies the function and purpose
of
the frame. Three different formats exist, defining the
three types of frames: information transfer type
(I
26-17
01111110
ADDRESS CONTROL DATA CHECKSUM
OllIlllO
frame), supervisory type
(S
frame), and unnumbered
type
(U
frame). See Fig. 16. The PIF bit in the control
field provides for a check-pointing mechanism allowing
a response frame to be logically associated with the
appropriate initiating command frame. In NRM, the
primary station sets the PIF bit to
1
to
poll
a
secondary
station. The secondary station sets PIF to 1 in the last
frame sent in response to a poll. In ARM and ABM,
receipt of a frame with the PIF bit set to 1 causes the
responding station to set the
PIF
bit to 1 in the next
appropriate frame.
The I frames are used to transfer user information
across a data link. A so-called
window mechanism
is
used to guarantee sequential error-free delivery of the
information without degrading the performance
of
the
link. Successive frames are numbered sequentially
(modulo some number
2"),
where the numbers range
from
0
to the maximum, 2"
-
1.
The frame sequence
number is transmitted in the control field
N(S).
The
sender maintains a list of consecutive sequence numbers
called the
sending window
corresponding to frames it is
permitted to send. Likewise, the receiver maintains a
list of consecutive sequence numbers called the
receiv-
ing window
for frames it is permitted to receive. Most
acknowledgements in these DLC protocols are handled
in a
piggyback
fashion. A receiver that has correctly
received all frames numbered up to some number,
k,
will send in the
N(R)
field of the next
I
frame the
number
N(R)
=
k
+
1;
i.e., the sequence number of the
next frame the receiver is expecting. In case an
I
frame
is not ready for transmission, the receiver will send an
S
frame with
N(R)
=
k
+
1.
Upon receiving an acknowl-
edgement, the sender advances the lower edge of its
sending window to
N(R)
and the upper edge to
N(R)
+
W,.
The sequence numbers of frames already transmit-
ted that are within the sender window represent frames
sent but
as
yet not acknowledged. The window size,
W,
,
represents the maximum number of such frames. It
is determined
as
a
function
of
the frame transmission
time and the end-to-end propagation delay
SO
as
to "fill
,
1
0
s
SUPERVISORY COMMANDS
f
RESPONSES
IS
FRAME1
the pipe" and achieve high throughput. This feature is
particularly important when dealing with wideband
satellite channels where the ratio of round-trip delay to
frame transmission time is high. The receive window,
W,,
is
determined
as
a function of the buffer space
available at the receiver. The sending window,
W,,
and
receive window,
WR,
need not be the same. The
window mechanism protects against the loss of
a
frame
and the loss
of
acknowledgement, detects and filters out
duplicates, and guarantees that the network level re-
ceives the frames in sequential order. It is important,
however, that the condition
Ws
+
WR
5
2"
be satisfied.
In the ADCCP and HDLC standards, two sequence
ranges are available: the unextended case, which is
modulo
8,
and the extended case, which is modulo 128.
There are four supervisory frames. Receive ready
(RR) is used to indicate that the receiver is ready to
receive I frames; receive not ready (RNR) is used to
indicate
a
temporary busy condition. Both RR and
RNR
S
frames acknowledge I frames already received.
Reject (REJ) is used to request retransmission
of
all
I
frames starting with N(R); selective reject (SREJ) is
used to request the retransmission of a single designated
I
frame, N(R).
There are 32 U-frame commands and/or responses
that can be defined, although fewer than
32
are in fact
determined in the current standards. They do not
contain a sequence number and thus are not accounted
for in the normal flow of frames. They are mainly used
in the control of the data link. Examples are: the set
mode commands (SNRM, SARM, SABM, etc.), dis-
connect command
(DISC),
an unnumbered poll com-
mand, an unnumbered information (UI) command/
response, an unnumbered acknowledgement (UA), and
a frame reject (FRMR). (The frame reject
is
used to
indicate that a received frame was in error and cannot be
corrected by retransmission, such
as,
for example, an
information field greater than the maximum established
length, receipt of a control field that
is
either invalid
or
not implemented, etc.)
s
P/f-
hIR1
12345678
RESPONSES (U FRAME)
1
INFORMATION TRANSFER COMMAND:
I
RESPONSE
(I
FRAME1
Fig.
16.
Control
field
formats
in
ADCCP.
(FromPuulE. Green,
Jr.,
Computer
Network
Architectures
and
Protocols,
0
1982.
Used
by
permission
of
Plenum Publishing Corp., New York.)
REFERENCE DATA FOR ENGINEERS
The FCS consists of the 16-bit checksum obtained
from the CRC error detection technique using the
CRC-CCITT generator. An optional 32-bit FCS is also
available if a higher degree of error detection is needed.
The corresponding generator polynomial is
x32
t
x26
t
+
x2
+
x
+
1.
Just as with character-oriented DLC
protocols, classes of procedures are defined in order to
provide organization and direction for the application of
the bit-oriented data link control procedures. Certain
commands belong to all the classes, while others are
viewed as being optional. Examples are: UNC, 3,
4-unbalanced NRM with SREJ and UI capabilities;
BAC, 2, 8-balanced ABM with REJ and the restric-
tion on the use of
I
frames as commands only.
x23
+
x22
t
x16
+
x12
+
XI1
+
XI0
+
x*
+
x7
+
x5
+
x4
MULTIACCESS LINK CONTROL
Multiaccess protocols arise whenever a communica-
tion channel is shared by many independent contending
users. Two major factors contribute
to
a multiaccess
situation: the need to share an expensive communica-
tion channel in order to achieve its efficient utilization,
and the need to provide a high degree
of
connectivity for
communication among independent subscribers. The
main issue of concern is how to control access to the
common channel to allocate the available bandwidth
efficiently. The solutions to this problem form the set
of
protocols known
as
multiaccess protocols. These proto-
cols and their performance differ according to the
environment and the specific requirements to be satis-
fied.
In
satellite channels, there is an inherent long
propagation delay of approximately
0.25
s,
a delay that
is usually long compared to the transmission time of a
packet given the bandwidth usually available. In ground
radio environments, the opposite is true: the transmis-
sion radius is relatively small due to a limited power
supply at the radio units and a heavy signal attenuation,
and the data rate is relatively low,
so
that the propaga-
tion delay
is
relatively short compared to the transmis-
sion time of a packet. Finally, local area environments
are characterized by a large and often variable number
of inexpensive devices; they call for networks with
simple topologies and inexpensive connection interfac-
es; the propagation delay
is
short but the bandwidth can
be high; the propagation delay may
or
may not be larger
than the packet transmission time.
Multiaccess schemes are evaluated according to vari-
ous
criteria: bandwidth utilization, message delay, the
ability to support traffic of different types simultaneous-
ly
(with different priorities, variable message lengths,
and differing delay constraints), and robustness (defined
here as the insensitivity to errors resulting in misinfor-
mation).
Multiaccess protocols differ by the static or dynamic
nature of the bandwidth allocation algorithm, the cen-
tralized or distributed nature
of
the decision-making
process, and the degree of adaptivity
of
the algorithm to
changing needs. Accordingly. these protocols can be
grouped into several classes described hereafter.
Fixed Assignment Techniques
Fixed assignment techniques consist of allocating the
channel to the users, independently of their activity, by
partitioning the time-bandwidth space into slots that are
assigned in a static predetermined fashion. These tech-
niques take two common forms: orthogonal, such as
frequency division multiple access (FDMA) or synchro-
nous time division multiple access (TDMA), and
“quasi-orthogonal,
’*
such as code division multiple
access (CDMA)
.
The FDMA technique consists of assigning to each
user a fraction of the bandwidth and confining its access
to the allocated subband. Orthogonality is achieved in
the frequency domain. The TDMA technique consists
of assigning fixed predetermined channel time slots to
each user; the user has access to the entire channel
bandwidth, but only during its allocated slots. Here,
signaling waveforms are orthogonal in time. The
TDMA approach is more complex to implement than
FDMA, but an important advantage is the connectivity
that results from the fact that all receivers listen to the
same channel while senders transmit on the same
common channel at different times. Accordingly, with
TDMA, many network realizations, both in ground and
satellite environments, are easier to accomplish.
The CDMA technique allows overlap in transmission
both in the frequency and time coordinates. It achieves
orthogonality by the use of different signaling codes in
conjunction with matched filters (or equivalently, corre-
lation detection) at the intended receivers. Each user is
assigned a particular code sequence. which is modulat-
ed on the carrier with the digital data modulated on top
of that. Two common forms exist: the frequency-
hopped SSMA and the phase-coded SSMA. In the
former, the frequency is periodically changing accord-
ing to some known pattern; in the latter, the carrier
is
phase modulated by the digital data sequence and the
code sequence. Multiple orthogonal codes are obtained
at the expense of increased bandwidth requirements (in
order to spread the waveforms). With CDMA, there is
also a lack of flexibility in interconnecting all users
(unless, of course, matched filters corresponding to all
codes are provided at all receivers). However, CDMA
has the advantage of allowing the coexistence of several
systems in the same band, as long as different codes are
used for different systems.
Random Access Techniques
Since data traffic in computer communication is
characterized as bursty, a more advantageous approach
than fixed assignment is to provide a single sharable
high-speed channel to the large number of users. The
strong law of large numbers then guarantees that, with a
very high probability, the demand at any instant will be
approximately equal to the sum of the average demands
of that population. When dealing with shared channels
in a packet-switched mode, one must be prepared to
resolve conflicts that arise when more than one demand
COMPUTER COMMUNICATIONS NETWORKS
26-19
is placed on the channel. For example, in packet-
switched channels, whenever a portion of the transmis-
sion of one user overlaps with the transmission
of
another user, then the two collide and “destroy” each
other (unless
a
code division multiple-access scheme is
used). The existence of some positive acknowledgement
scheme permits the transmitter to determine if
a
trans-
mission is successful or not.
ALOHA-Pure ALOHA permits
a
user to transmit
any time it desires. If a user transmits a packet, and
within some appropriate time-out period following its
transmission it receives an acknowledgement from the
destination, then it knows that no conflict occurred.
Otherwise, it assumes that a collision occurred and it
must retransmit. To avoid continuously repeated con-
flicts, the retransmission delay is randomized across the
transmitting devices, thus spreading the retry packets
over time.
A slotted version, referred to
as
slotted
ALOHA,
is obtained by dividing time into slots of
duration equal to the transmission time of
a
single
packet (assuming constant-length packets), Each user is
required to synchronize the start of transmission of its
packets to coincide with the slot boundary. When two
packets conflict, they will overlap completely rather
than partially, providing an increase in channel efficien-
cy over pure ALOHA. Due to conflicts and idle channel
time, the maximum channel efficiency available with
ALOHA is less than 100 percent,
18
percent for pure
ALOHA and
36
percent for slotted ALOHA. Note that,
although the maximum achievable channel utilization is
iow
,
the ALOHA schemes are superior to fixed assign-
ment schemes when there is a large population of bursty
users and low packet delay is of the essence. (See
reference
3.)
Carrier Sense
Multiple
Access (CSMA)-In the
CSMA technique, an attempt is made to avoid colli-
sions by listening to the carrier due to transmission from
another user before transmitting, and inhibiting trans-
mission if the channel is sensed busy. This is advanta-
geous when the propagation delay between any source-
destination pair is small compared to the packet trans-
mission time. Many CSMA protocols exist; they differ
according to the action that
a
terminal takes to transmit
a packet after sensing the channel. In all cases, however,
when
a
terminal learns that its transmission has incurred
a
collision, it reschedules the transmission of the packet
according to a randomly distributed delay. At this new
point in time, the transmitter senses the channel again
and repeats the algorithm dictated by the protocol. In
nonpersistent
CSMA,
a
ready terminal senses the
channel and operates
as
follows. If the channel
is
sensed
idle, the terminal transmits the packet. If the channel
is
sensed busy, then the terminal schedules the retransmis-
sion of the packet to some later time according to the
retransmission delay distribution. At this new point in
time, it senses the channel and repeats the algorithm
described.
In the
1-persistent
CSMA protocol, a ready terminal
senses the channel and operates
as
follows. If the
channel is sensed idle, it transmits the packet with
probability one. If the channel
is
sensed busy, it waits
until the channel goes idle and then immediately
transmits the packet with probability one. In l-persis-
tent CSMA, whenever two or more terminals become
ready during a packet transmission period. they wait for
the channel to become idle (at the end of that transmis-
sion), and then they all transmit with probability one.
A
conflict will also occur with probability one. Random-
izing the starting time of transmission of packets
accumulating at the end of
a
transmission period
reduces interference and improves performance. The
p-persistent
scheme involves including an additional
parameter
p,
the probability that
a
ready packet persists
(1
-
p
being the probability of delaying transmission by
T
seconds, where
7
is the maximum propagation delay
among all pairs). Parameter
p
is chosen to reduce the
level of interference while keeping the idle periods
between any two consecutive nonoverlapped transmis-
sions as small
as
possible.
The CSMA technique has been applied
to
ground
radio (e.g., PRNET), and to local area communications
(e.g., ETHERNET). In ETHERNET, CSMA is used
on
a
tapped coaxial cable to which
all
the communicat-
ing devices are connected. On the coaxial cable, in
addition to sensing carrier, it is possible for the trans-
ceivers to detect collisions. This is achieved by having
each transmitting device compare the bit stream it is
transmitting to the bit stream it sees on the channel.
When transmitting users detect interference among
several transmissions (including their own), they abort
the transmission of colliding packets. This variation of
CSMA is referred to as
carrier sense multiple access
with collision detection
(CSMA-CD).
The performance of CSMA is heavily dependent on
the ratio,
a,
of
propagation delay to packet transmission
time. The maximum throughput of
a
CSMA protocol
degrades significantly as
a
gets larger. For a ratio
a
=
0.01,
nonpersistent CSMA achieves a channel utiliza-
tion equal to
0.8
15,
a
significant improvement over the
ALOHA schemes.
While until recently most of the concepts described
in this section had been realized in experimental
systems (namely, the ALOHA System, PRNET, and
Xerox’s experimental ETHERNET),
it
is important to
note that today many contention systems of the
ETHERNET type are available on the market. Exam-
ples are the Hyperchannel and the Hyperbus of Network
Systems
Corporation, 2-Net
of
Zilog, Omninet
of
Corvus, and ETHERNET itself. The latter has been
announced
as
a
product made available jointly by Xerox
Corporation, Digital Equipment Corporation, and
INTEL. Complete specifications of the data link and
physical link protocols have been issued and constituted
the basis of
a
standard for the IEEE Computer Society
Project
802
on the standardization of local networks.
A
key feature that distinguishes this product from other
already available systems is the LSI implementation
of
many of the data link and physical link protocols. The
LSI
implementation of network protocols clearly marks
a trend in the evolution of computer networking, a trend
that is indicative of the existence of a wide market and
the need to provide reasonably priced components.
Busy-Tone Multiple Access (BTMA)-In
ground radio environments, it is possible for two
terminals to be within range of the intended receiver,
but out of range of each other or separated by some
physical obstacle opaque to radio signals. The existence
of hidden terminals in such an environment significant-
ly
degrades the performance of CSMA. The hidden-
terminal problem can be eliminated by frequency divid-
ing the available bandwidth into two separate channels,
a busy-tone channel and a message channel, thus giving
rise to
busy-tone multiple access
(BTMA). As long as a
node senses carrier on the message channel, it transmits
a (sine wave) busy-tone signal on the busy-tone channel.
It is by sensing carrier on the busy-tone channel that
nodes determine the state of the message channel. The
action that a node takes pertaining to the transmission
of the packet is again prescribed by the particular
protocol being used, similar to those described for
CSMA.
Capture-Capture in narrow-band channels can be
defined as the ability of a receiver to receive a packet
successfully (with nonzero probability) although the
packet is partially or totally overlapped by another
packet transmission. Capture is mainly due to a discrep-
ancy in receive power between two signals that allows
the receiver to receive the stronger correctly; both
distance and transmit power contribute to this discrep-
ancy. Clearly, capture improves the overall network
performance, and, by means of adaptive transmit power
control, it allows one to achieve either fairness to all
users or intentional discrimination.
Spread-Spectrum Multiple Access (SSMA)-
The SSMA technique is considered here to be a CDMA
scheme. In one form
of
SSMA for packet radio, all
transmitters employ the same code. Security, coexis-
tence with other systems, and the ability to counteract
the effects of multipath and capture are key benefits of
SSMA. Contrary to the case
of
nonspread systems, the
effect of interference in SSMA is minimized by the
“capture effect,” defined as the ability of the receiver
to “lock on” one packet while all other overlapping
packets appear as noise. The receiver locks
on
a packet
by correctly receiving the preamble appended to the
front of the transmitted packet. As long as the pream-
bles of different packets do not overlap in time, and the
signal strength of the late packets is not too high,
capture of the earliest packet occurs with a high
probability. In essence, SSMA allows a packet to be
captured at the receiver, while CSMA allows a user to
capture the channel. It is possible to use CSMA in
conjunction with SSMA, but the channel sensing is
more difficult. This mode will have the benefit of
keeping away all users within hearing distance of the
transmitter and thus help keep the capture effect and
antijamming capability of the system at the desired
level,
Centrally Controlled Demand
Assignment
Demand assignment techniques require that explicit
information regarding the need for the communication
resource be exchanged. These techniques may be either
centralized, whereby a central scheduler performs the
assignment, or distributed, whereby all stations take
active part in the assignment. Centrally controlled
techniques are addressed in the present subsection.
Circuit Oriented Systems-In circuit oriented
systems, the bandwidth is divided into FDMA or
TDMA subchannels that are assigned on demand. The
satellite SPADE system, for example, has a pool of
FDMA subchannels that are allocated on request. It
uses one subchannel operated in a TDMA fashion with
one slot per frame permanently assigned to each user
to
handle the requests and releases of FDMA circuits.
Intelsat’s MAT-1 system uses the TDMA approach.
The TDMA subchannels are periodically reallocated to
meet the varying needs
of
earth stations.
The Advanced Mobile Phone Service (AMPS), intro-
duced by Bell Laboratories, is another example of
a
centrally controlled FDMA system. The uniqueness of
this system, however, lies in an efficient management of
the spectrum based on space division multiple access
(SDMA). That
is,
each subchannel in the pool of
FDMA channels
is
allocated to different users in
separate geographical areas, thus considerably increas-
ing the spectrum utilization. To accomplish space
division, the AMPS system has a cellular structure and
uses a centralized handoff procedure (executed by a
central office) that reroutes the telephone connections to
other available subchannels as the mobile users move
from one cell to another.
Polling Systems-In packet oriented systems, poll-
ing consists of having a central controller send polling
messages to the terminals, one by one, asking the
polled terminal to transmit. If the polled terminal has
something to transmit, it goes ahead; if not, a negative
reply (or absence of reply) is received by the controller,
which then polls the next terminal in sequence. Polling
requires this constant exchange of control messages
between the controller and the terminals and
is
efficient
only if
(1)
the round-trip propagation delay is small,
(2)
the overhead due to polling messages is low, and
(3)
the
user population is not a large bursty one.
Adaptive Polling
or
Probing-The primary limi-
tation of polling in lightly loaded systems is the high
overhead incurred in determining which of the termi-
nals have messages. A modified polling technique
called
probing,
based on a tree searching algorithm,
helps decrease this overhead. This technique assumes
that the central controller can broadcast signals to all
terminals. First the controller interrogates all terminals,
asking if any of them has a message to transmit, and
repeats this question until some terminals respond by
putting a signal on the line. When a response is
received, the central station divides the population into
subsets (according to some tree structure) and repeats
the question to each of the subsets. The process is
continued until the terminals having messages are
identified. When a single terminal is interrogated, it
transmits its message. This probing technique can be
made adaptive by having the controller start a cycle by
probing groups of smaller size as the probability of
terminals having messages to transmit increases.
Split-Channel Reservation Multiple Access
(SRMA)-An attractive alternative to polling is the
use
of
explicit reservation techniques. In dynamic
reservation systems, it is the terminal that makes a re-
quest for service
on
some channel whenever it has a
message to transmit. The central scheduler manages
a
queue of requests and informs the terminal of its
allocated time. In SRMA, the available bandwidth is
divided into two channels, one used to transmit control
information and the second used for the data messages
themselves. The request channel is operated in a ran-
dom access mode (ALOHA or CSMA). Upon correct
reception of the request packet, the scheduling station
computes the time at which the backlog
on
the message
channel will empty and transmits back to the terminal
an answer packet containing the address of the terminal
and the time at which it can start transmission.
Demand Assignment With
Distributed Control
There are two reasons why distributed control is
desirable. The first is reliability; with distributed con-
trol the system
is
not dependent
on
the proper operation
of a central scheduler. The second is improved
perform-
ance,
especially when dealing with systems with long
propagation delays, such as those using satellite chan-
nels. The basic element underlying all distributed
algorithms is the need to exchange control information
among the users, either explicitly or implicitly. Using
this information, all users then execute independently
the same algorithm, with the result that there is some
coordination in their actions.
Reservation-ALOHA-Reservation-ALOHA for
a satellite channel is based on a slotted time axis where
the slots are organized into frames of equal size. The
duration
of
a frame must be greater than the satellite
propagation delay.
A
user that has successfully accessed
a slot in a frame is guaranteed access to the same slot in
the succeeding frame, and this continues until the user
stops using it. “Unused” slots, however, are free to be
accessed by
all
users in a slotted ALOHA contention
mode. A slot in a frame is an unused slot if in the
preceding
frame it either was idle or contained a
collision. Users need simply to maintain a history of the
usage of each slot for just one frame duration. Since
no
request is explicitly issued by the user, this scheme has
been referred to as an
implicit reservation
scheme.
Clearly, Reservation-ALOHA is effective only if the
users generate stream type traffic or long multipacket
messages. Its performance will degrade significantly
with single packet messages, since every time
a
packet
is successful the corresponding slot in the following
frame
is
likely to remain empty.
A First-in First-out (FIFO) Reservation Scheme
-In this scheme, reservations are made explicitly.
Time division is used to provide a reservation sub-
channel. The channel time is slotted
as
before, but every
so
often a slot is divided into
V
small slots that are used
for the transmission of reservation packets (as well as
possibly acknowledgements and small data packets);
these packets contend
on
the
V
small slots in a slotted
ALOHA mode. All other slots are data slots and are
used
on
a reservation basis, free
of
conflict. To execute
the reservation mechanism properly, each station must
maintain information
on
the number of outstanding
reservations (the “queue in the sky”) and the slots at
which its own reservations begin. These
are
determined
by the
FIFO
discipline based on the successful reserva-
tions received. To maintain synchronization of control
information at the proper time and to acquire the
correct count of packets in the queue if out-of-sync
conditions
do
occur, each station sends information
regarding the status
of
its queue in its data packet. This
information is also used by new stations that need to
join the queue. The robustness of this system is
achieved by a proper encoding of the reservation packets
to increase the probability
of
their correct reception at
all
stations.
A Round-Robin
(RR)
Reservation Scheme-The
basis of this scheme is fixed TDMA assignment, but
with the major difference that “unused” slots are
assigned
to
the active stations on a round-robin basis.
This is accomplished by organizing packet slots into
equal-size frames of duration greater than the propaga-
tion delay and such that the number of slots in
a
frame is
larger than the number of stations. One slot in each
frame is permanently assigned to each station. To allow
other stations
to
know the current state (used or unused)
of its own slot, each station is required to transmit
information regarding its own queue
of
packets piggy-
backed in the data packet header (transmitted in the
previous frame). A zero count indicates that the slot in
question is free. All stations maintain a table of the
queue lengths
of
all
stations, allowing them to allocate
among themselves unassigned slots in the current
frame. Round-robin
or
other scheduling disciplines can
be used. A station recovers its slot by deliberately
causing a conflict in that slot, which other users detect.
Distributed
Tree
Retransmission Algorithms-
Tree algorithms are based
on
the observation that a
contention among several active sources is completely
resolved if and only if
all
the sources are somehow
subdivided into groups such that each group contains at
most one active source. (See probing in the section
on
centrally controlled demand assignment
.)
Each source
corresponds to a leaf
on
a
binary
tree. The channel time
26-22
axis
is
slotted, and the slots are grouped into pairs.
Each slot in a pair corresponds to one of the two
subtrees of the node being visited. Starting with the root
node of the tree, we let all terminals in each of the two
subtrees of the root transmit in their corresponding
slots. If any of the two slots contains a collision, then
the algorithm proceeds to the root of the subtree
corresponding to the collision and repeats itself. This
continues until all the leaves are separated into sets such
that each of them contains at most one packet. This
is
known to all users, as the outcome of the channel is
either a successful transmission or an idle slot. Colli-
sions caused by the left subtree (first slot of a pair) are
resolved prior to resolving collisions in the right sub-
tree. This scheme provides a maximum throughput of
0.347
packetsislot. Clearly, a binary tree is not always
optimum. If, each time a return to the root node is
made, the tree is reconfigured according to the current
traffic conditions, it can be shown that the optimum tree
is binary everywhere except for the root node, whose
optimum degree depends
on
traffic conditions.
The preceding four schemes have been proposed for
satellite channels. All assumed fixed-size slots, and thus
can be implemented in systems that have been built for
synchronous TDMA. If used in systems with small
propagation delay, such as ground radio, then they will
perform significantly better. Due to the inherent small
propagation delay in ground radio and local environ-
ments, other access modes with distributed control are
also possible if all devices are in line-of-sight and
within range of each other. A description of these
follows.
Minislotted Alternating Priorities (MSAP)-
The MSAP technique is a “carrier-sense” version of
polling with distributed control. The time axis is slotted
with the slot size again equal to the maximum propaga-
tion delay (and referred to hereafter as a minislot). All
users are synchronized and may start transmission only
at the beginning of a minislot. Users are considered to
be ordered from
1
to
M.
When a packet transmission
ends, the alternating priorities (AP) rule assigns the
channel to the same user that transmitted the last packet
(say user
i)
if it is still busy; otherwise the channel is
assigned to the next user in sequence (i.e., user [i(mod
M)
+
11).
The latter (and all other users) detects the end
of
transmission
of
user
i
by sensing the absence of
carrier over one minislot. At this new point in time,
either user [i(mod
M)
+
11
starts transmission of a
packet (which will be detected by all other users) or it is
idle, in which case a minislot is lost and control
of
the
channel is handed to the next user in sequence. The
overhead at each poll in this scheme is one minislot.
Scheduling rules other than AP are
also
possible, such
as round-robin and random order.
The Assigned-Slot Listen-Before-Transmission
Protocol-Time is minislotted and divided into
frames, each containing an equal number
of
minislots
(say
L).
To
each minislot of a frame is assigned a given
subset
of
MIL
users.
A
user with a packet ready for
transmission in a frame can sense the channel only in its
assigned minislot. If the channel is sensed idle, trans-
mission takes place; if not, the packet is rescheduled for
transmission in a future frame. Parameter MIL is
adjusted according to the load placed on the channel.
For
high throughput, MIL
=
1
is found to be optimum,
and the scheme becomes a conflict-free one that ap-
proaches MSAP. For very low throughput, MIL
=
M
(Le.,
L
=
1)
is found to be optimum; this corresponds
to pure CSMA. In between the two extreme cases,
intermediate values of MIL are optimum.
The
URN
Scheme-The time axis is divided into
packet slots, and all users are synchronized. Assuming
that
all
users know the exact number,
n,
of busy users,
the scheme consists of giving full access right (i.e., the
right to transmit with probability
1)
to some number,
k,
of users. A successful transmission will result if there is
exactly one busy user among these
k.
The probability of
such an event is maximized when
k
=
LMIn], where
[MIn] denotes the integer part of MIn. Assume the
system is lightly loaded (for instance
n
=
1).
A large
number
of
users are given access right (in the example
n
=
I,
the number is
k
=
M),
but only a few and
hopefully only one will make use of it (in the example
n
=
1, a successful transmission takes place). As the
load increases,
k
decreases and the access right is
gradually restricted. For the extreme case of
n
=
M,
k
=
1
and the scheme converges to TDMA. One
possible scheme for estimating
n
with good accuracy is
to
include a single reservation minislot at the beginning
of each data slot. An idle user that turns busy sends a
standard reservation message of few bits. All users are
able to detect the following three events: no new busy
users, one new busy user, and more than one new busy
user (termed an erasure). As it is impossible with this
minimal overhead to estimate the exact number of new
busy users when the latter
is
greater than one, errors in
estimation result; however analysis and simulation have
shown that this error is negligible and, furthermore,
that the scheme is insensitive to small perturbations in
n.
This last statement is even more important with
respect to the robustness of the scheme, since it means
that all users need not have exactly the same estimate for
n.
As for coordinating the selection
of
the
k
users. an
effective mechanism
is
the use
of
synchronized
pseudorandom generators at all users, which allow
them to draw the same
k
pseudorandom numbers.
Another mechanism, referred to as a round-robin slot
sharing window mechanism, consists
of
having a win-
dow
of
size
k
move over the population space. When a
collision occurs, the window stops and decreases in
size. When there is no collision, the tail of the window
is advanced to the head of the previous window, and the
size is again set to
k
as determined by
12.
Distributed Control Algorithms in Local Area
Networks-In addition to the random-access schemes
described previously, all above algorithms are also
applicable to local-area (broadcast)
bus
networks, as
COMPUTER COMMUNICATIONS NETWORKS
26-23
these exhibit the required characteristics of small propa-
gation delay and full connectivity. But in local-area
communication, a slightly different topology, namely
the
ring
(or loop), has also been widely considered. As
described previously in connection with Fig.
7,
in the
ring topology messages are not broadcast but rather
passed from node
to
node along unidirectional links,
until they return to the originating node. A simple
scheme suitable for a ring consists of passing the access
right sequentially from node to node around the ring.
(Note that in a ring, the physical locations of the nodes
define a natural ordering among them.) One implemen-
tation of this scheme is exemplified by the Distributed
Computing System’s network where an 8-bit
control
token
is passed sequentially around the ring. Any node
with a ready message may, upon receiving the control
token, remove the token from the ring, send the
message, and then pass on the control token. Another
implementation consists of providing a number of
message slots
that are continuously transmitted around
the ring.
A
message slot may be empty or full; a node
with a ready message waits to see an empty slot pass by,
marks it as full, and uses it to send its message.
A
still
different strategy is known
as
the
register insertion
technique. Here, a message to be transmitted is first
loaded into a shift register. If the ring is idle, the shift
register is just transmitted. If not, the register is inserted
into the network loop at the next point separating two
adjacent messages; the message to be sent is shifted out
onto the ring while an incoming message is shifted into
the register. The shift register can be removed from the
network
loop
when the transmitted message has re-
turned to it.
Priority-Oriented Demand Assignment
(P0DA)-In the context of a satellite channel, PODA
has been proposed as the ultimate scheme that attempts
to incorporate all the properties and advantages seen in
many of the previous schemes. It has provision for both
implicit and explicit reservations, thus accommodating
both stream and packet-type traffic. It may also inte-
grate the use of both centralized and distributed control
techniques, thus achieving a high level of robustness.
Channel time is divided into two basic subframes, an
information subframe and a control subframe. The
information subframe contains scheduled packets and
packet streams that also contain, piggybacked, control
information such as reservations and acknowledge-
ments. The control subframe
is
used exclusively to send
reservations that cannot be sent in the information
subframe in a timely manner. In order to achieve
integration of centralized and distributed assignments,
the information subframe is further divided into two
sections, one for each type. Access to the control
subframe (which
is
divided into slots accommodating
fixed-size control packets) can take any form that
is
suitable to the environment. It can be by
fixed
assign-
ment
(TDMA) if the number of stations is small (giving
rise to the so-called FPODA), or by
contention
as in
ALOHA if the stations have a low duty cycle (giving
rise to CPQDA), or a combination of both. The
boundary between the control subframe and the infor-
mation subframe is not fixed, but varies with the
demand placed on the channel. As in the FIFO and
RR
reservation schemes, distributed control is achieved by
having all stations involved in this type of control keep
track of their queue length information. Priority sched-
uling can thus be achieved. For stream traffic, a
reservation is made only once and is retained by each
station in a stream queue. Centralized assignment may
be used when delay is not the crucial element. This
scheme has been proposed in the context of a satellite
channel but may be applied to other environments as
well.
THE
NETWORK LAYER
The network layer consists of those functions that
control the transportation of data from source-host to
destination-host
.
It
serves directly transport entities
residing at the network hosts, relieving them from any
concern about network issues such as switching, rout-
ing, and congestion control. The network-layer func-
tions are implemented at all switching nodes of a
network. This layer is the highest one that resides at the
switching nodes. It makes use of the data-link layer
to
accomplish the error-free transmission of data over
individual links.
The Network
Services
The nature of the services provided by the network
layer varies considerably depending on the switching
technique used in the communication subnet and the
transport-layer requirements pertaining to the delivery
of data from one end to the other.
A network-layer protocol for a circuit-switched net-
work
is
found in CCITT Recommendation
X.21
(1972).
As
stated earlier, X.21 is a general-purpose
interface between DTE and DCE for synchronous
operation on public data networks. When circuit-
switched services are provided,
X.21
includes a data-
link-layer function and a network-layer function needed
for call establishment. The data-link layer is character
oriented and includes only the minimum elements
necessary for basic operation, namely character syn-
chronization (using two or more SYN characters) and
error detection (using odd parity). The network layer
clearly defines the procedures used in processing the
various phases of call requests, incoming calls, facility
requests, call progress, and call clearing. The reason
these procedures belong to the network layer as opposed
to the physical layer (although the end result
is
a direct
physical connection between the two end hosts) is that
the network layer receives the remote DTE (or DCE)
address from the transport layer and makes use
of
the
data-link layer in processing the calls.
With packet switched networks, two types of network
services exist: the
datagram service
and the
virtual
REFERENCE
DATA
FOR ENGINEERS
circuit
(VC)
service.
In the VC model, the network
layer provides the transport layer with a “perfect”
connection: no errors, no duplicates, and all packets are
delivered in order. In the datagram model, the network
layer accepts messages from the transport layer and
simply makes the best effort to deliver them indepen-
dently (and not necessarily in order). The implementa-
tion of the datagram mode is simple; it merely consists
of a routing algorithm that attempts delivery of the
messages to their destination. For VC, in addition to
routing the messages, error control
and
sequencing must
be implemented at the end nodes. In theory, packets
may travel on different routes and arrive in any order.
Resequencing at the destination node would then be
required. In practice, the implementation of a VC in the
subnet is by establishing a route between the source and
destination end nodes at connection time, and by
continuously using the same route for all packets
belonging to the same virtual circuit. The implementa-
tion requires the packet to carry a virtual circuit
number, and each node to contain a table with an entry
for each VC traversing it, relating incoming packets
from an adjacent neighbor with a VC number to an
outgoing link and a VC number on that link. Forward-
ing packets
to
the destination node is then straightfor-
ward. All nodes use the first-come-first-served service
discipline, thus preserving the order of packets for each
VC. End-to-end reliability and sequencing are achieved
by means of a window mechanism, which also provides
flow control. It is to be noted, however, that the network
layer does not achieve complete end-host to end-host
reliability, since it is subject to node and link failures;
depending on the environment and on the application,
higher level functions (at the transport layer) must exist
to guarantee that reliability.
In multihop store-and-forward networks, the network
layer includes a routing algorithm that is responsible for
deciding on which output link a packet should be
transmitted. Although one primary objective is that
each packet reaches its destination, there are several
other objectives that are also very important, such as to
minimize packet transit times, to avoid congestion and
deadlocks, to maximize the network throughput, etc. It
is also desirable that the algorithm be simple, robust,
stable, and fair to all users. There is a broad spectrum of
routing algorithms. They vary according to various
attributes pertaining to the nature of decision-making
(centralized or distributed), the degree of adaptivity,
the frequency of updates, etc. Several routing tech-
niques are described below.
Directory Routing-In directory routing, each
node maintains a table with one row for each destina-
tion. The row gives one or several outgoing links
together with relative weights assigned to them. Upon
receipt of a packet with a given destination address, the
node simply performs a table look-up and chooses one
of the alternatives, using the relative weights as proba-
bilities. The selection of routes and their weights may
be based on the number of hops. If the source-
destination traffic requirement of the network is station-
ary,
then it is possible to use routes that minimize the
average message delay in the network. For a given
destination, the routes from an intermediate node to
that destination are entirely determined by the tables
and independent of the source. This is not restrictive,
since if node
j
is on the optimal path from source
i
to
destination
k,
then the optimal path from
j
to
k
should
follow the same route. This is known as the optimality
principle. As a result, the set
of
routes from all sources
to
a
given destination form a tree with the destination as
a root; such a tree is called the
sink tree
for that
destination.
Hierarchical Routing-If the size of the network
is large, then hierarchical routing is used. The network
is partitioned into regions; node addresses are hierarchi-
cal and contain a region number and a node number
within the region. In the table at each node, there is an
entry for each destination in the region in which the
node is located, and an entry for each of the other
regions. Hierarchical routing decreases the overhead
incurred in terms of storage and processing require-
ment. If the network is very large, a hierarchy with
more than two levels may be needed.
Static Versus Dynamic Routing-Static routing
refers
to
the case in which the table content
is
fixed.
Static routing is adequate if the topology and traffic
conditions do not change much. Dynamic routing refers
to the case in which table contents change as the
network condition changes. This is also referred to as
adaptive routing.
For example, if routing tables are
based on minimizing message delay, then the routes are
modified as the traffic pattern changes. There
is
a wide
range of adaptivity depending on the frequency of
changes, the type and amount of information used, and
the means for implementing the changes. For example,
static routing may be used, but changed only when there
is a failure. To construct the best routing tables in the
nodes at all times, information is needed about the
instantaneous state of the network and its traffic.
Unfortunately, it is not possible for the nodes to have
complete and up-to-date information about the entire
network. To provide it would also constitute too great an
overhead. Several practical alternatives are presented
below.
Centralized Routing-In centralized routing, a
node is designated as the
routing control center
(RCC).
Each node periodically sends status information to the
RCC
.
The RCC thus acquires global information, based
upon which it computes optimal routes. New routing
tables are periodically distributed to the nodes in the
network. While centralized routing may achieve global
optimal and relieve the node from the task of routing
computation, it has some drawbacks: the information
collected at the RCC may be old due to the delay in the
COMPUTER COMMUNICATIONS NETWORKS
26-25
network; the communication overhead incurred in col-
lecting status information and distributing routing infor-
mation may be substantial; the reliability of the entire
network rests on the proper operation of the control
center.
Isolated Routing-Isolated routing is the most
extreme case of decentralized routing. In isolated rout-
ing, each node makes its own routing decision based on
information it has at hand. The
hot
potato
technique
consists of passing the packet on as quickly as possible,
by sending (or queueing) it on the outgoing link with
the shortest queue. Variations of this shortest-queue
routing are obtained by applying various biases. For
example, the link selected may be determined by a
combination of the weights assigned to the static
alternate routes and the queue size at each. Another
isolated technique is the
backward learning
technique.
It consists of having a node attempt to estimate the
number of hops (or delay) of a route going from it to
some destination (starting with an outgoing link) by
measuring the number of hops (or delay) incurred by
packets arriving from that destination on that route
(i.e~, on that outgoing link). To implement this tech-
nique, using the delay measure for example, each packet
is time-stamped when it sets off on its journey, and
from this time-stamp each node compiles a table of
information about delays. One main problem with that
implementation is that the delays measured are incurred
by packets traveling in the direction opposite to that of
concern.
Delta Routing (or Hybrid Routing)-The delta
routing algorithm consists of using both central and
local decisions. Using information periodically sent to it
by
the nodes, the RCC computes the
k
best paths for
each pair
of
nodes, where only paths that differ in the
initial line are considered. The RCC then sends to each
node all equivalent paths (i.e., those with cost or delay
differing by less than some number
6)
for each
of
its
possible destinations.
In
routing a packet, the node may
choose any of the equivalent paths either at random, or
by choosing the line with the smallest current cost (or
delay). By adjustment of
k
and
6,
the scheme can be
made more
or
less centralized. Transpac, the French
public packet switching network, uses delta routing.
Distributed Algorithms-In this class of algo-
rithms, the nodes exchange information about delays by
sending control messages
to
one another.
To
keep the
overhead low, this information
is
exchanged only
among adjacent nodes. Each node communicates to its
neighbors its estimate of the minimum delay to every
other node
of
the network. When receiving such esti-
mates from its neighbors, a node adds to them its own
delay to reach each
of
the neighbors, and selects the best
outgoing link for each destination. Information ex-
change may take place either periodically at regular
intervals or asynchronously, such as when the estimates
change by more than some amount. The old ARPANET
routing algorithm was
of
this type.
Session
Routing and Logical Circuit Routing-
In the routing algorithms discussed above, the routing
decision is made for different packets independently. In
session routing, the route is chosen when a session is
established. All packets in the session go on the same
path. In logical circuit routing, the route is chosen by
means of a route set-up packet when the virtual circuit is
established. The route setup packet finds its way to the
destination using any of the schemes described above.
All
packets belonging to a virtual circuit are then
transmitted on the same route. Packets must only carry
the virtual circuit number. Routing in the subnet is
implemented as described in the subsection headed
“The Network Services.” Different logical circuits
between the same pair
of
hosts may take different
routes.
Broadcast Routing-Broadcast routing refers to
those techniques by which to deliver a packet originat-
ing at some source to all possible destinations in the
network. Of course, this can be accomplished by
sending multiple copies of the same packet, one for
each destination. However, more efficient techniques
exist. In the
multidestination routing
scheme, a packet
is issued with a list of destinations. At an intermediate
node, a copy of the packet is sent out on an outgoing
line if the latter is the best route for some destination
(Le., on the sink tree for that destination); the copy will
then contain the list of destinations that are to use that
line. After some number
of
hops, each copy will
contain a single address and is treated as a normal
packet. A more efficient technique makes use of the
sink tree associated with the source of broadcast.
Assuming knowledge of the spanning sink tree in both
directions, each node will broadcast the packet on all
links belonging to the spanning tree except the one on
which it arrived. Normally, the spanning sink tree
is
known only in the direction toward the sink. In that
case, an approximation of the above algorithm is as
follows. Copies arriving at some node on a link
belonging to the spanning sink tree are repeated on all
links except the one on which they came. Copies
arriving on all other links are discarded. This algorithm
is called
reverse path forwarding.
Congestion
Control
Congestion in an uncontrolled network
is
inevitable
due
to
the fact that all resources (line capacities, buffer
space, and processing capability) are limited. It is also
often due to the protocols in use, such as, for example,
the need to retransmit packets that are in error, the need
for sequencing, etc. Some types of congestion may be
relieved by the routing element that,
if
made dynamic,
would attempt to route traffic on underutilized paths.
But unfortunately, routing is not sufficient to prevent
congestion altogether; it merely helps reduce it or delay
it. Other flow control procedures are needed to prevent
congestion. Many of these functions are present in the
network layer and thus are presented here. There are,