Adaptive Packet Routing for Bursty Adversarial Traffic

摘要

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 subproblems: 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. (1996, in “Proc. of 28th STOC,” pp. 376–385). 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. (1997, in “Proc. of 38th FOCS,” pp. 294–302) (who deal with the nonadaptive 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 polynomially bounded delivery time.