An Incremental Scalable Network Architecture With Fault-Tolerant Communication

The design of interconnection network topologies significantly impacts the performance and reliability of parallel systems. Enhanced incremental scalability enables networks to expand with reduced hardware overhead. In practice, rather than always adding many nodes at once, a small number of nodes are occasionally added as needed. However, existing topologies struggle to achieve effective incremental scalability. To address this, we propose the incremental scalability exchanged hypercube (ISEH), a novel interconnection network for parallel computing. The significant advantages of ISEH include improved incremental scalability and interconnection flexibility, while maintaining low interconnection complexity. Its diameter remains unchanged as the network size increases linearly and does not exceed the diameter of the exchanged hypercube. First, we present the topological properties of ISEH, including isomorphism, incremental scalability, and diameter. Next, we design an efficient communication method for ISEH to ensure low communication overhead. To support reliable communication, we design algorithms to construct disjoint paths between any two distinct nodes. Furthermore, based on generalized exchanged <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-cubes, we propose the incremental scalability generalized exchanged <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">X</i>-cubes, offering better incremental scalability. Finally, we compare the performance of ISEH with other interconnection networks and evaluate the proposed algorithms. The results demonstrate that ISEH achieves a favorable balance among incremental scalability, diameter, and flexibility compared to existing networks.