Efficient group communication and the degree-bounded shortest path problem

In this thesis we develop a framework for studying and understanding the tradeoffs involved in efficient multicast route determination. Using this framework, we developed an algorithm (Myriad) that exhibits superior theoretical and empirical results over previously published work. We have validated this work through extensive simulation using a variety of metric spaces, and by proving a series of mathematical theorems concerning degree-bounded spanning trees over metric spaces. This study is done through examination of the degree-constrained minimum average-latency spanning tree problem (or DC-MAL). Creating a solution which places each participant at their optimal locality along a path from the root is an NP-hard problem, thus motivating a search for approximate solutions. This type of organization for information relaying is a natural model of the multicast problem and lends itself to theoretical analysis that can be applied in application level peer-to-peer overlay networks. Out-degree constraints follow directly from the need for high bandwidth multimedia streams and the ability to relay the information without any loss. Study of this problem is important since it is expected that the demand for multicast applications will continue to grow, and such applications require scalability to millions of simultaneous subscribers.