Title: Optimal Oblivious Reconfigurable Networks

Abstract: Reconfigurable networks are a new communication network paradigm that allows changing the pattern of interconnections between nodes millions of times per second. Network architectures that leverage this capability are being proposed as an energy-efficient way to meet the growing demand for bandwidth in datacenters. Understanding how to make the best use of this technology requires developing novel theory to quantify the inherent trade-offs and identify optimal network designs. Our focus in this talk will be on the trade-off between maximizing throughput and minimizing latency. For every constant throughput guarantee, we characterize (up to a constant factor) the minimum latency achievable by an oblivious reconfigurable network design. If one allows a small constant additive loss in throughput, it becomes possible to achieve every point on this latency-throughput curve simultaneously, just by varying the routing paths used to forward data with different latency requirements. The analysis of these network designs involves a mixture of linear programming, combinatorics, and Fourier analysis. No prior knowledge of computer networking will be assumed.

Bio: Bobby Kleinberg is a Professor of Computer Science at Cornell University. His research concerns algorithms and their applications to machine learning, economics, networking, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies; he and his co-workers received the 2018 SIGCOMM Networking Systems Award for pioneering the first Internet content delivery network. He is a Fellow of the ACM and a recipient of the ACM SIGecom Mid-Career Award for advancing the understanding of on-line learning and decision problems and their application to mechanism design.