Research On Scalability Of Inter-Domain Routing In Internet

After developing more than forty years, Internet is growing rapidly. Now, Internet is a world-wide super information system, related with everything in people’s working and life. With the increasing size of Internet, Internet routing scalability becomes one of the hot topics in the Internet field. Because some factors like the overloading of the IP address semantics, the unreasonable ad-dress allocation, more and more specific prefixes inject into the Interne core, which leads to rapid expansion of the global routing table size. Recently, In-ternet routing is facing serious scalability problem which is an issue in two aspects:rapid expansion of the global routing table size and the increasing rate of BGP updates. The "super-linear" increase of the global routing table and the increasing rate of routing updates will lead that the scalability of Internet archi-tecture and routing mechanisms face big challenges. The scalability problem of routing is an burning issue in the Internet field.The ID/Locator split based scalable routing architecture solves the over-loading semantics of IP address. However, the evaluation methods of the s-calability of these novel routing architectures need deep research. The global deployed hierarchical addressing (HA) can support the routing scalability. But it may bring excessive prefix problem. Thus, research on the deployment solu-tions of HA which could not only assure the routing scalability, but also solve the excessive prefix problem, is significant. BGP churn is another aspect of the routing scalability problem. In order to limit the rate of BGP update, Minimum Route Advertisement Interval (MRAI) is proposed. This mechanism is one of the effective ways in reducing the rate of BGP updates. However, it may delay the convergence time of routing system.To speed up the BGP convergence, the default value (30s) of MRAI should be reduced. How to reduce MRAI in the super-scale Internet is an open issue. The diverse MRAI timer brought by the incremental deployment of updating MRAI may lead to an devastating impact on the BGP convergence time and BGP churn. Thus, research on the setting of MRAI is important. Based on the above mentioned problems which still exist in the research on the scalability of Internet routing, this thesis studied the scalability of Internet inter-domain routing, having the following research results:1. To propose a method on evaluating the scalability of the ID/Locator s-plit based routing solutions. Through the analysis and abstraction of the ID/Locator split based routing solutions, a general model of these solu-tions is proposed. The prefix allocation and routing advertisement in In-ternet routing system is modeling. Based on this model, the analysis and evaluation method on the routing scalability of host-based and network-based routing solution are proposed. The results show that the routing s-calability of the ID/Locator split based routing solutions is far better than the routing scalability of the current Internet.2. For seeking the solutions to both the routing scalability problem and the excessive prefix problem, analyze the impact on the prefixes amount and routing table size of ASes in the different deployments of hierarchical addressing(HA). This chapter theoretically analyzes arbitrary AS’s prefix amount and routing table size in different HA deployments. Modeling on the prefix allocation and routing advertisement, this chapter mathemati-cally proves that with the lower position that HA starts to deploy, the less prefixes arbitrary AS is allocated. In addition, we also conclude that if the starting position of HA’s deployment is getting lower, The routing table sizes of ASes in HA zone are monotonically decreasing, while the routing table size of ASes in non-HA zone are monotonically increasing. In order to prove the conclusion of the analysis and reference to the routing scal-ability and addressing in future Internet, the prefix allocation and routing advertisement process in different HA deployments is simulated based on real Internet topology and the prefixes amount and routing table size of ASes in these deployments are evaluated. Comparing the results and the practical data in Internet, the suitable deployment of HA for current Inter-net topology are obtained. These deployment methods could effectively solve the excessive prefix problem and improve the routing scalability.3. Incremental deployment is an effective way to update MRAIs over the world-wide Internet. However, the diverse MRAIs could bring devas-tating impact on the BGP convergence time and rate of BGP updates. Choose the tier-1 ASes which have the greatest influence and update M-RAI setting in these ASes. Analyze the impact of this deployment on the convergence time and BGP churn of Internet routing system. Based on a timed BGP model, analyze the impact of this deployment oh the conver-gence process. The results of the experiment show that, the deployment which is reducing the MRAI values of the tier-1 ASes, is a reasonable de-ployment to reduce MRAI valude in world-wide Internet for speeding up the convergence process. This deployment method could make the same effort as the deployment of updating the MRAI synchronously in all nodes of Internet on the metrics of convergence time and BGP update amount. In order to reference to the design of future Internet, analyze the impacts of this deployment on the BGP convergence process based on the evolu-tion of Internet topology. The results show that this deployment is still a suitable deployments in future Internet topology. 4. Propose a setting method of MRAI timer, MRAI-MNMS(MRAI-MoreNearby More Smaller). This method could avoid the negative impacts which may be brought by the diverse MRAI value without the cooperation of ASes. Based on BGP model, analyze the negative impact on the BGP convergence process in the scenario of setting the bigger MRAI in the nodes which is nearer to the destination. The experiment results show that, MRAI-MNMS could reduce BGP update amount and don’t increase BGP convergence time. This setting method also support incremental deployment. Based on different network condition, we propose different deployments of MRAI-MNMS.