Research On Self-Organization Characteristics And Essential Problems Of Inter-Domain Routing System

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.