Assessing reliability of multistage interconnection networks

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 com...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 1993-10, Vol.42 (10), p.1207-1221
Main Authors: Colbourn, C.J., Devitt, J.S., Harms, D.D., Kraetzl, M.
Format: Article
Language:English
Subjects:
Applied sciences
Computer networks
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Exact sciences and technology
Hardware
Joining processes
Mathematics
Multiprocessor interconnection networks
Polynomials
Software
Telecommunication network reliability
Telecommunications
Telecommunications and information theory
Telephony
Teleprocessing networks. Isdn
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
ISSN:0018-9340
1557-9956
DOI:10.1109/12.257707