Permutation networks have been used in the literature to model interprocessor and processor-memory interconnections in parallel computers. This paper introduces new permutation network designs and generalizes the notion of a permutation network to provide a more flexible model of such interconnections. The new designs are based concentrators and superconcentrators, and for (n) inputs they can be optimized to obtain self-routing permutation networks with (O(n \lg n)) cost, (O(\lg n)) depth, and (O\left(\lg ^{2} n\right)) routing time. ({ }^{1}) The main feature of these new network designs is that they do not require complex routing schemes such as Clos networks since they are inherently self-routing. Generalizations of these designs are also given to obtain permutation networks in which the numbers of inputs and outputs may be different, and/or the maximum number of parallel routes between inputs and outputs can be less than the number of inputs or outputs, or both. For (n) inputs, (\alpha n) outputs, and (O\left(n^{\epsilon}\right)) parallel routes, where (0<\alpha \leq 1), (0<\epsilon<1), these generalized designs can be optimized to have permutation networks with (O(n)) cost, (O(\lg n)), depth, and (O\left(\lg ^{2} n\right)) routing time. It is shown that the previously known designs, such as Clos networks, result in inferior realizations when compared with these new designs. 1994 Academic Press, Inc.