On Distributed Communications Series
V. History, Alternative Approaches, and Comparisons
Contents
Preface
Summary
I. Introduction
II. The Distributed Network Concept
Definition of "Distributed Network"
In ODC-I[1] it is suggested that the term "distributed network" is best used to delineate those communications networks based on connecting each station to all adjacent stations, rather than to just a few switching points, as in a centralized network. It is difficult to limit the use of the term to describe a single network, since it is frequently used in this broader meaning--as delineating that portion of the spectrum of networks having a more decentralized configuration than those which exist as a single, inseparable entity.
Various modes of system connectivity--i.e., configurations--are depicted in Fig. 1. Figure 1-a shows a centralized communications network; Fig. 1-b, a decentralized network; and, Fig. lc, a distributed network. Figure l-d is a series of points along a continuum, representing more accurately how Figs. 1-a, 1-b, and 1-c delineate zones on a broad spectrum of possible system designs where the boundaries between zones are fuzzy.
To appreciate how fuzzy these boundaries can be, consider Fig. 2. One very large communications network in existence today is called the "spider web." When this network is viewed in a schematic, one obtains the illusion of Fig. 2-a. However, when only allowable paths between nodes are examined, one finds the number of such possible paths highly limited; so much so in fact, that it would appear that the network is formed by a superposition of the separate overlay networks of Fig. 2-b and Fig. 2-c. It can be seen that there is little, if any, connection of the warp and the woof of the spider web. While Fig. 2 is an exaggeration of such actual networks, Fig. 3 is a somewhat less strained example of this phenomenon; the separate non-switchable links are shown on maps, as in Fig. 3-b. Thus, one must be careful in examining a graph of a communications network in considering the limitations of signal paths at the nodes. To do otherwise would lead to confusing a network with nil survivability with a highly connected and more survivable one having full switching capability at all nodes.
We are thus interested specifically in communication switching node doctrines that are able to produce "efficient" traffic routing using "local control only" and without need for a central control point. A second payoff for use of local control is that it avoids telling a possible enemy precisely which links are not destroyed, a probable occurrence should it be necessary to transfer network station and link information to a remote control point.
Definition of Perfect Switching
"Perfect switching" is defined as that form of switching that permits a connection to be established between any two points in a network composed of short links that connect switching nodes. Each link terminates at two and only two switching nodes and any number of tandem links may be used to form the connection. The channel capacity of all links and nodes permits all such possible connections to exist simultaneously. This implies "no blocking"; i.e., establishment of any connection between two points shall not preclude connection between any two other points.
Heuristic Learning
The underlying concept of distributed networks is as old as man. Any interconnected grid of paths or roads may be considered as being a distributed network. When one drives to work over a distributed (or grid) road system and encounters a potential delay, it is possible to turn off, bypassing the traffic jam or obstruction. Thus, the actual route taken depends not only upon a predetermined route, but also upon the happenstance of encountering necessary detours which take us off the preferred shortest path. In spite of this uncertainty, and regardless of the number of detours, we almost always manage to get to work. On some mornings when we have a little extra time, we may chance to try a route that we have never taken before. If we find that this new route is quicker because of less traffic than our old route, we will probably take this newer route in the future. By this process, we learn in a relatively short time the quickest route between home and work. We may say that we have used a "heuristic" process to learn a "best" path in a network.
While this Memorandum examines different types of distributed communication networks, we shall emphasize the development of those networks that use heuristic route-learning.
Store-and-Forward Versus Circuit Switching
Networks are described as being either of the store-andforward type or the circuit-switched type. If the switches at the switching nodes of a network are semi-permanently engaged so that a "real-time" channel exists between the calling and called parties, circuit switching is being used. If messages are relayed from a source station via relay stations and stored at each relay station until a circuit is available to the next relay station (as in a telegraph system), store-and-forward switching is being utilized. The differentiation between the two categories, store-and-forward switching and circuit switching, is not always precise. For example, present-day telephone switching practice is called circuit switching, yet it makes use of a store-and-forward technique to relay dial pulses from switching center to switching center. When a call is placed from New York to Los Angeles, store-and-forward is used to establish the switching connection. After the connection is established, circuit switching commences. Thus, we must exercise caution in the interpretation of these differentiating terms.
Need For Switching
Figure 4-a shows three stations, A, B, and C, that are to communicate with one another. Three bi-directional links are required. In Fig. 4-b six stations, A, B, C, D, E, and F, are to communicate with one another. Fig. 4-c plots the number of links required as a function of the number of terminal stations in a network in which each station must be able to communicate with every other station in the network and where no switches are allowed. The number of links required by the network is
where N is the number of terminal stations. Thus, the number of links in this communication network will increase roughly as the square of the number of stations in the network. To keep the number of links in the network within reason as network size increases, we are forced to the expedient of Fig. 5. In Fig. 5-a we see three links connecting three communications stations; but, in Fig. 5-b we add a switching center, W, to connect A to B or to C, as needed. (If A is speaking to B, then there is no need for a channel between A and C, since A is already busy.) Figure 5-c shows six stations, each communicating with one another. If we imagine the links of Fig. 5-c as rubber bands, the links can be bundled in any manner without upsetting the basic topography of Fig. 5-c. We can visualize all the stations being connected to a single node as in Fig. 5-d or alternatively, we can connect the stations to the two separate switching nodes Y and Z.
Figure 5-f shows 12 stations interconnected to one another. One can visualize the large number of possible groupings of these "rubber-band" links, such as in Figures 5-g and 5-h.
In the past much work has been done to pick that network topology that most economically connects stations or groups channels in such a manner by applying switching at the nodes. It is not necessary to always have as many separate channels to connect switching stations R to S, for example, as there are link paths in Fig. 5-f. At any one time, very few of the subscribers in the network will be talking. If there were an overload between switching station R and S, for instance, then by proper design of the switching centers and transmission characteristics of the links, an alternate path might be found from R to U, to T, to S, and so on to the eventual end station. When-ever it is necessary to have a large number of stations communicate among a large number of potential addressees, it is a practical necessity to use some form of switching. There is always a very wide variety of potential groupings and possible network configurations. The shape and complexity of the resulting network is very much dependent upon the economies one wishes to make in circuit groupings. The choice of these groupings in turn depends upon the statistics of the expected traffic. If the traffic statistics are known very accurately, large savings in cost of selection of routes and assignment of channels can be realized. However, if it is necessary to build a military network whose configuration and demands are subject to drastic changes with little advance notice, then a network whose design is based on peace-time statistics may be expected to block, or overload, and prevent fulfillment of the original goal--i.e., permitting any subscriber to talk to any other subscriber.
[1]ODC is an abbreviation for the series title, On Distributed Communications. The numeral refers to the specific volume in the series. A list of all items in the series is found on p. 49.
III. Early History
IV. Specific Hardware Proposals
V. Conclusions
Appendix A. Summary Charts
Appendix B. The DDD System
List of Publications in the Series