IEEE/ACM Transactions on Networking · 2008 · 214 citations · 52 references
ComputingComputer ScienceComputer SystemsCollective BehaviorComputer NetworksDistributed SystemsPeer-to-peer NetworksPeer-to-peer SystemsStochastic NetworksBandwidthHeterogeneous NetworksOverlay Network TopologyOverlay NetworkingPeer SamplingRepresentative SamplesUnstructured Peer-to-peer Networks
This paper presents a detailed examination of how the dynamic and heterogeneous nature of real-world peer-to-peer systems can introduce bias into the selection of representative samples of peer properties (e.g., degree, link bandwidth, number of files shared). We propose the metropolized random walk with backtracking (MRWB) as a viable and promising technique for collecting nearly unbiased samples and conduct an extensive simulation study to demonstrate that our technique works well for a wide variety of commonly-encountered peer-to-peer network conditions. We have implemented the MRWB algorithm for selecting peer addresses uniformly at random into a tool called ion-sampler. Using the Gnutella network, we empirically show that ion-sampler yields more accurate samples than tools that rely on commonly-used sampling techniques and results in dramatic improvements in efficiency and scalability compared to performing a full crawl.
52
Equation of State Calculations by Fast Computing Machines
N. Metropolis, Arianna W. Rosenbluth, M. N. Rosenbluth et al. · The Journal of Chemical Physics · 1953 · 37.1K citations
Monte Carlo sampling methods using Markov chains and their applications
W. Keith Hastings · Biometrika · 1970 · 15.2K citations
Ion Stoica, Robert Morris, David R. Karger et al. · 2001 · 9.7K citations
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · 2001 · 6.4K citations · Full text