Adaptive packet routing for bursty adversarial traffic
William A. Aiello, Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosén · 1998
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 en-route. The problem is especially severe when packet injections are 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, with only their destinations specified, into network nodes in a continuous manner subject to certain limitations on the injection rate. The question whether it is possible to deal with such an adversary and to design protocols that would “discover ” routes which avoid “traffic jams ” so that nodes only store a bounded number of packets, was left as an open problem by Andrews et al. [AAF+] (who deal with the “non-adaptive ” case where the adversary provides 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 polynomiallybounded delivery time.