Group Membership
Measurement and Modelling
University of California, Los Angeles
Overview
A realistic and systematic group membership model can have significant impact on the design and development of multicast protocols. However, multicast research has traditionally been plagued by a lack of real data and an absence of a systematic simulation methodology. In this project, we identify properties of group members that reflect their spatial clustering and the correlation among them. Then we obtain values for these properties by monitoring the multicast group membership in the Internet. Based on our measurement and analysis, we propose a comprehensive model that can generate realistic groups. Such a realistic group membership model can help us improve the effectiveness of simulations and guide the design of group-communication protocols.
Motivation
Despite the significant breakthrough in modelling the traffic and the topology of the Internet, there has been little progress in multicast modelling. Only recently, properties of group membership have received some attention, but the spatial properties have not been adequately measured and controlled. As a result, the design and evaluation of multicast protocols is based on commonly accepted by often unproven assumptions. For example, the majority of simulation studies assumes that users are uniformly distributed in the network. However, previous studies show that spatial distribution of members have significant influence on the design and evaluation of multicast schemes and protocols, such as the scaling properties of multicast trees, the aggregatability of multicast state and the size of multicast trees. Therefore, realistic models and a systematic evaluation methodology can greatly benefit the multicast research community.
Our Approach
1. Charateristics of the Group Membership
We define several properties of group
membership and quantify them through measurements.
-
Member Clustering:
Clustering captures
the proximity of the group members. We employ network-aware clustering
to identify member clusters using network prefixed based on BGP routing
snapshots. Since a node in the network is a cluster of size 1, we also
call some individual unclustered nodes as clusters. -
Group Participation Probability
:
Different clusters have different probabilities in participating in
multicast groups: some clusters are more likely to be part of the group. -
Pairwise Correlation in Group Participation
:
This metric captures the joint probability that two clusters are members
of a group. Given two clusters Ci and Cj,
we denote the participation probabilities of cluster Ci
and Cj as pi and pj
respectively, and the joint participation probability of Ci
and Cj is denoted by pi,j. The
correlation coefficient between Ci and Cj,
coef (i,j), is the normalized covariance between Ci
and Cj:
2. Membership Feature Measurement
We measure properties of multicast group membership in real applications.-
MBONE: We use data from NASA and IETF broadcasts over the MBONE, which are single-source large-scale application. The data sets are provided by Chalmers and Almeroth from University of Santa Barbara. We observe that MBONE multicast members are highly clustered and the clusters exhibit skewed distribution and strong pairwise correlations in their participation.
-
Net Game: We use Qstat tool to collect membership at net games, which are multiple-source interactive applications. We find that net game members are not as clustered and there does not seem to be a strong correlation between users. The uniform random membership can roughly model net games. However, this could be partially due to the small scale of the games we were able to measure.
3. GEM: A Group Membership Model
Since real membership distribution does not follow the simple uniform random distribution, we develop a comprehensive group membership model, called GEM (GEneralized Membership Model) to generate membership distribution that conform to realistic distribution. GEM considers all the group membership properties above, and works as follows:
The core of our model is the selection of the member clusters, which generate sets of member clusters that follows the group participation probability of each cluster and the pairwise correlation between any two clusters. There are only O(K+K^2) input constraints, but we need O(2^K) constraints to be able to generate the desired distribution. Therefore, we assume Maximum Entropy for the missing constraints. In other words, our member clustering algorithm combines two "conflicting" forces: it maximizes the entropy (randomness), while trying to match given distribution. In this way, our model is able to generate member clusters for uniform distribution, non-uniform distribution without correlation, and non-uniform distribution with correlation.
We validate our model with great success: the generated groups match the real data very well.
For details of our approach, please
refer to our publications.
Download
Measurement data sets: MBONE (zip files), Netgames (zip files)
GEM utilities: coming soon...
Publications
-
Measuring and Modelling the Group Membership in the Internet
Jun-Hong Cui, Michalis Faloutsos, Dario Maggiorini, Mario Gerla, and Khaled Boussetta
In Proceedings of ACMSIGCOMM/USENIX Internet Measurement Conference (IMC2003), Miami Beach, Florida, October 27-29, 2003 -
Modelling the Spatial Properties of Group Members in the Internet
Jun-Hong Cui, Dario Maggiorini, Michalis Faloutsos, Mario Gerla, and Khaled Boussetta
UCLA CSD Technical Report #030011, February 2003