R.J. Cole, B.M. Maggs, and R.K. Sitaraman

Proceedings of the Thirty Sixth Annual Symposium on the Foundations of Computer Science, 1995, 558-570.

In this paper we show that even if every node or edge in an N-node butterfly network fails independently with some constant probability, p, it is still possible to identify a set of Theta(N) nodes between which packets can be routed in any permutation in O(log N) steps, with high probability. Although the analysis is complicated, the routing algorithm itself is relatively simple.

postscript of full paper