On multiple-fault diagnosis of baseline interconnection networks

We use the general fault model of [7] to study the multiple-fault diagnosis method for the baseline interconnection networks. We find that six tests are sufficient for the 4∗4 and 8∗8 network diagnosis plus that the number of tests is double as the network size increases. A new and systematic multiple-fault diagnosis procedure is developed. The following new results are derived in this study: 1) The necessary and sufficient conditions of test vectors for detecting a fault or multiple faults and determining the fault types in a switching element or a link and in a 4∗4 baseline network are derived. 2) Six tests are necessary and sufficient for detecting multiple faults and determine partially the fault types in a 4∗4 baseline network and an 8∗8 baseline network. Multiple faults can be detected and the fault types can be partially determined by 2log2N tests in an N∗N baseline network, N ≥ 8. 4) If K distinct vectors are sufficient for diagnosing a R∗R baseline network, then d[log2(N∗K/R+2)] tests are sufficient for diagnosing an N∗N baseline network for N ≥ R.