The Batcher-banyan self-routing network: universality and simplification
- 1 January 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 36 (10) , 1175-1178
- https://doi.org/10.1109/26.7538
Abstract
It is shown that the Batcher-banyan network performs as a universal self-routing switch when inputs with unassigned destinations are present. This is demonstrated by first proving that banyan networks can realize permutations represented by bitonic sequences, and then noting that the sorted output of the Batcher network can be viewed as a bitonic sequence. Two methods are proposed for reducing the complexity of the Batcher-banyan network. In the first method, one stage of the banyan network is eliminated by assigning proper destination tags to the unassigned inputs. In the second, a self-routing switch based on the binary-radix sorting scheme is shown to be more economical for a small number of lines. >Keywords
This publication has 7 references indexed in Scilit:
- A Broadband Packet Switch for Integrated TransportIEEE Journal on Selected Areas in Communications, 1987
- On the Rearrangeability of 2(Iog2N) –1 Stage Permutation NetworksIEEE Transactions on Computers, 1985
- The Universality of the Shuffle-Exchange NetworkIEEE Transactions on Computers, 1981
- Study of multistage SIMD interconnection networksPublished by Association for Computing Machinery (ACM) ,1978
- Access and Alignment of Data in an Array ProcessorIEEE Transactions on Computers, 1975
- Banyan networks for partitioning multiprocessor systemsPublished by Association for Computing Machinery (ACM) ,1973
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971