IP网络中主动式故障快速恢复算法的研究

发布时间：2018-04-02 06:27

本文选题：IP网络快速恢复　切入点：无环替换　出处：《河南科技大学》2017年硕士论文

【摘要】：为了解决传统网络协议故障恢复时间过长而加剧网络丢包、网络拥塞的问题,人们提出了IP网络主动式故障快速恢复技术。这是一种通过预计算的方法得到备份转发路径的故障恢复机制,这种机制主要应用于故障发生后和重路由之间的时间段内。在现有的主动式故障恢复算法中,LFA算法计算复杂度低,只需要在现有的路由协议上经过简单的修改就可以实现,因此LFA相较于其他算法更加具有优势。LFA技术的关键是根据无环公式计算出故障时用来替换正常节点的下一跳节点,并且保证到达目的节点的流量不形成路由环路。但是,LFA算法在现阶段还存在着一定缺陷。在实际网络环境中并不是所有的节点都满足拥有替换节点的条件,因此该算法并没有对整个网络起到完全的保护作用。此外,在面临多故障时LFA算法不能避免形成环路的问题也将是研究改进的重点。本文通过公式推导和证明得出新的无环替换公式,大量仿真实验表明新提出的算法在链路保护覆盖率以及多故障上具有更优的效果。本文的主要贡献如下:1.针对LFA算法故障保护覆盖率不理想的问题,首先对LFA算法的无环替换公式进行修改并通过理论推导验证算法的可行性,通过改进公式得到改进的Modified LFA算法;之后采用与LFA算法相结合的混合算法Mixed LFA算法,当网络中发生故障时首先采用LFA算法进行转发,当LFA算法不能保护时采用Modified LFA算法进行转发,只有当两种算法都不能保护时再选择丢包;通过仿真实验验证,Mixed LFA算法在故障保护覆盖率上相较于LFA算法提高了8.89%;2.为解决LFA算法在多故障情况下不能避免形成环路的问题,本文首先分析了在多故障情况下使用LFA算法形成环路的原因和条件,得到结论只有在两个节点之间才能形成环路,在三个或者三个以上节点之间不能形成环路;根据得到的结论对LFA算法在备份路由表创建的步骤进行改进,将LFA算法中互为无环替换节点的路由表项标记为不可用得到了改进的算法I-LFA算法;通过仿真实验验证,I-LFA算法能够解决IP网络中的多故障恢复问题且避免形成路由环路。
[Abstract]:In order to solve the problem of packet loss and network congestion caused by the long fault recovery time of traditional network protocol, the active fast fault recovery technology of IP network is proposed.This mechanism is used to obtain the recovery mechanism of the backup forwarding path by the method of prediction. This mechanism is mainly used in the time period between the fault and the rerouting.Among the existing active fault recovery algorithms, the LFA algorithm has low computational complexity and can be implemented by simply modifying the existing routing protocols.Therefore, the key of LFA technology is to calculate the next hop node which is used to replace the normal node in the absence of loop formula, and to ensure that the flow to the destination node does not form a routing loop.However, the LFA algorithm still has some defects at the present stage.In the real network environment, not all nodes satisfy the condition of having replacement nodes, so the algorithm does not protect the whole network completely.In addition, the problem that the LFA algorithm can not avoid the formation of loops in the face of multiple faults will also be the focus of research and improvement.In this paper, a new acyclic substitution formula is derived and proved by formula. A large number of simulation experiments show that the proposed algorithm has a better effect on link protection coverage and multiple faults.The main contributions of this paper are as follows: 1.Aiming at the problem that the coverage of fault protection of LFA algorithm is not ideal, this paper first modifies the acyclic replacement formula of LFA algorithm and verifies the feasibility of the algorithm by theoretical derivation, and obtains the improved Modified LFA algorithm by improving the formula.Then the hybrid algorithm Mixed LFA, which is combined with LFA algorithm, is adopted. When the network fails, the LFA algorithm is first used to forward, and the Modified LFA algorithm is used to forward the LFA algorithm when it can not be protected.Only when the two algorithms can not protect, we choose to lose the packet. The simulation results show that the mixed LFA algorithm can improve the fault protection coverage by 8.89% compared with the LFA algorithm.In order to solve the problem that LFA algorithm can not avoid forming loops in multi-fault cases, this paper first analyzes the reasons and conditions of using LFA algorithm to form loops in multi-fault cases, and draws a conclusion that loops can only be formed between two nodes.The loop can not be formed between three or more nodes. According to the conclusions, the steps of creating LFA algorithm in backup routing table are improved.The routing table items in the LFA algorithm are marked as unusable, and the simulation results show that the I-LFA algorithm can solve the multi-fault recovery problem in IP networks and avoid the formation of routing loops.
【学位授予单位】：河南科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.06

【相似文献】