ON THE DISTRIBUTION OF DELAYS IN BUFFERED MULTISTAGE INTERCONNECTION NETWORKS FOR UNIFORM AND NONUNIFORM TRAFFIC.

The random delay experienced by a packet traversing a buffered, multistage, packet-switching banyan network is analyzed. The generating function for the distribution of delays at the first stage of the network is found for uniform traffic and for a very general class of nonuniform traffic. It is conjectured that delays experienced at the various stages of the network are nearly the same and are nearly independent, which allows the total delay distribution to be approximated. In the case of uniform traffic (i. e. each input node sends a packet to every output node with equal probability), better approximations for the distribution of delays at later stages of the network are attained by assuming that in the limit a sort of spatial steady state is achieved. Finally, messages composed of more than one packet are considered. Extensive simulations confirm the conjectures and formulas.