loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.