
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks
Hiroshi MASUYAMA Yuichirou MORITA Hiroyuki OKADA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.557568 Publication Date: 1992/07/25
Online ISSN: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Computer Networks Keyword: fault tolerant, BPC permutation, delta network,
Full Text: PDF(956KB) >>Buy this Article
Summary:
The numbers of passes required to realize permutations in the class of Bit PermuteComplement (BPC) permutations such as BitReversal, MatrixTranspose, PerfectShuffle, and BitComplement 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 extrastage 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.

