Study And Implementation On Test Of Conflicting BGP Routing Policies

The Internet consists of rapidly increasing number of hosts interconnected by constantly evolving networks of links and routes. In term of management, it is composed of thousands of Autonomous Systems (ASes) operated by many different administrative domains such as Internet Service Providers (ISPs), companies and universities. Since two ISPs might merge into one and each administrative domain can operate one or several ASes, so dynamic management structure come into being. A pair of ASes interconnect via dedicated links and/or public Network Access Points (NAPs) and routing between ASes is determined by inter-domain routing protocol such as Border Gateway Protocol (BGP). BGP allows each AS to choose its own administrative policy in selecting the best route, and announcing and accepting routes.Previous work on Internet routing architecture indicates that conflicting BGP routing policies would cause routing oscillation, viz. an network layer reachability information appears and disappears repeatedly in a routing table, that will directly or indirectly affect the capability of Internet. So study on BGP routing stability has important significance to the development of Internet. The main purpose of this thesis is to study methods for test of conflicting BGP routing policies and put forward a system that can test some categories of conflicting policies in BGP routing system.In this thesis, BGP is analyzed in detail and a BGP abstract model is set up. Based on the model and BGFs selective export rule, heuristic algorithms that can infer AS relationships from BGP routing tables are presented, then a method that can be used to detect conflicts between routing policies based on relationships of ASes is put forward. Also, the thesis converts the question of testing of conflicting BGP routing policies into the question of testing the alive lock of routing network algebra expressions according to relative knowledge of routing network algebra, and a corresponding algorithm is implemented. Moreover, another algorithm for testing conflicting routing policies based on topological sorting and counter-topological sorting method is introduced.Related experiment data is also presented in the thesis. SSFnet that is an emulational tool is adopted during the test of conflicting routing policy testing system. BGP routing system examples with conflicting policies, witch are built by SSFNet, are used in the test experiments, and the results of these experiments are consistent with those are expected.Both theory and experiments show that the algorithms based on AS relationship, routing network algebra and topological sorting can discover different categories of conflicting BGP...