Speaker: Will Rosenbaum (https://www.willrosenbaum.com)

Abstract: In this talk, we consider packet forwarding in the adversarial queueing theory (AQT) model introduced by Borodin et al. In the AQT model, packets are injected adversarially into a network. The goal is to devise a protocol that delivers packets to their respective destinations while using the smallest possible buffer space per node. For simple network topologies, we describe an optimal local protocol, and demonstrate a smooth trade-off between a protocol’s locality and its worst-case buffer space requirement. We also discuss lower bounds and open questions related to the space complexity of packet forwarding.

Location: Otaniemi Tbuilding, room T6