Research On Algorithms For IP Network Fast Recovery

IP FRR is a mechanism used before rerouting,and this mechanism can get some backup routing paths by pre calculated without the need of rerouting.In IP FRR,LFA algorithm has low computational complexity.LFA can be achieved by existing routing protocols through a simple modification,so compared with other algorithms LFA has more advantages.The key of LFA algorithm is to compute the next hop node to replace the normal node according to the acyclic formula,and ensure that the traffic arriving at the destination node does not form the routing loop.However,there are some defects in the LFA algorithm at this stage.In LFA algorithm,not all nodes satisfy the conditions of the replacement node,so the algorithm does not play a full role in the protection of the entire network.In addition,the LFA algorithm can't avoid the problem of forming loops in the face of multiple faults.Through the derivation and proof of the formula,a new formula of acyclic substitution is obtained.A large number of simulation experiments show that the proposed algorithm has a better effect on the link protection coverage and multiple faults.In view of the above problems,the main contributions of this paper are as follows:1.In order to solve the problem that the coverage rate of fault protection is not up to 100% in LFA algorithm,firstly we improve the formula of LFA algorithm and get a new algorithm called Modified LFA algorithm;then we use a mixed algorithm called Mixed LFA algorithm to improve the coverage rate of fault protection by combining with LFA algorithm and Modified LFA algorithm.When a fault occurs in the network we using LFA algorithm for forwarding,only when LFA algorithm can't protect we use Modified LFA algorithm for forwarding.If these two algorithms both can't protect,we choose lose the packet.Simulation results show that the Mixed LFA algorithm in fault protection coverage rate increased by 8.89% compared to the LFA algorithm.2.In order to solve the problem that LFA can't avoid the formation of the loop in the case of multiple faults,firstly we analyzed the reasons of the formation of loop conditions.The conclusion shows that the loop can only be between two nodes,loop formed in three or more than three nodes can't appear.According to the conclusions we proposed an improved algorithm called I-LFA algorithm by improve the backup routing table creating steps.The simulation results show that I-LFA algorithm cansolve the problem in multi fault recovery problems in network.