A Point-to-Point Parallel Routing Algorithm of Chordal Rings with Degree 4

Chordal ring with degree 4, is an interconnection network that each node added extra two undirected link in an undirected ring. Its hop size h means it added one link for message passing directly between two nodes whose distance is h originally. In this paper, we use the Chalamaiah's algorithm for obtaining the results of point-to-point shortest path. Chalamaiah's algorithm is O (h/g+log(h)) in time complexity, where g is GCD (N,h). Moreover, because the degree of each node is fixedly 4, we proposed a point-to-point parallel routing algorithm for obtaining four parallel routing paths under some restricted condition. We can prove that the four paths are node-disjointed. Our parallel routing algorithm is the same in time complexity, and the longest distance of these four parallel routing paths d+8 in worse case, where d is distance from source node to destination node.