[bittorrent] New P2P protocols

Nick Johnson arachnid at notdot.net
Fri Mar 25 21:28:44 EST 2005


On 25/03/2005, at 10:01 PM, Bill Cox wrote:

> Hi.
>
> The most exciting aspect of this new group to me is
> the possibility that
> we may be able to come up with some new protocols.
> Since these will not
> be BitTorrent (though BT-like), we were not allowed to
> discuss them
> before in detail.  So, for example, we should now be
> free to come up
> with a way of actually agreeing on and implementing a
> new protocol.

A friend and I have been working on the design for a protocol similar 
to BT ourselves. This is probably a good time and place to share our 
ideas:

-Online/Fountain codes. The paper at 
http://www.rateless.com/oncodes.pdf details a coding scheme that allows 
one to generate a limitless number of encoded blocks from a source 
file, such that a peer collecting any subset of them totalling a little 
more (about 103% to 105%) than the original filesize can reconstruct 
the original file. Using this, seeds can continually churn out new 
encoded blocks, while peers redistribute the ones they already have, 
resulting in a situation where nearly every peer has something useful 
to exchange with any other peer, and eliminating any need for 
rarest-first distribution.

-Homomorphic hashes. The paper at 
http://www.pdos.lcs.mit.edu/~max/docs/kf03.pdf details a 'homomorphic 
hash' function - a hash specifically designed for systems like Online 
codes, that allows you to verify the integrity and validity of encoded 
blocks, instead of having to wait until a block is decoded to verify 
it.

-Multicast. Online codes applied to encoding a single chunk into 1k 
encoded blocks provide an ideal multicast platform: A server can 
multicast encoded packets to multiple listeners, and they need only 
recieve a sufficient quantity to reconstruct the chunk. Our working 
idea for this is to have multiple multicast channels at different 
bitrates, each transmitting encoded chunks of the most wanted block by 
that channel's listeners. Since each channel has a different rate, 
listeners can subscribe to whatever set of channels makes best use of 
its available bandwidth.

We believe multicast of any form would be a major boost to a BT-like 
file distribution system. While most of the Internet does not have 
multicast deployed, there are plenty of areas that do - for example, 
university networks, which are often particularaly popular places to 
use systems like BT. Having a major file distribution system use 
Multicast would provide a substantial incentive for ISPs to implement 
multicast, too. Any ISP implementing multicast would immediately see a 
drop in incoming and outgoing traffic as peers swap chunks between 
themselves on that ISP's network.

-Merkle Trees. Familiar to everyone here, I'm sure.

-Proximity-based connections. While BT does a reasonable job of picking 
good peers to download from and upload to, it's far from ideal. As an 
example, downloading a .torrent on a system with very asymmetric 
bandwidth (1mbit international, 100mbit New Zealand), the speeds were 
generally orders of magnitude slower than downloading similar .torrents 
from trackers that are restricted to NZ only peers. BT was simply not 
finding many NZ peers to share with. This is non-optimal both in 
download speed and in network utilisation.

The proposal here is to use IP as a crude approximation of network 
proximity. If a system prefers peers that are in the same /n as it to 
peers that are in the same /m, where n<m, it will likely be connecting 
to peers closer to it, and making better use of the network.

-DHTs as a tracker replacement. With the system preferring local peers 
to remote ones, it makes sense to have a discovery system that prefers 
to return them. If you organise the peers in a swarm into a distributed 
hash table, and store the IPs in that table, peers can do queries for 
IPs near theirs. If the peer hash is the IP and so is the data, the 
connection structure for a DHT closely resembles the ideal set of 
connections for the client to download from - several close links and a 
few to distant points on the hash.

-Teredo for NAT traversal. When behind a NAT, Teredo can be used to 
obtain an un-natted IPv6 address instead.

-Estimation of set similarity. The paper at 
http://www.eecs.harvard.edu/~michaelm/postscripts/sigcomm2002.pdf 
describes a means for estimating how similar the set of downloaded 
blocks of two peers are. I haven't had a chance to read this one in 
detail yet, but it looks promising.

-Bloom filters instead of bit fields. For large bitfields representing 
the nodes a peer has, Bloom Filters with an acceptible false-positive 
rate can be used to reduce overhead.


Obviously not all these systems will work well in a single protocol, 
but they all have their own benifits. The right combination of 
technologies could lead to some substantial improvements over BT. In 
particular, Online Codes, Multicast, and Teredo seem particularaly 
promising to me.

-Nick Johnson




More information about the BitTorrent mailing list