Optimal Oblivious Reconfigurable Networks

Optimal Oblivious Reconfigurable Networks (via Zoom)

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. I focus on the tradeoffs between maximizing throughput and minimizing latency. For every constant guaranteed 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 load balancing, which I show is necessary for oblivious network designs, becomes more costly when average path length is not an integer, since equalizing the load balanced path lengths is not achievable.

This talk is based on joint work with Daniel Amir, Robert Kleinberg, Rachit Agarwal, Hakim Weatherspoon, and Vishal Shrivastav. To be published at STOC 2022.

Bio: Tegan Wilson is a 4th year CS PhD student at Cornell University advised by Bobby Kleinberg. She is broadly interested in algorithms, graph theory, and combinatorics. Prior to graduate school, she received a B.A in Computer Science and Mathematics from Carleton College.