Spatial Clustering for IP Multicast: Algorithms and an Application

Abstract

We introduce spatial clustering of multicast group members as a mechanism to scale wide-area multicast-based applications. To motivate the use of such structures, we present a clustering based re-keying scheme for secure multicast. Using amortized analysis, we show that the communication, processing, and storage costs for this scheme to distribute keys upon membership changes is of constant order. This improves upon the previously known best-case logarithmic bounds under the same assumptions. Next, we develop a clustering algorithm and a cluster formation protocol that can be built atop IP multicast to create clusters with properties required to implement the secure multicast scheme. To show the viability of such a clustering scheme on the Internet, we present results from implementing this clustering technique on a Internet map of over 280,000 IP routers. We describe how a small set (~ 64) of multicast addresses can be used to efficiently implement intra-cluster communication in large groups (> 64K members). clustering protocol to demonstrate protocol robustness under varying membership dynamics.