Skip to main content



Applications of game theory in the BitTorrent protocol

BitTorrent is a file sharing protocol that allows large files to be efficiently distributed across a network. It works by splitting a file into a bunch of smaller chunks that are easier to transfer. Then each person, or “peer,” who wants to download this file must acquire all of the chunks and assemble them. To achieve this goal, peers must work together by trading the chunks they currently have for chunks that another peer has. For example, say peer Alice has chunks 1, 2, and 5 while peer Bob has chunks 2, 3, and 4. Then, if the full file is composed of chunks 1 through 5, Alice can trade chunks 1 and 5 for Bob’s 3 and 4. This will give each of them the full file. Now imagine the file has chunks 1 through 6, so Alice and Bob are unable to assemble the full file with just their combined chunks. This is where additional peers are needed. Enter Carol, who has chunks 4, 5, and 6. Now Alice can get 6 from Carol by trading her 1, and Bob get 6 from C by trading his 2. Although this example works out well, it is not so simple in real life, where there can be thousands of peers and thousands of file chunks.

In a network of peers, each peer is responsible for his own well-being. A problem arises in peer-peer interactions when one peer decides to be lazy. Uploading chunks to other peers costs money and bandwidth, so reducing one’s upload rate is obviously desirable. However, lazy peers hurt download speeds for everyone else, because they are not contributing by sharing chunks. The situation can be modeled as follows:

Assume that the benefit is 4 for full download speed and 2 for half download speed, and assume that the penalty is -2 for full upload speed and -1 for half upload speed. When one person uploads at full speed, the other person downloads at full speed, and likewise for half speed. One peer cannot download at full speed if the other peer is uploading to them at half speed. Let “active” correspond to full upload speed, and “lazy” correspond to half upload speed. The following table results from this situation:

 

Clearly, the best situation (with the highest social welfare) occurs when both Alice and Bob are active uploaders, rather than lazy. However, also note that this situation is not in Nash Equilibrium; both peers will get better results if they unilaterally switch to lazy. Therefore, there needs to be some other incentive to make (Active, Active) the most appealing choice.

The article Incentives Build Robustness in BitTorrent gives details on a “choking algorithm” that incentivizes the cooperative (Active, Active) strategy. A peer using this choking algorithm will play a variant of tit-for-tat with other peers by rewarding active uploading and punishing lazy uploading. For example, say that Alice and Bob are actively sharing chunks of data at full speed, and Bob decides to pull a fast one on Alice by becoming lazy and decreasing his upload rate to Alice. Alice detects this, and punishes Bob by “choking” him, or decreasing her upload rate to Bob. Now fairness is restored, and both Alice and Bob have a payout of 1. But they could do better if both choose to be active, and Bob realizes this, so in a show of good faith, he decides to become active again. Then Alice, abiding by her tit-for-tat strategy, follows Bob by also becoming active. Now both Alice and Bob have a payout of 2, and social welfare is maximized.

Now say Bob finishes his download, and leaves the network before Alice has finished. But now Alice has no download partners, so she needs to find other peers willing to trade with her so she can finish downloading the file. To seek out peers, she plays the first move in a tit-for-tat strategy: cooperation. She actively uploads chunks to random peers until she finds one that reciprocates and actively uploads chunks back to her. This gets Alice back on track to downloading the full file. Clearly, tit-for-tat is a useful strategy in the world of BitTorrent.

Source: http://www.ittc.ku.edu/~niehaus/classes/750-s06/documents/BT-description.pdf

– dfelt

Comments

Leave a Reply

Blogging Calendar

September 2012
M T W T F S S
 12
3456789
10111213141516
17181920212223
24252627282930

Archives