[bittorrent] New P2P protocols

arachnid at notdot.net arachnid at notdot.net
Sat Mar 26 18:27:10 EST 2005

Justin Cormack wrote:

> 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?
Yes. Digital Fountain have a patent on nearly every concievable 
variation on their original invention. Online codes are a substantial 
improvement, but are still covered. I meant to mention this, but 
On the plus side, I live in NZ, and they don't apply to me. ;)

>> -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).
True, but probabilistic verification coupled with publisher-specific 
hashes reduce the cost substantially.

>> -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.
I disagree. P2P is massively inefficient - it consumes large amounts of 
bandwidth with the same traffic going backwards and forwards over the 
same links. Especially in restricted environments like ISPs and 
University networks, with shared bandwidth, Multicast can massively 
decrease the required bandwidth by allowing multiple recipients to get 
the benifit of a single transmission.

>> -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.
Hence the structure of a DHT, where peers have several links to close 
peers and a few links to remote peers. Bifurcation isn't really an 
issue for the same reason. These problems have already been encountered 
and mostly solved for DHTs.

>> 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.
> Obviously not all these systems will work well in a single protocol,
> Have you got a plan of action?
Our working plan was a BT-like system, with merkle-trees for hashing, 
potentially a DHT for peer tracking (though that is still being argued 
about), peer locality estimation for greater efficiency, and a 
multicast mode for networks that support it, making use of online codes 
to eliminate the need for retransmissions, and to allow anyone to come 
in at any stage.
For the multicast mode, peers would publish any number of streams, 
transmitting at bitrates that are powers of two. Each would have its 
own list of 'active' subscribers recorded, and the piece transmitted on 
that channel at any one time would be the piece fewest of the 'active' 
subscribers currently have.

-Nick Johnson

More information about the BitTorrent mailing list