Title :
Fast self-routing permutation switching on an asymptotically minimum cost network
Author :
Jan, Ching Yuh ; Oruç, A. Yavuz
Author_Institution :
Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA
fDate :
12/1/1993 12:00:00 AM
Abstract :
A self-routing permutation network with O((n lg n)) switches and O(lg2n) routing time, where lg denotes log2, is presented. More generally, a permutation network with O(kn1+1k/) cost and O(k lg n) routing time for any k, 1⩽k lg n, is described. This improves D. Nassimi and J. Sahni´s (1982) routing algorithm that gives O(k lg3 n) routing time for the same cost expression. The only networks capable of permutation switching with O(n lg n) cost and O(lg n) routing time are the AKS sorting network and E. Upfal´s (1989) packet routing network, but the constants hidden in the complexities of these networks are so large that they remain impractical until n gets very large
Keywords :
computational complexity; multiprocessor interconnection networks; packet switching; AKS sorting network; asymptotically minimum cost network; complexities; cost expression; packet routing network; self-routing permutation switching; Communication switching; Computer networks; Cost function; Logic devices; Logic gates; Multiprocessor interconnection networks; Packet switching; Routing; Sorting; Switches;
Journal_Title :
Computers, IEEE Transactions on
