caa a22 4500 475789601 CHVBK 20180406123708.0 cr unu---uuuuu 170329e20000501xx s 000 0 eng 10.1023/A:1019171418147 doi (NATIONALLICENCE)springer-10.1023/A:1019171418147 A fault tolerant routing scheme for hypercubes [Elektronische Daten] [Khaled Day, Saad Harous, Abdel‐Elah Al‐Ayyoub] An efficient distributed fault‐tolerant routing algorithm for the hypercube is proposed based on the existence of a complete set of node‐disjoint paths between any two nodes. Node failure and repairs may occur dynamically provided that the total number of faulty nodes at any time is less than the node‐connectivity n of the n‐cube. Each node maintains for each possible destination which of the associated node‐disjoint paths to use. When a message is blocked by a node failure, the source node is warned and requested to switch to a different node‐disjoint path. The methods used to identify the paths, to propagate node failure information to source nodes, and to switch from one routing path to another incur little communication and computation overhead. We show that if the faults occur reasonably apart in time, then all messages will be routed on optimal or near optimal paths. In the unlikely case where many faults occur in a short period, the algorithm still delivers all messages but via possibly longer paths. An extension of the obtained algorithm to handle link failures in addition to node failures is discussed. We also show how to adapt the algorithm to n‐ary n‐cube networks. The algorithm can be similarly adapted to any interconnection network for which there exists a simple characterization of node‐disjoint paths between its nodes. Kluwer Academic Publishers, 2000 Day Khaled Department of Computer Science, Sultan Qaboos University, Muscat 123, Oman aut Harous Saad Department of Computer Science, Sharjah University, UAE aut Al‐Ayyoub Abdel‐Elah Department of Mathematics and Computer Science, The University of Akron, Akron, OH, USA aut Telecommunication Systems Kluwer Academic Publishers 13/1(2000-05-01), 29-44 1018-4864 13:1<29 2000 13 11235 https://doi.org/10.1023/A:1019171418147 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1019171418147 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Day Khaled Department of Computer Science, Sultan Qaboos University, Muscat 123, Oman aut NATIONALLICENCE 700 1- Harous Saad Department of Computer Science, Sharjah University, UAE aut NATIONALLICENCE 700 1- Al‐Ayyoub Abdel‐Elah Department of Mathematics and Computer Science, The University of Akron, Akron, OH, USA aut NATIONALLICENCE 773 0- Telecommunication Systems Kluwer Academic Publishers 13/1(2000-05-01), 29-44 1018-4864 13:1<29 2000 13 11235 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer