The Research On Fault Tolerant Multicast In Hypercube Network

Hypercube interconnection network has the advantages of normality, great ability of fault tolerance, short diameter, embeddability and so on, it's one of the most popular, versatile and efficient topological structures of inter- connection networks. With the increace of the network size, the possibility of node failture also increases. The locally k-subcube-connected hypercube is the fault tolerant model for hypercube, whose ability of fault tolerance is much greater than others. Based on the analysis of the current research staus about demestic and international articles, the paper does the reasarch of fault tolerant multicast algorithm on the hypercube network with fault nodes and the related issues.Firstly, a fault-tolerance multicast algorithm based on the reachability model is introduced. According to the drawback of the original algorithm, we improve the fault-tolerance multicast algorithm based on the reachability model is introduced. The improved fault-tolerance multicast algorithm is a heuristic algorithm, it uses divide-and-conquer strategy to solve the multicast problem. The improved fault-tolerance multicast algorithm takes every sub-cube as a correct node. On the source node, the algorithm does with the muliticast nodes , it links the neighbor nodes which are in the same sub-cube and puts the neighbor sub-cube in the same path. Among the sub-cubes, the dissertation use Sheu's MT algorithm to constrcuct the multicast tree backbone. In the sub-cube, it multicasts again to compete a whole multicast process. At the same time, considering that the nodes join or leave will effect on the MT, the dissertation proposes the multicast tree maintenance mechanism.Secondly, accordance with the problem that node needs to exchange routing information with its neighbor nodes to update rouiting table, the dissertation introduces the routing table updating algorithm based rechability model and makes detailed analysis. According to the existing algorithm's defects, an optimized algorithm is proposed. The node tests neighbors'reachability in fixed hour to make sure that whether it needs to update routing table; then the optimized algorithm is divided into two parts of sending message ande accepting message on the basis of the task the node assumes. When a node exchanges routing information with ineighbor nodes, it sends routing updating package to neighbors rather than the whole routing table.Finally, according to the subject, the improved algoriths are simulated on network simulation platform OMNET++, and the simulation results are compared with the original algorithms in performance.