OPTIMUM CONGESTED ROUTING STRATEGY ON TWISTED CUBES
Tseng-Kuei Li, Jimmy J.M. Tan, Lih‐Hsing Hsu, Ting‐Yi Sung · Journal of Interconnection Networks · 2000
Given a shortest path routing algorithm of an interconnection network, the edge congestion is one of the important factors to evaluate the performance of this algorithm. In this paper, we consider the twisted cube, a variation of the hypercube with some better properties, and review the existing shortest path routing algorithm 8 . We find that its edge congestion under the routing algorithm is high. Then, we propose a new shortest path routing algorithm and show that our algorithm has optimum time complexity O(n) and optimum edge congestion 2 n . Moreover, we calculate the bisection width of the twisted cube of dimension n.