## Abstract

We analyze the random delay experienced by a message traversing a buffered, multistage packet-switching banyan network. We find the generating function for the distribution of waiting time at the first stage of the network for a very general class of traffic, assuming 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, we conjecture that delays experienced at the various stages of the network are nearly the same and are nearly independent. This allows us 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.

Original language | English (US) |
---|---|

Pages (from-to) | 1337-1352 |

Number of pages | 16 |

Journal | IEEE Transactions on Computers |

Volume | 37 |

Issue number | 11 |

DOIs | |

State | Published - Nov 1988 |

Externally published | Yes |

## Keywords

- Banvan networks
- discrete networks
- interconnection networks
- parallel processing
- performance analysis
- queueing theory

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics