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 x n meshes. In deflection routing, a message cannot be queued and it is always moving until it reaches its destination. ln worm routing, the m essage is considered to be a worm, a sequence of k flits which, during the routing, follow the head oi the worm, which knows the destination address. We show how to derive a deflection worm routing algorithm fr om 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 a pplied). Our result generalizes the method of Newman and Schuster in w hich only packet routing algorithms with a maximum queue of tour packe ts can be used.