Fault-Tolerant Node-to-Set Disjoint-Path Routing in Hypercubes

摘要

Hypercube-based interconnection networks are one of the most popular network topologies when dealing with parallel systems. In a hypercube of dimension n, node addresses are made of n bits, and two nodes are adjacent if and only if their Hamming distance is equal to 1. In this paper we introduce a fault-tolerant hypercube routing algorithm which constructs n minus the number of faulty nodes f disjoint paths connecting one source node to k = n - f destination nodes in O(n~2) time complexity.