Rarest first and choke algorithms are enough
By Arnaud Legout, Guillaume Urvoy-Keller, Pietro Michiardi. ACM/SIGCOMM Internet Measurement Conference, 2006
446 citations recorded by the source corpus.
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.
Subfields: Computer Networks and Communications
View Paper: https://www.semanticscholar.org/paper/2e6649111da7e718ec525257123242a73feb76e2
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Jin Li
- Ethan Buchman
- Arvind Krishnamurthy
- T. Anderson
- Cheng Huang
- Arun Venkataramani
- Keith W. Ross
- A. Dimakis
Citations in the corpus
- Do incentives build robustness in bit torrent (2007, background): “Other studies [2, 7, 11] have pointed out the presence of significant altruism in BitTorrent or suggest preserving it [11].”
- Can internet video-on-demand be profitable? (2007, background): “For example, YouTube, a video-sharing service which streams its videos to users on-demand, has about 20 million views a day with a total viewing time of over 10,000 years to date [1].”
- Tendermint: Byzantine Fault Tolerance in the Age of Blockchains (2016, background): “Information should be gossiped in a “rarest first” manner in order to maximize gossip efficiency and minimize the chance that some information becomes unavailable [62]”