Empirical Evaluation of Randomly-Wired Multistage Networks (Extended Abstract)
Tom Leighton, Derek Lisinski, Bruce MacDowell Maggs · 1990
) Tom Leighton 1;2 Derek Lisinski 2 Bruce Maggs 2 1 Mathematics Department and 2 Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract In this paper, we present experimental data 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. Data is presented for a variety of routing models, including storeand -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 every situation, we find that randomly-wired networks outperform traditional networks with the same amount of hardware. In some cases, the differences are dramatic, particularly when several switches in the network are faulty. Overall, the data provides excellent empirical confirmation of recent theoretical work. 1 Backgroun...