TL;DR
This paper introduces the In-Transit Buffer (ITB) mechanism, a novel approach to enhance network performance in source-routed environments. By strategically using buffers to temporarily eject and re-inject packets, ITBs break routing cycles, ensure minimal paths, and significantly reduce network contention, leading to substantial throughput improvements across various routing algorithms.
What Problem Does This Paper Address?
Modern high-performance computing relies on efficient interconnects, particularly in clusters of workstations (COWs). These networks often feature irregular topologies and utilize source routing for its simplicity and speed. However, traditional source routing algorithms like "up/down" can lead to performance bottlenecks due to concentrated traffic near the "root" switch and the use of non-minimal paths. While more advanced algorithms like DFS and Smart offer better traffic balancing, they can have high computational overhead or still suffer from performance limitations. This paper addresses the challenge of improving network performance by tackling issues of deadlocks, non-minimal paths, and unbalanced traffic distribution in source-routed networks.
Methods
The core innovation presented is the In-Transit Buffer (ITB) mechanism. The fundamental idea is to split paths in the Channel Dependence Graph (CDG) by selecting an intermediate host (an ITB) where a packet is fully ejected from the network and then re-injected. This process effectively breaks cycles, ensuring deadlock-free routing and guaranteeing minimal paths. Crucially, ITBs also improve performance by freeing up network links when packets are ejected, thereby reducing contention. The authors apply this mechanism to existing routing schemes:
- Up/down Routing: ITBs are used to break cycles and ensure minimal paths. Two approaches are explored: using the minimum number of ITBs required for deadlock-free routing (UD_MITB) and using more ITBs to further improve performance (UD_ITB).
- DFS and Smart Routing: ITBs are applied to these more advanced algorithms to further boost their performance, referred to as DFS_ITB and B_ITB (for balanced ITB with Smart).
The paper evaluates the impact of ITBs on network throughput and latency under various traffic patterns and network sizes.
Datasets
The evaluation is performed using simulated networks based on the Myrinet network architecture. The paper analyzes networks with 16, 32, and 64 switches, corresponding to 64, 128, and 256 hosts, respectively. The network topologies are generated randomly, with specific constraints: 8-port switches, 4 hosts per switch, and single links between neighboring switches.
The traffic patterns used for evaluation include:
- Uniform: Destinations chosen randomly with equal probability.
- Bit-reversal: Destinations computed by reversing the bits of the source host ID.
- Local: Destinations within a limited number of switches from the source.
- Hot-spot: A percentage of traffic is directed to a specific host, with the rest distributed randomly.
- Combined: A mix of the above distributions.
Message sizes of 512 bytes are primarily used for results, with some latency analysis for 32-byte messages.
Key Insights and Ideas
- ITBs are a versatile tool: The ITB mechanism isn't limited to fixing deadlocks; it's a powerful technique for improving overall network performance by reducing contention and balancing traffic.
- Trade-off between latency and throughput: While ITBs significantly boost throughput, they can introduce a small latency penalty, especially for short messages. This highlights a critical design decision for network architects.
- ITBs benefit even advanced routing: Even sophisticated algorithms like Smart, which already excel at traffic balancing, see performance gains with ITBs, primarily by reducing network contention.
- Network size amplifies ITB benefits: The performance improvements from ITBs become more pronounced as the network size increases, suggesting their importance in larger-scale systems.
- Minimal paths are guaranteed: A key advantage of ITBs is their ability to ensure that all utilized routes are minimal, a significant improvement over some traditional routing schemes.
Key Results
The ITB mechanism consistently improves network throughput across all tested routing algorithms and network sizes.
- Up/down routing: UD_MITB improves throughput by factors of 1.12, 1.50, and 2.00 for 16, 32, and 64-switch networks, respectively. UD_ITB further boosts this, with factors of 1.22, 2.14, and 2.75 for the same network sizes.
- DFS routing: DFS_ITB improves throughput over DFS by factors of 1.10, 1.39, and 1.54 for 16, 32, and 64-switch networks.
- Smart routing: B_ITB routing increases network throughput by a factor of 1.33 for a 32-switch network.
- Latency: For 512-byte messages, ITBs cause a slight average latency increase (never higher than 5%). This increase is more noticeable for short messages (32 bytes), with maximum latency increases up to 22.09% for UD_ITB.
- Traffic Balancing: ITBs significantly improve traffic balancing, especially for algorithms like up/down that suffer from congestion near the root switch. For example, in a 32-switch network, UD_MITB routing shows only 10% of links used more than 30% of the time, compared to UD routing where some links are overused by more than 50%.
Limitations and Future Work
- Latency Penalty: The authors acknowledge that ITBs introduce a latency penalty, particularly for short messages. This necessitates a careful selection of the number of ITBs based on application requirements.
- Overhead: While not extensively quantified in terms of performance impact, the process of ejecting and re-injecting packets incurs overhead in terms of time and buffer resources.
- Future Work: The authors plan to implement the ITB mechanism on an actual Myrinet network to validate simulation results. They are also actively researching techniques to reduce the overhead associated with ITBs.
Summary updated