Empirical evaluation of randomly-wire multistage networks

Experimental data are presented indicating that multistage interconnection networks with randomly positioned wires are likely to be substantially better for message routing applications than traditional multistage networks, such as the butterfly. The data are presented for a variety of routing models, including store-and-forward routing, cut-through routing, and circuit switching, as well as for scenarios in which a potentially large number of switches are faulty. In most cases, the differences are dramatic, particularly when several switches in the network are faulty. The data provide empirical confirmation of recent theoretical work