On Distributed Communications Series

III. Determination of Path-Lengths in a Distributed Network

I. Introduction

The distributed communications network examined in this Memorandum is a collection of communication stations interconnected in a more or less regularized manner and employing a common switching doctrine. The connectivity is such that the number of bi-directional lines (or unidirectional links) between a station and its neighbors is constant over the interior of the network; lengths and bandwidth capabilities of the lines may vary over the network. Switching, or routing, is performed by choosing a "best" initial link toward a desired addressee, rather than by attempting to choose a "best" overall path.

Certain stylized connectivities may be introduced to define the redundancy level of such networks--the concept is illustrated in Fig. l.[1] It is useful and instructive to deal with such connectivities, and we shall do so. However, many of the observations reported in this Memorandum are dependent on a constancy of connectivity and routing doctrine rather than on any specific regularity of connectivity.

The choice of a "best" initial link is effected by adjoining to each station, Si a matrix, Hi, which assigns to each link, Lj,i, of station Si a measure, Hi(J,K), of link j's merit as an initial link along which to route messages destined for station Sk--for all stations, Sk, in the network. The figure of merit used in this Memorandum is the expected number of stations to be traversed before delivery of the message. That is, a value, K = Hi(j,k), states that station Si expects a message destined for station Sk that is sent out along link Lj,i to traverse K stations before delivery. By adjoining to every message an integer, h--the hand-over number, which is incremented by unity each time the message is retransmitted by a station--the values of Hi may be continuously updated as a function of the hand-over numbers associated with incoming messages and of the current values of Hi. Messages are routed by applying a decision procedure to those Hi values pertinent to the messages' destinations.

The transient behavior of the Hi, and of message-flow as the Hi change under suitable updating algorithms, is discussed in ODC-II. The present Memorandum is concerned with "steady-state" flow, wherein the Hi have assumed their "best" values and there remain fixed.

[1] Figure 1 is taken from ODC-I, where the concept of redundancy levels is fully described; ODC is an abbreviation of the series title, On Distributed Communications. The number following refers to the particular volume within the series.

Next chapter