A Novel Node-to-Set Node-Disjoint Fault-Tolerant Routing Strategy in Hypercube
This paper proposes a node-to-set node-disjoint routing algorithm based on a path storage model for the hypercube networks with faulty nodes.Two properties of the storage model are listed in the paper on condition that the n-dimension hypercube has no more than n-1 faulty nodes.The first is that its path length is no more than hamming distance plus 2,and the second is that its sub-cube model can be partitioned from the global model.Based on the model,a novel routing algorithm is brought up to generate node-to-set node-disjoint fault-tolerant path.It adopts divide-and-conquer strategy to take full advantage of the regularity of hypercube.The routing algorithm can reduce the path length to n + f + 2 at most and decrease the time complexity to O(mn) in a faulty-node hypercube system(where n is the number of dimensions,m is the number of destination nodes and f is number of faulty nodes).Experiment results show that the average path length is shorten by 9~10% compared with existing algorithms in a ten-dimension hypercube with no more than nine faulty nodes.
Interconnection networks Hypercube networks disjoint path Fault tolerance
Endong Wang Hongwei Wang Jicheng Chen Weifeng Gong Fan Ni
State Key Laboratory of High-end Server& Storage Technology,Beijing,China,100085;Inspur Group Co.,Ltd.Beijing,China,100085
国际会议
ACA,Advanced Computer Architecture(2014年全国计算机体系结构学术会议)
沈阳
英文
58-67
2014-08-23（万方平台首次上网日期，不代表论文的发表时间）