Study On The Predictability For Inter-Domain Routing

The Border Gateway Protocol (BGP) is the de facto exterior gateway protocol deployed on the Internet. Inside a autonomous domain, network managers can get the router topology and control the route. At the interdomain level on the other hand, the approach used in the Internet is the one of a distributed control of the routing information. Each autonomous system(AS) use border gateway protocol(BGP) to exchange routing information with other ASes. A key feature of BGP is that it allows each network manager to define its routing policies. An AS may advertise all its routes or a fraction of its routes to neighboring ASes. It seems hardly impossible to organize (inter-)domain routing in a way which accommodates all three requirements:world-wide reachability, highly-configurable policies to enforce economic goals and mechanisms for quality assurance. A better understanding of what is going on in the routing layer, is therefore indispensable. However, large-scale dynamic network running on the external BGP (eBGP), internal BGP (iBGP), interior gateway protocol IGP interactions between very complex, it does not really understand。Existing simulation topology is a router with a single representation of each AS, Peer AS settings are based on the edge of AS connectivity graph, without taking into account the internal BGP and IGP Interior Gateway Protocol, as well as a number between the two AS the impact of the export point. Although this resulted in a simulated network topology is to rely on real data, but the results of reproduction and the actual routing does not match. Based on the NSF project "Study On InterDomain Routing Stability and Managebility", this dissertation discussed several problem of inter-domain routing prediction and simulation.In the introduction part of the dissertation, we summarize the present situation of the research of Internet inter-domain topology and simulation, introduce the importance of inter-domain routing prediction and simulation. We simply introduce BGP common attributes and BGP process, analyze the model of routing prediction and simulation.We detailedly analyze the model of the AS topology in the Internet and the construction of real AS topology. We analyze the characteristic of AS hierarchical structure, emphasize the characteristic of the structure of top tier AS and the path of interdomain route. Using the path information included in BGP routing table, we infer the tier of each AS according to the structure characteristic of different tier AS. We introduce the commercial relationships between ASes on classification, summarize the recent research on routing policies and AS relationships, introduce the general rules to set routing policies in accordance with AS relationships. We propose an approach to infer AS relationship from several BGP routing tables. According to the characteristic of AS PATH structure in a Tier-1 AS’s routing table, we use several Tier-1 AS’s routing tables to verify the inferred AS relationship, use other routing tables to verify assistantly. Compared with other similar algorithm, we do not use experiential parameter and the result has higher correct ratio.We studied multi-exports of ISP. First of all, builded the model of relationship between AS. We construct a technique to register the changing of path attribute, and propose an algorithms to detect inconsistent routes using routing and configuration data from an AS’s border routers base on rib-in-policy-history.We achieve the algorithm based on a simulated ISP topology to use of c-bgp simulation tools, the results showed that the algorithm is feasible. Second, We have also examined the sub-optimal routing problem a number of multi-exports, we propose an algorithm to checking for optimal egress points in iBGP routing of route reflection graph. Our simulations with C-BGP show that topology exists for more than 30% of suboptimal route choices.We studied the impact of Domain routing protocols and routing interactions. respectively, discussed the iBGP full-mash with MED attributes and reflection on the impact of routing, and proposed the prediction algorithm based on MED attribute or reflection. The results by topology modeling and simulation showed that the IGP, iBGP domain routing protocols, such as the impact of the choice of inter-domain routing results. Simulation of reality network studied. We studied the problem of how to inferred the initial model of Internet from the public data, given the modeling method of to inferred the reality network simulation from initial model. We improved the Per-prefix heuristics based on summary of simulation in the current popular, models consider the evolution of business relationships between AS impact. Through simulation experiments, represents the reality of inter-domain network topology, the results show that the improved test Per-prefix on Akamai-Sample match observed in the number of paths to increase significantly.