A general approach to dynamic packet routing with bounded buffers
Open Access
- 1 March 2001
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 48 (2) , 324-349
Abstract
We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasi-static (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependices make standard queuing techniques inapplicable. We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithms for routing on a butterfly or two-dimensional mesh with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.Keywords
This publication has 10 references indexed in Scilit:
- Adversarial queuing theoryJournal of the ACM, 2001
- Dynamic deflection routing on arrays (preliminary version)1996
- Universal continuous routing strategies1996
- Bounding delays in packet-routing networks1995
- Bounds on the greedy routing algorithm for array networks1994
- Simple algorithms for routing on butterfly networks with bounded queues1992
- The efficiency of greedy routing in hypercubes and butterflies1991
- Average case analysis of greedy routing algorithms on arrays1990
- How to emulate shared memory1987
- Efficient Schemes for Parallel CommunicationJournal of the ACM, 1984