A Fast Parallel Routing Algorithm for Strictly Nonblocking Switching Networks

摘要

A class of strictly nonblocking (SNB) networks B(N,p, α) can be constructed from vertical stacking of multiple planes of Banyan networks. Fast routing algorithms are needed for finding available connection paths in B(N,p,α) networks. In this paper, by modeling the switching routing problem in SNB networks as strong edge coloring problem, we propose a simple and fast parallel routing algorithm for routing connections in SNB B(N,p, α) networks. The proposed algorithm can route connections in SNB B(N,p, α) networks in O(N~(1/2)) time using a completely connected multiprocessor system of N processing elements. Our algorithm can be translated into algorithms with an O (lg N lg lg N) slowdown factor for the class of N-processor hypercubic networks, whose structures are no more complex than a single plane of B(N,p,α) networks.