loading...
Greedy Dynamic Hot-Potato Routing on Arrays
Dallas/Richardson, Texas, USA December 07-December 07
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2000.9002832000 International Symposium on Paral ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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.


Suggestions