On Distributed Communications Series

III. Determination of Path-Lengths in a Distributed Network

III. Computational Techniques

Monte Carlo Simulation

The simulator is described in detail in the program listing of Appendix B; briefly, it operates in the following manner:
  1. a network is defined in terms of its size, configuration, and connectivity;
  2. link-lengths are assigned--as transmission times--by being drawn from a uniform distribution bounded by the parameters TPMAX and TPMIN;
  3. the hand-over number tables, Hi, are preset to either
  4. a fixed number,
  5. the routing and transmission of messages through the network is directly simulated by applying the routing doctrine Rl;
  6. delivery or dropping of a message results in the insertion of a new "random" message into the network, thus maintaining loading;

  7. new messages may be "choked" by applying R1 first to enroute messages, then to new messages (which are, in effect, kept on a special stack).
The parameter

where ML is the processing time per message-unit (i.e., message-unit length). (TPMAX-TPMIN)/2 is the average line-length (or average transmission time), and a message-unit requires ML time units to be inserted into or with-drawn from a link. In (3.1),

Under uniform loading in a fully loaded network, at each time period all links would be jammed and all stations would be simultaneously accepting and transmitting a message. The average number of messages in a fully loaded network would, therefore, be equal to

The loading ratio of a network is then equal to

Model A (Ma)

A model of network behavior is abstracted by considering the four possibilities that exist for the disposition of messages at any station (disregarding the possibility of dropout). A message being routed at a station has associated with it that station' 5 prediction of the best-path length to the message's addressee. The message may either
  1. remain at the station, or
  2. be retransmitted to a neighbor whose best-path prediction is
    1. one (1) less than the previous station's prediction,
    2. the same as the previous,
    3. one (1) greater than the previous.

That is, links may be characterized as being "best," "next best," or "worst" for any message. The model defined in Fig. 2 assumes:

  1. a uniform distribution of links with respect to "best," "next best," and "worst" overall addressees;
  2. a uniform probability,
  3. uniform loading;
  4. stations connected to neighbors only.
The first assumption is the weakest of the four; however, within the interior of "reasonably" connected networks satisfying the last assumption, it is "reasonably" valid.

Model B (Mb)

Model B is obtained from the previous one by aggregating "next best" and "worst" links. In Mb, therefore, a message at a station whose best-path prediction for the message is, say, n, will have a probability p(n,x) of being delivered in x traverses, given by

Comparison of Results

The three techniques were applied to networks of size 10x10 and 14x7, using redundancy levels of 2, 3, and 4. Figure 3 exhibits the results of the 14x7, redundancythree case--all other runs produced the same behavior; Fig. 4 tabulates statistics for the various runs.

Relation (3.1) was used to equate simulator loading with the probability of link impairment,

Figure 4 indicates that the transition from a redundancy level of three to a level of four results in diminishing returns. For redundancy levels greater than two, it appears that an HMAX equal to twice the longest best-path is sufficient to reduce dropouts to the "noise" level under normal, arid even higher than normal, loadings

[1] This defines "uniform" loading.

Previous chapter
Next chapter