AN EMPIRICAL-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 rat her natural way to model off-line packet routing problems, which reduc es the problem of off-line packet routing to that of finding edge disj oint paths on a multistage graph. The multistage off-line method can m odel any kind of routing pattern on any graph and can incorporate the size of the maximum queue allowed in any processor. The paths for the packets are computed by a greedy heuristic method. Based on the multis tage off-line method, we study the permutation packet routing problem on two-dimensional meshes. We ran millions of experiments based on ran dom generated data and, for all of our experiments, we were able to co mpute a solution of length equal to the maximum distance a packet had to travel, and thus, match the actual lower bound for each routing pat tern.