Hypercube Fault Tolerant Routing with Bit Constraint

Abstract

Thanks to its simple definition, the hypercube topology is very popular as interconnection network of parallel systems. There have been several routing algorithms described for the hypercube topology, yet in this paper we focus on hypercube routing extended with an additional restriction: bit constraint. Concretely, path selection is performed on a particular subset of nodes: the nodes are required to satisfy a condition regarding their bit weights (a.k.a. Hamming weights). There are several applications to such restricted routing, including simplification of disjoint paths routing. We propose in this paper two hypercube routing algorithms enforcing such node restriction: first, a shortest path routing algorithm, second a fault tolerant point-to-point routing algorithm. Formal proof of correctness and complexity analysis for the described algorithms are conducted. We show that the shortest path routing algorithm proposed is time optimal. Finally, we perform an empirical evaluation of the proposed fault tolerant point-to-point routing algorithm so as to inspect its practical behaviour. Along with this experimentation, we analyse further the average performance of the proposed algorithm by discussing the average Hamming distance in a hypercube when satisfying a bit constraint.