08-16-2017, 09:15 PM
RESIDUAL-BASED ESTIMATION OF PEER AND LINK LIFETIMES IN P2P NETWORKS
ABSTRACT:
Existing methods of measuring lifetimes in P2P systems usually rely on the so-called Create-Based Method (CBM), which divides a given observation window into two halves and samples users created in the first half every time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we first derive a model for CBM and show that small window size or large may lead to highly inaccurate lifetime distributions. We then show that create based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the Project by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultra peer lifetimes in a network of 6.4 million users and 60 million links.
ABSTRACT:
Existing methods of measuring lifetimes in P2P systems usually rely on the so-called Create-Based Method (CBM), which divides a given observation window into two halves and samples users created in the first half every time units until they die or the observation period ends. Despite its frequent use, this approach has no rigorous accuracy or overhead analysis in the literature. To shed more light on its performance, we first derive a model for CBM and show that small window size or large may lead to highly inaccurate lifetime distributions. We then show that create based sampling exhibits an inherent tradeoff between overhead and accuracy, which does not allow any fundamental improvement to the method. Instead, we propose a completely different approach for sampling user dynamics that keeps track of only residual lifetimes of peers and uses a simple renewal-process model to recover the actual lifetimes from the observed residuals. Our analysis indicates that for reasonably large systems, the proposed method can reduce bandwidth consumption by several orders of magnitude compared to prior approaches while simultaneously achieving higher accuracy. We finish the Project by implementing a two-tier Gnutella network crawler equipped with the proposed sampling method and obtain the distribution of ultra peer lifetimes in a network of 6.4 million users and 60 million links.