Node-to-set and set-to-set cluster fault tolerant routing in hypercubes

✍ Scribed by Qian-Ping Gu; Shietung Peng

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 365 KB
• Volume: 24
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(98)00050-7

✦ Synopsis

We study node-to-set and set-to-set fault tolerant routing problems in n-dimensional hypercubes r n . Node-to-set routing problem is that given a node s and a set of nodes

path connects a node of and a node of . From Menger's theorem, it is known that these two problems in r n can tolerate at most n À k arbitrary faulty nodes. In this paper, we prove that both routing problems can tolerate n À k arbitrary faulty subgraphs (called cluster) of diameter 1. For 2 T k T n, we show that, in the presence of at most n À k faulty clusters of diameter at most 1, the k paths of length at most n 2 for node-to-set routing in r n can be found in Okn optimal time and the k paths of length at most n k 2 for set-to-set routing in r n can be found in Okn log k time. The upper bound n 2 on the length of the paths for nodeto-set routing in r n is optimal.