An Intra-Domain Routing Protection Algorithm Based on Forwarding Graph

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.