Adaptive Packet Routing for Bursty Adversarial Traffic
William Aiello, Eyal Kushilevitz, Rafail Ostrovsky and Adi Rosen
Abstract: One of the central tasks of networking is packet-routing when edge bandwidth is limited. Tremendous progress has been achieved by separating the issue of routing into two conceptual sub-problems: path selection and congestion resolution along the selected paths. However, this conceptual separation has a serious drawback: each packet's path is fixed at the source and cannot be modified adaptively in-route when traffic conditions change. The problem is especially severe when packets insertion is modeled by an adversary, whose goal is to cause ``traffic-jams''.
In this paper, we consider this adversarial setting, motivated by the ``adversarial queuing theory model'' of Borodin et al. [BKR+]. More precisely, we consider an adversary who injects packets into nodes with only their destinations specified (but is limited to injection of sequences of packets that~-~roughly speaking~-~do not inherently overload the network). The question whether it is possible to deal with such an adversary and to design protocols that would ``discover'' the right routes and would avoid ``traffic jams'' (i.e., will keep the buffers at the nodes bounded) was left as an open problem in the recent paper of Andrews et al. [AAF+] (which deals with the case where the adversary does provide routes for the packets). In the present paper, we resolve this open problem. In particular, we present a simple, deterministic, local-control protocol that applies to any network topology. Our protocol guarantees that, for any injection sequence generated by the adversary, the buffers at the nodes are polynomially-bounded and that each packet has a polynomially-bounded delivery time.
comment: Appeared in Proceedings of The 30's ACM Symposium on Theory of Computing (STOC-98)
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |