A Tree-Turn Model for Irregular Networks

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. 1