MeshTree: A Delay optimised Overlay Multicast Tree Building Protocol
Su‐Wei Tan, A. Gill Waters, John S. Crawford · Kent Academic Repository (University of Kent) · 2005
This paper investigates the problem of generating low delay degree-constrained overlay multicast trees for single source real-time applications in a distributed environment. This optimisation problem has been proven to be NP-hard. Traditional distributed solutions often use a greedy approach where on-tree nodes try to get as close as possible to the data source, i.e. the root. Due to the degree constraint and limited topology information at the overlay nodes, this can result in an inefficient structure where nodes close to the root are placed under nodes that are farther from the root. This is the greedy problem. This problem can be avoided by creating a minimum cost tree which connects nodes that are close to each other. However, the low cost tree can have high end-toend delay. Based on these observations, we devise a simple distributed protocol, called MeshTree, to construct trees that avoids the greedy problem while providing good delay properties. The main idea is to embed the delivery tree in a degree-bounded mesh containing many low cost links. Our simulation results show that MeshTree is comparable to the centralised Compact Tree algorithm, and always outperforms a distributed scheme by Banerjee et al. for this optimisation problem. In addition, it always yields trees with lower cost and traffic redundancy.