Hi everyone,
Since we have a visitor, it would be great if as many people could attend the talk as possible. Thank you to the students who are taking the speaker to lunch!
Title: 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 Distinguished Postdoc at Northeastern working under
Rajmohan Rajaraman. She received her PhD from Cornell University and was advised by Robert Kleinberg. Her recent work has focused on network and routing design for reconfigurable datacenter networks. Her website is here:
https://teganwilson.github.io/
Best,
Sandeep
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}