O(n) routing in rearrangeable networks

In (2n-1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Omega(n(2)) compared to its propagation delay O(n) only. Her e, we attempt to identify the sets of permutations, which are routable in O (n) time in these networks. We define four classes of self-routable permuta tions for Benes network. An O(n) algorithm is presented here, that identifi es if any permutation P belongs to one of the proposed self-routable classe s, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both probl ems are resolved in O(n) time by this algorithm. It covers all the permutat ions that are self-routable by anyone of the proposed techniques. Some inte resting relationships are also explored among these four classes of permuta tions, by applying the concept of 'group-transformations' [N. Das, B.B. Bha ttacharya, J. Dattagupta, Hierarchical classification of permutation classe s in multistage interconnection networks, IEEE Trans. Comput. (1993) 665-67 7] on these permutations. The concepts developed here for Benes network, ca n easily be extended to a class of (2n-1)-stage networks, which are topolog ically equivalent to Benes network. As a result, the set of permutations ro utable in a (2n-1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent. (C) 2000 Elsevier S cience B.V. All rights reserved.