On Distributed Communications Series
III. Determination of Path-Lengths in a Distributed Network
IV. Input-Choking and Stack Lengths
Input-choking 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),
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
|(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:
- dropouts will occur tinder no-choke conditions; to insure a low dropout rate, STACK will have to be unconscionably large--hence, unfeasible;
- under uniform loading, no-choking produces a small, uniform increase in loading;
- 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.
 See p. 9.