Improving InfiniBand Routing through Multiple Virtual Networks

José Flich, Pedro López, José Carlos Sancho, Antonio Robles, José DuatoISHPC 2002 · DOI

TL;DR

This paper proposes a novel routing strategy for InfiniBand networks that leverages multiple virtual networks (implemented via virtual lanes) to significantly improve throughput and traffic balance. By using different "up/down" routing trees on each virtual network, the authors demonstrate substantial performance gains, especially in larger networks, without sacrificing deadlock freedom.

What Problem Does This Paper Address?

InfiniBand is a high-performance interconnect standard poised to become dominant in high-performance computing and data centers. However, its default routing mechanism, "up/down", suffers from significant drawbacks: unbalanced channel utilization and a tendency to route packets through non-minimal paths. This leads to network congestion, reduced throughput, and inefficient use of network resources. While InfiniBand supports multiple virtual lanes (VLs) that can be used to mitigate these issues, existing approaches primarily focus on reducing head-of-line blocking rather than addressing the fundamental limitations of the "up/down" algorithm itself. The authors aim to overcome these limitations by proposing a more effective utilization of virtual lanes.

Methods

The core of the proposed methodology is to treat each virtual lane (VL) as a separate virtual network. Within each virtual network, a distinct "up/down" routing tree is established, each with a different root node. This allows packets to be routed through different paths, offering a better traffic balance and increasing the likelihood of finding minimal paths.

The authors propose a strategy for selecting root nodes: one root is chosen as the node closest to all other nodes (similar to Myrinet's approach), and the second root is the node farthest from the first. This aims to distribute traffic and minimize interference between the paths of the two virtual networks.

For implementation in InfiniBand, each virtual network (and its corresponding "up/down" tree) is mapped to a unique Service Level (SL), which is then mapped to a specific virtual lane using the SLtoVL mapping tables. This approach requires only a small number of SLs/VLs, preserving resources for Quality of Service (QoS) if needed. The routing decision for a packet is made at the source, which consults a table to determine the appropriate SL (and thus virtual network) to use for reaching its destination.

Datasets

Not discussed in the paper. The evaluation relies on a custom InfiniBand simulator.

Key Insights and Ideas

  • Virtual Lanes as Virtual Networks: The most significant insight is viewing virtual lanes not just as buffers but as independent virtual networks, each capable of hosting a distinct routing algorithm. This unlocks a powerful way to overcome the limitations of a single routing scheme.
  • Multiple "Up/Down" Trees for Balance: Using multiple "up/down" trees, each with a different root, effectively distributes traffic across the network, preventing the congestion often seen near a single root node in the standard "up/down" approach.
  • Root Node Selection Matters: The choice of root nodes for the "up/down" trees significantly impacts performance. Strategically selecting distant root nodes appears to be a good heuristic for balancing traffic and improving throughput.
  • Trade-off Between Performance and Resources: While using more virtual networks (and thus more "up/down" trees) generally leads to better performance, it comes at the cost of consuming additional SL/VL resources, which might be needed for QoS. The paper highlights that this trade-off is more favorable in larger networks.
  • Hotspot Traffic Challenges: The proposed method's effectiveness can be impacted by non-uniform traffic patterns like hotspots. In such cases, one virtual network might become saturated prematurely, negating the benefits. However, with multiple hotspots, the benefits are restored.

Key Results

  • Significant Throughput Increase: Using two virtual networks (two "up/down" trees) provides substantial improvements:
  • 16-switch networks: 1.63x throughput increase.
  • 32-switch networks: 3x throughput increase.
  • 64-switch networks: 1.95x throughput increase (average 2.14x).
  • Improved Traffic Balance: Simulations show a much more even distribution of link utilization when using multiple virtual networks compared to a single "up/down" tree, which suffers from high utilization on links near the root.
  • Larger Networks Benefit Most: The performance gains from using additional virtual networks are more pronounced in larger networks (32 and 64 switches). For smaller networks (16 switches), two virtual networks are often sufficient.
  • Hotspot Traffic Impact: With a single hotspot and 20% hotspot traffic, the benefits of two virtual networks are reduced, and in some cases, performance can slightly degrade in smaller networks. However, as the hotspot traffic percentage decreases or the number of hotspots increases, the benefits of the proposed method become significant again.
  • Three Virtual Networks: Using three virtual networks provides further, though diminishing, returns. It is particularly beneficial for 32 and 64-switch networks, where throughput can be increased by factors of 2.58 and 3.22, respectively.

Limitations and Future Work

  • Root Node Selection: The paper acknowledges that the proposed strategy for selecting root nodes is simple and that a more sophisticated selection could yield even better performance. Figure 7 illustrates a high variation in throughput based on root node selection, suggesting that further research in this area is warranted.
  • Hotspot Traffic Mitigation: While the paper explores hotspot traffic, further work could investigate more robust strategies for handling highly skewed traffic patterns.
  • Generalization: The authors suggest that their approach of using multiple virtual networks can be generalized to other deadlock-free routing algorithms, not just "up/down".
  • Future Work: The authors plan to explore better criteria for selecting the number and location of root nodes, as well as evaluating other routing algorithms and combinations of algorithms.

Summary updated

BibTeX
@inproceedings{flich2002improving,
  author = {José Flich and Pedro López and José Carlos Sancho and Antonio Robles and José Duato},
  title = {{Improving InfiniBand Routing through Multiple Virtual Networks}},
  booktitle = {ISHPC},
  year = {2002},
  doi = {10.1007/3-540-47847-7\_7},
}
Figure