On Distributed Communications Series
III. Determination of Path-Lengths in a Distributed Network
III. Computational Techniques
Monte Carlo SimulationThe simulator is described in detail in the program listing of Appendix B; briefly, it operates in the following manner:
- a network is defined in terms of its size, configuration, and connectivity;
- link-lengths are assigned--as transmission times--by being drawn from a uniform distribution bounded by the parameters TPMAX and TPMIN;
- the hand-over number tables, Hi, are preset to either
- a fixed number,
- the routing and transmission of messages through the network is directly simulated by applying the routing doctrine Rl;
- delivery or dropping of a message results in the insertion of a new "random" message into the network, thus maintaining loading;
- 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).
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
- remain at the station, or
- be retransmitted to a neighbor whose best-path prediction is
- one (1) less than the previous station's prediction,
- the same as the previous,
- 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:
- a uniform distribution of links with respect to "best," "next best," and "worst" overall addressees;
- a uniform probability,
- uniform loading;
- stations connected to neighbors only.
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 ResultsThe 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
 This defines "uniform" loading.