Inter-domain Multipath Routing Algorithm And Its Application

The Internet consists of tens of thousands of independent Autonomous Systems (AS). Each AS is independently administered by a single authority, such as a university, a company, or a government agency. Accordingly, the routing in the Internet can be divided into two parts:intra-domain routing, which deals with the routing inside one AS; and inter-domain routing, which deals with the routing among different ASes. In inter-domain routing, different authorities may have different and sometimes competing business interests, which have a profound impact on inter-domain routing practices. With the increasing of the size of the Internet and the popularity of new applications, ASes need inter-domain routing with high reliability and flexibility. However, today’s inter-domain routing protocol (BGP) is not flexible enough to satisfy diverse performance requirements as it has each router selected and advertised a single route for each prefix.As an effective solution, multipath inter-domain routing can provide high reliability and flexibility routing by developing the path diversity of the Internet. The research about multipath inter-domain routing mainly focuses on the measurement and analysis of the path diversity, the implementation of multipath inter-domain routing based on BGP and the design of new routing architecture.This dissertation, based on measurement and analysis of the path diversity, puts forward a Local-topology Multipath Inter-domain Routing protocol called LTMIR. The main contributions of this dissertation include:Firstly, we design the inter-domain path characteristics analysis model and develop the experimental framework, and analyse experimental results based on real Internet topology data, such as the path diversity in local topology, which can support the design of multipath inter-domain routing protocol. Secondly, we put forward LTMIR which implements multipath routing by developing the path diversity in local topology, besides we design and develop a Click-based Multipath Routing Simulator called MRS to analyze the forwarding performance and path diversity of LTMIR. Finally, we conclude this dissertation and give some suggestions about future work.