On nonuniform packet switched delta networks and the hot-spot effect

The author analyses the performance of a multistage interconnection network (MIN) with a packet-switching protocol, embedded in a closed network of processors. First, the expected value of transmission time through a delta-2 type of MIN is determined. A formula for its probability density function is obtained from which the variance and higher moments follow. Previously densities have only been estimated by simulation which is expensive and can be unreliable, especially in the often crucial tail region. Numerical results reveal new insights into the hot-spot phenomenon which occurs when one output address is selected more frequently than the others. The author first shows how mean transmission time on hot paths increases with the hot-spot intensity and compares this with cooler paths. He also plots the density functions for these transmission times. Hence it is possible to determine precisely transmission time variability and to obtain reliability measures from their tails. The approach can handle arbitrary routing frequencies to the MIN output addresses and suggests new approximation techniques with wider applicability.