[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
> 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
> 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
> 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.
More information about the BitTorrent