2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00) Greedy Dynamic Hot-Potato Routing on Arrays Dallas/Richardson, Texas, USA December 07-December 07 ISBN: 0-7695-0936-3
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.
Citation:
I. Caragiannis, C. Kaklamanis, I. Vergados, "Greedy Dynamic Hot-Potato Routing on Arrays," ispan, pp.178, 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), 2000 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||