[bittorrent] New P2P protocols
arachnid at notdot.net
Fri Mar 25 21:28:44 EST 2005
On 25/03/2005, at 10:01 PM, Bill Cox wrote:
> The most exciting aspect of this new group to me is
> the possibility that
> we may be able to come up with some new protocols.
> Since these will not
> be BitTorrent (though BT-like), we were not allowed to
> discuss them
> before in detail. So, for example, we should now be
> free to come up
> with a way of actually agreeing on and implementing a
> new protocol.
A friend and I have been working on the design for a protocol similar
to BT ourselves. This is probably a good time and place to share our
-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
file, such that a peer collecting any subset of them totalling a little
more (about 103% to 105%) than the original filesize can reconstruct
the original file. Using this, seeds can continually churn out new
encoded blocks, while peers redistribute the ones they already have,
resulting in a situation where nearly every peer has something useful
to exchange with any other peer, and eliminating any need for
-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
-Multicast. Online codes applied to encoding a single chunk into 1k
encoded blocks provide an ideal multicast platform: A server can
multicast encoded packets to multiple listeners, and they need only
recieve a sufficient quantity to reconstruct the chunk. Our working
idea for this is to have multiple multicast channels at different
bitrates, each transmitting encoded chunks of the most wanted block by
that channel's listeners. Since each channel has a different rate,
listeners can subscribe to whatever set of channels makes best use of
its available bandwidth.
We believe multicast of any form would be a major boost to a BT-like
file distribution system. While most of the Internet does not have
multicast deployed, there are plenty of areas that do - for example,
university networks, which are often particularaly popular places to
use systems like BT. Having a major file distribution system use
Multicast would provide a substantial incentive for ISPs to implement
multicast, too. Any ISP implementing multicast would immediately see a
drop in incoming and outgoing traffic as peers swap chunks between
themselves on that ISP's network.
-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
example, downloading a .torrent on a system with very asymmetric
bandwidth (1mbit international, 100mbit New Zealand), the speeds were
generally orders of magnitude slower than downloading similar .torrents
from trackers that are restricted to NZ only peers. BT was simply not
finding many NZ peers to share with. This is non-optimal both in
download speed and in network utilisation.
The proposal here is to use IP as a crude approximation of network
proximity. If a system prefers peers that are in the same /n as it to
peers that are in the same /m, where n<m, it will likely be connecting
to peers closer to it, and making better use of the network.
-DHTs as a tracker replacement. With the system preferring local peers
to remote ones, it makes sense to have a discovery system that prefers
to return them. If you organise the peers in a swarm into a distributed
hash table, and store the IPs in that table, peers can do queries for
IPs near theirs. If the peer hash is the IP and so is the data, the
connection structure for a DHT closely resembles the ideal set of
connections for the client to download from - several close links and a
few to distant points on the hash.
-Teredo for NAT traversal. When behind a NAT, Teredo can be used to
obtain an un-natted IPv6 address instead.
-Estimation of set similarity. The paper at
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.
-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.
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.
More information about the BitTorrent