THE COMPOSITE BANYAN NETWORK

A new multipath multistage interconnection network called the composit e banyan network is proposed. The network incorporates both the banyan and the reverse banyan networks and is constructed by superimposing t he two. The basic building blocks in the composite banyan network are 3 x 3 switching elements with log(2)N stages. A major advantage of the composite banyan network over existing networks with 3 x 3 SEs is an efficient and fast control algorithm that sets up a path between any s ource and destination pair. Instead of complex numerical calculations, the network can easily generate a primary routing tag and alternate t ags through simple binary operations. Also, the network has a lot of f avorable features, including regularity, symmetry, and easy rerouting capability under faults and conflicts. It is shown that at least two t otally disjoint paths exist between any source and destination pair, w hich increase the degree of fault-tolerance. A deterministic permutati on routing algorithm is also developed for the 8 x 8 composite-banyan network, Using a simple tabular method, it is shown that the algorithm always finds a set of conflict-free tags.