Abstract |
We study the route assignment problem of the rearrangeable nonblocking Clos networks which can be modeled as the edge-coloring problem of the bipartite graph. In our study, we explores the parallel processing of a new algebraic method of edge coloring, called complex coloring, and apply it to the route assignment in Clos networks. The proposed distributed parallel routing algorithm possesses two important features: optimality and rearrangeability. The optimality ensures that the algorithm always returns a proper coloring with the minimum number of required colors, and the rearrangeability allows partially re-coloring the existing connection patterns if the underlying graph only changes slightly. The minimum running time of our proposed routing algorithm is O(log?N ) if the port number n on each input/output module is a constant independent of N, or else the maximum order is O(〖√N log〗?N ) if n=√N, where N is the Clos network size. |
Affiliation |
Lingkang Wang received the B.S. degree in communication engineering from University of Electronic Science and Technology of China, Chengdu, in 2013. She is currently a Ph.D. student in electronics engineering at Shanghai Jiao Tong University, Shanghai. Her research interests include complex coloring and its application in switching systems. |