First, this paper shows that the Cayley graph of degree four on n 2n vertices is isomorphic to the n-dimensional wrapped butterfly network, a result published three years earlier by the first two authors [1].
The classical idea of a one-to-one permutation routing is then introduced: each vertex of a network sends a message to one other vertex in such a way that the destination vertices are a permutation of the source vertices. In an oblivious one-to-one permutation routing, the path taken by any message is unaffected by the path of any other message. The authors make use of information provided by their isomorphism proof to develop a simple greedy algorithm that solves this oblivious routing problem on the wrapped butterfly network in O ( &sqrt; n 2n ) time, the least possible upper bound.
The paper is clearly written and largely self-contained.