FAULT DIAGNOSIS AND PERMUTING PROPERTIES OF CC-BANYAN NETWORKS.

Vladimir Cherkassky, Eliezer Opper

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

A graph-theoretic approach to the analysis of permuting properties and optimal fault diagnosis of multistage interconnection networks that can be used in real-time multicomputer systems is presented. The proposed method of fault diagnosis allows optimal on-line diagnosis in rectangular CC-banyan and equivalent networks (e. g. , ADM and barrel switch) with arbitrary fanout f and arbitrary number of levels L. The diagnosis method covers stuck-at-0, stuck-at-1, and bridge-type faults and can be applied serially for fault detection or in parallel for fault detection and location. An analytical expression for the total number of distinct permutations performable by rectangular CC-banyan network with an arbitrary number of stages and fanout two is derived. An interesting relationship between the ability to perform cyclic shift permutations and the existence of Hamiltonians in a CC-banyan network graph is observed.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherIEEE
Pages175-183
Number of pages9
ISBN (Print)0818605669
StatePublished - Dec 1 1984

Fingerprint Dive into the research topics of 'FAULT DIAGNOSIS AND PERMUTING PROPERTIES OF CC-BANYAN NETWORKS.'. Together they form a unique fingerprint.

Cite this