Research On Multicast Routing Optimizing Strategy In Hypercube

Hypercube network is an interconnection model with excellent topologicalproperties, including strong fault-tolerant ability brought by highly redundantcommunication paths, self-embedding, the scalability and simple routing algorithm.The composite network can be obtained by the combination of this topology andother type network, so this topology is proved to be one of the most attractivenetworks in parallel computer designing.The overall performance of parallel computer based on hypercube topologydepends largely on its routing strategies, which mainly contains multicastcommunication strategy, fault-tolerant communication strategy and disjoint pathcommunication strategy. In many large-scale scientific and engineering projects,polymerization communication/multicast communication accounts for a largeproportion of all the communication overhead, thereby, to design multicastcommunication strategy with efficient communication is an effective way toimprove system efficiency and reliability. With the scale increasing of themultiprocessor system and the increasing of the connection failure or processorfailure frequency, multicast routing strategy is required to possess the property offault tolerance to ensure that the system continuous operation. It is a challengingproblem to design fault-tolerant multicast routing strategy with communicationamount being as small as possible. Disjoint path routing policy is divided into twotypes, including single target node and many destination node. The disjoint pathrouting with single target node is a comprehensive solution to increase the networkbandwidth between nodes and increase ability of fault tolerance; the disjoint pathrouting with multi-target node can be considered as multicast communication withthe path disjoint. They provide a higher level of assurance for network and systemreliability. To optimize the multicast communications, fault-tolerant communicationdisjoint path is the research focus in the hypercube network routing strategy.The main contents of this thesis are as follows:To reduce communication overhead of the multicast strategy based on treetopology, this thesis firstly studies multicast tree heuristic algorithm based onlevel-wise clustering strategy (LWC-MT). By proposing the cost of the clusteringoperation and the optimization of multicast scheme tree generating process,LWC-MT generates multicast program along the smallest cost growth direction. Thesimulation results show that the novel algorithm generates smaller communicationoverhead than current algorithms.To reduce multicast communication overhead under the conditions that possess certain fault-tolerant communication capabilities, the thesis presents an optimizedmulticast algorithm (FT-MT) and distributed fault-tolerant multicast routing strategybased on local k-dimensional subcube connectivity hypercube (DFT-MT). By usingoptimized fault-tolerant path storage model, FT-MT constructs fault-tolerantmulticast solution to ensure fault tolerance, and it reduces the overhead at the sametime. For Hypercube networks with local k-dimensional subcube connectivity,DFT-MT achieves localized management and distributed storage of the optimizedfault-tolerant path storage model, and circumvents large amounts of informationexchange overhead during the storage model updating process. Simulation resultsshow that under the condition that the networks meets local k-dimensional subcubeconnectivity, the communication overhead generated by the algorithm is less thanthe method in the existing literatures.To optimize multicast communication path length in path-based multicaststrategy with large number of the destination node, this thesis proposes a multicastpath construction strategy based on great target node distribution density (MDPMP)and ACO-based multicast path construction algorithm (AMPA). By using the unevennature of the target node distribution density, MDPMP divides hypercube into manysub-cubes to construct a multicast path. Simulation results show that the path lengthgenerated by MDPMP with lots of target nodes is shorter than that in relatedliteratures. To obtain shorter multicast path, AMPA introduces the ant colonyalgorithm to strike the subcube partitioning problem, and then create multicast paths.The simulation results show that the path length is reduced. Furthermore, toeffectively alleviate the calculated time complexity problem of the ant colonyalgorithm, distributed AMPA is introduced by combining the MDPMP and AMPA.The experimental results show that, with respect to a centralized algorithm, resultsof distributed AMPA algorithm is in the acceptable range.To reduce the length of the path in disjoint multi-path communication, thisthesis proposes a one-to-many node disjoint fault-tolerant optimal path algorithmand one-to-one disjoint fault-tolerant dual-path algorithm. One-to-many nodedisjoint fault-tolerant optimal path optimization algorithm generates multipledisjoint paths by using the optimized fault-tolerant path model, with the results thatthe average path length and the longest path length is less than that in the existingalgorithms. One-to-one disjoint fault-tolerant dual-path algorithm generates twopaths that at least one path is the optimized path between two points.