Assessing Reliability of Multistage Interconnection Networks

Charles J. Colbourn, John S. Devitt, Daryl D. Harms, Miro Kraetzl

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Efficient methods for determining the lower and upper bounds on the probabilities of source-to-terminal communication in a multistage interconnection network are developed. A novel lower bounding strategy (shifting) and a novel upper bounding strategy (renormalization) are presented; both can be computed in polynomial time. These strategies can be combined with existing methods based on coherence, and on consecutive cuts, to obtain an improvement on previously known efficiently computable bounds. A second efficient upper bound (averaging) is developed. An empirical evaluation of the bounds is discussed. Finally, the value of these bounding strategies in assessing the reliability of interconnection networks is examined.

Original languageEnglish (US)
Pages (from-to)1207-1221
Number of pages15
JournalIEEE Transactions on Computers
Issue number10
StatePublished - Oct 1993
Externally publishedYes


  • Multistage interconnection network
  • approximation strategy
  • blocking probability
  • channel graph
  • computational method
  • two-terminal reliability

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Assessing Reliability of Multistage Interconnection Networks'. Together they form a unique fingerprint.

Cite this