APPLICATIONS OF MATCHING AND EDGE-COLORING ALGORITHMS TO ROUTING IN CLOS NETWORKS

Rearrangeable Clos networks have been studied in the literature in con nection with telephone switching and communication networks. This pape r examines the applicability of matching and edge-coloring in bipartit e graphs to the rearrangement problem in these networks. A survey of v arious matching and edge-coloring algorithms is given, and these algor ithms are evaluated for their suitability and effectiveness. It is sho wn that no single matching or edge-coloring algorithm reported in the literature performs well over all Clos networks. It is further shown t hat the time complexity of the looping algorithm for Benes networks is at least as good as any routing algorithm that can be obtained from m atching or edge-coloring. (C) 1994 John Wiley & Sons, Inc.