We study the performance of packet routing on arrays with bounded buffers in the routing switches, asuming that new packets are continuously inserted at all the nodes. We give the first routing algorthm on this topology that is stable under an injection rate withi na constant factor of the hardware bandwidth. Unlike previous results, our algorithm does not require the globla synchronization of the insertion times or the retraction and reinsertion of excessively delayed messages and our analysis holds for a broad range of packet generation stochastic distributions. This result represents a new application of a general technique for the design and analysis of dynamic algorithms that we first presented in [Broder et al., FOCS 96, pp.390-399].
展开▼
