计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
12期
102-106
,共5页
林沛%杨裔%陈宜漂%邓毓博
林沛%楊裔%陳宜漂%鄧毓博
림패%양예%진의표%산육박
自适应路由%裂痕故障块%虚拟网络%容错%路由表%二维网格
自適應路由%裂痕故障塊%虛擬網絡%容錯%路由錶%二維網格
자괄응로유%렬흔고장괴%허의망락%용착%로유표%이유망격
adaptive routing%cracky fault block%virtual network%fault-tolerance%routing-table%2D mesh
基于裂痕故障块的二维网格自适应容错路由算法是一种有效的容错算法,不仅能够解决活锁问题,而且克服了传统故障块模型中状态良好的节点不能参与路由的缺陷,但同时具有明显的缺点:每次路由到以故障块边界节点为根节点的内部树时,都需要遍历此内部树,因此算法的路由长度并不是最短的。针对上述问题,提出基于裂痕故障块的自适应容错路由表算法,其中路由表由裂痕故障块内部树上的节点创建,通过路由表上保留的有用消息决定是否遍历内部树。实验结果证明,随着网格规模的扩大,该算法最大可减少70%的平均路由长度,并且其实现简单,可以有效地延长网络寿命。
基于裂痕故障塊的二維網格自適應容錯路由算法是一種有效的容錯算法,不僅能夠解決活鎖問題,而且剋服瞭傳統故障塊模型中狀態良好的節點不能參與路由的缺陷,但同時具有明顯的缺點:每次路由到以故障塊邊界節點為根節點的內部樹時,都需要遍歷此內部樹,因此算法的路由長度併不是最短的。針對上述問題,提齣基于裂痕故障塊的自適應容錯路由錶算法,其中路由錶由裂痕故障塊內部樹上的節點創建,通過路由錶上保留的有用消息決定是否遍歷內部樹。實驗結果證明,隨著網格規模的擴大,該算法最大可減少70%的平均路由長度,併且其實現簡單,可以有效地延長網絡壽命。
기우렬흔고장괴적이유망격자괄응용착로유산법시일충유효적용착산법,불부능구해결활쇄문제,이차극복료전통고장괴모형중상태량호적절점불능삼여로유적결함,단동시구유명현적결점:매차로유도이고장괴변계절점위근절점적내부수시,도수요편력차내부수,인차산법적로유장도병불시최단적。침대상술문제,제출기우렬흔고장괴적자괄응용착로유표산법,기중로유표유렬흔고장괴내부수상적절점창건,통과로유표상보류적유용소식결정시부편력내부수。실험결과증명,수착망격규모적확대,해산법최대가감소70%적평균로유장도,병차기실현간단,가이유효지연장망락수명。
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.