Internet Communication Mode And The Routing Algorithm

With the fast development of high-performance technology, the interconnection networks of different topologies, such as tree, ring, Mesh, hypercube and star network etc., are developed rapidly, the interconnection networks have already played a very important role to the development of the society. In interconnection networks different applications need different communication modes, such as unicast, multicast, broadcast and anycast. How to realize such communication modes efficiently is an important subject for research. The communication efficiency in the network depends on the efficiency of routing algorithm, so study on routing algorithms of different communication modes under different topologies has important theoretical and realistic significance. The main research work and innovates of this paper are as follows: 1. Analyze the state of current research in the interconnection networks and study communication modes in the networks deeply, such as unicast, multicast, broadcast and anycast. 2. Base on the study of the hypercube networks, an efficent broadcast routing algorithm with fault-tolerance on locally k-subcube-connected hypercube networks is developed. Broadcast communication is one of the most frequently used communication modes in the interconnection networks. With continuous increases in network size, more and more nodes are faulty. So broadcast routing with fault-tolerance has already become an important subject in the interconnection networks. A lot of scholars have proposed various algorithms for the broadcast routing with falut-tolerance. But most researches concentrate on reducing the time complexity and it is less likely to consider raising the ablity of fault tolerance for the Hn network. To the author's knowledge, there has not been any development of efficient broadcast routing algorithms for hypercube that allows the number of faulty nodes to be larger than O(n). This thesis proposes an efficient broadcast routing algorithm with fault-tolerance on locally k-subcube-connected hypercube networks, based on the conception of locally k-subcube-connected hypercube. This algorithm is distributed and local-information-based in the sense that each node in the network knows only its neighbors'status and no global information of the network is required by the algorithm. It can tolerant the upper bound 2^n-1-2^n-k for faulty nodes under the condition of locally k-subcube-connected hypercube. This is a much larger bound on the number of faulty nodes compared to the previous broadcast algorithms. More over, this algorithm can construct broadcasting paths of nearly optimal length in a faulty hypercube Hn in linear time.