A balanced and robust spanning tree algorithm for overlay multicast

Overlay multicast has become an increasingly popular alternative to IP-supported multicast, because of its flexibility and adaptivity. It requires a routing spanning tree on overlay network, using which messages transfer from the source to the destinations. In many multimedia applications, the spanning tree should provide low-delay paths for each member, and consume less network resources at the same time. However, these two metrics always conflict. In addition, the robustness of the spanning tree is also important as the overlay network is usually in dynamic environment and easy to various disturbances. In this paper, we first introduce a problem model for balanced spanning tree which require both the bounded delay and minimal network cost. Then, we propose our heuristic algorithm to this problem. After that, we take a delicate approach to the robustness in our algorithm, thus turn it to a balanced and robust algorithm. Finally the simulation results show that our balanced and robust spanning tree achieves a desirable trade-off for the delay performance and the network resource utility, and display robustness to node failure.