faq

The FairTorrent Project

Home

This is an FAQ that answers some technical questions about FairTorrent and how it differs from other clients such as BitTorrent, Azureus, Proportional Response and BitTyrant. More details are available in the paper on all of the questions below. Also feel free to contact me with questions and/or feedback, and I will work to beef up and clarify this FAQ.

Q: How does FairTorrent client accomplish strong correlation between its upload and download rates?

A: FairTorrent uses a deficit-based algorithm. In a nutshell, FairTorrent keeps track of deficits with each neighbor where deficit = bytes sent to the neighbor - bytes received from the neighbor. It always send the next data block to a peer with the smallest deficit. The faster peer A gets data from peer B, the faster the deficit with B is decremented, and the more frequently A sends data back to B. This leads to a very fast-convergence of peerwise bandwidth-exchange rates. In a large network this also leads to a very fast convergence between the peer's total download rate and the peer's total upload rate. (see the paper for details)

Q: Don't other clients such as the original BitTorrent or Azureus implement "incentives" ?

A: Yes, but the methods used to implement incentives in BitTorrent/Azureus are highly imprecise. This allows a strategic client, such as BitTyrant, or even a free-rider to game Azureus clients in the wild. (e.g. a BitTyrant peer B can exchange data with an Azureus peer A, where B uploads at a much lower rate to A than it downloads from A).

Q: Is their something fundamentally different in the approach of FairTorrent as compared to other clients?

A: There are two fundamental differences. First, FairTorrent is deficit-based while other clients such as BitTorrent, Azureus, Proportional Response, and K-TFT use rate-allocation. The second difference is that other clients perform peer discovery, where as FairTorrent does not need to do peer discovery. That is, other clients waste much time discovering better peers to exchange data with.

Q. Let's take these two aspects apart. First, what is rate-allocation, and what is peer-discovery?

A: In rate-allocation a peer allocates upload rates to a subset of neighbors for a duration of a round, typically 10-20 seconds. It re-adjusts the rates each round based on the rates that it observes from these peers. BitTorrent, for example, unchokes, or allocates its upload rate to the best k - j out of k peers from the previous round (i.e. peers from who it received the highest rate), and adds j random peers. The policy of replacing a subset of peers every round is known as optimistic unchoking. The peer uses optimistic unchoking to perform peer-discovery, i.e. crawl through the network and discover a better set of peers to exchange data with. A high-uploading peer may waste much time and bandwidth to discover other high-uploading peers to exchange data with.

Q: Why is rate-allocation bad and how does FairTorrent avoid it?

A: Rate-allocation is wasteful, and often leads to sub-optimal use of bandwidth. There are a number of reasons: (1) a peer commits its bandwidth for a duration of a round. (2) it uses the observed download rate from a peer as a prediction of future contribution from that peer. Such predictions are often erroneous. Especially in a dynamic environment peers often change their allocations or may stop reciprocating all-together. (3) Discovery of better peers is quite slow in real networks. Especially high-uploading peers may waste a lot of bandwidth and time before they can find other high-uploading peers to exchange data with.

FairTorrent, on the other hand, avoids allocating rates and wasting bandwidth on incorrect predictions. Every time a FairTorrent peer is ready to upload a block of data, it makes an optimal decision of which peer to send that block to. By sending the next block to the peer with the smallest deficit FairTorrent is able to maintain very even peer-exchange rates.

Q: How does FairTorrent avoid long peer-discovery times ?

A: FairTorrent simply does not need peer-discovery. For example, in BitTorrent a peer that uploads at a rate of 100 KB/s, may want to discovery 4 peers with whom it will reciprocate at a rate of 25KB/s or better. It may take a while to find such peers in a live network. FairTorrent, on the other hand, does not attempt to discover such peers. It will exchange data at any rate with any neighbor, as long as in total it gets a reciprocation of 100 KB/s. For example, lets say that the peers on the FairTorrent's randomized list are willing to reciprocate at the rates of : 10, 10, 30, 5, 40, 5, 10, 10, 10, etc... . FairTorrent peer will quickly converge to a scenario where it uploads at a rate of 10, 10, 30, 5, 40, and 5 to the first 6 peers on the list respectively, and receive a combined 100 KB/s back. This convergence will happen very quickly by using the deficits, without rate-allocation, and FairTorrent will not even need to consider peers further down the list as long as it gets back its 100 KB/s. At the same time observe that only two clients among the first 9 upload at a rate >= 25. Thus, a BitTorrent client will need to look through the entire list and keep looking further to find those additional clients.

Q: How is FairTorrent resilient to strategic peers such as free-riders ?

A: It is resilient simply by following its deficit-based algorithm. If some peer reciprocates at a very slow rate or 0, or say it's an adoptive peer that just cut its reciprocation rate, then the deficit with that peer stops being decremented. That means FairTorrent will prefer to reciprocate to other peers from whom it receives data and the deficit with those peers constantly keeps being decremented.

Q: What about the Proportional Response algorithm, does not it accomplish the same as FairTorrent with its proportional rate allocation ?

A: Not in practice! Proportional Response algorithm [STOC 2007 paper], also implemented by the PropShare client in [SIGCOMM 2008 paper], allocates its rates similar to BitTorrent, however, instead of splitting its rate evenly between k neighbors, it allocates it in proportion to the download rate received from these neighbors in the previous round. This is an improvement on BitTorrent, and the original algorithm, described in the STOC 2007 paper carries some nice properties.

However, the original algorithm makes some very simplified assumptions about live networks, and is difficult to adopt in practice. For example, Proportional Response assumes that each peer in each round can accurately estimate the intended allocation rate towards it from all neighbors. This is critical in order for the client to accurately re-adjust its allocations in the subsequent round. In practice, this is hard to accomplish. For example, PropShare client relies on the optimistic unchoking to crawl through the network and only estimates rates from several neighbors at a time. Thus, it does not hold a coherent view of neighbors' allocations in each round. The incoherent view, and the fact that each peer performs its own peer discovery and thus constantly replaces a subset of peers that it uploads to in each round, causes incorrect rate re-allocation in the subsequent round, which often leads to divergence rather than convergence of rates. One way to deal with the problem encountered by PropShare, may be to use very tiny data blocks in exchanging data with peers, and thus exchange data at more granular rates so as to closer approximate the original Proportional Response algorithm. However, this is unlikely to solve the problem, as small data blocks will result in high IP and BitTorrent protocol overheads. See our paper for the results that compare FairTorrent with PropShare.

Q: What about K-TFT? Is it not deficit-based, does it not achieve the same as FairTorrent ?

A: No and NO. K-TFT, also known as block-based TFT, is essentially BitTorrent, thus uses rate-allocation, but places a hard limit on how much peer B can owe to A. Once peer B owes more than k data blocks to A, A stops uploading to B. In fact K-TFT suffers from bandwidth under-utilization, as high-uploading peers will often stop uploading to their neighbors once the limits are reached.

Q: Does FairTorrent suffer from bandwidth under-utilization as compared to other clients ?

A: No. In fact, we measured FairTorrent's upload capacity utilization to be higher than that of other clients. The reason is that a FairTorrent peer always uploads a data block as long as at least one neighbor is requesting data. In BitTorrent a peer only uploads to a subset of peers in each round, and thus there is a higher chance that a peer may not have data to send to its neighbors.