Adaptive Packet Routing for Bursty Adversarial Traffic

✍ Scribed by William Aiello; Eyal Kushilevitz; Rafail Ostrovsky; Adi Rosén

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 236 KB
• Volume: 60
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1999.1681

✦ Synopsis

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 trafficjams. 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