Date Added: Jan 2011
Unstructured p2p and overlay network applications often require that a random graph be constructed, and that some form of random node selection take place over that graph. A key and difficult requirement of many such applications is heterogeneity: peers have different node degrees in the random graph based on their capacity. Using simulations, this paper compares a number of techniques - some novel and some variations on known approaches - for heterogeneous graph construction and random node selection on top of such graphs. The authors focus is on practical criteria that can lead to a genuinely deployable toolkit that supports a wide range of applications.