Arnaud Legout
ABSTRACT
The performance of peer-to-peer file replication comes from its piece and peer selection strategies. Two such strategies have been introduced by the BitTorrent protocol: the rarest first and choke algorithms. Whereas it is commonly admitted that BitTorrent performs well, recent studies have proposed the replacement of the rarest first and choke algorithms in order to improve efficiency and fairness. In this paper, we use results from real experiments to advocate that the replacement of the rarest first and choke algorithms cannot be justified in the context of peer-to-peer file replication in the Internet.We instrumented a BitTorrent client and ran experiments on real torrents with different characteristics. Our experimental evaluation is peer oriented, instead of tracker oriented, which allows us to get detailed information on all exchanged messages and protocol events. We go beyond the mere observation of the good efficiency of both algorithms. We show that the rarest first algorithm guarantees close to ideal diversity of the pieces among peers. In particular, on our experiments, replacing the rarest first algorithm with source or network coding solutions cannot be justified. We also show that the choke algorithm in its latest version fosters reciprocation and is robust to free riders. In particular, the choke algorithm is fair and its replacement with a bit level tit-for-tat solution is not appropriate. Finally, we identify new areas of improvements for efficient peer-to-peer file replication protocols.
- http://www.slyck.com.Google Scholar
- http://www.bittorrent.com/.Google Scholar
- Bittorrent protocol specification v1.0. http://wiki.theory.org/BitTorrentSpecification, June 2005.Google Scholar
- R. Bhagwan, S. Savagen, and G. Voelker. Understanding availability. In International Workshop on Peer-to-Peer Systems, Berkeley, CA, USA, February 2003.Google ScholarCross Ref
- A. R. Bharambe, C. Herley, and V. N. Padmanabhan. Analysing and improving bittorrent performance. In Proc. IEEE Infocom'2006, Barcelona, Spain, April 2006.Google ScholarCross Ref
- E. W. Biersack, P. Rodriguez, and P. Felber. Performance analysis of peer-to-peer networks for file distribution. In Proc. Fifth International Workshop on Quality of Future Internet Services (QofIS'04), Barcelona, Spain, September 2004.Google ScholarCross Ref
- Y. Chawathe, S. Ratnasamy, L. Breslau, and S. Shenker. Making gnutella-like p2p systems scalable. In Proc. ACM SIGCOMM'03, Karlsruhe, Germany, August 25-29 2003. Google ScholarDigital Library
- B. Cohen. Incentives build robustness in bittorrent. In Proc. First Workshop on Economics of Peer-to-Peer Systems, Berkeley, USA, June 2003.Google Scholar
- P. Felber and E. W. Biersack. Self-scaling networks for content distribution. In Proc. International Workshop on Self-* Properties in Complex Information Systems, Bertinoro, Italy, May-June 2004.Google Scholar
- P. Ganesan and M. Seshadri. On cooperative content distribution and the price of barter. In IEEE ICDCS'05, Columbus, Ohio, USA, June 2005. Google ScholarDigital Library
- C. Gkantsidis and P. Rodriguez. Network coding for large scale content distribution. In Proc. IEEE Infocom'2005, Miami, USA, March 2005.Google ScholarCross Ref
- K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of dht routing geometry on resilience and proximity. In Proc. ACM SIGCOMM'03, Karlsruhe, Germany, August 25-29 2003. Google ScholarDigital Library
- L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, and X. Zhang. Measurements, analysis, and modeling of bittorrent-like systems. In Proc. ACM IMC'2005, Berkeley, CA, USA, October 2005. Google ScholarDigital Library
- M. Izal, G. Urvoy-Keller, E. W. Biersack, P. Felber, A. A. Hamra, and L. Garcés-Erice. Dissecting bittorrent: Five months in a torrent's lifetime. In Proc. PAM'04, Antibes Juan-les-Pins, France, April 2004.Google ScholarCross Ref
- S. Jun and M. Ahamad. Incentives in bittorrent induce free riding. In Proc. SIGCOMM'05 Workshops, Philadelphia, PA, USA, August 2005. Google ScholarDigital Library
- T. Karagiannis, A. Broido, N. Brownlee, and K. C. Claffy. Is p2p dying or just hiding? In Proc. IEEE Globecom'04, Dalla, Texas, USA, Nov. 29-Dec. 3 2004.Google ScholarCross Ref
- T. Karagiannis, A. Broido, M. Faloutsos, and K. C. Claffy. Transport layer identification of p2p traffic. In Proc. ACM IMC'04, Taormina, Sicily, Italy, October 2004. Google ScholarDigital Library
- D. Kostić, R. Braud, C. Killian, E. Vandekieft, J. W. Anderson, A. C. Snoeren, and A. Vahdat. Maintaining high bandwidth under dynamic network conditions. In Proc. USENIX'05, Anaheim, CA, USA, April 2005. Google ScholarDigital Library
- A. Legout, G. Urvoy-Keller, and P. Michiardi. Rarest first and choke algorithms are enough. Technical Report (inria-00001111, version 3 - 6 September 2006), INRIA, Sophia Antipolis, September 2006.Google ScholarDigital Library
- A. Parker. The true picture of peer-to-peer filesharing. http://www.cachelogic.com/, July 2004.Google Scholar
- J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips. The bittorrent p2p file-sharing system: Measurements and analysis. In Proc. 4th International Workshop on Peer-to-Peer Systems (IPTPS'05), Ithaca, New York, USA, February 2005. Google ScholarDigital Library
- D. Qiu and R. Srikant. Modeling and performance analysis of bittorrent-like peer-to-peer networks. In Proc. ACM SIGCOMM'04, Portland, Oregon, USA, Aug. 30-Sept. 3 2004. Google ScholarDigital Library
- S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In Proc. ACM SIGCOMM'01, San Diego, California, USA, August 27-31 2001. Google ScholarDigital Library
- P. Rodriguez and E. W. Biersack. Dynamic parallel-access to replicated content in the internet. IEEEACM Transactions on Networking, 10(4), August 2002. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. ACM SIGCOMM'01, San Diego, California, USA, August 27-31 2001. Google ScholarDigital Library
- X. Yang and G. de Veciana. Service capacity in peer-to-peer networks. In Proc. IEEE Infocom'04, pages 1--11, Hong Kong, China, March 2004.Google Scholar
Index Terms
- Rarest first and choke algorithms are enough
Recommendations
Understanding churn in peer-to-peer networks
IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurementThe dynamics of peer participation, or churn, are an inherent property of Peer-to-Peer (P2P) systems and critical for design and evaluation. Accurately characterizing churn requires precise and unbiased information about the arrival and departure of ...
Poster: Destabilizing BitTorrent's clusters to attack high bandwidth leechers
CCS '11: Proceedings of the 18th ACM conference on Computer and communications securityBitTorrent protocol incentivizes sharing through its choking algorithm. BitTorrent choking algorithm creates clusters of leechers with similar upload capacity to achieve higher overall transfer rates. We show that a malicious peer can exploit BitTorrent'...
FairTorrent: bringing fairness to peer-to-peer systems
CoNEXT '09: Proceedings of the 5th international conference on Emerging networking experiments and technologiesPeer-to-Peer file-sharing applications suffer from a fundamental problem of unfairness. Free-riders cause slower download times for others by contributing little or no upload bandwidth while consuming much download bandwidth. Previous attempts to ...
Comments