【作者】 赵金晶；

【导师】 卢锡城；

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

【摘要】 基于BGP(Border Gateway Protocol)的域间路由系统作为Internet的核心设施,不但是传递网络可达信息的基本机制、自治系统AS(Autonomous System)互连的纽带和ISP(Internet Service Provider)实现策略控制的主要手段,而且对Internet的演化起着关键作用。目前域间路由系统在扩展性、收敛性、稳定性、健壮性和安全性等方面存在诸多问题,对Internet的性能和安全造成不良影响,并会制约新一代互联网的健康发展。已有的研究工作大都基于传统路由系统的严格层次模型,采用静态的基于图论的方法,没有很好地把握域间路由系统的拓扑规律和动态行为模型,域间路由系统的许多问题没有得到有效地解决。随着Internet规模的扩展和商业化进程的加速,域间路由系统规模膨胀、结构密集、互联关系复杂、路由策略多样,表现出显著的开放复杂巨系统特征。本文基于域间路由系统自组织特性,利用复杂系统理论和ISP之间交互的自组织规律,提出改善域间路由系统性能以及实现域间组播部署的新方法和新机制,为构造安全、可信、可控、可管的新一代互联网,促进新一代网络的持续健康发展做出贡献。本文主要从以下五个方面进行了深入研究:●域间路由系统自组织特性分析域间路由系统和Internet一样是一个复杂巨系统,自组织理论是当前对于复杂系统研究的重要成果,是研究复杂系统的有效工具。本文从自组织特性的角度分析了域间路由系统的内在规律和外在表现,并且评价了改善域间路由系统的扩展性、收敛性、稳定性和安全性的各种方法。在对域间路由系统发展趋势进行剖析的基础上,给出了利用自组织特性解决域间路由系统问题的指导原则和几种可行的方法。●域间路由系统动态演化过程研究域间路由系统是以AS为节点构成的自组织系统。本文研究了Internet域间路由系统中各个AS在其成长消亡过程中需要考虑的各种影响因素,系统地阐述了AS之间商业关系的产生和变化,基于复杂系统理论建立了Internet域间路由系统的动态演化模型—CMV-HOT。通过对模型的研究,分析了多宿主、商业关系等因素对域间路由系统拓扑及特性的影响。●Internet域间路由协议BGP收敛趋势的预测和分析路由表的快速增长增加了路由器处理路由信息的时延和路由信息的扩散时间,网络规模的膨胀加大了路由信息的扩散范围,从而影响BGP协议的收敛延迟。深入研究域间路由系统的基本理论,以确定域间路由系统扩展性和收敛性的基本性能约束关系成为当务之急。本文考虑了对收敛时间产生影响的各种因素,给出了更精确的BGP收敛时间上界,进而根据域间路由系统的幂律特性和BGP协议标准分析了各个因素的变化趋势,在此基础上,对BGP的收敛时间的变化趋势进行了预测。理论分析和模拟试验显示BGP的收敛时间最终会受到CPU处理效率、AS度数以及MRAI(Minimum Route Advertisement Interval)的影响,而传输路径长度以及链路延迟反而会使收敛时间越来越小。因此网络规模的扩大和应用负载的增加带给域间路由系统最重要的影响就是对路由器处理能力的挑战。●BGP收敛性及其对网络性能影响的定量分析从Internet的结构特征入手,分析了BGP的收敛特性与域间路由系统的幂律特性及层次性之间的关系。根据幂律特性以及AS间商业关系的层次性特点建立了域间路由系统幂律-层次模型,将整个域间路由系统分为核心层、转发层和边缘层,在此基础上分析了不同层次上的各类收敛事件的收敛参数与网络结构的联系。理论分析和模拟试验显示核心层的收敛时间小于转发层,而影响的AS数目和转发路径的范围却大于转发层,并且网络的幂律特性对BGP收敛性有很大的影响。利用这个规律,对BGP的收敛过程进行了改进,提出“Best Up”收敛模式,有效地缩短了网络的收敛过程。●域间组播的计费问题研究IP组播广泛部署的困难在于合理的跨域部署和有效的计费机制,这种困难在很大程度上源于ISP之间利益的差异和行为协调的复杂性。本文基于自组织理论,从ISP之间的关系和AS结构着手,探求域间组播的合理的结构模型和RP(汇聚点)部署的经济学方法。实用的收费机制是域间组播部署的关键。本文将Internet看作一个生态系统,采用博弈论的方法,提出了有效的收费机制。从不同参与者的动机出发,系统地讨论了现有的IP组播服务模型及其收费机制。针对不同的实际应用场景,提出ICP-USER、ICP-ISP和ICP-ISP-USER三种模型。对每个模型的适用环境、解析方法以及算法的复杂性进行了全面讨论。综上所述,本文的工作针对域间路由系统中亟待解决的关键问题提出了有效的解决方案,对于推进自组织系统的理论研究和实用化具有一定的理论意义和应用价值。更多还原

【Abstract】 The inter-domain routing system based on the BGP (Border Gateway Protocol) protocol is a kernel establishment in the Internet. It is not only the basic mechanism of exchanging the reachable information, but also the key way to inter-connect the ASs (autonomous systems) and establish the policy control in ISPs (Internet Service Providers). It is very important in the Internet evolution process. Nowadays, there are a lot of problems in the expansibility, convergency, stability, robustness and security of the inter-domain routing system, and which blight the capability and security of the whole Internet greatly and restrain the development of the next generation Internet.The existing research, based on the strict hierarchical structure in the traditional networks and using the static graph theory, could not grasp the topology disciplines and the dynamic behavior of the inter-domain system comprehensively. Therefore, many problems couldn’t be solved perfectly by these methods. With the rapid development of the size and commercial process in the Internet, the inter-domain routing system is becoming more expanded in the scale, more complex in the interrelation, and much denser in the structure. All of these mean that the inter-domain routing system is an open complex giant system; the interactions between ISPs expose a greatly self-organized property. And this trend is the basic rule of the inter-domain routing system, which would become more and more obvious in the next generation network. Studying and designing a new routing system based on the self-organization system theory is an efficient way to solve all kinds of the performance and security problems in the routing system.In this dissertation, we provide some new techniques and mechanisms to improve the performance of the inter-domain routing system and implement the inter-domain multicasting using the complex system theory and the self-organized rules in ISPs based on the self-organization property of the inter-domain routing system itself. Our goal is to do some contribution to the continuance and healthy development of the new generation network and the process of constructing a more reliable, more faithful, more controllable and more manageable internet.Our work expands the research in five aspects as follows:Analysis on the self-organization property of the inter-domain routing systemThe inter-domain routing system is a complex huge system just as the Internet. The self-organization theory is an efficient tool to deal with the complex system. We abstract the internal rules and external behavior of the inter-domain routing system from the view of the self-organization property and evaluate the promotion methods for the expansibility, convergency, stability, robustness and security for BGP. Based on the prediction of the trend of the inter-domain routing system, several solutions and guidance are presented by using its self-organization property.Research on the dynamic evolution process of the inter-domain routing systemThe inter-domain routing system is a self-organized system consisted of autonomous systems. Our research study all kinds of factors that the AS should consider during its process from its growth to death, integrally explore the commercial relations between ASs, and factually build a dynamic evolution model of the inter-domain routing system based on the complex system theory, named CMV-HOT. Through the analysis of the evolution model, the influence of the multi-homing and commercial relations to the inter-domain routing system is studied.Quantitative prediction of the BGP convergence timeThe rapid increment of the routing table size causes the routing information processing time and propagating time on the network much longer. And the inflating of the Internet makes the expanding range and paths of the routing information larger. So it is emergent to confirm the basic restriction between the expansibility of the inter-domain routing system and the performance of the BGP convergence.We present a new BGP convergence model and analyze the convergence delay bounds of BGP. The development trends of all factors influencing the convergence time are forecasted based on the Power-Law of AS-level Internet topology and the BGP protocol standards. Furthermore, we predict what the BGP convergence delay will be. The results show that BGP convergence time will be influenced by processing efficiency of CPU, degree of ASs and value of MRAI greatly, but the influence of path length and link delay will be reduced.The quantitative analysis of the influence of BGP convergence to the network performanceThe physical Internet is one of the most common examples of complex networks in the real society. Its growing structure is the result of competitive and cooperative processes without any centralized control in determining the self-organized evolution of the system. We analyze the relationship between BGP convergence and the characteristics of the Internet. The Internet is classified into three hierarchies based on the Power-Law and commercial relations of autonomous systems. The relation of the network topology and the BGP convergence performance is presented for all sorts of convergence events in different layers. The result shows that the Power-Law nature of network influences the BGP convergence greatly. So we present a new approach to improve BGP convergence based on power- law, called "Best Up", which behaves better than normal convergence mode in the experiments.The research on the pricing problem of the inter-domain multicastA practical pricing mechanism is the foundation for the deploying of IP multicast in the inter-domain Internet. However, the different kind of profit and the behavior of each AS make this problem complex. The IP multicast service model and its pricing mechanism are discussed in this dissertation by considering the motivations of different partners in the process. Three models are proposed for all applications in the real environments. They are ICP-USER model, ICP-ISP model and ICP-ISP-USER model respectively. In each model, the applied scenarios, resolving method and the complexity of algorithm are illustrated. Here, the Internet is considered as an ecosystem. So we give a general discussion on the practical pricing mechanism based on the game theory of the complex system for the stability of the economic development in the Internet.In summary, our work presents solutions to several key problems of the inter-domain routing system, and has academic value and practical value for advancing the self-organized system theory and its practicability.更多还原