Multicasting...

The problem of multicasting, that is, disseminating the same information from a single source to many receivers, is a well studied problem at the network level and at the application level. Although IP level multicast has not been widely adopted, gains can be made by deploying multicast enabled applications on the internet. Potential multicast applications include multimedia distribution and news/event notification. When constructing application-level multicast routes, we are able to leverage the availability of gathered topology information. Peer-to-peer overlay networks provide an attractive option because of the topology information that is either available at the overlay level or can be inferred by what is known, and several such models exist.
Multicast distribution routes are represented by a rooted, directed spanning tree. The problem of determining such a rooted tree which covers all subscribers is complicated by the need to balance network resources while optimizing the serving of the communication group. In order to enable real-time or near real-time delivery for bandwidth intensive multicast communication streams (such as a live video broadcast), the multicast distribution tree must have a bounded out-degree in order to allow for smooth playback/presentation of the material for subscribers.
This leads us to study the minimum average-latency degree-bounded directed spanning tree problem, a well known NP-hard problem. Recent works propose approximate solutions to this problem. Our work differs from previous work in that we focus on the additional constraint of minimizing the depth or hop count from the source in the message distribution.
Hop count and time-to-live (TTL) bounds are important in the design of communication protocols, particularly at the application-level, in order to minimize congestion in unstructured networks. Here we present a new heuristic algorithm, called DBSPT, that improves upon previous solutions, both in terms of empirical evaluation and theoretical worst-case approximation factors for degree and depth-bounded minimum average-latency spanning trees. We present an empirical analysis in which we compare our DBSPT algorithm against other solutions to the problem including the SPT- Dijkstra’s algorithm and MST-Prim’s Algorithm. Our algorithm consistently outperforms all previous algorithms in terms of Average Latency, Average Depth and Average Hop Count.