| Internet is now a critical component of our information infrastructure. In the last years, the number of and the diversity of the applications supported in the Internet have remarkably increased. The growth has increased the demands on higher reliability and robustness of the underlying routing protocols. The reliability of the Internet depends on the reaction time necessary for the underlying routing protocol finding the backup paths in case of failures. However, due to scalability and stability concern, current Internet routing protocols select a single best route to each destination by default, such as OSPF and BGP. Single path routing does not provide fault tolerance against node or link failures. The delay in reacting or recovering from network failures such as link failures can lead to routing disruptions, such as transient routing loops or transient routing outages. Border Gateway Protocol (BGP) is the dominant inter-domain routing protocol. However, many studies show that the poor reliability of BGP is one of the root causes for the fragile Internet.BGP is also widely known for some problems in terms of suboptimal path use, insufficient support for load balancing and poor security because it is a single-path routing protocol. Inter-domain multipath routing explores the underlying network AS-level path diversity to improve the Internet's reliability, performance and resource utilization. Thus, inter-domain multipath routing is considered as a useful and necessary method to address the problems faced by BGP. Therefore, the main research area for this dissertation is inter-domain multipath routing. Based on a survey of the current proposals on inter-domain multipath routing protocols, several protocols and solutions are proposed to guarantee AS-path diversity, network stability, protocol scalability and security. Our major contributions are summarized as follows:1, we survey the current inter-domain routing protocols and classify these protocols into three categories: protocols on BGP-based single path announcement, protocols on BGP-based multiple path announcement and new Internet routing architecture based protocols. Furthermore, several key metrics are presented to compare the different inter-domain multipath routing protocols. Meanwhile, we point out three challenges to implement inter-domain multipath routing, which are multiple paths discovery, alternative path selection and forwarding packets.2, we propose a failure-hiding based interdomain multipath routing protocol, called YAMR (Yet Another Multipath Routing). YAMR is composed of two key components: path selection technique and information hiding. Path selection technique provides YAMR multiple paths with provable guarantee for any single link failure while information hiding lets YAMR dramatically improves the routing efficiency by controlling the path failure information in a local area. 3, we propose a regional multipath approach, Regional Multipath Inter-domain Routing (RMI), where multiple paths are only allowed to be propagated within a well-defined range. With multipath routing in a region, we enable inter-domain routing with rich path diversity and improved security, and no longer have to sacrifice scalability. We show how to propagate multiple paths based on the region by theoretical analysis and by extensive simulations. Our simulations show that the number of messages generated using this approach and convergence delay is much less than BGP and BGP with full multipath advertisement.4, we present a novel approach, Multipath Dependency graph (MD-graph), to examine routing policy conflicts under multipath environment. The MD-graph allows us to identify the dependency between multiple paths. Most important, a MD-graph can be used to represent more flexible ranking functions than absolute preferences. Based on MD-graph, we evaluate the dependency of the graph. The result of the dependency analysis can be used to determine if a cyclic dependency or a multipath oscillation exists. Finally, we identify the sufficient conditions for the convergence of multipath routing, which can be used as configuration guidelines for multipath selection and dissemination.5, we propose a multipath advertisement based detection method for prefix hijacking, called SMD (Self-monitoring Detection), to analyze and compare different multipath protocols with various types of multipath advertisements. Most multipath routing proposals focus only on disseminating additional routes to increase the reliability of the Internet, and do not concern the security issues that the additional routes bring to the table. Based on multipath dissemination, SMD utilizes the loopback paths to detect the prefix hijacking. We systematically analyze the effectiveness of two types of, advertising the most disjoint path advertisement or the second best path advertisement with the best path, on detecting prefix hijacking. Our analysis and measurement results show that advertising the second best route with the best route is an efficient and effective way to disseminate multipath information with respect to inter-domain routing security.
|
PDF Full Text Request