A clustering structure for reliable multicasting

In reliable multicast, the multicast packets must be acknowledged. We propose a clustering structure which can be used by most of the existing reliable multicast protocols for collecting acknowledgements and for making local retransmissions. Given a network N and a multicast routing tree (or a set of trees) T, we consider a subgraph G of N induced by the members of a multicast group. We then form disjoint clusters (local groups) of multicast receivers such that the receivers within a cluster are densely connected in G. The goal is to obtain a balanced clustering structure (dependent on the topology of G) such that the number of clusters is constant and the cluster size is kept low. This structure enables different clusters to process acknowledgments concurrently. It is also used to localize retransmissions. That is, when a packet is missed at a node, we will obtain the lost packet from another node which resides in the same cluster or at a nearby cluster whenever possible.