A heuristic routing algorithm for Clos network
Xinming Duan, Shuqiang Liu · 2008
This paper presents a new Clos network routing algorithm in order to reduce the high time complexity of original algorithm for Clos network. The paper illustrates that it is an independent problem whether a column in specification matrix is completive. As a result, it eliminates backtrackings among columns and backtrackings among elements in the same column. The presented algorithm completely achieves non-blocking routing and reaches low time complexity O(N3/2) even in the worst case. So the algorithm is readily applicable to the control of Clos network.