ALCOMFT-TR-01-56

Ioannis Caragiannis, Christos Kaklamanis and Ioannis Vergados
Greedy Dynamic Hot-Potato Routing on 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. Motivated by recent theoretical work on dynamic routing, we address the dynamic case where packets are continuously injected into the network. We describe three greedy hot-potato routing algorithms and present simulation experiments on tori of several sizes using four well-known greedy (also known as work-conserving) protocols (namely FIFO, LIFO, FTG, and NTG) for the implementation of injection buffers. Our results demonstrate that there exists a greedy hot-potato routing algorithm that is stable for all greedy injection queueing protocols for injection rates very close to 100\% of the network capacity. Furthermore, according to the algorithms we studied, we can claim that the one-pass property is not appropriate for the dynamic case, since the system cannot achieve stability at high injection rates.

Postscript file: ALCOMFT-TR-01-56.ps.gz (81 kb).