An Invariant Oblivious Minimum-routing Algorithm for Binary Hypercubes
Dobri Atanassov Batovski, Gennady Veselovsky · Parallel and Distributed Processing Techniques and Applications · 2002
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 sourcedestination 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.