FAULT DIAGNOSIS AND PERMUTING PROPERTIES OF CC-BANYAN NETWORKS.

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.