作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

基于裂痕故障块的自适应容错路由表算法

林 沛1,杨 裔2,陈宜漂2,邓毓博2   

  1. (1. 兰州文理学院网络中心,兰州 730000;2. 兰州大学信息科学与工程学院,兰州 730000)
  • 收稿日期:2013-07-24 出版日期:2013-12-15 发布日期:2013-12-13
  • 作者简介:林 沛(1983-),男,讲师、硕士、CCF会员,主研方向:网络安全,网络规划与优化;杨 裔,副教授、博士;陈宜漂,硕士;邓毓博,博士
  • 基金资助:
    甘肃省自然科学基金资助项目(1107RJZA188)

Adaptive Fault-tolerant Routing-table Algorithm Based on Cracky Fault Block

LIN Pei 1, YANG Yi 2, CHEN Yi-piao 2, DENG Yu-bo 2   

  1. (1. Network Center, Lanzhou University of Arts and Science, Lanzhou 730000, China; 2. School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, China)
  • Received:2013-07-24 Online:2013-12-15 Published:2013-12-13

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

中图分类号: