Improving Oblivious Reconfigurable Networks with High Probability

Tegan Wilson, Daniel Amir, Vishal Shrivastav, Robert Kleinberg, Hakim Weatherspoon

Abstract

In a landmark 1981 paper, Valiant and Brebner introduced Valiant load balancing (VLB), which routes messages through a randomly sampled intermediate node. While VLB gains obliviousness, it doubles routing paths. Forty years later, VLB remains a standard for balancing load in datacenters. However, reconfigurable networks offer new possibilities. This work shows that a strictly superior latency-throughput tradeoff is achievable when throughput bounds are relaxed to hold with high probability. We also demonstrate that semi-oblivious routing provides a provable asymptotic advantage over fully-oblivious routing in this setting.

Introduction: The 2x Barrier

For decades, Valiant Load Balancing (VLB) has been the cornerstone of oblivious routing. By routing every packet through a random intermediate node, VLB ensures that traffic is distributed evenly across the network, regardless of the actual demand pattern. This decentralization is critical for modern datacenters where traffic patterns fluctuate too rapidly for centralized control.

However, VLB's robustness comes at a cost: it doubles the path length (a multiplicative stretch of 2). In the context of reconfigurable networks—where topologies can be dynamically adjusted via optical switches—this "2x barrier" has long been considered the optimal tradeoff for guaranteed throughput. This research challenges that assumption, demonstrating that by shifting the focus to "high probability" (w.h.p.) guarantees, we can significantly improve network efficiency.

Methodology: Beyond Multiplicative Stretch

The authors propose a novel routing scheme and connection schedule specifically for reconfigurable topologies. Their approach moves away from the traditional two-hop VLB model toward an additive stretch of 1.

Key Innovations:

  1. Randomized Connection Schedules: Instead of simple rotations, the system utilizes schedules based on "constellations"—mathematical structures that ensure any subset of a specific size forms a basis, facilitating robust connectivity.
  2. Additive Stretch Routing: The scheme employs a single "spraying hop" followed by a direct path to the destination. This reduces the path length from $2g$ to $g+1$, where $g$ is the average hop count of the underlying topology.
  3. Timing as a Source of Entropy: To compensate for the reduced randomness of a single spraying hop, the algorithm randomizes the timing of when direct hops occur. This use of temporal entropy is a novel way to maintain load balancing without increasing path length.
  4. Bilinear Form Tail Bounds: To rigorously prove these results, the authors developed a new exponential tail bound for bilinear forms on the orbits of permutation group actions, ensuring that load is distributed evenly with high probability.

Results: Breaking the VLB Limit

The primary contribution of this work is the demonstration of a latency-throughput tradeoff that is strictly superior to VLB. By allowing for a vanishingly small probability of failure, the network can achieve nearly double the throughput for a given latency constraint.

Comparison of routing goals and performance metrics across different schemes.

As shown in the table above, the proposed oblivious routing (w.h.p.) and semi-oblivious routing schemes reduce the average hop count from $2g$ to approximately $g+1$. This reduction directly translates to a throughput increase from $1/(2g)$ to $1/(g+1)$.

Semi-Oblivious Advantage

A particularly striking result is the separation between fully-oblivious and semi-oblivious routing. In semi-oblivious routing, the connection schedule remains oblivious (randomized), but the routing can be demand-aware (e.g., reacting to local congestion). The authors prove that semi-oblivious reconfigurable networks (SORNs) can achieve lower average latency than fully-oblivious ones (ORNs) for the same throughput, a rare instance where semi-obliviousness provides a provable asymptotic edge.

Throughput vs. log-scale latency for N=10^20, comparing guaranteed and high-probability bounds.

The figure above illustrates the performance gains. The "guaranteed throughput lower bound" (blue) represents the traditional VLB-style limit. The new "w.h.p." bounds (orange and green) show significantly lower latency across various throughput regimes, effectively "breaking" the previous performance ceiling.

Limitations and Future Directions

While this work marks a significant theoretical advance, several challenges remain:

  • The Logarithmic Gap: A small $\tilde{O}(\log N)$ gap exists between the current upper bounds and the theoretical lower bounds.
  • Time-Varying Demands: The current semi-oblivious design is optimized for stationary traffic; adapting it for rapidly shifting demands is an open problem.
  • Physical Constraints: Real-world factors like discrete packet sizes and propagation delays are not yet fully integrated into the model.
  • Integer Reciprocals: The proofs currently face edge-case difficulties when throughput targets are exact reciprocals of integers (e.g., $1/3$), which may require multi-constellation solutions.

This research opens a new frontier in network design, suggesting that the "speed limits" we have accepted for forty years may be bypassable in the era of reconfigurable hardware.

Summary updated

Abstract

In a landmark 1981 paper, Valiant and Brebner gave birth to the study of oblivious routing and, simultaneously, introduced its most powerful and ubiquitous method: Valiant load balancing (VLB). By routing messages through a randomly sampled intermediate node, VLB lengthens routing paths by a factor of two but gains the crucial property of obliviousness. Forty years later, with datacenters handling workloads whose communication pattern varies too rapidly to allow centralized coordination, VLB continues to take center stage as a widely used - and in some cases provably optimal - way to balance load in the network obliviously to the traffic demands. However, the ability of the network to rapidly reconfigure its interconnection topology gives rise to new possibilities. In this work we revisit the question of whether VLB remains optimal in the novel setting of reconfigurable networks. Prior work showed that VLB achieves the optimal tradeoff between latency and guaranteed throughput. In this work we show that a strictly superior latency-throughput tradeoff is achievable when the throughput bound is relaxed to hold with high probability. The same improved tradeoff is also achievable with guaranteed throughput under time-stationary demands, provided the latency bound is relaxed to hold with high probability and that the network is allowed to be semi-oblivious, using an oblivious (randomized) connection schedule but demand-aware routing. We prove that the latter result is not achievable by any fully-oblivious reconfigurable network design, marking a rare case in which semi-oblivious routing has a provable asymptotic advantage over oblivious routing. To analyze our routing scheme we prove an exponential tail bound which may be of independent interest, concerning the distribution of values of a bilinear form on an orbit of a permutation group action.
BibTeX
@inproceedings{wilson2023improving,
  author = {Tegan Wilson and Daniel Amir and Vishal Shrivastav and Robert Kleinberg and Hakim Weatherspoon},
  title = {{Improving Oblivious Reconfigurable Networks with High Probability}},
  booktitle = {STOC},
  year = {2023},
  doi = {10.48550/arxiv.2308.14837},
}
Figure