A closed form formula for the normalized throughput of unbuffered multistage interconnection networks

Abstract

The normalized throughput of an unbuffered multistage interconnection network (MIN) under the uniform traffic model can be computed iteratively [6] or recursively [7]. However, the asymptotic performance of such networks as the number of stages increases cannot be determined using these procedures. A closed form formula for the normalized throughput of unbuffered MINs is presented in this paper. The new formula is proved by mathematical induction on the number of stages. The major advantage of the closed form formula is that the asymptotic performance of unbuffered square MINs can be easily determined. The formula is generalized to unbuffered MINs in the presence of nonidentical input rates and non‐square switch size.