文章詳目資料

影像處理暨通訊期刊

  • 加入收藏
  • 下載文章
篇名 A Point-to-Point Parallel Routing Algorithm of Chordal Rings with degree 4
卷期 4
作者 Chan, Hung-Chang
頁次 51-55
關鍵字 interconnection networkschordal ringparallel routingalgorithm
出刊日期 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.

相關文獻