Tegan Wilson, Cornell University

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 these oblivious 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, Hakim Weatherspoon, Vishal Shrivastav, and Rachit Agarwal.

See: https://theory.cs.rutgers.edu/theory_seminar