Proof of the deadlock-freeness of ALD routing algorithm

Wang, Hong and Xu, Du and Jiang, Guo and Yao, Yao and Xu, Shizhong and Li, Lemin (2006) Proof of the deadlock-freeness of ALD routing algorithm. [Preprint]

Full text available as:



This is the appendix to the paper Load-Balanced Adaptive Routing for Torus Networks to provide a detailed, formal proof of the deadlock-freeness of the routing algorithm proposed in the paper. The paper is submitted to Electronics Letters, and the abstract of which is as follows: A new routing algorithm for torus interconnection networks to achieve high throughput on various traffic patterns, Adaptive Load-balanced routing with cycle Detection (ALD), is presented. Instead of the -channels scheme adopted in a few recently proposed algorithms of the same category, a cycle detection scheme is employed in ALD to handle deadlock, which leads to higher routing adaptability. Simulation results demonstrate that ALD achieves higher throughput than the recently proposed algorithms on both benign and adversarial traffic patterns.

Item Type:Preprint
Keywords:deadlock, routing algorithm, torus networks
Subjects:Computer Science > Dynamical Systems
ID Code:4701
Deposited By: Wang, Hong
Deposited On:14 Jan 2006
Last Modified:11 Mar 2011 08:56


Repository Staff Only: item control page