Abstract

Packet routing on multistage interconnection networks such as butterfly and shuffle-exchange experiences a delay of $O\left(\sqrt{N}\right)$, where N is the number of processing elements, when several packets have to travel the same path. Furthermore, these interconnection networks do not provide good fault tolerance because a small number of physical paths correspond to each logical path even when additional stages are used. Expander graphs have been shown to support asymptotically optimal parallel algorithms and routing. Leighton and Maggs¹ demonstrated that random permutations applied to the conventional butterfly network tend to distribute the messages equally on the average over all links, thus significantly reducing contention. Simulations show that these two-butterfly networks have significantly lower delay and better fault tolerance (up to N^3/4 random faults). Arora et al.² recently gave an on-line algorithm for nonblocking routing using two back-to-back 2-butterflies. We examine the implementation requirements of the two-butterfly network and conclude that optoelectronic technology is favorable for large scale implementation.

© 1991 Optical Society of America