Fast deflection routing for packets and worms

Abstract

We consider deflection routing on the n×n mesh and torus. In deflection routing a message cannot be buffered, and is therefore always moving until it reaches its destination. In addition, routing choices have to be made locally. We give a nearly optimal deterministic algorithm for the permutation routing problem for packets, the first such result for deflection routing. We extend the deterministic algorithm to the case when the messages are worms: a contiguous physical stream of bits that must follow the head of the message uninterrupted through the network. We then give an optimal randomized algorithm for permutation routing for worms of any length up to n.