Breaking the VLB Barrier for Oblivious Reconfigurable Networks

Breaking the VLB Barrier for Oblivious Reconfigurable Networks

Abstract: Valiant Load Balancing (VLB) has a long history in both the theory and practice of oblivious routing. Even after forty years, VLB continues to take center stage as a widely used — and in some settings, 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 [AWSWKA’22] 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. Our results are enabled by a novel oblivious routing scheme that improves VLB by stretching routing paths the minimum possible amount — an additive stretch of 1 rather than a multiplicative stretch of 2 — yet still manages to balance load with high probability when either the traffic demand matrix or the network’s interconnection schedule are shuffled by a uniformly random permutation.
This talk is based on joint work with Daniel Amir, Nitika Saran, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon. 

Bio: Tegan is a 6th year PhD student at Cornell advised by Robert Kleinberg, and is generally interested in algorithms, graph theory, networks and routing, and combinatorics. Her recent work has focused on network and routing design for reconfigurable datacenter networks, and proving optimal throughput versus latency guarantees in this space.