【作者】 王芳；

【导师】 陈山枝；

【作者基本信息】 北京邮电大学 ， 计算机科学与技术， 2009， 博士

【摘要】 近年来,新科学技术的推出、新业务种类的出现促进了网络的迅速发展,Internet承载了越来越多的流量,服务提供商(SP)发现Internet能带来潜在的高额利润,然而即使在可靠的网络中也无时无处不存在的各种故障使得服务不可用或者性能下降。为了保障用户业务的服务质量(Qos),主要研究在故障、攻击等意外情况下系统如何保证任务及时完成的网络生存性受到SP关注,而适用于实际纯IP网络的IP网络生存性以其成本低、细粒度、处理故障范围较大、保护时间较长成为目前的研究热点。本文不考虑安全性方面的问题。IP网络生存性根据备份路径建立时间的先后分为主动性策略和被动性策略。而依据故障后当前网络状况自适应建立备份路径的被动性策略由于较长的故障处理时间不能满足现有业务99.999%服务可用性(service availability)的要求。因此本文主要围绕着基于主动策略的IP网络生存性故障处理技术进行了研究,研究的侧重点为处理频繁故障引起的路由振荡抑制机制、网络瞬时单链路/节点故障恢复机制和基于最小覆盖集的多链路故障解决方案。论文的主要工作包含以下几个方面:(1)根据实际骨干网络中路由振荡的引发原因,通过分析路由收敛过程中收敛时间在各个阶段的决定因素,确定链路振荡与路由振荡之间的关系,将路由振荡抑制转化为链路振荡抑制,以本地处理的角度提出了动态自适应的调节Hello定时器的路由振荡抑制机制。仿真结果表明该机制不仅能很好的抑制振荡,且占用较小的网络资源,同时保证网络可靠性和稳定性。通过搭建试验网络证实该机制可与现有路由协议互通。(2)分析了现有网络瞬时故障处理技术存在的问题,提出基于备份链路的单链路故障恢复机制,它综合考虑故障前后节点最短路径树的区别与联系,而不是仅专注于故障前或故障后的网络拓扑,为故障链路寻找备份链路,建立无环备份路径。该算法具有100%网络覆盖率、较低的算法复杂度,且改进了偏转路由对网络双向链路的限制和故障迟缓路由算法对硬件的依赖性,仿真结果证明它具有良好的性能。(3)为了解决网络瞬时单节点故障问题,在BLSL算法基础上通过分析故障节点孩子子树之间以及与节点其他子树之间的关联,建立备份链路连接被分离的各个子树从而构建备份最短路径树获得备份路由表,并提出一种受限的松散源路由数据传输模式,它不仅保证备份路径中无路由环路,且减少了备份路由表条目。仿真结果证明该算法的备份路径与最优路径相差不多。(4)将解决多链路故障的多拓扑技术归结为求解最小覆盖集问题,本文借鉴图论中图的最小生成树及其余树的相关知识提出了拓扑子图路由算法,每个拓扑子图保护部分链路,所有拓扑子图保护全部链路。该算法获得与余树中连续孤立节点个数相关的拓扑子图个数,解决了现有多拓扑技术无法理论证明备份拓扑个数的问题,仿真结果证明拓扑子图备份路径平均长度较小。更多还原

【Abstract】 Internet has seen tremendous growth in the past decade with the introduction of new science and technology and the emergence of new services, so that service providers find out that more and more traffics in the Internet have the potential to bring more profits. But the failures happening everywhere and every time even in the robust network may make the service unavailable and performance digressive. Network survivability is popular among service providers to guarantee Qos. The main research content of survivability is a network how to complete the service on time dynamically in face of challenges such as failure and attack. As the pure IP network is exactly the component in real network, the IP network survivability becomes hot because of its lower cost、fine-grained、and longer time to protect. This dissertation don’t take Network Security into account.There are two directions: Reactive and Proactive based on the establish time of backup-path. But Reactive Policy wastes so much time on failure recovery time which can’t satisfy real-time service Qos requirement such as VOIP. Therefore this dissertation focuses on the Proactive IP network survivability for routing flap suppression mechanism handling frequent failure、network single transient failure recovery mechanism and multi-link-failure solution based on minimum cover set. The main contributions are as follow:(1)The causes of routing flap in real backbone network are analyzed. And the relationship of link flap and routing flap is given based on the determinants at every phases of routing convergence. The suppression of routing flap transfers into the suppression of link flap. A localized approach is proposed to suppress the routing flap through dynamically tuning the Hello timer. Simulation results show that this mechanism can achieve better performance in eliminating routing flap and consume much less computation resources at the same time. And a small network is built to verify it can interoperate with the existing routing protocol.(2)After analysis of the existing failure recovery algorithms handling single failure, a single-link failure recovery mechanism based on backup-link is proposed. It considers about the differences and the relations between SPF of the node failure or not, and picks up backup-link to build loop-free backup-path. This mechanism not only has 100% network coverage and a lower algorithm complexity, but also improves the two-way link limitation of Defection Routing and the dependence of Failure Insensitive on hardware. Routing. Experiments prove the algorithm has better performance.(3) In order to handle the single node failure problem, backup links are used to connect the depart sub-trees of failure node to the other sub-tree of the root node SPF after the analysis of their relationship based on BLSL algorithm. Loosely constrained routing is proposed to transfer data through routers in the backbone network. It is the way to keep loop-free routing in backup-path, and decreases the number of routing table entry at the same time. Simulation results prove that the backup path of this algorithm is almost the same as the shortest path and better than the others.(4)Multi-topology technology which is used to solve the problem of multi-failures is the method to solve minimum cover set problem. Sub-topology routing algorithm is proposed based on the knowledge of Graph Theory about minimum spanning tree and its extended tree. Every sub-topology protects some links which don’t belong to it, all sub-topology keep all links safe. The number of sub-topology in a network is depended on the number of the continuous isolated nodes in extended tree which can not prove by the other multi-topology technologies. And experiments certificate that the average backup path length in sub-topology is smaller and it has a lower the packet loss rate.更多还原