ALCOMFT-TR-01-58

Constantinos Bartzis, Ioannis Caragiannis, Christos Kaklamanis and Ioannis Vergados
Experimental Evaluation of Hot-Potato Routing Algorithms in 2-Dimensional Processor Arrays
Patras. Work packages 2 and 5. May 2001.

Abstract: In this paper we consider the problem of routing packets in two-dimensional torus-connected processor arrays. We consider four algorithms which are either greedy in the sense that packets try to move towards their destination by adaptively using a shortest path, or have the property that the path traversed by any packet approximates the path traversed by the greedy routing algorithm in the store-and-forward model. In our experiments, we consider the static case of the routing problem where we study permutation and random destination input instances as well as the dynamic case of the problem under the stochastic model for the continuous generation of packets.

Postscript file: ALCOMFT-TR-01-58.ps.gz (46 kb).