Applying clustering algorithms to multicast group hierarchies

Multicasting offers group communication a considerable efficiency gain, particularly for large groups. As the size of the group increases, management and protocols become more complex and severe scaling problems can arise, for example in the routers at the network layer, for reliable file distribution at the transport layer and for large scale Peer-to-Peer file sharing or processing sharing systems at the application layer. Hierarchies help to reduce complexity, state space requirements and the number of messages exchanged between participants. In this paper, we propose the use of clustering algorithms to help in determining hierarchical multicast trees. Clustering algorithms help to partition user populations according to a variety of criteria. Here, we principally consider proximity. We apply the k-means clustering algorithms iteratively to construct successive hierarchical levels. We examine the performance of the technique for multicast groups, first based on the geographical location of the participants and, secondly, based on the usual weighted graph representation of network topology. The results show that it is a promising technique for multicast tree construction. The report concludes with suggestions for applying the clustering technique in a variety of ways. Emphasis is placed on the transport and application layers to produce tree-based overlay networks.