Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks

Hiroshi MASUYAMA; Yuichirou MORITA; Hiroyuki OKADA

Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks

Hiroshi MASUYAMA, Yuichirou MORITA, Hiroyuki OKADA

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.557-568

Publication Date: 1992/07/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Computer Networks

Cite this

Copy

Hiroshi MASUYAMA, Yuichirou MORITA, Hiroyuki OKADA, "Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 4, pp. 557-568, July 1992, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_4_557/_p

Copy

@ARTICLE{e75-d_4_557,
author={Hiroshi MASUYAMA, Yuichirou MORITA, Hiroyuki OKADA, },
journal={IEICE TRANSACTIONS on Information},
title={Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks},
year={1992},
volume={E75-D},
number={4},
pages={557-568},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - Fault Tolerant Routing for Realization of BPC Permutations in Delta Networks
T2 - IEICE TRANSACTIONS on Information
SP - 557
EP - 568
AU - Hiroshi MASUYAMA
AU - Yuichirou MORITA
AU - Hiroyuki OKADA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - 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.
ER -