篇名 | A Point-to-Point Parallel Routing Algorithm of Chordal Rings with degree 4 |
---|---|
卷期 | 4 |
作者 | Chan, Hung-Chang |
頁次 | 51-55 |
關鍵字 | interconnection networks 、 chordal ring 、 parallel routing 、 algorithm |
出刊日期 | 201212 |
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.