An Emperical Study of Off-Line Permutation

Packet Routing on 2-Dimensional Meshes Based on

the Multistage Routing Method

Antonios Symvonis Jonathon Tidswell
Basser Department of Computer Science Hydrographic Sciences Australia P/L
University of Sydney PO Box 85
Sydney, N.S.W. 2006 Cammeray, NSW 2062
Australia Australia
[email protected] [email protected]

February 1, 1994

Abstract

In this paper we present the multistage off-line method, a new and rather natural way to model off-line packet routing problems, which reduces the problem of off-line packet routing to that of finding edges disjoint paths on a multistage graph. The multistage off-line method can model any kind of routing pattern on any graph and can incorporate the size of the maximum queue allowed to be created in any processor. The multistage off-line method accommodates all optimal solutions and can be used to obtain lower bounds based on the actual routing problem under consideration. The paths of the packets are computed by a greedy heuristic method. A lot of freedom is left for the user of the method in order to incorporate in the heuristic properties of the underlying interconnection network. Based on the multistage off-line method, we studied the permutation packet routing problem on 2-dimensional meshes. We ran millions of experiments based on random generated data and, for all of our experiments, we were able to compute a solution of length equal to the maximum distance a packet has to travel, and thus, match the actual lower bound for each routing pattern.

Index terms: Mesh, multistage graph, off-line algorithm, packet routing, permutations.