page 2  (7 pages) 1 3

1 Introduction

In this note, we study the routing of messages in undirected graphs. Message routing has been abstracted in several ways. In packet routing it is assumed that a message can be transmitted between two adjacent processors (vertices of the undirected graph) in a single step as a packet. We examine the routing model known as deflection (or hot-potato) routing in which packets continously move between processors from the time they are injected into the network until the time they are consumed at their destination.

The advantage of deflection routing is obvious. No queueing area is required at the processors. However, the fact that packets always move implies that at any step each processor must transmit the packets it received during the previous step (unless they were destined for it). As a result, several packets might be derouted away from their destination. This makes the analysis extremely difficult.

The work of Feige and Raghavan[4] which provided analysis for deflection routing algorithms for the torus and the hypercube, renewed the interest in deflection routing. As a result, several papers appeared with deflection routing as their main theme. Bar-Noy et al [1] gave a nearly optimal deterministic algorithm for routing permutations on the n ? n mesh and torus. Based on sorting algorithms, Newman and Schuster [8] derived asymptotically optimal algorithms for routing permutations on the mesh and the torus networks and a near optimal algorithm for the hypercube. Kaufmann et al [7] fine tuned their results for the case of meshes and managed to reduce the constant hidden in the asymptotic analysis.

Ben-Aroya and Schuster [2] considered the general situation where a mesh is loaded with k packets that have to be routed to their destinations in a hot-potato manner. Through clever analysis of their greedy algorithm they showed that routing will terminate within dist + 2(k ? 1) steps where dist is the initial maximum distance a packet has to travel. Indepedently, Borodin et al [3] formalized the notion of the deflection sequence, a nice way to charge each deflection of an individual packets to distinct packets traveling on the network. By using their method, they show that routing k packets in a hot-potato manner can be completed within dist + 2(k ? 1) steps for trees, butterflies and multidimensional meshes, where dist is the initial maximum distance a packet has to travel. For two dimensional meshes, even though their result is the same with that of Ben-Aroya and Schuster [2], their algorithm is considered to be superior since it is has better performance for the significant case of permutation routing1.

In their paper, Borodin et al [3] mention several open problems. Among them, i) the problem (attributed to Hajek [6]) of deriving a deflection routing algorithm for an arbitrary undirected graph which routes any routing pattern consisting of k packets within dist + 2(k ? 1) steps where dist is the initial maximum distance a packet has to travel, and ii) whether the one-pass of links" property (as defined by Feige and Raghavan [4]) is a substantial restriction to fast deflection routing.

In this research note we build on the research of Borodin et al [3] and we describe a simple algorithm which satisfies the one-pass of links" property and routes any k packet routing pattern on any undirected graph G within 2diamG + 2(k ? 1) routing steps where diamG is the diameter of graph G. Besides of comming very close to the desired diamG + 2(k ? 1) routing performance, our result also shows that the one-pass of links" property is not a major restriction for routing on undirected graphs (note that tehre exist routing patterns on trees which require diamG + 2(k ? 1) steps for their routing). For a d-dimensional mesh M the required number of routing steps reduces to diamM + (d ? 1) + 2(k ? 1) where diamM is the diameter of the mesh M .

1The Algorithm of Ben-Aroya and Schuster [2] has not been analysed for the special case of permutation routing yet.