TY - GEN

T1 - DISTRIBUTION OF WAITING TIMES IN CLOCKED MULTISTAGE INTERCONNECTION NETWORKS.

AU - Kruskal, Clyde P.

AU - Snir, Marc

AU - Weiss, Alan

PY - 1986/12/1

Y1 - 1986/12/1

N2 - An analysis is made of the random delay experienced by a message traversing a buffered, multistage packet-switching banyan network. The generating function for the distribution of waiting times at the first stage of the network is found for a very general class of traffic, assuming that messages have discrete sizes. For example, traffic can be uniform or nonuniform, messages can have different sizes, and messages can arrive in batches. For light to moderate loads, the authors conjecture that delays experienced at the various stages of the network are nearly the same and are nearly independent. This allows them to approximate the total delay distribution. Better approximations for the distribution of waiting times at later stages of the network are attained by assuming that in the limit a sort of spatial steady-state is achieved. Extensive simulations confirm the formulas and conjectures.

AB - An analysis is made of the random delay experienced by a message traversing a buffered, multistage packet-switching banyan network. The generating function for the distribution of waiting times at the first stage of the network is found for a very general class of traffic, assuming that messages have discrete sizes. For example, traffic can be uniform or nonuniform, messages can have different sizes, and messages can arrive in batches. For light to moderate loads, the authors conjecture that delays experienced at the various stages of the network are nearly the same and are nearly independent. This allows them to approximate the total delay distribution. Better approximations for the distribution of waiting times at later stages of the network are attained by assuming that in the limit a sort of spatial steady-state is achieved. Extensive simulations confirm the formulas and conjectures.

UR - http://www.scopus.com/inward/record.url?scp=0022880931&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022880931&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0022880931

SN - 0818607246

T3 - Proceedings of the International Conference on Parallel Processing

SP - 12

EP - 19

BT - Proceedings of the International Conference on Parallel Processing

A2 - Hwang, Kai

A2 - Jacobs, Steven M.

A2 - Swartzlander, Earl E.

PB - IEEE

ER -