Middleton W.M. (ed.) Reference Data for Engineers: Radio, Electronics, Computer and Communications
Подождите немного. Документ загружается.
25-28
Ri2
BITSIS
REFERENCE
DATA
FOR ENGINEERS
DISTORTED
DA7
A
TO
DISTORTED
USER
CHANNEL DECODER
DATA TO
R/2
BITSIS
CHANNEL
+
DECODER
USER
SYMMETRIC ENCODER DECODER
SOURCE
USER
4
SOURCE
X
Fig.
28.
A
degraded
diversity
system
R,
BITS/S
4
ENCODER
.
i
-x
has partial knowledge about the transmitted signal, but
these variations will not be considered here. The
jammer and the transmitter each must operate within
certain constraints. The most important case is one in
which the jammer and transmitter are each limited in
average power, and this is the case we discuss.
The set of channels that the jammer can use is
restricted in that he has a limited average transmitter
power. Let
QN
denote the set of channel noise distribu-
tions that satisfy power constraints on the jammer,
-
R,
BITSIS
-
ENCODER
-
SOURCE
+
A
Q,
=
{Q:
Jz2Q(z)
dz
5
N}
-Y
and let
Ps
denote the set of probability distributions
on
the channel input that satisfy average power constraints
on the transmitter.
Ps
=
(p:
Jx2p(n)
dx
5
S)
The
jammed capacity
is given by:
max
min
PEPS
Q~QN
min max
QEQN
pes
C(S,
N)
=
I(P;
Q)
I(P;
Q)
-
-
The first expression gives the capacity of the channel if
the jammer must first choose the channel noise statistics
before the transmitted waveform is designed. The sec-
ond expression gives the capacity
if
the transmitted
waveform is designed before the jammer chooses the
channel noise. The well-known minimax theorem of
game theory says that the two expressions are equal.
For the discrete-time, continuous-amplitude channel
with transmitter and jammer both limited in average
power, the minimax jammer strategy is to transmit
Gaussian noise, and the minimax transmitter strategy is
to encode assuming Gaussian noise. From the point of
view of the jammer, the jammed capacity is the data
rate to which the jammer can hold the transmitter. From
the point of view of the transmitter, the jammed
capacity is the data rate that the transmitter can achieve
in the presence of the jammer.
The most important application is the band-limited
waveform channel in which the transmitter and the
jammer are each limited
in
average power. The jammer
saddle point is
C(S,
N)
=
W
log (1
+
S/N)
This expression is linear in the bandwidth,
W.
If
the
signal power,
S,
and the jammer power,
N,
are fixed,
the capacity can be increased by increasing
W.
This
is
the basis for the practice of spectrum spreading dis-
cussed below. If the spectral power density,
No
(watts/
hertz), is fixed rather than
N,
then
C(S,
No)
=
W
log
(1
+
SJWN,)
The capacity is bounded as
W
increases.
Spectrum
Fig.
29.
Remote
compaction
of
dependent data
INFORMATION THEORY
AND
CODING
25-29
R”
-
..X
HIXIM
HiXl
H(XM
Fig.
30.
The
Slepian-Wolf admissible rate region.
spreading is useful only when the jammer’s total power
is limited. It is worthless if his spectral power density is
limited instead. Spectrum spreading does not improve
performance against broad-band white noise.
Spectrum Spreading
A
spread-spectrum
system is one that takes
a
signal of
small bandwidth, say
yW,
where
y
is much smaller than
one, and converts it into a signal of high bandwidth,
W.
This is done as shown in Fig.
31
by modulating the
information waveform with a wideband waveform that
is not known to the jammer. The wideband waveform
may be noise-like (hence called pseudo-noise, or
PN),
or
a time-varying carrier frequency (called frequency
hopping). The wideband signal is transmitted through
the channel, received, and then compressed back into
the original low-bandwidth signal by demodulating the
information waveform from the wideband waveform.
This scheme requires that the transmitter and receiver
share knowledge of the bandspreading waveform
through a secure channel. If the jammer knows nothing
about the wideband waveform, his “best” strategy is to
use wideband noise of bandwidth
W.
After the signal
spectrum is compressed, the jammer signal will still
have bandwidth
W,
but the signal will have bandwidth
yW.
A bandpass filter will reduce the jammer noise
power by the factor
y.
The reciprocal of the factor
y
is
called the processing gain
of
the spread-spectrum sys-
tem.
A
spread-spectrum system does not make optimum
use of the wide bandwidth. This can be seen by looking
at the channel capacity. The channel capacity of the
available wideband channel of bandwidth
W
and jam-
mer power
N
is
C
=
W
log
(1
+
SIN)
However, the channel capacity of the spread-spectrum
channel of compressed bandwidth
yW
and processed
jammer power
yN
is
CSS(Y)
=
rW
1%
(1
+
SlYN)
whereas if only the narrow bandwidth,
yW,
is used,
there is no reduction
of
jammer power, and the channel
capacity
is
C,(y)
=
yW
log
(1
+
SIN)
If the channel must transmit
R
bits per second, the
wideband channel requires a signal-to-noise ratio of at
least
SIN
=
2(RIW)
-
1
while the spread-spectrum channel requires a signal-to-
noise ratio of
SIN
=
y(2(R‘Vw)
-
1)
which can be considerably larger than what is needed in
the wide bandwidth but is smaller than
JAMMING
,“iAL
USER
DECODER/
DEMODULATOR
ENCODER/
MODULATOR
WIDEBAND
SIGNAL
WIDEBAND
SIGNAL
SECURE
CHANNEL
WIDEBAND
SIGNAL
DESCRIPTION
Fig.
3
1.
Spread-spectrum signaling.
25-30
KEY
-
REFERENCE
DATA
FOR
ENGINEERS
SECURE
CHANNEL
SIDE
-
which is required if there
is
no spectrum spreading at
all. Spread-spectrum by itself improves performance,
hut much better improvement is theoretically possible
using the wide bandwidth.
The use of M-ary orthogonal signaling, spread-
spectrum, and error-control codes in combination will
make better use of the wide bandwidth. In addition,
error-control codes are necessary in a spread-spectrum
system to protect against partial-time
or
partial-band
jamming tactics.
A
well-designed spread-spectrum sys-
tem will use an error-control code and a modulation
SOURCE
waveform that operate at a small
Eb/No
and then spread
the spectrum of this waveform to fill out the available
frequency band.
L
ENCRYPT CHANNEL
--c
DECRYPT
-
USER
Cry
PtograPhY
Three major kinds of cryptosystem are shown in Fig.
32.
The first two kinds require some type of key; the
third kind relies on noise in the channel to hide the
message. While at first it may seem that the wire-tap
channel (Fig.
32C)
is not a true cryptosystem, in fact it
would be misleading to ignore it. All cryptosystems
have internal compartments where the message or the
~
PUBLIC
CHANNEL
SIDE
+
CRYPT
ANALYST
+
CRYPT
+
ANALYST
(A)
Conuentlonol
cryptosystern
SOURCE
----c
ENCRYPT CHANNEL
-
DECRYPT
-
USER
-
-
PUBLIC
KEY
--c
NOISY CRYPT
CHANNEL
-
ANALYST
NOISY
(C)
Wlre.tap
channel
Fig.
32.
Types
of
cryptosystem.
SOURCE
ENCODE
4
CHANNEL
-
DECODE
-c
USER
-
key exists in the clear. The designer relies on the fact
that any portion that leaks out will be buried in the
ambient noise. Hence the wire-tap channel is present in
every cryptosystem. A secure side channel for transmit-
ting a key is of this type.
A conventional cryptosystem (Fig. 32A) is secure
from a direct attack by the cryptanalyst if the key
is
nearly as long as the message. A so-called “one-time
pad” has one random bit in the key for each bit
of
the
message, and it is not reused. The one-time pad can be
penetrated only by an attack on the secure side channel.
Since it is difficult to transmit and store long keys, most
cryptosystems have short keys. Then there is redundan-
cy in the encrypted message that the cryptanalyst can
exploit.
A public-key cryptosystem (Fig. 329) differs from a
conventional cryptosystem in that it relies on one-to-
one functions,
f(x),
whose inverses,
f-*(x),
are very
difficult-even computationally intractable-to de-
duce. These are sometimes called one-way functions.
Hence, the user randomly makes
up
an
f-’(x),
finds
f(x),
and publicly announces that he can decrypt mes-
sages that are encrypted with
f(x).
The cryptanalyst
always knows the encoding key, but
is
unable to convert
this into a decoding key.
REFERENCES
1.
Gallager, R. G.
Information Theory and Reliable
Communication.
New York: John Wiley
&
Sons,
Inc., 1968.
2. McEliece, R.
J.
The Theory of Information and
Coding.
Reading, Mass.
:
Addison-Wesley Publish-
ing Co., Inc., 1977.
3. Ash,
R.
9.
Information Theory.
Interscience,
1965.
4.
Viterbi,
A.
J.,
and Omura,
J.
K.
Principles
of
Digital Communication and Coding.
New York
McGraw-Hill Book Co., 1979.
5.
Franaszek, P. A. “Sequence-State Coding for
Digital Transmission.”
Bell System Tech.
J.,
1968,
6. Adler,
R.
L., Coppersmith, D., and Hassner, M.
“Algorithms for Sliding Block Codes.
”
IEEE
pp.
113-157.
Transactions on Information Theory, Vol. IT-29,
7. Rissanen,
J.,
and Langdon, G. G. Jr. “Universal
Modeling and Coding.”
IEEE Transactions
on
Information Theory,
Vol. IT-27,
1981,
pp.
12-23.
8.
Berlekamp, E. R.
Algebraic Coding Theory.
New
York McGraw-Hill Book Co., 1968.
9. Blahut, R.
E.
Theory and Practice of Error-Control
Codes.
Reading, Mass.: Addison-Wesley Publish-
ing Co., Inc., 1983.
10.
Clark, G. C., and Cain, J. Bibb.
Error-Correction
Coding for Digital Communications.
New York:
Plenum Press, 1981.
11. Lin,
S.,
and Costello,
D.
J.
Jr.
Introduction to
Error Correction Codes.,
Englewood Cliffs,
N.J.:
Prentice-Hall, Inc., 1983.
12. Peterson, W. W., and Weldon,
E.
J.
Jr.
Error
Correcting Codes,
2nd ed. Cambridge, Mass.: The
M.
I.
T. Press, 1971.
13. Wozencraft,
J.
M., and Jacobs,
I.
M.
Principles
of
Communication Engineering.
New York: John
Wiley
&
Sons, Inc., 1965.
14. Davenport, W. B. Jr., and Root, W. L.
Random
Signals and Noise.
New York: McGraw-Hill Book
Co., 1958.
15.
Van Trees,
H.
L.
Detection, Estimation, and Mod-
ulation Theory,
Part
1.
New York: John Wiley
&
Sons, Inc., 1968.
16.
Berger,
T.
Rate Distortion Theory:
A
Mathematical
Basis for Data Compression.
Englewood Cliffs,
N.J.: Prentice-Hall, Inc., 1971.
17. Van der Meulen,
E.
C. “A Survey of Multi-Way
Channels in Information Theory: 1961-1976.”
IEEE Transactions on Information Theory,
Vol
.
18. Berger, T. “Multiterminal Source Coding,” in
The Information Theory Approach to Communica-
tions,
G.
Longo, ed. New York: Springer-Verlag,
1977.
19. El Gamal, A,, and Cover, T. M. “Multiple User
Information Theory.
’
’
Proceedings IEEE,
Vol
.
68,
20. Special Issue on Spread Spectrum,
IEEE Transac-
tions
on
Communication Theory,
Vol. COM-30,
May, 1982.
1983; pp. 5-22.
IT-23, 1977,
pp.
1-37.
1980,
pp.
1066-1083.
26
Computer
Communications
Networks
Fouad
A.
Tobagi
and
Mario
Gerla
The Structure
of
Computer Networks
26-2
Switching Techniques
Types
of
Computer Communications Networks
Network Functions
26-7
The Physical Layer
26-9
The Data Link Control Layer
26-13
Asynchronous DLC Protocols
Synchronous DLC Protocols
Multiaccess Link Control
26-18
Fixed Assignment Techniques
Random Access Techniques
Centrally Controlled Demand Assignment
Demand Assignment With Distributed Control
The Network Services
Routing
Congestion Control
CCITT Recommendation
X
.25
Higher-Level Protocols
26-29
The Network Layer
26-23
The Transport and Session Layers
The Presentation Layer
High Speed Local Area Networks
26-30
A Taxonomy
of
Local Area Networks
LOW- and Medium-Speed LANs
High-speed LANs
Supercomputer Networks
Ultragigabit Networks
High Speed Wide Area Networks
Bandwidth and Traffic Allocation in ATM Networks
Congestion Control in ATM
26-36
26-2
About two decades ago, a great challenge to many
computer system designers was to enhance the process-
ing power
of
computers and make them available to a
large number of users
on
a time-sharing basis. The
design of fast arithmetic and control units as well as the
design of complex operating systems were identified
among the key tasks needed to accomplish this objec-
tive. As time-sharing progressed, it was soon realized
that such large resources would not be effectively
utilized unless the problem of connecting remote user
terminals to the central computing facility was ade-
quately solved, thus allowing a large population of users
to share the facility. With this problem, the field of
computer communications came into existence. The
early communications systems were merely
terminal
access networks.
The next stage in the evolution consist-
ed of the creation of the so-called distributed
resource-
sharing networks.
The goal here is to interconnect
computers and their users at various geographically
distributed sites in order to allow the sharing of
hardware and software resources developed at all sites
by all users connected to the network. Today the term
computer communications
has a much broader mean-
ing. Not only does it refer to communications among
computers and their users, but it also refers to all kinds
of communications applications (among humans and
among machines) that make use of the computer as a
tool. Examples of such applications are voice communi-
cations, electronic mail, facsimile, image transfer,
process control, etc. The goals are also somewhat more
diverse. Instead of communications per se, the driving
force may very well be that of cost or reliability of
computing power. High reliability may be achieved by
having alternative sources of computing made available
via a communications network. Lower cost may be
achieved via distributed computing architectures that
are simpler to design, cheaper to build, and easier
to
maintain, and of which communication is an intrinsic
part. Thus, while in the seventies one might have
characterized the computer communications field as
having been in its research and development phase, the
eighties and beyond will be marked by the wide use of
this relatively new technology for a large repertoire of
applications.
In the following, the structure of computer communi-
cations networks is examined and their building blocks
identified. First, the various types
of
networks in
existence and the switching techniques in use are
described. Then the general functions
of
a network
needed in establishing a communications path among
remote users are described, and the organization
of
these functions into a standard layered architecture
called the
Open Systems Interconnection reference
model
is discussed. Using this reference model as a
guide, we then examine in more detail the functions in
each of the layers and highlight standards whenever
applicable. Finally, we introduce a class of network
architectures which has emerged in the past few years,
namely, the class
of
high-speed networks. The
OS1
model also applies, with some modifications, to this
class, but the requirements, characteristics, and appli-
cations of high-speed networks are
so
different from
those of conventional networks that a separate treatment
at the end of this chapter is justified. Two sections are
dedicated to this subject, namely, high-speed local area
networks and high-speed wide area networks.
THE STRUCTURE
OF
COMPUTER NETWORKS
A
computer-communication network typically com-
prises a collection of computing resources called
hosts,
a collection of users, some of which are associated with
the hosts, and a so-called
communication subnet
that
connects them (Fig.
1
.)
The communication subnet
consists of two basic components: the communication
channels and the switching elements (or switching
nodes). Depending on
(
1)
the physical medium used for
the communication channels,
(2)
the subnet topology
according to which the communication channels and the
switching elements are interconnected to form a net-
work, and
(3)
the switching technique used in providing
a physical path among two or more communicating
parties, several computer network types may be identi-
fied.
Switching Techniques
There are two basic types of switching techniques:
circuit switching
and
message switching.
In circuit
switching, a total path of connected lines is set up from
the origin to the destination at the time the call is made,
and the path remains allocated to the source-destination
pair (whether used or not) until it is released by the
communicating parties. The switches, called circuit
switches (or office exchange in telephone jargon), have
no capability of storing or manipulating users’ data on
their way to the destination. The circuit is set up by a
special signaling message that finds its way through the
network, seizing channels in the path as it proceeds.
Once the path is established, a return signal informs the
source
to
begin transmission. Direct transmission of
data from source to destination can then take place
without any intervention on the part of the subnet.
In message switching, the transmission unit is a well
defined block of data called a
message.
In
addition to
the text
to
be transmitted,
a
message comprises a
header
and a
checksum.
The header contains information
regarding the source and destination addresses as well
as other control information; the
checksum
is used for
error control purposes. The switching element is a
computer referred to as a
message processor,
with
processing and storage capabilities. Messages travel
independently and asynchronously, finding their own
way from source to destination. First the message is
transmitted from the host to the message processor to
which it
is
attached. Once the message is entirely
received, the message processor examines its header,
and accordingly decides on the next outgoing channel
on
which to transmit it. If this selected channel is busy,
COMPUTER COMMUNICATIONS NETWORKS
26-3
h
“REMOTE”
TERMINAL
FACILITY
Fig.
1.
The structure
of
a
computer-communication network.
(From Leonard
Kleinrock,
Computer Applications,
Vol.
11
of
Queueing Systems,
0
1976
by
John
Wiley
&
Sons,
Inc.,
New
York.)
the message waits in a queue until the channel becomes
free, at which time transmission begins. At the next
message processor, the message is again received,
stored, examined, and transmitted on some outgoing
channel, and the same process continues until the
message is delivered to its destination. This transmis-
sion technique is also referred to as the
store-and-
forward
transmission
technique.
A
variation of message switching is
packet
switching.
Here the message is broken up into several pieces of a
given maximum length, called
packets.
As with mes-
sage switching, each packet contains a header and a
checksum. Packets are transmitted independently in a
store-and-forward manner.
With circuit switching, there is always an initial
connection cost incurred in setting up the circuit.
It
is
cost-effective only in those situations where once the
circuit is set up there is a guaranteed steady flow of
information transfer to amortize the initial cost. This is
certainly the case with voice communication in the
traditional way, and indeed circuit switching is the
technique used in the telephone system. Communica-
tion among computers, however, is characterized as
bursty.
Burstiness
is
a result of the high degree of
randomness encountered in the message-generation
process and the message size, and of the low delay
constraint required by the user. The users and devices
require the communication resources relatively infre-
quently; but when they do, they require a relatively
rapid response. If a fixed dedicated end-to-end circuit
were
to
be set up connecting the end users, then one
must assign enough transmission bandwidth to the
circuit in order to meet the delay constraint with the
consequence that the resulting channel utilization is
low. If the circuit of high bandwidth were set up and
released at each message transmission request, then the
set-up time would be large compared to the transmis-
sion time of the message, resulting again in low channel
utilization. Therefore, for bursty users (which can also
be characterized by high peak-to-average data rate
requirements), store-and-forward transmission tech-
niques offer a more cost-effective solution, since a
message occupies a particular communications link
only for the duration of its transmission on that link; the
rest
of
the time it is stored at some intermediate
message switch and the link is available for other
transmissions. Thus the main advantage
of
store-and-
forward transmission over circuit switching is that the
communication bandwidth is dynamically allocated,
and the allocation is done on the fine basis
of
a
particular link in the network and a particular message
(for a particular source-destination pair).
Packet switching achieves the benefits discussed
so
far and offers added features. It provides the full
advantage of the dynamic allocation of the bandwidth,
even when messages are long. Indeed, with packet
switching, many packets of the same message may be in
transmission simultaneously over consecutive links of a
path from source
to
destination, thus achieving a
“pipelining’
’
effect and reducing considerably the over-
all transmission delay
of
the message as compared to
message switching.
It
tends to require smaller storage
allocation at the intermediate switches.
It
also has better
error characteristics and leads to more efficient error
recovery procedures, as it deals with smaller entities.
Needless to say, packet switching presents design prob-
lems of its own, such as the need to reorder packets of a
given message that may arrive at the destination node
out of sequence.
Fig.
2
illustrates the three switching modes for an
26-4
REFERENCE
DATA
FOR ENGINEERS
example of a communication subnet involving four
nodes and three transmission links. The figure shows
the advantage of packet switching over message switch-
ing and
of
message switching over circuit switching.
Clearly, this comparison involves a number of trade-
offs,
and it is not hard to imagine situations where the
conclusion may be reversed. This depends on a number
of
factors, among others the number
of
hops from
source
to
destination, the length
of
the message, the
amount of overhead incurred in the header and check-
sum of each message and packet, the circuit set-up
delay, etc.
For
example, fast circuit switching accom-
n
I I
SUBNETWORK
DESTINATION
I
plished with solid-state implementation of the switches
can achieve a set-up time on the order of a fraction
of
a
second (a few milliseconds per switch), which renders
this technique a viable solution. In most cases, however.
the picture shown in Fig.
2
reflects the real situation.
The advantages of store-and-forward transmission are
obtained at the expense
of
higher processing and storage
capabilities at all switches. Overall, however, the pres-
ent economics are in favor
of
store-and-forward.
Roberts? has shown that since the early
60s,
the
?
Reference
1.
NODE
START
4
I
CONNECTIOK
DELAY
PROPAGATION
DELAY
DATA
TRANSMISSION
TIME
C
i-
(Ai
The
fransmission poth.
(6)
Circuit
switching.
j
2
.-t
FINISH
Fig.
2.
Comparison of network delay
for
circuit, message, and packet switching.
(From
LeonardKleinrock,
Computer Applications,
COMPUTER COMMUNICATIONS NETWORKS
incremental cost of computing needed to send one
megabit of data through a nationwide network has been
decreasing at
a
much faster rate than the incremental
cost
of
the communication land lines in a national net,
with a crossover point having occurred about
1969.
Fig.
3
summarizes Roberts’ findings concerning these cost
trends (the reader is referred
to
the portion of the figure
corresponding to the range up to
1974).
In the development that follows, the three terms
message switching, packet switching, and store-and-
forward are used interchangeably unless the distinction
is made explicitly.
NODE
A
B
C
START
-
PROCESSING
DELAY
DATA
TRANSMISSIOP
TIME
I
H~ADER
{
(Cj
Message switching
-
4
26-5
Types
of
Computer
Communications Networks
A
distinction is first made between
circuit-switched
networks
and
packet
communication
networks.
Clearly,
circuit-switched networks are those that use circuit
switching. When used for local communication, these
networks have
a
star topology with
a
single switch in the
center, and they may often be privately owned (e.g.,
CBX). Long-haul or nationwide networks, on the other
hand, have
a
hierarchical mesh topology: subscribers
are connected to local central offices via two-wire
C
START
;!
I
I
?
NODE
A
(0)
Packet
switching.
Vol.
II
of
Queueing
Systems,
0
1976
by
John
Wiley
&
Sons,
Inc., .Vew
York.)