We prove a sufficient condition for the stability of dynamic packet routing
algorithms. Our approach reduces the problem of steady state analysis to t
he easier and better understood question of static routing. We show that ce
rtain high probability and worst case bounds on the quasi-static (finite pa
st) performance of a routing algorithm imply bounds on the performance of t
he dynamic version of that algorithm. Our technique is particularly useful
in analyzing routing on networks with bounded buffers where complicated dep
endencies 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 particula
r we give the first dynamic algorithms for routing on a butterfly or two-di
mensional mesh with bounded buffers. Both the injection rate for which the
algorithm is stable, and the expected time a packet spends in the system ar
e optimal up to constant factors. Our approach is also applicable to the re
cently introduced adversarial input model.