Algorithm Research On Multicast Routing With Fault-Tolerance And High Reliability

In the multicast communication, packets are delivered through a tree topology. Since a single failure may lead to serious destructing results, the enhancment of the fault-tolerant ability is very important for a multicast routing system. Proactive algorithms of fault-tolerant multicast routing are attractive because they are fast in fault recoveries, Generally, there are two types of redundant routing trees: disjoint dual-tree and partly overlapped dual-tree. Proactive algorithms, however, are with two main problems: 1) Those algorithms based on disjoint dual-tree require the network topology to be strong in its connectivity. 2) The global fault-tolerance is not considered by them at all. As a matter of fact, the global fault-tolerance may be degradated or even lost by a local change in a multicast tree, In order to solve these problems, this thesis studies fault-tolerant multicast routing algorithms, which can guarantee failure recovery in the case of network failures.In this thesis, global reliability which can reflect the property of routing structure time-varying is used to be measurement of fault-tolerant performance. Then we propose a global reliability model and apply it to the selection of redundant dual-tree, by which the research and fault-tolerant multicast routing algorithm's design could be carried out. The researches in the thesis are as follows:1.The routing global reliability modelAccording that the partial reliability can not reflect the whole capability of fault-tolerant in the process of data transmission, thesis proposes routing global reliability model fully considering the changes of routing structure The model established a direct correspondence between two routing types (disjoint dual-tree and partly overlapped dual-tree) and routing global reliability, provides convenient analysis model for designing high reliability of fault-tolerant multicast routing algorithm. The model has been applied to selection of redundant dual-tree, some approaches could improve the capability of fault-tolerant: using partly overlapped dual-tree as multicast routing, minimizing vulnerability in partly overlapped dual-tree and being apt to braided structures. Under the guidance of the conclusions, we designed the following algorithm.2.The research on fault-tolerant multicast routing algorithmThesis proposes a fault-tolerant multicast routing algorithm of minimizing vulnerability (VOMRA) based on ant colony optimization algorithm, using group nodes driving and didymous ants to search partly overlapped dual-tree; the method of pheromone monomer update is reset, the methods of pheromone entirety update are putting a premium on more optimal tree and punishing worse tree, so algorithm tends to redundant routing of smaller value of vulnerability and braided structures. Algorithm can find out partly overlapped dual-tree that satisfies restriction and has maximum reliability.3.The reseach on fast recovery methodVOMRA algorithm is powerless to the failure in vulnerability. Thesis proposes a method for fast failure recovery of vulnerability which quickly reconnects the isolated sub-tree to primary tree again depend on calculating shortest path from the failure point to the primary tree. According to a number of isolated sub-tree caused by node failure, we set relation for isolated sub-tree to avoid loop. Methods shorten the fault recovery time by using the way of local recovery and the shortest failure recovery path together.4.The research on performance of the algorithmIn order to obtain better fault-tolerant performance, this thesis proposes the FR-VOMRA algorithm which combines VOMRA algorithm and fast fault recovery method for vulnerability. The algorithm gives different roles to nodes in multicast tree, nodes in different roles could implement different operation in process of failure recovery.In order to compare transmission and the fault-tolerant performance between FR-VOMRA and the existing IDFP and PAS algorithm, this thesis designs simulation system of adding new multicast routing algorithm in NS2. Simulation results show that transmission performance of FR-VOMRA is slightly worse in normal mode, but in the fault mode, both the transmission performance and the fault-tolerant performance of FR-VOMRA have greater advantage over PAS and IDFP.