On shortest path routing algorithm in crossed cube-connected ring networks

摘要

Crossed cube is a variation of hypercube, but some properties of the former are superior to those of the latter. However, it is difficult to extend the scale of crossed cube networks. For example, it is necessary to double the number of nodes to extend the scale of crossed cube networks. As a kind of hierarchical ring interconnection networks HRN, crossed cube-connected ring interconnection network CRN can effectively overcome the disadvantage. When extended, it only needs to be added a crossed cube. hence, it is a good topology for interconnection networks. Routing algorithm decides the performance of parallel computer system. In this paper, we first introduce the sufficient and necessary conditions for each link of one node in crossed cube to be a candidate link of a shortest path, and then present a shortest path adaptive routing algorithm with time complexity of O(n²) for CRN. At each routing step, it always choose a link in a good state to route from all the candidate links that belong to the shortest paths. Theoretical analysis show that the algorithm can output any shortest path.