|
Title:
|
STOCHASTIC LINK-FAULT-TOLERANT ROUTING IN A HYPER-STAR GRAPH |
|
Author(s):
|
Bui Thi Thuan, Yuki Hirai, Huynh Thi Thanh Binh, Keiichi Kaneko |
|
ISBN:
|
978-989-8533-25-8 |
|
Editors:
|
Hans Weghorn |
|
Year:
|
2014 |
|
Edition:
|
Single |
|
Keywords:
|
Hypercube, star graph, interconnection network, faulty link, dependable computing |
|
Type:
|
Full Paper |
|
First Page:
|
45 |
|
Last Page:
|
52 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
A hyper-star graph hs(n,k) is a generic topology that provides interconnection networks for parallel processing systems and it has merits of a hypercube and a star graph simultaneously. In a parallel processing system, it is necessary to construct algorithms that are based on existence of faulty elements. Therefore, in this paper, we focus on a hyper-star graph hs(n,k) with faulty links and propose an adaptive fault-tolerant routing algorithm for node pairs. at each node of the graph, for each distance, the algorithm calculates the probability that a fault-free path exists from the node to an arbitrary node with the distance. Then, a fault-free path will be constructed base on the calculated values. We conducted a computer experiment to prove the proposed algorithm's effectiveness. |
|
|
|
|
|
|
