loading...
A fault location technique and alternate routing in Benes network
Bangalore, India November 23-November 24
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ATS.1995.485319Fourth Asian Test Symposium (ATS'95)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
N. Das, Electron. Unit, Indian Stat. Inst., Calcutta, India
J. Dattagupta, Electron. Unit, Indian Stat. Inst., Calcutta, India
An NxN Benes network B(n), (n=log/sub 2/N), being a rearrangeable network, can realize any NxN permutation in a single pass. But even in the presence of a single switch fault in B(n), no NxN permutation can be implemented in one pass, it requires either recirculation through intermediate nodes, or reconfiguration of the system in a degraded mode. We characterize a class C of multiple switch faults in B(n), in the presence of which the network is always capable of realizing any arbitrary NxN permutation P in two passes. By this technique, every source-destination path is set up in a single pass, only the whole set of N source-destination paths of P is partitioned in two subsets and are realized in two successive passes. The novelty of the routing technique lies in the fact that the exact locations of the faults are not important here, only the information of an optimal region of the network containing the faulty switch is sufficient. This feature actually enables us to develop here, very fast and simple procedures for multiple switch fault detection and location as well. In this paper, we have shown that just two one bit test vectors are sufficient to detect and locate all single faults, all double faults and also many cases with 3, 4, 5 and 6 faults. Given a set F of multiple switch faults, we detect and locate its equivalent fault set F' by the fault location technique presented.
Index Terms:
multistage interconnection networks; fault diagnosis; network routing; reconfigurable architectures; fault tolerant computing; fault location technique; alternate routing; Benes network; rearrangeable network; single switch fault; recirculation; reconfiguration; source-destination path; routing technique; exact locations; multiple switch fault detection; one bit test vectors; equivalent fault set; multistage interconnection networks
Citation:
N. Das, J. Dattagupta, "A fault location technique and alternate routing in Benes network," ats, pp.71, Fourth Asian Test Symposium (ATS'95), 1995
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions