On-the-fly distributed tree construction for scalable efficient application layer multicast

Abstract

The advances of networking and computing technologies leveraged large scale group communication applications such as multimedia streaming. Supporting group communications basically inquires the multicasting ability. Application layer multicast has been focused because it can support group communication without router level support. In this dissertation, we assumed the environment that multicast session members are not known a priori and their joining sequence is also unaware. To support this extreme distributed environments, we formulated a problem named DBMDT-S that effectively models the sequenced joining problem. DBMDT-S problem aims at minimizing the diameter in the situation that session members joins sequentially. Hence given problem is not polynomial time solvable, we devsied a new heuristic algorithm named BrotherHood algorithm. The designed algorithm can evolve to a better state as the population of the session increases as time goes by. We performed a simulation study to evaluate and the result is very promising. It is better than another heuristic algorithm named ICT, a known best until now, in terms of diameter and average distance from root to any node. Also BH does not require many repositioning of already joined nodes.