On Distributed Communications Series

V. History, Alternative Approaches, and Comparisons

Contents
Preface
Summary
I. Introduction
II. The Distributed Network Concept
III. Early History

IV. Specific Hardware Proposals

The following specific system descriptions are not intended to imply an exhaustive survey of distributed systems; only enough cases are given to provide an introduction to the general subject.

Time-of-Arrival

In 1957, Frank Yates of the Hughes Aircraft Company described in engineering detail a non-synchronous time-of-arrival procedure to connect a group of stations together into a circuit-switched tree structure. Each node is connected via relay points to the origination station via the shortest possible path.

In Fig. 8 origination station A is connected via links K, E, and H. In Yates' method, shown in Fig. 9, a repetitively available time slot is reserved for each station allowed to transmit new traffic. During the initiation of each time slot all stations in the network listen over all their input lines to their neighbors. The leading edge of the first signal to arrive at each node via the several input lines throws local switches to disconnect all other input lines. Figure 9 shows four digital signals racing to arrive via lines 1, 2, 3, and 4. The message arriving first came over line 3. Thus, the switching node ignores later inputs from all stations other than from line 3. The signal from line 3 is amplified and sent outward on all connected outgoing lines. This procedure is shown to produce Yates' goal of transmitting messages which flood the network and try all possible paths, yet avoids the "ring-around-the-rosy" effect (i.e., a defective route selection doctrine which allows tandem points which form a closed loop to be tried; the result is identical to falling into "a closed loop" in an improper computer pro-gram--useful work ceases until the loop is broken).

In Yates' approach, time slots must be assigned to every potential user. If the potential user has nothing to transmit during his time slot, this time is generally wasted. Each transmitting station floods the entire network, and so the system lends itself to simultaneous user-to-user communication between pairs of end users.

Random Repeated Relay

In early 1958, Jack Carne of The RAND Corporation suggested a random relay scheme designed for transmitting a small volume of critical data over a meteor-burst network (see Fig. 10). Carne's notions have not been described in any published document, but Carne examined his scheme using pencil-and-paper Monte Carlo simulation to provide an indication of whether it would work or not.

The scheme uses memory at each node of the network to implement a store-and-forward relay operation. Long-range meteor-burst transmission radio propagation occurs when a meteor trail is in a favorable point in space to cause reflection of a transmitted station radio beam to a ground station. These links are fundamentally unreliable, since favorably located meteor trails occur only on a random basis. Carne's propagation rules were:

  1. Each node has sufficient storage to simultaneously store messages from all potential transmitting stations;

  2. Each message from each origination station carries a time-stamp or a serial number tag;

  3. Each station serially transmits the latest message it has received from each possible transmitting station;

  4. Each station receives data from several stations and sends to several stations;

  5. New traffic serves to flush out old traffic;

  6. A serial number appended to each standard-length message block provides a means for selecting newer traffic in preference to older traffic.
The original application envisioned for this doctrine had a low data rate requirement, where the efficiency of network utilization was not important.[1]

Directional Relay

In 1959, Lt. Colonel Todd Williams of the Rome Air Development Center proposed a circuit-switched system comprising a linear grid array of microwave stations transmitting voice-bandwidth frequency-division channels. Any array of stations in which each node is connected to its neighbors by four or fewer links (planar networks) can be drawn in the form of a rectangular grid for ease of analysis or description.

Williams recently graciously supplied the writer with a detailed description of his network switching doctrine and Sharla Boehm of RAND performed a simulation of this network which compared it against distributed networks that were able to use "perfect switching"; i.e., those that test all possible paths.

Williams' routing doctrine avoided the ring-around-the-rosy problem by the following procedures:

  1. All stations in the grid array are assigned a coordinate address comprising a column and a row number (see Fig. 11-a).

  2. The coordinates of the addressee station are subtracted from those of the calling station to determine the quadrant of the addressee station relative to the calling station (see Fig. 11-b).

  3. If addressee station is in quadrant I, one can go east or north to reach the end destination; if addressee station is in quadrant II, one can go west or north to reach the end destination; if addressee station is in quadrant III, one can go west or south to reach the end destination; if addressee is in quadrant IV, one can go east or south to reach the end destination.

  4. The operation of each tandem mode is tested before the switch connection is locked up, thereby avoiding defective links.

  5. Backing out upon encountering a dead end is allowed, provided one remains in the same quadrant.

  6. After path is found, then and only then, are the circuit relays locked up.

Several assumptions were made in the RAND simulation of the Williams' network in order to compare it against the goal of perfect switching:

  1. A network array of 324 stations consisting of an 18 x 18 grid was used;

  2. The network had a uniform connectivity of redundancy level 2;

  3. There was infinite channel capacity for each switching point and link;

  4. An infinite number of drops to baseband was permitted;

  5. Only nodes were destroyed.

Because all surviving stations in a large group of adjacent surviving stations cannot always communicate with one another, except in the case of perfect switching, several different survivability criteria were used for comparison (see Fig. 12):

Criterion I (Perfect Switching)--Curve I is the number of stations contained within the largest single group of surviving stations, under the assumption of perfect switching. This curve is included as a comparison reference.

Criterion II (Williams' Switching)--Curve II is the largest number of stations in the largest single group of surviving stations with which any single station was able to communicate.

Criterion III (Williams' Switching)--Curve III is the average number of stations in the largest single group of surviving stations with which any single station was able to communicate. This demonstrates that although a station is a member of the largest single group, it cannot communicate with all of the stations in the group (see ODC-I).

Criterion IV (Williams' Switching)--Curve IV is the average number of stations with which the average station, surviving or not, was able to communicate.

There is a premium for being able to try all the path combinations possible under perfect switching--particularly in the event of heavy damage. For example, if in Fig. 11-a stations (0,5), (1,4), and (2,3) are destroyed, it would be impossible to communicate with (0,6), (1,5), (1,6), (2,4), (2,5), and (2,6), because of the quadrant-crossing limitation used to prevent the ring-around-the-rosy effect.

Williams' directional relay method has one very strong factor to recommend it: it is a relatively simple circuit-switched system able to handle voice. This simplicity must be weighed against a less than full realization of what perfect switching offers in survivability. As in any circuit-switched system, there will also be additional losses due to finite channel capacity of the links and number of tandem links that can be used.

Synchronous Flooding

In 1959, the writer, while employed at the Hughes Aircraft Company, described a switching scheme in a proposal submitted to Boeing. The peculiar requirement of the application called for a very-low-data-rate system, requiring the path-seeking ability of the Yates' system, coupled with freedom from the possibility of the network being seized by either equipment failure or by intentional acts.

The system uses what might be called a "synchronous-flooding" routing doctrine. Distances and bit rates are such that it is possible to synchronize each station in the network to operate in step. Each relay station receives messages from all adjacent stations simultaneously. The number of simultaneous messages received is as great as the number of links connecting each station. All messages transmitted by a single message origination station are simultaneously examined at each node. A decision is reached as to whether a correct message has been received and the single assumed correct message is sent out on all lines. Logical apparatus for reaching this decision is contained at each node and operates as follows:

  1. A number, called a "hand-over number," is affixed to each originated message. This hand-over number tag provides a measure of the path length traversed by each message. The hand-over number tag is incremented every time a message is relayed.

  2. The hand-over numbers of all messages transmitted by each origination station are examined simultaneously. Those messages with the lowest hand-over number are assumed to be the most recent messages and are propagated, while all other messages are dropped.

  3. Two messages arriving simultaneously and bearing the same hand-over number but differing in message content are rejected to eliminate distorted messages. Also rejected are those messages which have been sent by two separate stations, both claiming to be the same station. If two messages arrive by different directions and have the same path length, they must match. If they are different, something is wrong, and "wrong" messages are not propagated. However, no valid messages will be lost, because a verified valid message will arrive later by an alternative path.

  4. Messages bearing a hand-over number less than the predetermined minimum possible hand-over number are rejected and a trouble indication message sent For example, if two stations are a minimum of five links apart, then it is clearly impossible for messages to be transmitted from one to the other with a hand-over number of less than five.

  5. Messages having a hand-over number greater than a predetermined maximum value are assumed to be undesirably old and are rejected.

Under these selection criteria, one and only one received message survives. This latest assumed valid message is stored and held in storage until the proper transmission time frame occurs. A sequential time frame is reserved for the consecutive transmission of a standard-length message from each possible orgination station.

The relay scheme is really a broadcasting system, since each message is transmitted to all stations. Hence, it is called a "flooding" technique. Its chief merit is that in the event of fraudulent signal intervention, only a few stations in the network will receive the fraudulent message. Undesired signals are generally suppressed at most nodal points in the network. The system automatically uses its connection redundancy to provide automatic error correction. If an independent error occurs in the text portion of the message, it will be propagated only until the node is reached where comparison of messages bearing the same hand-over number takes place. Such messages will then be rejected.

The limitations of this method of propagation include:

  1. Inability to rapidly relocate the positions of stations in the network because of the minimumfixed-distance-between-nodes test;

  2. Suitability only for very low data rates;

  3. Requirement for local storage and relatively long time delays necessitated by reception of messages from several different directions.

Although synchronous flooding is perhaps somewhat more secure than other networks described, it also makes least efficient use of the communications resource.

Figure 13 is a detailed example of message propagation in this network. Signals originate at Station 22 and are transmitted simultaneously to the north, east, south, and west. Messages arriving at Station 32, for example, will bear a hand-over number of 0. The hand-over number is incremented and passed on to the next station, No. 42. Messages at Station 33 arrive from two different directions: from Station 23 bearing a hand-over number of 1; and from Station 32 also bearing a hand-over number 1. These two simultaneously arriving messages are compared. If identical, the common message is transmitted out in all four directions.

All stations other than those in the diagonally-shaded area (Fig. 13), will, simultaneously (i.e., with the same hand-over number), receive messages from two or more links. These messages must exactly match; otherwise, these messages will not be relayed. If a fraudulent Station X were to insert messages, it could, theoretically, pretend it was Station 22 to those stations on the right-hand side of the network. However, if a rule that a known minimum distance exists between any two stations is included, then this counterfeiting would be credible only within the smaller dot-shaded area. If the number of cooperating friendly stations is much greater than the number of fraudulent stations, then even these few fraudulent stations can be located or cut out of the network with little impairment of residual network performance.

Saturation Signaling

In 1959, Gunnar Svala of the North Electric Company described a circuit-switching arrangement which he calls "saturation signaling." In this system, high-speed signaling information is broadcast throughout the entire network. When the end-party responds, a circuit is established between the called end-party and the calling party and all the tentative searching connections are closed off. In saturated signaling, each node or switching center may be connected to adjacent neighbors in the canonical manner of the distributed network. Each switching center is essentially a conventional switched toll-telephone exchange, but with the addition of a rapid-access memory and a sequential line-scanning device.

The rapid-access memory keeps a record of the telephone numbers of all local subscribers currently connected to the local switching center. The rapid-scanning device sequentially examines all circuits (trunks and lines) connected to the switching center.

Basically, the system uses a flooding technique in which the called number is transmitted throughout the network in a manner somewhat similar to Yates' method. Ring-around-the-rosy is prevented by each switching center asking the question, "Have I just received this called number?" The rapid-access memory at each node traversed is scanned until the called number is found. At this time, revertive signals are sent which lock up the circuit connection.

Figure 14 illustrates the propagation of signals in Svala's system. Switching center A transmits the telephone number of the party being called to several adjacently connected stations, B, C, and E. Each of these centers examines its own local memory to see if the called station is a local one. If not, the called number is relayed to other switching centers.

The saturated signaling system appears to be a form of perfect switching with the resulting high survivability expected from such systems. There is, of course, an inevitable set of problems found in any complex system of this sort. What happens if many of the stations are destroyed? Will there be blocking because the signaling is overloaded while waiting to time out? How much time is spent in signaling relative to active circuit usage? These questions are most readily answered by a simulation, and such simulation is being conducted by the North Electric Company under a feasibility study contract with the U.S. Army Research and Development Laboratories.

A key feature of this network is that it allows a user to move across the country and take his telephone number with him. He has only to inform his last connected central office and his new one of the change of address.

Two-Phase Routing

In 1960, John Bower, in a patent disclosure entitled, "Logic for an Interconnected Net," described (in operational form only) a communication system which would essentially operate in two sequential time phases. During time phase A, information at the nodes on the status of traffic loads at each station in the network is transmitted to all other nodes. Each node contains memory to record the status, thereby enabling it to determine the optimum direction for routing traffic to any given end station. During a much longer time phase B, useful traffic is sent, based upon a flow pattern that corresponds to the most recent network status and loading measurements.

Hot-Potato Routing

In 1960, the writer suggested the use of a "hot-potato" routing doctrine upon which to build a common-user, all-digital communications network; this system is described in detail in the other papers of this series. All traffic is converted to digital signals and blocked into standardized-format packets of data. Each packet of data, or "message block," is rubber-stamped with all the signaling information needed by other stations to determine optimum routing of the message block.

The system has a set of properties that are markedly different than present-day networks. Some are advantageous and others disadvantageous. These are described in detail in ODC-XI. Briefly, some of the features include:

  1. Very efficient usage of time-shared digital links;
  2. A high upper limit on allowable data rates;

  3. Relative immunity to the effects of illicit intervention;

  4. Application of a future all-digital network communication requirement;

  5. Allows a reliable system to be built using lowcost and unreliable links.
The disadvantages of the hot-potato system include:
  1. It is fundamentally an all-digital system;

  2. It requires a more complex routing logic at the nodes than has ever been previously attempted.
In summary, one pays the price of logical switching complexity but buys a set of unusual network properties; e.g., the network can handle digital data on an extremely short-term store-and-forward basis, and the system appears to be able to handle "real-time" digital voice.

Tessellated Network

In 1961, Jack Craig of The RAND Corporation proposed a "Tessellated Network."[2] This network was designed to meet the communications requirements of a specific task- -the air defense problem. In this network, each station transmits information to a small ring of adjacent stations. The inherent broadband capability of a microwave link is utilized together with conventional frequency division multiplexing to provide a large number of separate voice bandwidth channels. These channels are then so assigned that separate channels emanate from each station to adjacent stations. Switching per se, is not used. Craig and Reed suggest that a modest amount of manual patching at each node can be used to restore communications between essentially adjacent stations after attack. While this network makes inefficient use of a broadband channel by conventional communication practices (since but few of the potential channels in the microwave link are in active use), it should be pointed out that all distributed networks designed to withstand heavy attack are fundamentally inefficient. After attack, the last surviving link of the redundant network might have to carry the entire network traffic. Therefore, one must start with a built-in excess capacity. To build a network with merely enough capacity to handle the normal pre-attack load, is to be certain of not having enough capacity after an attack. While the tessellated network, conceptually, is the simplest of the networks proposed, it appears to be of primary use in those cases where a station usually needs only to speak to adjacent stations or stations only a few spans away. If the tessellation is extended to too many remote stations, the bandwidth (number of channels required) builds up tremendously, and survivability decreases markedly due to the requirement for a greater number of tandem serial connections.

The survivability of a network using tessellation is highly dependent upon the span distance required, given finite bandwidth link capacities. If the span distances are short, with connection made only to adjacent stations, the survivability of the network is excellent--resembling perfect switching. But, if the span distances between connected nodes are very great, then the survivability will be closer to that of diversity of assignment--leaving much to be desired. The efficacy of diversity of assignment drops off markedly with increasing span length (see ODC-I).

[1]The equipment necessary to implement a meteor-burst system using this routing doctrine was examined in an unpublished study written by the consulting engineering firm of Janskey and Bailey, Washington, for The RAND Corporation.

[2]Craig, L. J., and I. S. Reed, Overlapping Tessellated Communications Networks, The RAND Corporation, P-2359, July 5, 1961.

V. Conclusions
Appendix A. Summary Charts
Appendix B. The DDD System
List of Publications in the Series