4th International ICST Conference on Communications and Networking in China

Research Article

A balanced and robust spanning tree algorithm for overlay multicast

  • @INPROCEEDINGS{10.1109/CHINACOM.2009.5339869,
        author={Wendao  Zhao and Nengwei  Hua},
        title={A balanced and robust spanning tree algorithm for overlay multicast},
        proceedings={4th International ICST Conference on Communications and Networking in China},
        publisher={IEEE},
        proceedings_a={CHINACOM},
        year={2009},
        month={11},
        keywords={Overlay multicast robustness multimedia NP-hard},
        doi={10.1109/CHINACOM.2009.5339869}
    }
    
  • Wendao Zhao
    Nengwei Hua
    Year: 2009
    A balanced and robust spanning tree algorithm for overlay multicast
    CHINACOM
    IEEE
    DOI: 10.1109/CHINACOM.2009.5339869
Wendao Zhao1,2,*, Nengwei Hua1,2
  • 1: Department of Information and Communication Engineering Zhejiang University
  • 2: Hangzhou, China
*Contact email: wdzhao@zju.edu.cn

Abstract

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.