IV. On a Future System Development
We will soon be living in an era in which we cannot guarantee
survivability of any single point. However, we can still design systems in
which system destruction requires the enemy to pay the price of destroying n of
n stations. If n is made sufficiently large, it can be shown that highly
survivable system structures can be built--even in the thermonuclear era. In
order to build such networks and systems we will have to use a large number of
elements. We are interested in knowing how inexpensive these elements
may be and still permit the system to operate reliably. There is a
strong relationship between element cost and element reliability. To design a
system that must anticipate a worst-case destruction of both enemy attack and
normal system failures, one can combine the failures expected by enemy attack
together with the failures caused by normal reliability problems, provided the
enemy does not know which elements are inoperative. Our future systems design
problem is that of building very reliable systems out of the described set of
unreliable elements at lowest cost. In choosing the communications links of
the future, digital links appear increasingly attractive by permitting low-cost
switching and low-cost links. For example, if "perfect switching"[1] is used, digital links are
mandatory to permit tandem connection of many separately connected links
without cumulative errors reaching an irreducible magnitude. Further, the
signaling measures to implement highly flexible switching doctrines always
require digits.
Future Low-Cost All-Digital Communications Links
When one designs an entire system optimized for digits and high
redundancy, certain new communications link techniques appear more attractive
than those common today.
A key attribute of the new media is that it permits formation of new
routes cheaply, yet allows transmission on the order of a million or so
bits per second, high enough to be economic, but yet low enough to be
inexpensively processed with existing digital computer techniques at the relay
station nodes. Reliability and raw error rates are secondary. The network
must be built with the expectation of heavy damage, anyway. Powerful error
removal methods exist.
Some of the communication construction methods that look attractive in the near
future include pulse regenerative repeater line, minimum-cost or "mini-cost"
microwave, TV broadcast station digital transmission, and satellites.
Pulse Regenerative Repeater Line
Samuel B. Morse's regenerative repeater invention for amplifying weak
telegraphic signals has recently been resurrected and transistorized. Morse's
electrical relay permits amplification of weak binary telegraphic signals above
a fixed threshold. Experiments by various organizations (primarily the Bell
Telephone Laboratories) have shown that digital data rates on the order of 1.5
million bits per second can be transmitted over ordinary telephone line at
repeater spacings on the order of 6,000 feet for #22 gage pulp paper insulated
copper pairs. At present, more than 20 tandemly connected amplifiers have been
used in the Bell System T-l PCM multiplexing system without retiming
synchronization problems. There appears to be no fundamental reason why either
lines of lower loss, with corresponding further repeater spacing, or more
powerful resynchronization methods cannot be used to extend link distances to
in excess of 200 miles. Such distances would be desired for a possible
national distributed network.
Power to energize the miniature transistor amplifier is transmitted over the
copper circuit itself.
"Mini-Cost" Microwave
While the price of microwave equipment has been declining, there are
still untapped major savings. In an analog signal network we require a high
degree of reliability and very low distortion for a long string of tandem
repeaters. However, using digital modulation together with perfect switching
we minimize these two expensive considerations from our planning. We would
envision the use of low-power, mass-produced microwave receiver/transmitter
units mounted on low-cost, short, guyed towers. Relay station spacing would
probably be on the order of 20 miles. Further economies can be obtained by
only a minimal use of standby equipment and reduction of fading margins. The
ability to use alternate paths permits consideration of frequencies normally
troubled by rain attenuation problems reducing the spectrum availability
problem.
Preliminary indications suggest that this approach appears to be the cheapest
way of building large networks of the type to be described (see ODC-VI).
TV Stations
With proper siting of receiving antennas, broadcast television stations
might be used to form additional high data rate links in emergencies.[2]
Satellites
The problem of building a reliable network using satellites is somewhat
similar to that of building a communications network with unreliable links.
When a satellite is overhead, the link is operative. When a satellite is not
overhead, the link is out of service. Thus, such links are highly compatible
with the type of system to be described.
Variable Data Rate Links
In a conventional circuit switched system each of the tandem links
requires matched transmission bandwidths. In order to make fullest use of a
digital link, the post-error-removal data rate would have to vary, as it is a
function of noise level. The problem then is to build a communication network
made up of links of variable data rate to use the communication resource most
efficiently.
Variable Data Rate Users
We can view both the links and the entry point nodes of a multiple-user
all-digital communications system as elements operating at an ever changing
data rate. From instant to instant the demand for transmission will vary.
We would like to take advantage of the average demand over all users instead of
having to allocate a full peak demand channel to each. Bits can become a
common denominator of loading for economic charging of customers. We would
like to efficiently handle both those users who make highly intermittent bit
demands on the network, and those who make long-term continuous, low bit
demands.
Common User
In communications, as in transportation, it is more economical for many
users to share a common resource rather than each to build his own
system--particularly when supplying intermittent or occasional service. This
intermittency of service is highly characteristic of digital communication
requirements. Therefore, we would like to consider the interconnection, one
day, of many all-digital links to provide a resource optimized for the
handling of data for many potential intermittent users--a new common-user
system.
Figure 9 demonstrates the basic notion. A wide mixture of different digital
transmission links is combined to form a common resource divided among many
potential users. But, each of these communications links could possibly have a
different data rate. Therefore, we shall next consider how links of different
data rates may be interconnected.
Standard Message Block
Present common carrier communications networks, used for digital
transmission, use links and concepts originally designed for another
purpose--voice. These systems are built around a frequency division
multiplexing link-to-link interface standard. The standard between links is
that of data rate. Time division multiplexing appears so natural to data
transmission that we might wish to consider an alternative approach--a
standardized message block as a network interface standard. While a
standardized message block is common in many computer-communications
applications, no serious attempt has ever been made to use it as a universal
standard. A universally standardized message block would be composed of
perhaps 1024 bits. Most of the message block would be reserved for whatever
type data is to be transmitted, while the remainder would contain housekeeping
information such as error detection and routing data, as in Fig. 10.
As we move to the future, there appears to be an increasing need for a
standardized message block for all-digital communications networks. As data
rates increase, the velocity of propagation over long links becomes an
increasingly important consideration.[3] We soon reach a point where more
time is spent setting the switches in a conventional circuit switched system
for short holding-time messages than is required for actual transmission of the
data.
Most importantly, standardized data blocks permit many simultaneous users each
with widely different bandwidth requirements to economically share a broadband
network made up of varied data rate links. The standardized message block
simplifies construction of very high speed switches. Every user connected to
the network can feed data at any rate up to a maximum value. The user's
traffic is stored until a full data block is received by the first station.
This block is rubber stamped with a heading and return address, plus additional
house-keeping information. Then, it is transmitted into the network.
Switching
In order to build a network with the survivability properties shown in
Fig. 4, we must use a switching scheme able to find any possible path that
might exist after heavy damage. The routing doctrine should find the shortest
possible path and avoid self-oscillatory or "ring-around-the-rosey"
switching.
We shall explore the possibilities of building a "real-time" data transmission
system using store-andforward techniques. The high data rates of the future
carry us into a hybrid zone between store-and-forward and circuit switching.
The system to be described is clearly store-and-forward if one examines the
operations at each node singularly. But, the network user who has called up a
"virtual connection" to an end station and has transmitted messages across the
United States in a fraction of a second might also view the system as a
black box providing an apparent circuit connection across the U.S.
There are two requirements that must be met to build such a quasi-real-time
system. First, the in-transit storage at each node should be minimized to
prevent undesirable time delays. Secondly, the shortest instantaneously
available path through the network should be found with the expectation that
the status of the network will be rapidly changing. Microwave will be subject
to fading interruptions and there will be rapid moment-to-moment variations in
input loading. These problems place difficult requirements upon the switching.
However, the development of digital computer technology has advanced so rapidly
that it now appears possible to satisfy these requirements by a moderate amount
of digital equipment. What is envisioned is a network of unmanned digital
switches implementing a self-learning policy at each node so that overall
traffic is effectively routed in a changing environment--without need for a
central and possibly vulnerable control point. One particularly simple routing
scheme examined is called the "hot-potato" heuristic routing doctrine and will
be described in detail.
Torn-tape telegraph repeater stations and our mail system provide examples of
conventional store-and-forward switching systems. In these systems, messages
are relayed from station-to-station and stacked until the "best" outgoing link
is free. The key feature of store-andforward transmission is that it allows a
high line occupancy factor by storing so many messages at each node that there
is a backlog of traffic awaiting transmission. But, the price for link
efficiency is the price paid in storage capacity and time delay. However, it
was found that most of the advantages of store-and-forward switching could
be obtained with extremely little storage at the nodes.
Thus, in the system to be described, each node will attempt to get rid of its
messages by choosing alternate routes if its preferred route is busy or
destroyed. Each message is regarded as a "hot potato," and rather than hold
the "hot potato," the node tosses the message to its neighbor, who will now try
to get rid of the message.
The Postman Analogy
The switching process in any store-and-forward system is analogous to a
postman sorting mail. A postman sits at each switching node. Messages arrive
simultaneously from all links. The postman records bulletins describing the
traffic loading status for each of the outgoing links. With proper status
information, the postman is able to determine the best direction to send out
any letters. So far, this mechanism is general and applicable to all
store-and-forward communication systems.
Assuming symmetrical bi-directional links, the postman can infer the "best"
paths to transmit mail to any station merely by looking at the cancellation
time or the equivalent handover number tag. If the postman sitting in the
center of the United States received letters from San Francisco, he would find
that letters from San Francisco arriving from channels to the west would come
in with later cancellation dates than if such letters had arrived in a
roundabout manner from the east. Each letter carries an implicit indication of
its length of transmission path. The astute postman can then deduce that the
best channel to send a message to San Francisco is probably the link
associated with the latest cancellation dates of messages from San
Francisco. By observing the cancellation dates for all letters in transit,
information is derived to route future traffic. The return address and
cancellation date of recent letters is sufficient to determine the best
direction in which to send subsequent letters.
Hot-Potato Heuristic Routing Doctrine
To achieve real-time operation it is desirable to respond to change in
network status as quickly as possible, so we shall seek to derive the network
status information directly from each message block.
Each standardized message block contains a "to" address, a "from" address, a
handover number tag, and error detecting bits together with other housekeeping
data. The message block is analogous to a letter. The "from" address is
equivalent to the return address of the letter.
The handover number is a tag in each message block set to zero upon initial
transmission of the message block into the network. Every time the message
block is passed on, the handover number is incremented. The handover number
tag on each message block indicates the length of time in the network or path
length. This tag is somewhat analogous to the cancellation date of a
conventional letter.
The Handover Number Table. While cancellation dates could conceivably
be used on digital messages, it is more convenient to think in terms of a
simpler digital analogy--a tag affixed to each message and incremented every
time
the message is relayed. Figure 11 shows the handover table located in the
memory of a single node. A row is reserved for each major station of the
network allowed to generate traffic. A column is assigned to each separate
link connected to a node. As it was shown that redundancy levels on the order
of four can create extremely "tough" networks and additional redundancy brought
little, only about eight columns are really needed.
Perfect Learning. If the network used perfectly reliable,
error-free links, we might fill out our table in the following manner.
Initially, set entries on the table to high values. Examine the handover
number of each message arriving on each line for each station. If the observed
handover number is less than the value already entered on the handover number
table, change the value to that of the observed handover number. If the
handover number of the message is greater than the value on the table, do
nothing. After a short time this procedure will shake down the table to
indicate the path length to each of the stations over each of the links
connected to neighboring stations. This table can now be used to route new
traffic. For example, if one wished to send traffic to station C, he
would examine the entries for the row listed for station C based on traffic
from C. Select the link corresponding to the column with the lowest
handover number. This is the shortest path to C. If this preferred link is
busy, do not wait, choose the next best link that is free.
Digital Simulation
This basic routing procedure was tested by a Monte Carlo simulation of a
7x7 array of stations. All tables were started completely blank to simulate a
worst-case starting condition where no station knew the location of any other
station. Within 1/2 second of simulated real world time, the network had
learned the locations of all connected stations and was routing traffic in an
efficient manner. The mean measured path length compared very favorably to the
absolute shortest possible path length under various traffic loading
conditions. Preliminary results indicate that network loadings on the order of
50 per cent of link capacity could be inserted without undue increase of path
length. When local busy spots occur in the network, locally generated traffic
is intermittently restrained from entering the busy points while the potential
traffic jams clear. Thus, to the node, the network appears to be a variable
data rate system, which will limit the number of local subscribers that can be
handled. If the network is carrying light traffic, any new input line into the
network would accept full traffic, perhaps 1.5 million bits per second. But, if
every station had heavy traffic and the network became heavily loaded, the
total allowable input data rate from any single station in the network might
drop to perhaps 0.5 million bits per second. The absolute minimum guaranteed
data capacity into the network from any station is a function of the location
of the station in the network, redundancy level, and the mean path length of
transmitted traffic in the network. The "choking" of input procedure has been
simulated in the network and no signs of instability under overload noted. It
was found that most of the advantage of store-and-forward transmission can be
provided in a system having relatively little memory capacity. The network
"guarantees" very rapid delivery of all traffic that it has accepted from a
user (see ODC-II, -III).
Forgetting and Imperfect Learning
We have briefly considered network behavior when all links are working.
But, we are also interested in determining network behavior with real world
links--some destroyed, while others are being repaired. The network can be
made rapidly responsive to the effects of destruction, repair, and transmission
fades by a slight modification of the rules for computing the values on the
handover number table.
Learning
In the previous example, the lowest handover number ever encountered for
a given origination, or "from" station, and over each link, was the value
recorded in the handover number table. But, if some links had failed, our
table would not have responded to the change. Thus, we must be more responsive
to recent measurements than old ones. This effect can be included in our
calculation by the following policy. Take the most recently measured value of
handover number; subtract the previous value found in the handover table; if
the difference is positive, add a fractional part of this difference to the
table value to form the updated table value. This procedure merely implements
a "forgetting" procedure--placing more belief upon more recent measurements
and less on old measurements. This device would, in the case of network
damage, automatically modify the handover number table entry so as to
exponentially and asymptotically approach the true shortest path value. If the
difference between measured value minus the table value is negative, the new
table value would change by only a fractional portion of the recently measured
difference.
This implements a form of sceptical learning. Learning will take place even
with occasional errors. Thus, by the simple device of using only two separate
"learning constants," depending whether the measured value is greater or less
than the table value, we can provide a mechanism that permits the network
routing to be responsive to varying loads, breaks, and repairs. This learning
and forgetting technique has been simulated for a few limited cases and was
found to work well (see ODC-II, -III).
Adaptation to Environment
This simple simultaneous learning and forgetting mechanism implemented
independently at each node causes the entire network to suggest the appearance
of an adaptive system responding to gross changes of environment in several
respects, without human intervention. For example, consider self-adaptation to
station location. A station, Able, normally transmitted from one location in
the network, as shown in Fig. 12(a). If Able moved to the location shown in
Fig. 12(b), all he need do to announce his new location is to transmit a
few seconds of dummy traffic. The network will quickly learn the new location
and direct traffic toward Able at his new location. The links could also be
cut and altered, yet the network would relearn. Each node sees its environment
through myopic eyes by only having links and link status information to a few
neighbors. There is no central control; only a simple local routing policy is
performed at each node, yet the overall system adapts.
Lowest-Cost Path
We seek to provide the lowest cost path for the data to be transmitted
between users. When we consider complex networks, perhaps spanning continents,
we encounter the problem of building networks with links of widely different
data rates. How can paths be taken to encourage most use of the least
expensive links? The fundamentally simple adaptation technique can again be
used. Instead of incrementing the handover by a fixed amount, each time a
message is relayed, set the increment to correspond to the link-cost/bit of the
transmission link. Thus, instead of the "instantaneously shortest non-busy
path'" criterion, the path taken will be that offering the cheapest
transportation cost from user to user that is available. The technique can be
further extended by placing priority and cost bounds in the message block
itself, permitting certain users more of the communication resource during
periods of heavy network use.
[1]See ODC-V. (ODC is an abbreviation
of the series title, On Distributed Communications; the number following
refers to the volume in the series.
[2]Baran, P., Coverage Estimate of FM, TV and Power
Facilities Useful in a Broadband Distributed Network , The RAND
Corporation, RM-3008-PR, March 1962.
[3]
Contents
Previous chapter
Next chapter