Rearrangeability and Connectivity of Multistage Interconnection Networks with Nearest-Neighbour Interconnections


IEICE TRANSACTIONS on Communications   Vol.E77-B   No.12   pp.1546-1555
Publication Date: 1994/12/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching and Communication Processing
nearest-neighbour interconnections,  multistage interconnection network,  cellular array,  rearrangeability,  connectivity,  bipartite graph,  Kronecker product,  

Full Text: PDF>>
Buy this Article

Throughout the paper, the nearest-neighbour (NN) interconnection of switches within a multistage interconnection network (MIN) is analysed. Three main results are obtained: (1) The switch preserving transformation of a 2-D MIN into the 1-D MIN (and vice versa) (2) The rearrangeability of the MIN and (3) The number of stages (NS) for the rearrangeable nonblocking interconnection. The analysis is extended to any dimension of the interconnected data set. The topological equivalence between 1-D MINs with NN interconnections (NN-MINs) and 1-D cellular arrays is shown.