• Empirical evaluation of randomly-wired multistage networks. D. Lisinski, T. Leighton, and B. Maggs, Proceedings of the 1990 International Conference on Computer Design (ICCD), September 1990, pp. 380-385.

  In this paper, we present experimental data indicating that multistage interconnection networks with randomly-positioned wires are likely to be better for message routing applications than traditional multistage networks such as the butterfly. Data is 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 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 some of the switches in the network are faulty.

  Postscript Compressed Postscript
  Back to other publications

  Back to my home page