摘要： 基于裂痕故障块的二维网格自适应容错路由算法是一种有效的容错算法，不仅能够解决活锁问题，而且克服了传统故障块模型中状态良好的节点不能参与路由的缺陷，但同时具有明显的缺点：每次路由到以故障块边界节点为根节点的内部树时，都需要遍历此内部树，因此算法的路由长度并不是最短的。针对上述问题，提出基于裂痕故障块的自适应容错路由表算法，其中路由表由裂痕故障块内部树上的节点创建，通过路由表上保留的有用消息决定是否遍历内部树。实验结果证明，随着网格规模的扩大，该算法最大可减少70%的平均路由长度，并且其实现简单，可以有效地延长网络寿命。

关键词: 自适应路由, 裂痕故障块, 虚拟网络, 容错, 路由表, 二维网格

Abstract: The 2D mesh adaptive fault-tolerant routing algorithm based on cracky fault block is an effective fault-tolerant algorithm. It not only can solve the problem of live lock, but also can overcome the drawback that good nodes in the faulty block can not be used to take part in normal routing. However, this algorithm still has explicit disadvantages that its routing path is not the shortest due to its need to traverse every interior spanning tree while passing the cracky fault block. This paper proposes an adaptive fault-tolerant routing-table algorithm aiming at the problem of the shortest routing length. The table is created in the tree nodes memory and preserves the useful information to decide whether to traverse the interior tree or not. Experimental results prove that the proposed algorithm can reduce the average length of routing path by 70% with the expansion of mesh grid, and the algorithm is easy to implement and can significantly prolong networks lifetime.

Key words: adaptive routing, cracky fault block, virtual network, fault-toleranc, routing-table, 2D mesh

中图分类号: 

• TP393