On a Class of Rearrangeable Switching Networks - Part I: Control Algorithm

One type of a switching network which has drawn considerable interest lately is the class of rearrangeable switching networks (RSN). With these networks, any idle input terminal of the network can always bo connected to any idle output terminal by rerouting the existing connections if necessary. These networks can be used where oneto-one full access and nonblocking features are required, and rerouting is feasible, e.g., main distribution frames 1 and facility switches 2 in telephone systems and data transfer networks in a multiprocessor computer system. 3 Most of the earlier efforts, notably by C. Clos,4 V. E. Bcnes,5 and A. E. Joel, Jr., 6 have been made in the context of telephone switching networks. Their emphasis has been on the network structure, on its combinatorial properties and on bounds on the number of connections that require rerouting. Recently, this type of network has been of interest in such computer areas as data-sorting systems 7 and selfrepairing multiprocessors. 3 The network structure is also applicable for cellular arrays.* However, very few reports 0 1 0 have been made on the control aspect of these networks. This paper will begin with a brief discussion of the general structure of RSN's, followed by the development of a method for the con1570