A study of permutation networks: some generalizations and tradeoffs
A. Yavuz Oruç · 1991
Permutation switching is a critical element of many computer and communication systems. Within a group theoretical framework, this paper provides an indepth study of permutation networks, and examines the tradeoffs between network cost and set up or routing time. It introduces the notion of an (n, r, q)-permuter, i.e., a permuter with n inputs and r outputs that can realize all q! permutations between any q of its n inputs and q of its r outputs, where q ≤ r ≤ n. This generalization accounts for a switching environment where the maximum number of simultaneous paths may be less than the actual number of inputs and outputs. It is shown that the previously known designs, such as Clos networks result in inferior realizations of (n, r, q)-permuters. Using concentrators, the paper gives new network designs that lead to (n, r, q)-permuters with asymptotically minimum cost and quadlogarithmic routing time for all q ≤ r. More specifically, for q = O(lg n) and q = O(n ɛ), where 0 <ɛ<1, an (n, r, q)-permuter with O(n) switches is given 1. For the same values of q, Clos designs require at least n lg lg n and n lg n switches. Another advantage of the new designs is that they do not require complex routing schemes as Clos networks since they are inherently self-routing. It is also established that, when q = n = r, these same designs can be extended to permuters with O(n lg n) switches.