On the Rearrangeability of Some Multistage Connecting Networks

A multistage connecting network can be described by the following (see Fig. 1 for a three-stage example): (i) There are s ordered stages, where s > 1 is arbitrary. The ith stage, i = 1, · · ·, s, consists of r, copies of a switch i>,-. The jth copy of vi is denoted by vij. (u) Links can exist only between switches of adjacent stages or between v(vt) and input (output) terminals of the network. The set of links incident to a particular i>t- is partitioned into two subsets. Those which are linked to either or input terminals are called input links of i a n d those linked to either or output terminals are called output links. {in) The rx copies of v are called input switches of the network. Each vi is connected to n i input terminals. The rs copies of v, are called output switches of the network. Each vs is connected to n, output terminals. The three-stage Clos network is a special case of a multistage connecting network, satisfying the additional restrictions that s = 3 and 1411 Fig. 1--Generalized three-step Clos network.