ASYMMETRICAL MULTICONNECTION 3-STAGE CLOS NETWORKS

In this paper, we study routing problems in a general class of asymmet rical three-stage Clos networks. This class covers many asymmetrical t hree-stage networks considered by earlier researchers. We derive neces sary and sufficient conditions under which this class of networks is r earrangeable with respect to a set of multiconnections, i.e., connecti ons between subsets of input and output terminals. We first model the routing problem in these networks as a network-flow problem. If the nu mber 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 multico nnections in an asymmetrical Clos network can be transformed into the well-studied problem of routing a set of pairwise connections in a mor e symmetric form of the network. This approach results in a routing al gorithm with complexity O(mK2), where K is the aggregate capacity of t he interstage links in the network.