On unbiased sampling for unstructured peer-to-peer networks Export

@inproceedings{citeulike:5486555, abstract = {This paper addresses the difficult problem of selecting representative samples of peer properties ( eg degree, link bandwidth, number of files shared) in unstructured peer-to-peer systems. Due to the large size and dynamic nature of these systems, measuring the quantities of interest on every peer is often prohibitively expensive, while sampling provides a natural means for estimating system-wide behavior efficiently. However, commonly-used sampling techniques for measuring peer-to-peer systems tend to introduce considerable bias for two reasons. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous nature of the overlay topology can lead to bias towards high-degree peers.We present a detailed examination of the ways that the behavior of peer-to-peer systems can introduce bias and suggest the Metropolized Random Walk with Backtracking (MRWB) as a viable and promising technique for collecting nearly unbiased samples. We conduct an extensive simulation study to demonstrate that the proposed technique works well for a wide variety of common peer-to-peer network conditions. Using the Gnutella network, we empirically show that our implementation of the MRWB technique yields more accurate samples than relying on commonly-used sampling techniques. Furthermore, we provide insights into the causes of the observed differences. The tool we have developed, ion-sampler , selects peer addresses uniformly at random using the MRWB technique. These addresses may then be used as input to another measurement tool to collect data on a particular property.}, address = {New York, NY, USA}, author = {Stutzbach, Daniel and Rejaie, Reza and Duffield, Nick and Sen, Subhabrata and Willinger, Walter}, booktitle = {IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement}, citeulike-article-id = {5486555}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1177084}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1177080.1177084}, doi = {10.1145/1177080.1177084}, isbn = {1-59593-561-4}, keywords = {peer, unbiased}, location = {Rio de Janeriro, Brazil}, pages = {27--40}, posted-at = {2009-08-19 14:17:03}, priority = {2}, publisher = {ACM}, title = {On unbiased sampling for unstructured peer-to-peer networks}, url = {http://dx.doi.org/10.1145/1177080.1177084}, year = {2006} }

TY - CONF ID - citeulike:5486555 L3 - citeulike-article-id:5486555 N2 - This paper addresses the difficult problem of selecting representative samples of peer properties ( eg degree, link bandwidth, number of files shared) in unstructured peer-to-peer systems. Due to the large size and dynamic nature of these systems, measuring the quantities of interest on every peer is often prohibitively expensive, while sampling provides a natural means for estimating system-wide behavior efficiently. However, commonly-used sampling techniques for measuring peer-to-peer systems tend to introduce considerable bias for two reasons. First, the dynamic nature of peers can bias results towards short-lived peers, much as naively sampling flows in a router can lead to bias towards short-lived flows. Second, the heterogeneous nature of the overlay topology can lead to bias towards high-degree peers.We present a detailed examination of the ways that the behavior of peer-to-peer systems can introduce bias and suggest the Metropolized Random Walk with Backtracking (MRWB) as a viable and promising technique for collecting nearly unbiased samples. We conduct an extensive simulation study to demonstrate that the proposed technique works well for a wide variety of common peer-to-peer network conditions. Using the Gnutella network, we empirically show that our implementation of the MRWB technique yields more accurate samples than relying on commonly-used sampling techniques. Furthermore, we provide insights into the causes of the observed differences. The tool we have developed, ion-sampler , selects peer addresses uniformly at random using the MRWB technique. These addresses may then be used as input to another measurement tool to collect data on a particular property. CY - Rio de Janeriro, Brazil SN - 1-59593-561-4 AD - New York, NY, USA EP - 40 TI - On unbiased sampling for unstructured peer-to-peer networks PB - ACM T2 - IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement SP - 27 KW - peer KW - unbiased AU - Stutzbach, Daniel AU - Rejaie, Reza AU - Duffield, Nick AU - Sen, Subhabrata AU - Willinger, Walter PY - 2006/// UR - http://dx.doi.org/10.1145/1177080.1177084 ER -