Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks

Hiroshi MASUYAMA  Yuichirou MORITA  Hiroyuki OKADA  

IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.557-568
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Networks
fault tolerant,  BPC permutation,  delta network,  

Full Text: PDF(956KB)
>>Buy this Article

The numbers of passes required to realize permutations in the class of Bit Permute-Complement (BPC) permutations such as Bit-Reversal, Matrix-Transpose, Perfect-Shuffle, and Bit-Complement permutations in delta and extrastage delta networks are obtained. The influence of the faults in the networks on the number of passes required for them is also investigated. First, how different are the time complexities required when using a route decision algorithm and an improved algorithm having taken some inherent properties into consideration is discussed and solved by obtaining real data. Next, how many passes are required to realize BPC permutations in delta networks when faults are present and when not present, and how many passes can be reduced by using an extra-stage are discussed continuously. As an important criterion for the fault tolerance of multistage interconnecting networks, Dynamic Full Access (DFA) has been suggested. A weakness of DFA as applied to BPC permutations is that the ability to realize such permutations in a finite number of passes can not be always measured by a criterion of DFA, because of the uneven distributions of paths required for the permutations. This reason suggests the ability to realize such permutations must be investigated from the different angle.