Abstract: Oblivious routing has a long history in both the theory and practice of networking. In this talk I will initialize the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in datacenter networking, due to its increased energy efficiency and scaling potential. I focus on the tradeoffs between maximizing throughput and minimizing latency in this space. For every constant throughput rate, I characterize the minimum latency (up to a constant factor) achievable by an oblivious reconfigurable network design. The tradeoff curve turns out to be surprisingly subtle: it has an unexpected scalloped shape, reflecting the fact that routing becomes more costly when average path length is not an integer, since equalizing the path lengths is not achievable. I show that in order to guarantee the throughput value, Valiant load balancing is necessary, which lengthens routing paths by a factor of two. However, I also 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.

This talk is based on joint work with Daniel Amir, Nitika Saran, Rachit Agarwal, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon.