Design of Identical Strictly and Rearrangeably Nonblocking Folded Clos Networks with Equally Sized Square Crossbars

Yamin LiComput 2025 · DOI

TL;DR

This paper introduces two novel network architectures, ISNBC and IRNBC, designed for high-performance computing and data centers. These networks utilize identical square crossbar switches across all stages, offering improved scalability, reduced communication path lengths, and significantly lower hardware costs compared to traditional Clos and fat-tree networks.

What Problem Does This Paper Address?

Modern high-performance computing and data center networks rely on multistage interconnection networks (MINs) like Clos networks and fat trees to connect vast numbers of processors or servers. Traditional Clos networks often suffer from using crossbar switches of different sizes, leading to wasted ports and increased costs. Fat trees, while addressing some of these issues, still face challenges with varying switch sizes at different stages. Furthermore, traditional designs often enforce fixed path lengths, limiting the exploitation of data locality. Existing solutions have also sometimes introduced unused switch ports to maintain nonblocking properties, further increasing hardware costs. This paper aims to resolve these issues by proposing new network designs that use uniformly sized square crossbars, eliminate unused ports, and enable shorter communication paths.

Methods

The paper proposes two new network architectures: Identical Strictly NonBlocking folded Clos (ISNBC) and Identical Rearrangeably NonBlocking folded Clos (IRNBC). These networks are built upon the principles of traditional unidirectional Clos networks but are adapted into a folded, bidirectional structure. The core innovation lies in using equally sized square crossbar switches for all stages, including the leaf and root switches in the folded design. This is achieved by merging ingress and egress switches into unified leaf switches and ensuring that all switches have the same input and output port count. The designs also incorporate "shortcut connections," allowing direct communication between leaf switches without traversing the root stage, thereby reducing path lengths. The paper systematically constructs these networks for various numbers of stages (2, 3, 4, 5, 7) and analyzes their properties.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Uniformity is Key: The primary insight is that using identical square crossbar switches throughout the network simplifies design, reduces costs, and eliminates wasted ports, which is crucial given the prevalence of square switches in modern hardware.
  • Folded Clos for Efficiency: Adapting the Clos network into a folded structure (like fat trees) allows for bidirectional communication and the introduction of shortcut paths, significantly improving efficiency and reducing latency.
  • Cost Reduction is Substantial: The proposed ISNBC and IRNBC networks demonstrate significant reductions in crosspoint costs compared to their traditional counterparts, offering a compelling economic advantage.
  • Scalability through Stages: The ability to construct these networks with an arbitrary number of stages (as demonstrated for 2, 3, 4, 5, and 7 stages) ensures they can scale to accommodate future demands.

Key Results

The paper demonstrates that the proposed ISNBC networks use between 46.43% and 87.71% of the crosspoints of traditional strictly nonblocking folded Clos networks. Similarly, IRNBC networks use between 53.85% and 60.00% of the crosspoints of traditional rearrangeably nonblocking folded Clos networks. These cost savings are achieved while maintaining nonblocking properties and enabling shorter communication paths. The paper provides detailed comparisons of switch counts and crosspoint ratios, illustrating the advantages of the proposed designs across various network sizes and stages.

Limitations and Future Work

A key limitation identified is that ISNBC networks require 3n × 3n square crossbar switches, and IRNBC networks require 2n × 2n square crossbar switches, where 'n' is related to the number of compute nodes. This constraint means that arbitrary-sized square crossbar switches might not perfectly fit these designs without some unused ports, although the paper suggests strategies for minimizing this. Future work proposed includes developing load-balancing adaptive routing algorithms and fault-tolerant routing algorithms for these new network architectures and evaluating their performance through simulations.

Summary updated

BibTeX
@article{li2025design,
  author = {Yamin Li},
  title = {{Design of Identical Strictly and Rearrangeably Nonblocking Folded Clos Networks with Equally Sized Square Crossbars}},
  journal = {Comput.},
  year = {2025},
  doi = {10.3390/computers14070293},
}
Figure