On Distributed Communications Series

III. Determination of Path-Lengths in a Distributed Network

IV. Input-Choking and Stack Lengths

Input-choking[1] in networks has two important consequences. First, since a link can be usurped by a message for no greater period of time than it takes to insert a message into a link (ML), it is clear that stack length can never exceed the number of links associated with a station; that is, stations require only one "word" of stack storage per link. Moreover, choking tends to smooth out potential activity peaks, particularly in the vicinity of "hog" stations and around the center of the network. Removal of input-choking simply means that new messages are treated as enroute messages. Under such conditions, stack lengths cannot be contained. Since stack storage must be finite, a new message-dropping criterion must be added to the routing doctrine, Rl:

(Rl) d) if no links are available and the stack is full, the message is dropped.

Thus, the choice of a fixed stack-storage length, STACK, large enough to reduce stack dropouts to the noise level, becomes as important as a choice of HMAX. Since stack length is a highly local phenomenon--strongly dependent on traffic distributions--there seemed to be no simple way of determining STACK without direct simulation. Accordingly, the simulator was applied--with no input-choking--to a 14x7 net of redundancy-three, with maximum stack lengths of 6, 9, and 12. The distributions obtained were almost identical to the "choked" distributions. They are not reproduced here; however, Fig. 5 compares the pertinent simulations, and leads us to the following conjectures:

  1. dropouts will occur tinder no-choke conditions; to insure a low dropout rate, STACK will have to be unconscionably large--hence, unfeasible;
  2. under uniform loading, no-choking produces a small, uniform increase in loading;
  3. hence, there seems to be no justification for adopting a no-choking doctrine.

These conjectures are fortified by a consideration of the distribution of total time in stacks (including inputwaiting time) for delivered messages. These distributions were identical for the choke and no-choke cases. In fact, the distributions shown in Fig. 6 were typical of all networks simulated; they show that the probability of excessive delays-in-stack is exceedingly small, even under high loading.

[1] See p. 9.

Previous chapter
Next chapter