Adaptive packet routing for bursty adversarial traffic

One of the central tasks of networking is packet routing when edge band-wid th is limited. Tremendous progress has been achieved by separating the issu e of routing into two conceptual subproblems: path selection and congestion resolution along the selected paths. However, this conceptual separation h as 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 pac ket 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 28t h STOC," pp. 376-385). More precisely, we consider an adversary who injects packets, with only their destinations specified, into network nodes in a c ontinuous manner subject to certain limitations on the injection rate. The question whether it is possible to deal with such an adversary and to desig n protocols that would discover routes which avoid traffic jams so that nod es only store a. bounded number of packets was left as an open problem by A ndrews et al. (1997, in "Proc. of 38th FOGS," pp. 294-302) (who deal with t he nonadaptive case where tho adversary provides routes for the packets). I n che present paper, we resolve this open problem. In particular, we presen t a simple, deterministic, local-control protocol that applies to any netwo rk topology. Out protocol guarantees that, for any injection sequence gener ated by the adversary, thc buffers at the nodes are polynomially bounded an d that each packet has a polynomially bounded delivery time. (C) 2000 Acade mic Press.