Self-Routing in 2-D Shuffle Networks


IEICE TRANSACTIONS on Communications   Vol.E79-B   No.2   pp.173-181
Publication Date: 1996/02/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching and Communication Processing
1-D shuffle,  2-D shuffle,  multistage interconnection network,  blockstructure,  switch-pattern preserving transformation,  bipartite graph,  colouring,  arbitrary permutation,  self-routing,  

Full Text: PDF>>
Buy this Article

Throughout the paper, the proper operating of the self-routing principle in 2-D shuffle multistage interconnection networks (MINs) is analysed. (The notation 1-D MIN and 2-D MIN is applied for a MIN which interconnects 1-D and 2-D data, respectively.) Two different methods for self-routing in 2-D shuffle MINs are presented: (1) The application of self-routing in 1-D MINs by a switch-pattern preserving transformation of 1-D shuffle stages into 2-D shuffle stages (and vice versa) and (2) the general concept of self-routing in 2-D shuffle MINs based on self-routing with regard to each coordinate which is the original contribution of the paper. Several examples are provided which make the various problems transparent.