On Distributed Communications Series

III. Determination of Path-Lengths in a Distributed Network

II. The Routing Doctrine

Let So, Sd, and h refer to a message's originating station, addressee, and hand-over number, respectively. Messages arriving at station Si via link Lj,i cause the values of Hi

to be updated by the following updating doctrine (Ul):

Let station Si have links


and let HMAX, the maximum allowable hand-over number, be a fixed parameter. Station Si retransmits messages by applying the following routing doctrine (Rl):

In practice, the Hi are originally set equal to HMAX; as messages move through the network, these values eventually assume their absolute minima. These minimum values may be calculated a priori by a best-path[1] algorithm.

That is, B(i,k) is the length of the best path from Si to sk, Nx is the number of such best paths of length x, and x' is the length of the longest best path. The distribution, B, defined by

is called the best-path distribution for the network. It will be shown later that B is of great utility in predicting traffic-flow in steady-state networks. If messages are generated by choosing origins and destinations randomly from a uniform distribution of stations, and if each message is completely routed through the network before the next message is originated, then the resulting distribution of message path-lengths is clearly B. That B is equally valid for low-load conditions is shown by Fig. 3,[2] to be discussed later.

The HMAX test in routing doctrine Rl is essential. Traffic will, in practice, be cut into message blocks of fixed length and be sent piecemeal (but serially). If the differential time delay is excessive, then the order of arrival of these message blocks could fall out of sequence. This differential time delay is equivalent to the difference in hand-over numbers of the arriving message blocks. Therefore, the lower the tolerable maximum hand-over number, the higher the overall data rate between two network users will be. We also chose to drop message blocks whose hand-over number exceeds this maximum allowable, to insure flushing out message blocks addressed to nonexisting stations. Since fixing the length of message blocks implies fixing station processing time (for routing), network time may be equated to station traverses by using an average link-length for the network, and temporal decisions can then be made on the basis of some maximum hand-over number and the handover number associated with messages. Thus, the problem of choosing an HMAX small enough to maintain "integrity" of communications, yet large enough to guard against excessive message dropout is a central one. The choice of such a value for a given network depends on a knowledge of the distribution of message path-lengths of delivered messages under varying traffic densities and using an unbounded HMAX. Three methods for determining such distributions--Monte Carlo simulation, mathematical modeling, and approximate calculation--are described and compared in the next section.


[1] See Sec. VI.

[2] See p.14.


Contents
Previous chapter
Next chapter