A general method for deflection worm routing on meshes based on packet routing algorithms

In this paper, we consider the deflection worm routing problem on n×n meshes. In deflection routing, a message cannot be queued and it is always moving until it reaches its destination. In worm routing, the message is considered to be a worm, a sequence of k flits which, during the routing, follow the head of the worm, which knows the destination address. We show how to derive a deflection worm routing algorithm from a packet routing algorithm which uses queues of size O(f(N))(N is the side-length of the mesh in which the packet routing algorithm is applied). Our result generalizes the method of Newman and Schuster in which only packet routing algorithms with a maximum queue of four packets can be used