一种基于转发图的域内路由保护算法

An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph

业界提出利用路由保护算法来解决网络中的故障问题,然而已有的路由保护算法存在4个方面的问题:1)无法应对网络中所有可能的单故障情形;2)需要额外辅助机制的协助;3)不支持增量部署;4)每个结点存储多个到达目的地址的备份下一跳.提出一种基于转发图的域内路由保护算法(an intradomain routing protection algorithm based on forwarding graph,RPBFG)来解决这4个问题.首先建立了以最大化故障保护率为目标、以转发图包含反向最短路径树为约束条件的路由保护模型;然后提出了利用遗传算法构造满足上述目标的转发图;最后根据构造的转发图计算出所有结点到达目的结点的备份下一跳.在11个真实拓扑结构中比较了RPBFG,NPC,U-turn,MARA-MA,MARA-SPE在故障保护率和路径拉伸度的性能.实验结果表明,RPBFG可以应对网络中所有可能的单故障;在平均路径拉伸度方面,RPBFG比NPC,U-turn,MARA-MA,MARA-SPE分别降低了0.11%,0.72%,37.79%,36.26%.

Currently,intra-domain routing protocols which are deployed on the Internet respond to network failures through a global convergence mechanism.In the process of routing convergence,a large number of data packets will be discarded,leading to network interruption.The industry proposes to use routing protection methods to solve the above problem.However,the existing routing protection methods have the following four problems:1)they cannot cope with all possible single failures in the network;2)they need the assistance of additional auxiliary mechanisms;3)they do not support incremental deployment;4)each node stores multiple backup next hops for each destination,increasing storage and computation costs.We propose an intra-domain routing protection algorithm based on forwarding graph(RPBFG)to solve the above four problems of existing routing protection algorithms.We first establish a routing protection model with the goal of maximizing the failure protection ratio and the constraint that the forwarding graph contains the reverse shortest path tree;then a genetic algorithm is proposed to construct a forwarding graph that satisfies the above goal;finally,the backup next hop of all nodes arriving at the destination node is calculated according to the constructed forwarding graph.We compare the performance of RPBFG,NPC,U-turn,MARA-MA and MARA-SPE in 11 real topologies,including failure protection ratio and path stretch.The experimental results show that RPBFG can deal with all possible single failures in the network,and that is to say the failure protection ratio of RPBFG is 100%,while the average failure protection ratio of NPC,U-turn,MARA-MA and MARA-SPE is 45.05%,74.53%,89.78%and 91.24%respectively.In the aspect of path stretch,RPBFG decreased by 0.11%,0.72%,37.79%and 36.26%respectively compared with NPC,U-turn,MARA-MA and MARA-SPE.The research results will help to promote the progress of Internet service providers in deploying intra-domain routing protection schemes in real networks.