【作者】 赵锋；

【导师】 卢锡城；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2007， 博士

【摘要】 网络的广泛应用对网络性能提出了越来越高的要求。路由系统优化是提高网络性能的重要途径。然而,大规模自治系统的复杂性使得路由系统优化面临许多挑战。本文面向大规模自治系统,对路由系统优化的关键问题展开研究。在综合考虑路由系统和数据平面及管理平面之间的关系、以及路由系统内的域内路由协议和域问路由协议的相互影响的基础上,本文采用基于图论及概率论的分析手段和模拟仿真方法,重点研究了IBGP拓扑的可视性问题、路由系统运行参数优化问题和IBGP拓扑的健壮性问题,提出了相应的方法和机制来提高网络性能。大规模自治系统通常采用路由反射机制。然而路由反射拓扑的引入可能会带来可视性问题。现有的完全可视的IBGP拓扑构建算法BGPSep存在扩展性问题。因此为解决IBGP拓扑的扩展性和完全可视性问题,本文提出了两个IBGP拓扑构建算法:BGPSep_D和BGPSep_S。BGPSep_D算法利用了当前一些自治系统的拓扑存在割边链路这种特性,首先考虑满足某些度数约束的顶点,然后利用割集特性进行IBGP拓扑的构建。本文证明了该算法生成的IBGP拓扑具有完全可视、无环转发以及针对IGP故障的健壮性等属性。通过使用真实的骨干网拓扑进行模拟实验,结果表明其生成的IBGP拓扑的最大度可以减少9%-50%,具有更好的扩展性。BGPSep_D算法所生成的IBGP拓扑和自治系统的IGP拓扑特性相关,因而对某些自治系统,BGPSep_D算法构建的IBGP拓扑的最大度可能仍然比较大。针对该问题,本文综合考虑了IGP拓扑特性以及域内的最短路径路由特性,借鉴割集思想,提出了BGPSep_S算法。和BGPSep相比,BGPSep_S生成的IBGP拓扑的最大度可以减少27%-68%,具有很好的扩展性,并且可以保证完全可视性和无环转发属性。路由系统运行参数的设置直接影响路由系统的收敛性、稳定性和健壮性,进而影响网络的数据平面转发性能。理解路由系统运行参数的不同设置对网络的影响是优化这些参数的基础。因此本文将故障对网络的影响进行建模分析。首先讨论了IBGP会话的可靠性,为分析故障对域间流量的影响以及路由系统的健壮性奠定基础。然后采用概率论方法量化了故障发生时的流量损失及转移时间和主要的运行参数之间的关系,并通过模拟方法进行了验证说明,给出了优化建议。根据量化分析结果,本文指出在进行协议参数的优化时应该考虑网络拓扑特性和流量特性。并为解决运行参数优化的冲突,提出了一个潜在利润损失模型,应用该模型给出某些协议运行参数的优化建议。对于一个大规模自治系统,可选的IBGP拓扑结构非常多。在不同的IBGP拓扑下,同样的故障对路由或流量的影响往往并不一样。因此,可通过规划IBGP拓扑来控制故障对网络的影响。控制平面的微小变化可能会对数据平面产生巨大的影响,因此在构建IBGP拓扑时应该考虑对数据平面的影响。但是现有度量IBGP拓扑健壮性的所有测度都没有从数据平面进行考虑,因而本文提出了一个新的测度:流量损移率。为计算流量损移率,本文提出了基于IGP路由恢复时间分布的IBGP会话失败概率计算方法。基于流量损移率测度,本文定义了路由反射器可冗余及会话约束的路由反射拓扑设计问题,分析了问题的复杂度,并给出了路由反射器冗余度和流量损移率的关系,讨论了该问题的优化下界。对每一个簇内都有一个冗余路由反射器的拓扑设计问题给出了可解条件。通过采用真实网络拓扑的路由和流量数据进行实验,结果表明,基于流量损移率测度进行IBGP拓扑规划可以有效降低故障对网络流量的影响。本文的研究成果对于设计和实现高性能路由器以及运行和管理高性能网络具有很好的理论意义和实践意义,对新型网络体系结构和路由协议的研究具有较大的参考价值。更多还原

【Abstract】 Increasing demands are being placed on the performance of IP networks. Routing optimization is an efficient and effective way to improve the network performance. However, it is challenging to optimize routing in large scale autonomous systems (ASes) due to the complexity of such systems.This dissertation investigates some essential problems of routing optimization in large scale autonomous systems, especially the problems of IBGP visibility, routing protocols running parameters optimization and IBGP robustness. In consideration of the relationship between the routing system, the data plane and the management plane, as well as the complex interaction between the internal gateway protocol and the border gateway protocol, we present some new algorithms and mechanisms to improve the network performance by using graph theory, probability theory and simulation methods.Route reflection is widely used as an alternative to full mesh IBGP sessions inside an autonomous system for scalability reason. However, it may cause the complete visibility problem. Although the IBGP configuration generated by the existing algorithm BGPSep guarantees the property of complete visibility, BGPSep does not reduce the number of IBGP sessions of the top level route reflectors. To solve the scalability and visibility problems of IBGP networks, we present two algorithms, namely BGPSepD and BGPSepS, for constructing IBGP configurations. In the observation that a lot of pendant vertexes exist in the IGP topologies of some large ASes, we conditionally remove some vertexes from the IGP graph. By applying the BGPSep algorithm to the remaining graph, we obtain the BGPSep_D algorithm. Then we prove that IBGP topologies generated by BGPSep_D hold the properties of complete visibility, loop-free forwarding and robustness to IGP failures. The performance of BGPSep_D is evaluated on several real-world backbone topologies. Experimental results show that the maximum degrees of the IBGP topologies generated by BGPSepD for these backbone IGP topologies can be reduced by about 9%-50%. However, the scalability of IBGP topologies produced by BGPSep_D depends on the characteristics of IGP topologies, hence not satisfactory in some ASes. To further improve the scalability of IBGP topologies, we present another IBGP topology construction algorithm called BGPSep_S, by taking into consideration the vertexes degrees, the vertexes separators and the shortest paths between vertexes in the underlying IGP graph. We also prove that BGPSep_S guarantees the properties of complete visibility and loop-free forwarding in normal situations. The experiments show that the maximum degrees of the IBGP topologies generated by BGPSep_S for several real-world backbone topologies can be reduced by 27%-68%, compared with full mesh and BGPSep. Different settings of routing protocols running parameters have different impact on the routing convergence, routing stability and robustness. An insight into their effects on the networks is the premise of appropriate setting of them. This dissertation models the effects of failures on networks. We discuss the reliability of IBGP sessions for analyzing how failures affect interdomain traffic. Then based on probability theory, we give quantitative relations between the time of traffic loss/shift and the influential factors: the main tunable parameters and the failure duration. The analysis results are validated by simulations. The results of analysis and simulations demonstrate that the characteristics of both IGP topologies and traffic should be considered in the selection of parameter settings. To solve configuration conflict, a potential profit loss model is presented and some suggestions on the configuration are given.There may be lots of IBGP topologies available for a large scale autonomous system. Different IBGP topologies may have different impact on network performance. Robust IBGP networks are very important to the stability and reliability of Internet. Although several metrics have been presented to measure the robustness of IBGP networks, they only considered the impact of route reflection networks on the control plane. A small number of routing changes may cause large traffic shifts. A robust network should have low sensitivity to traffic load variations. So we propose a new metric called TDR (Traffic Diversion Rate) to measure the impact of route reflection networks on the data plane. A new approach is presented to calculate the failure probability of IBGP sessions, a parameter in TDR, based on the probability distribution of IGP routing recovery time. With this TDR metric, we investigate the optimization problem of finding the most robust IBGP route reflection topologies, in which a cluster is allowed to have one or more redundant route reflectors and the maximum number of IBGP sessions that a router can have is limited. We discuss the relationship between the route reflectors redundancy and the robustness of topologies, and give the lower bound of the optimization. In the case that there is a redundant route reflector within each cluster, we give the solvability conditions for the optimization problem and show that the problem in general is NP-hard. Simulations show that with the optimal route reflection topology that minimizes TDR, the network loses or shifts much less traffic than with the optimal route reflection topologies found according to other metrics.In summary, the performance of IP networks can be improved by optimizing IBGP topologies and routing protocols running parameters. Our research results are valuable to design high performance routers and to run high performance networks. They are also meaningful to the research on new network architectures and new routing protocols.更多还原