Fault Tolerant Routing Algorithms Of Regular Networks And Reliable Multicast

Along with the increment of interactive multi-user application, such as network video conference, VOD/AOD, Internet-TV, interactive simulation, remote teaching etc. Internet needs high reliable multicast routing service to ensure the reliability of the transmission queue, but multicast implements based on high levels are generally short of reliability assurance, so studies in reliable multicast is hot in current network technology. Reliable multicast technology based on high levels mainly refers to scalability, fault tolerance, multicast algorithm, path length of the control topologies and reliability, fault tolerance, maintainability and scalability of the multicast protocols. Due to the rapidly increment of the node number in Internet and the randomness caused by nodes' going in and out the network, only the reliable multicast protocols which support large node number and have better fault tolerance ability can be used, so studies focus on the scalability and fault tolerance of the multicast protocols.This paper introduces some basic conceptions and some related works; Firstly, we discuss the fault tolerance of hypercube network, propose some route algorithms with fault tolerance and analyze the fault tolerance, path length and satisfy large node number of these algorithms. Then, due to the better fault tolerance ability of hypercube and the control topology requirements of the reliable multicast transmission, we propose control model of reliable multicast based on logical hypercube, and we also propose protocol of the reliable and fault tolerance multicast based on the analysis of the performances of the model. Our works are as follows:(1) Based on L2 which is a fault tolerance algorithm of local subcube, we propose the improved route algorithm L3 and the P2P route algorithm NL2 with fault tolerance ability, and we analyze the connectivity probability of NL2 by a new analysis method which based on globle connectivity, the theory analysis and calculation show the route connectivity of NL2 is better than L3, but L3 is more better than L2. We propose the P2P and parallel route algorithm HPPA, describe andanalyze it clearly, deduce the formulas for parallel route number, route connectivity probability, and nodes' fault probability. We analyze the upper bound of the nodes' fault probability in many conditions and the expected value of the path length created by NL2. We propose the improved algorithm NL2N and get the better upper bound expression of the path length.(2) Based on the feature that reliable multicast protocol using control topology and some advanced works such as HyperCast of LogCube and CubeFullDist of FullCube, we propose a new control topology—ComCube and discuss the building and maintaining process of it clearly. We put forward the conception of enlarging structure connectivity by logical edges, not only does it correct the defect of LogCube that it's fault tolerance ability is not good due to some nodes' lower connectivity, but also conquers the defect of FullCube that it's logical edges are hard to build. Analysis shows ComCube breaks through the constraint that the node number must be 2m in Hypercube and still keeps the good features such as good scalability, good fault tolerance ability, short route path etc.(3) Due to the better fault tolerance feature of ComCube, we propose the fault tolerance and reliable multicast conception, and involve it in the reliable multicast protocol ComCast. We discuss the transmission and feedback process of ComCast in detail, analyze the reliability of the protocol, and extend the fault tolerance ability of HyperCast. To these three protocols, ComCast, CubeFullDist, and extended HyperCast, we simulate the states of structure construction, transmission and feedback, structure maintenance, and the nodes fault etc. We collect the data of transmission time, the maximum path length, node load in perfect state and fault state. The results shows that the total transmission performance of is better than CubeFullDist and extended HyperCast. ComCasfs path length is shorter and keep the node load stable.