BitTorrent Strategies: The End Game

December 26, 2007 at 11:51 PM | categories: Technical, BitTorrent | View Comments |

Downloads in BitTorrent take place according to a number of strategies, which map to stages. Initiating a torrent download has one strategy, normal operation has another strategy, and finally pulling down the last remaining pieces has yet another strategy. The End Game is the name for the final download strategy - there is a tendency for the last few pieces of a torrent to download quite slowly. To avoid this, many BitTorrent implementations issue requests for the same remaining blocks to all its peers. When a block comes in from one peer, you send CANCEL messages to all the other peers requested from, in order to save bandwidth. Its cheaper to send a CANCEL message than to receive the full block and just discard it. However, there is no formal definition of when to enter End Game Mode. In my BitTorrent implementation, Unworkable, I quite stupidly used a percentage-based threshold. When only 5% of the torrent download was incomplete, Unworkable would enter End Game Mode. I didn't notice how stupid this was until I got around to testing with a large torrent download, a Fedora Core 8 DVD image which is 4G in size or so. It turns out that 5% of 4G is quite a bit of data, and requesting each bit of it from every single peer is extremely inefficient. So I did some more research to find a more effective way to detect when to enter End Game. I found two popular definitions:

  1. All blocks have been requested
  2. Number of blocks in transit is greater than number of blocks left, and no more than 20
I didn't understand the choice of the number 20 in method 2, so I decided to go with option 1), which I did understand. In Unworkable CVS HEAD (and in the 0.4 release, coming in a week or two), the ill-informed percentage-based threshold is gone and End Game Mode is entered when all blocks are requested.

Niall O'Higgins is an author and software developer. He wrote the O'Reilly book MongoDB and Python. He also develops Strider Open Source Continuous Deployment and offers full-stack consulting services at FrozenRidge.co.

blog comments powered by Disqus