Clustering in P2P exchanges and consequences on performances

Stevens Le Blond, Jean-Loup Guillaume and Matthieu Latapy

LNCS, proceedings of the 4-th International workshop on Peer-to-Peer Systems IPTPS’05, 2005, Ithaka, New York, USA

We propose here an analysis of a rich dataset which gives an exhaustive and dynamic view of the exchanges processed in a running eDonkey system. We focus on correlation in term of data exchanged by peers having provided or queried at least one data in common. We introduce a method to capture these correlations (namely the data clustering), and study it in detail. We then use it to propose a very simple and efficient way to group data into clusters and show the impact of this underlying structure on search in typical P2P systems. Finally, we use these results to evaluate the relevance and limitations of a model proposed in a previous publication. We indicate some realistic values for the parameters of this model, and discuss some possible improvements.


Combining the use of clustering and scale-free nature of user exchanges into a simple and efficient P2P system

Pierre Fraigniaud, Philippe Gauron and Matthieu Latapy

LNCS, proceedings of the 11-th international conference Euro-Par, 2005, Lisbonne, Portugal

It appeared recently that user interests in a P2P system possess clustering properties that may be used to reduce significantly the amount of traffic of flooding-based search strategies. It was also observed that they possess scale-free properties that may be used for the design of efficient routing-based search strategies. In this paper, we show that the combination of these two properties make it possible to design an efficient and simple fully decentralized search strategy. Further, simulations processed on real-world traces show that other unidentified properties hidden in actual queries make our protocol even more efficient, performing searches in logarithmic expected number of steps.