LFA算法的一种高效实现方法

研究表明，网络中的故障不可避免而且频繁出现.当故障发生时，目前互联网部署的域内路由协议需要经历收敛过程.在此过程中，路由信息可能不一致，从而导致报文丢失，降低了路由可用性.因此，业界提出了利用LFA（loop free alternates）应对网络中发生的单故障情形，从而提高路由可用性.然而，已有的LFA实现方式算法时间复杂度大，需要消耗大量的路由器CPU资源.针对该问题严格证明了当网络中出现单故障时，只需要为特定的节点计算备份下一跳，其余受该故障影响节点的备份下一跳和该特定节点的备份下一跳是相同的.基于上述性质，分别讨论了对称链路权值和非对称链路权值中对应的路由保护算法.实验结果表明：与LFA相比较，该算法的执行时间降低了90%以上，路径拉伸度降低了15%以上，并且与LFA具有同样的故障保护率.

Efficient Implementation Method for LFA

Lots of related researches have shown that network failures occur inevitably and frequently on the Internet. When network failures occur, the currently deployed intra-domain routing protocol need to re-convergent. During the process of re-convergence, the packets may be lost due to inconsistent routing information, thus greatly reducing the Internet routing availability. LFA was proposed to cope with all the single failure scenarios. However, the existing LFA implementation algorithms are time-consuming and require a large amount of router CPU resources. This paper proves that when a single fault occurs in a network, it only needs to calculate the backup next hop for a specific node. The backup next hop of all the other affected nodes by the fault is the same as that of the specific node. Based on the above property, the paper proposes two routing protection algorithms to provide protection for networks with symmetric and asymmetric. The results show that these approaches reduce more than 90% computation overhead compared to LFA, and achieve less than 15% path stretch. Moreover, they can provide comparable protection ratio with LFA.