A level-wise clustering algorithm for multicast on hypercube network

Multicast tree method in hypercube network plays a great role in parallel computing environments. The optimal multicast tree problem on hypercube network is NP-hard and existing multicast algorithms are heuristic. We find there is still a large gap between the existing and the optimal. This paper proposes a level-wise clustering algorithm with reducing the communication traffic. The clustering process applies the level property of the tree and run level by level. Based on the model, an optimal multicast algorithm for hypercube interconnection networks can be constructed. By simulation experiments, the multicast algorithm has significant improvements in comparison to the existing algorithms.