An Invariant Oblivious Minimum-Routing Algorithm for Binary Hypercubes

摘要

An invariant oblivious minimum-routing algorithm for binary hypercubes is presented, where the knowledge of only three parameters: dimension n, source address, and destination address can completely determine the paths for all source-destination pairs on the basis of routing tables (modular source graphs). In this mode of operation, the paths for the source-destination pairs remain unchanged for arbitrary permutations. The approach is based on a modified version of dimension-order routing. The algorithm provides an n-step conflict-free packet permutation routing in binary hypercubes for a number of dimensions n ≤ 8 where all paths are restricted to minimal lengths. The Appendix contains routing tables for the aforesaid dimensions.