[bittorrent] New P2P protocols

Justin Cormack justin at street-vision.com
Sat Mar 26 08:00:51 EST 2005

On Sat, 2005-03-26 at 14:28 +1200, Nick Johnson wrote:
> -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 

You know the patent situation on this?

> -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.

Thats quite interesting, had assumed there was no way to verify rateless
codes on the fly. Reading the paper, there are still potential problems
(and computation cost is very high).

> -Multicast. Online codes applied to encoding a single chunk into 1k 

P2P replaces multicast with something better designed that works on
internet scale or local scale. Traditional multicast on large scale will
never happen in the real world.

> -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 

The problem with this is if no one in your area has some pieces, eg if
there are no seeds there it simply wont work. So be careful here.

> -DHTs as a tracker replacement. With the system preferring local peers 
> to remote ones, it makes sense to have a discovery system that prefers 

This makes it very easy for swarms to be split apart as they have fewer
connections to other local clusters. One peer going down can split the
swarm, and there may not be a seed in your half.

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

The advantage of Teredo is you dont have to code anything. Set up an
integrated ipv4 and ipv6 based system (this is non trivial) and the
Teredo side of things is not part of the protocol.

> -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.

Will look at this.

> -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.

This came up when we discussed addressing by hash, where it is very
useful. If addressing by block it may or may not be.

> 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.

Have you got a plan of action?

More information about the BitTorrent mailing list