一种逐跳方式的域内单节点故障保护算法

Hop-by-hop Single-node Failure Protection Algorithm in Intra-domain Routing Networks

研究表明,网络中的故障频繁发生.当网络出现故障时,目前互联网部署的域内路由协议需要经历收敛过程,在此期间将有大量报文丢失,导致用户体验下降,严重影响了因特网服务提供商(ISP,Internet Service Provider)的服务质量.因此,提高域内路由可用性成为亟待解决的一个科学问题.为了提升路由可用性,业界提出了快速重路由的基本框架(IP Fast Re-Route,IPFRR),基于该框架的解决方案可以减少路由协议收敛过程中报文丢失情况,然而该方案并不能100%保护网络中所有可能的单节点故障.因此,本文提出了一种基于逐跳方式的针对单节点故障的全保护方案,该算法具有如下特点:1)实现简单; 2)支持逐跳转发方式; 3)支持增量部署,因此适合在实际中部署.实验结果表明,该方案不仅可以100%保护网络中所有单节点故障情形的路由保护算法,并且具有较小的路径拉伸度.

Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur,the current deployed intra-domain routing protocol need to re-convergence. During the process of re-convergence,the packets may be lost due to inconsistent routing information,greatly reducing the Internet routing availability,seriously affecting the ISP′s service quality and reputation. Therefore,improving the Internet routing availability has become an urgent problem. Therefore,improving the Internet routing availability has become an urgent problem. A framework which is called IPFRR （IP Fast ReRoute） has been proposed to enhance the Internet routing availability,which can effectively reduce packet loss when failures occur. However,the scheme cannot supply complete protection against all single-node failure scenarios. In this work,we aim for hop-by-hop routing algorithm which can provide complete protection against all such a single-node failure scenarios. The algorithm has the following characteristics： 1）simple; 2） hop by hop routing; 3） incremental deployment,so it is suitable for deployment on today′s Internet. The experimental results show that the scheme can not only provide complete protection against all such a single-node failure scenarios,but also have smaller path stretch.