Hierarchical Clustering of Message Flows in a Multicast Data Dissemination System

Y. Tock, N. Naaman, A. Harpaz, and G. Gershinsky (Israel)


Multicasting algorithms, multicast mapping, data dissemi nation, receiver interest, hierarchical clustering, optimiza tion algorithms.


A large-scale data dissemination application is character ized by a large number of information flows and infor mation consumers. Consumers are interested in different, yet overlapping, subsets of the flows. Multicast is used to deliver subsets of the flows to subsets of the consumers. Since multicast groups are a limited resource, each con sumer must filter out a large number of unneeded flows. We alleviate the end-node filtering load by using hierarchi cal clustering of flows to transport-layer sessions, and clus tering of sessions to network-layer multicast groups. This scheme allows for hierarchical filtering of flows at the re ceivers. We formulate a cost function that models and em phasizes the filtering process, and propose algorithms for the solution of the hierarchical mapping problem. Perfor mance evaluation indicates a significant reduction of end node filtering cost compared to a non-hierarchic approach.

Important Links:

Go Back