Load-balanced Routing for Nested Interconnection Networks

Zhipeng Xu, Xiaolong Huang, Yuefan Deng

Abstract: We introduced the load-balanced routing algorithms, for interconnection networks resulting from nesting, by considering the pressure of the data forwarding in each node. Benchmarks on a small cluster with various network topologies, and simulations for several larger clusters whose prototypes are too costly to construct, demonstrated substantial gains of communication performance with our routing on these networks over other mainstream routing algorithms.

Introduction

As high-performance computing moves toward exascale capabilities, the primary bottleneck is increasingly the interconnection network (IN). Efficiently moving data between millions of cores without creating massive traffic jams is critical. Traditional topologies often face a trade-off between scalability and efficiency, frequently resulting in "hot spots"—specific nodes overwhelmed with forwarding tasks while others sit idle.

The Problem: Congestion in Massive Networks

Standard shortest-path routing algorithms, such as Floyd-Warshall, are typically "oblivious" to network congestion. While alternative strategies like Valiant’s routing attempt to balance the load by using random intermediate nodes, they often increase the number of "hops" a message takes, thereby increasing latency. The challenge lies in balancing the load across the network without sacrificing the efficiency of the shortest path.

Methodology

The researchers propose a dual-pronged solution involving nested mathematical structures and a sophisticated load-balancing routing algorithm.

1. Nested Topologies

Instead of designing massive networks from scratch, the authors utilize the Cartesian product of small, mathematically optimal base graphs (e.g., Peterson or Heawood graphs). By "nesting" these figures, they can construct large-scale networks where the total number of nodes grows exponentially while the network diameter (the maximum distance between any two nodes) grows only linearly.

Construction of a nested network via the Cartesian product of base graphs G1 and G2.

2. Load-balanced Routing Algorithm

The core contribution is a two-stage routing strategy designed to minimize "forwarding pressure" ($d_n$) across all nodes:

  • Stage 1 (Enumeration): The algorithm identifies all possible shortest paths between every pair of nodes.
  • Stage 2 (Optimization): It employs Mixed-Integer Nonlinear Programming (MINLP) to select specific paths from the enumerated set. The goal is to minimize the variance of the load across the network, ensuring no single node is disproportionately burdened.

Performance and Scalability

A key advantage of this approach is its inherent scalability. As illustrated in the comparison of network diameters, nested networks maintain a lower diameter than traditional hypercubes as the number of nodes ($N$) increases, facilitating faster communication in larger systems.

Comparison of network diameter (D) vs. number of nodes (N) for nested networks, hypercubes, and folded Petersen graphs.

Key Results and Benchmarks

The approach was evaluated using a physical 32-node Taishan cluster and SimGrid/SMPI simulations. The "Balanced Routing" consistently outperformed standard imbalanced shortest-path routing:

  • Throughput: Graph500 BFS tests showed gains of approximately 13% to 17% in MTEPS (Millions of Traversed Edges Per Second).
  • Latency: MPI All-to-all communication time was reduced by up to 50% for small packets.
  • Bandwidth: In the NAS Parallel Benchmarks (NPB) FT, performance increased from 41.3 to 61.4 Mops/s.

Conclusion and Future Work

This research demonstrates that load balancing can be achieved effectively by choosing wisely among available shortest paths. While the current MINLP approach is computationally intensive for global optimization in massive networks, the mathematical properties of nested products offer a path toward more efficient sub-problem solving. Future work will explore generalizing this logic for multi-level product networks in next-generation cloud and exascale systems.

Summary updated

Abstract

We introduced the load-balanced routing algorithms, for interconnection networks resulting from nesting, by considering the pressure of the data forwarding in each node. Benchmarks on a small cluster with various network topologies, and simulations for several larger clusters whose prototypes are too costly to construct, demonstrated substantial gains of communication performance with our routing on these networks over other mainstream routing algorithms.
BibTeX
@misc{xu2019load,
  author = {Zhipeng Xu and Xiaolong Huang and Yuefan Deng},
  title = {{Load-balanced Routing for Nested Interconnection Networks}},
  year = {2019},
  eprint = {1909.06497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1909.06497},
}
Figure