© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Meshtree: A Delay optimised Overlay Multicast Tree Building Protocol
Su-Wei Tan, A.G. Waters, and John Crawford
Technical Report 5-05, University of Kent, Computing Laboratory, University of Kent, April 2005.Abstract
We study decentralised low delay degree-constrained overlay multicast tree construction for single source real-time applications. This optimisation problem is NP-hard even if computed centrally. We identify two problems in traditional distributed solutions, namely the greedy problem and delay-cost trade-off. By offering solutions to these problems, we propose a new self-organising distributed tree building protocol called MeshTree. 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 existing distributed solutions in delay optimisation. In addition, it always yields trees with lower cost and traffic redundancy.
Download publication 557 kbytes (PostScript)
Bibtex Record
@techreport{2224,
author = {Su-Wei Tan and A.G. Waters and John Crawford},
title = {MeshTree: {A} {D}elay optimised {O}verlay {M}ulticast {T}ree {B}uilding {P}rotocol},
month = {April},
year = {2005},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2005/2224},
publication_type = {techreport},
submission_id = {9932_1118046925},
type = {Technical Report},
number = {5-05},
address = {University of Kent},
institution = {University of Kent, Computing Laboratory},
}