loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Fifth IEEE International Symposium on Network Computing and Applications (NCA'06)
A Tree-Turn Model for Irregular Networks
Cambridge, Massachusetts
July 24-July 26
ISBN: 0-7695-2640-3
Jiazheng Zhou, National Tsing Hua University, Taiwan
Xuan-Yi Lin, National Tsing Hua University, Taiwan
Yeh-Ching Chung, National Tsing Hua University, Taiwan
In this paper, we propose a general turn model, Tree-turn model, for irregular topology. In Tree-turn model, links are classified as either tree or cross and six directions are associated with channels of links. From these six directions, we prohibit some turns such that an efficient deadlock-free routing algorithm, Tree-turn routing, can be derived. There are three phases to construct the Tree-turn routing. First, build up a coordinated tree for a given topology. Second, construct a communication graph of the topology and the corresponding coordinated tree. Third, set up the forwarding table by using the all-pairs shortest path algorithm according to the prohibited turns derived from the Tree-turn model and the directions of the channels in communication graph. To evaluate the performance, we implement the Tree-turn routing algorithm along with the up*/down* routing algorithm and the L-turn routing algorithm on a software simulator. The simulation results show that Tree-turn routing outperforms other two routing algorithms for all test cases.
Citation:
Jiazheng Zhou, Xuan-Yi Lin, Yeh-Ching Chung, "A Tree-Turn Model for Irregular Networks," nca, pp.11-18, Fifth IEEE International Symposium on Network Computing and Applications (NCA'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.