Almost Optimal Permutation Routing on Hypercubes

the classical (or old-fashioned) store-and-forward model.
We introduce the first on-line algorithms that route any permutation
on the $d$-dimensional hypercube in $d+o(d)$ steps.

All previous algorithms lose a factor of at least two because
packets are first sent to randomly selected intermediate destinations
and then from there to the final destination. This well-known approach
is typically referred to as Valiant's paradigm. Unfortunately, it
blows up the length of the routing paths by a factor of two, so
that the worst-case path length is $2d$, resulting in runtime
$2d + o(d)$.

We show a surprisingly simple modification of Valiant's trick that
yields routing paths of length at most $d$. In addition, we show
how this path selection in combination with NTO/FTG scheduling gives
routing time $d + o(d)$.