An Emperical Study of Off-Line Permutation Packet Routing on 2-Dimensional Meshes Based on the Multistage Routing Method

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 experime..