Tel-Aviv University - Computer Science Colloquium
Sunday, November 8, 14:15-15:15
at 14:00 One of the central tasks of networking is packet-routing when link bandwidth is limited and packets are continuously injected into the network. One possibility to address this problem is to separate it into two sub-problems: path selection and congestion resolution along the selected paths. However, this approach has a drawback: each packet's path is fixed at the source and cannot be modified adaptively en-route when traffic conditions change. This is especially severe when traffic is bursty or deviates from the predictions. At the extreme such situation can be modeled as injection of packets controlled by an adversary, whose goal is to cause "traffic-jams".
In this talk we consider this adversarial setting, motivated by the "adversarial queuing theory model" of Borodin et al. Packets are injected into the network with only their destination specified. They are controlled by a worst-case adversary who is only limited by the condition, roughly speaking, not to inherently overload the network. No probabilistic assumptions are made on the injection of packets into the network.
We present a new simple and deterministic protocol for this setting, that applies to any network topology. The protocol makes hop-by-hop decisions on routing of packets and on congestion-resolution, and "discovers" in an on-line and distributed fashion the right routes that avoid "traffic jams". Thus, it guarantees, for any sequence of packets injected by such adversary, that the buffers at the nodes remain bounded and that each packet has bounded delivery time. We remark that this protocol resolves a central problem left open by previous work in adversarial queuing theory.
Joint work with William Aiello, Eyal Kushilevitz, and Rafail Ostrovsky.