Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks

Abstract

We propose a new family of communication architectures called ‘biswapped networks’. Given any n-node basis network Ω, the associated biswapped network Bsw(Ω) is built of 2n copies of Ω, using a simple rule for connectivity that ensures desirable attributes, including regularity, modularity, fault tolerance, and algorithmic efficiency. In particular, if Ω is a Cayley digraph, then so is Bsw(Ω). Our biswapped connectivity provides a systematic scheme for synthesizing large, scalable, modular, and robust parallel architectures. Furthermore, many desirable attributes of the underlying basis network Ω are preserved, as the Bsw(Ω) parameters are related to the corresponding parameters of Ω. We obtain a number of results on internode distances, Hamiltonian cycles, optimal routing, and node-disjoint paths for Bsw(Ω). We explore the relations between biswapped and swapped or optical transpose interconnection system (OTIS) networks, which may use a mix of electronic and optical links. In particular, we demonstrate that the biswapped connectivity removes an inherent asymmetry of swapped/OTIS networks, as well as the attendant complications in analyses and applications. Finally, we show that biswapped networks are complementary to, and offer advantages over, well-known and widely used interconnection architectures for parallel processing.

Keywords:

• bipartite graph
• Cayley graph/digraph
• fault tolerance
• Hamiltonian cycle
• hierarchical network
• interconnection network
• internode distance
• network diameter
• node-disjoint paths
• OTIS network
• shortest-path routing
• swapped network

2000 AMS Subject Classifications :

• 68R10
• 94C15
• 20G99

Acknowledgements

The research done by W. Xiao, W. Chen, M. He, and W. Wei was supported by the Natural Science Foundation of China (60973150) and the Guangdong Laboratory of Software and Applied Technology (2006B80407001).