School of Computing

Applying clustering algorithms to multicast group hierarchies

Gill Waters and Sei Guan Lim

Computer Science Technical Report 4-03, University of Kent, Computing Laboratory, August 2003.


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.

Download publication 625 kbytes (PDF)

Bibtex Record

author = {Gill Waters and Sei Guan Lim},
title = {Applying clustering algorithms to multicast group hierarchies},
month = {August},
year = {2003},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {},
    publication_type = {techreport},
    submission_id = {14844_1060099102},
    type = {Computer Science Technical Report},
    number = {4-03},
    institution = {University of Kent, Computing Laboratory},

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014