[bittorrent] New P2P protocols

David P. Mott dpmott at sep.com
Mon Mar 28 13:14:38 EST 2005

> Date: Sun, 27 Mar 2005 17:01:07 PDT
> From: mgp at ucla.edu
> Subject: Re: [bittorrent] New P2P protocols
> For anyone wondering what this whole online/rateless codes and Digital
> Fountain thing is, read this for a excellent high-level description:
> http://www.eecs.harvard.edu/~michaelm/postscripts/itw2004.pdf
> [1] http://www.rateless.com/msd.ps, http://www.rateless.com/oncodes.pdf
> [2] http://www.rateless.com

That reference on digital fountains (itw2004.pdf) was much appreciated.

I'd like to suggest, if someone has started a wiki somewhere, that we add 
a page with links like these for historical reference.

The thing that I did *not* get out of that paper was this: about how much 
more or less data (codes) would a client need to receive, in order to 
recreate the original content?  I got out of it that the client could 
recreate the actual content with a high degree of probability by use of 
some randomness, but I didn't grok how the client would know when it 
succeeded, or what percentage of all codes would need to be received in 
order to finish early.

I'm also a little fuzzy about the codes themselves -- are they data, or a 
symbol that represents a (potentially much larger) chunk of data?  If the 
latter, then you can't represent all possible chunks of data with a 16-bit 
code, so how does that work?

Without those answers, I can't get my brain wrapped around how much more 
bandwidth-efficient the fountain codes would be over just propogating 
chunks of binary data from one peer to another in a BT-like network. 
Granted, I just read that paper over lunch, and I haven't gone back for a 

(Could anyone clear that up for me?  I'd be happy with an individual 
email if you don't want to post it for everyone... thanks.)

However, there are other techniques described in that paper, specifically 
centering around the use of TCP connections and N:1 and N:N distributions 
that seem unrelated to fountain codes and which could be applied to a 
BT-like system.  Specifically, asking a peer to stream a number of 
chunks/blocks/codes to you at a specified rate seems appealing. 
Depending on the implementation, a clever client could request and receive 
data in roughly linear order, well enough to facilitate real-time 
streaming of data without lots of overhead like handshaking, pervasive 
have messages, unexpected blocking, etc.  I've wanted for a long time the 
ability to ask a peer for a number of chunks (or a range of chunks) and 
just have them send those to me as they get around to it.

I could suggest a set of messages that could facilitate this, if anyone's 
interested.  For now, I'll just ask, what do people think of that?


More information about the BitTorrent mailing list