[bittorrent] New P2P protocols

Justin Cormack justin at street-vision.com
Sat Mar 26 18:57:29 EST 2005


On Sun, 2005-03-27 at 10:04 +1200, Nick Johnson wrote:
> 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 forgot.
> On the plus side, I live in NZ, and they don't apply to me. ;)

I dont live in the US either. But software that is not usable there is a
problem.

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

Yes. I read it more as a demonstration that there are possibilities that
might work, but I am not sure that the one in the paper is really useful
as such. It is interesting. Try it and see...

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

In BT, multiple recipients get the benefit of a single point to point
transmission. Multicast isnt free, it uses links in a tree structure.
P2P uses links in a graph structure. Multicast is an attempt to do the
same as peer to peer with a perfect tree structured routing aware
network. P2P is an attempt to do an approcimate resilient fault tolerant
version, generally using worse metrics than the current routing topology
(though as you point out you can use closer approximations). Its a
different approach to the same problem. Remember multicast is just a bit
of software replicating traffic too.

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

My main problem with DHTs is the computational cost when peers are added
and leave all the time. It seems to me from a quick look at 15 or so
papers that it may not work in practise with constant leaving and
arrivals. Also the incentive structure to correctly route is not clear.
In a nice stable cooperative situation I think it is a nice solution.
Happy if you have counterexamples, but I am currently a sceptic.

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

Sounds interesting. I would try to make a plan that can somehow be tried
incrementally, or with different bits independent. Or build some sort of
simulator/testbed. Which we need to do for BT changes too anyway.

Why not try to make a DHT based distributed tracker for BT as it is now
and see if that works... its a smaller project to start with and would
be a good thing to get working as a standalone project...





More information about the BitTorrent mailing list