ASYMMETRICAL MULTICONNECTION 3-STAGE CLOS NETWORKS

In this paper, we study routing problems in a general class of asymmetrical three-stage Clos networks. This class covers many asymmetrical three-stage networks considered by earlier researchers. We derive necessary and sufficient conditions under which this class of networks is rearrangeable with respect to a set of multiconnections, i.e., connections between subsets of input and output terminals. We first model the routing problem in these networks as a network-flow problem. If the number of switching elements in the first and last stages of the network is 0(f) and the number of switching elements in the middle stage is m, then the network-flow model yields a routing algorithm with running time O(mf3). We then show that the problem of routing a set of multiconnections in an asymmetrical Clos network can be transformed into the well-studied problem of routing a set of pairwise connections in a more symmetric form of the network. This approach results in a routing algorithm with complexity O(mK2), where K is the aggregate capacity of the interstage links in the network.