Optimal Oblivious Permutation Routing in Small Hypercubes

For each d <= 8 we provide an oblivious algorithm for routing any permutation on the d-dimensional hypercube in at most d communication steps. To prove our result we show that any 1-to-2 d' -routing problem and any 2 d' -to-1-routing problem can be solved in at most d' (d' <= 4) communication steps on a d'-dimensional hypercube. Furthermore we present a class of efficiently working routing algorithms which allows us to make an improved statement about the complexity of some of the provided algorithms