In this thesis, we present a distributed algorithm for determining a degree-constrained multicast tree in the application layer, which reduces the average latency. We achieve our goal of generating a multicast tree exhibiting reduced average latency, distributed operation and reduced runtime by using a novel partitioning approach.
This study was done by examining the existing approaches for creating a degree-constrained tree that exhibit minimum average latency. An optimal solution for degree constrained minimum average latency spanning tree is an NP-hard problem, thus motivating a search for an approximate solution. Our proposed solution distributes the tree creation overhead among member nodes by recursively partitioning the member nodes into mutually exclusive sets determined by the degree constraint. This approach relies on local network information and can be applied to application level peer-to-peer overlay networks and wireless multi-hop networks.