Research On Routing Metric Based Intra-Domain Multipath Routing

With the rapid development of the Internet, it has become the world’s largest communications infrastructure, and has played an important role in people’s daily life. The current deployed intra-domain routing protocol adopt only shortest paths and best e?ort to forward packets. However, as a variety of new applications are emerging, for example,online stock trading, streaming media and online games, which require stringent network service availability and reliability. Therefore, the current intra-domain routing protocol deployed in the Internet cannot meet the requirements of these new applications. As an e?ective solution, multipath routing computes multiple paths for source-destination pairs, and provides not only redundant backups, but also other features such as aggregated bandwidth, high network availability and reliability. Therefore, multipath routing can e?ectively improve the quality of service of the network. The main contributions of this dissertation are summarized as follows:1. Proposing an intra-domain multipath routing model based on the routing metric algebra, which provide a framework to solve the multipath routing problem. The routing metric algebra is captured in structures of the form(S, ?, w, ⊕,). S is the set of paths;? is the path concatenation operator, where if the last node of path p is the first node of path q, then p ? q denotes the concatenation of p and q; w is a function that maps a path to its weight; ⊕ is a binary operator for path weight; is an order relation defined on the set of path weights.2. Based on the routing metric algebra, we further propose two e?cient distributed algorithms to calculate multiple routes for each destination in a router within a domain.Both of the algorithms are run locally and independently on each router, without exchanging messages other than the basic link states. Their loop-freeness and high e?ciency are formally proved.3. Both of the multipath routing algorithms can be partially deployed on only a portion of nodes. Therefore, we propose three incremental deployment algorithms to select the most proper set of nodes to be deployed. The experiment results show that genetic algorithm has the highest performance among all the algorithms. We can see that when a deployment on only 40% nodes already improve the network availability clearly.4.Proposing a novel link protection scheme, Hybrid Link Protection(HLP), to achieve failure resilient routing. HLP is implemented in two stages. Stage one provides Multiple Next-hop Protection(MNP), where only one single Shortest Path Tree(SPT) needs to be constructed on each node to find multiple next hops for any destination. Stage two provides Backup Path Protection(BPP). In the first step, each node in the network independently identifies its key links, which are links that cannot be protected by MNP. Then, selecting a minimum number of links need to be protected according to its contribution to network availability, using special paths and packet headers, to meet the network availability requirement.