The code-named research project “Avalanche” studies how to enable a cost effective, internet scalable and very fast file distribution solution (e.g. for TV on-demand, patches, software distribution). Such an approach leverages desktop PCs to aid in the distribution process, relieving congested servers and network links from most of the traffic.

Details

Existing Peer-Assisted file delivery systems use swarming techniques to simultaneously obtain different pieces of a file from multiple nodes. One problem of such systems is that as the number of receivers increases it becomes harder to do optimal scheduling of pieces to nodes. One possible solution is to use a heuristic that prioritizes exchanges of “locally rarest” pieces. But such local-rarest policies often fail to identify the “globally rarest” piece when peers have a limited view of the network. The end result is slower downloads, stalled transfers, etc.

The Avalanche model fixes these problems using network coding. Instead of distributing the blocks of the file, peers produce linear combinations of the blocks they already hold. Such combinations are distributed together with a tag that describes the parameters in the combination. Any peer can generate new unique combinations from the combinations it already has. When a peer has enough independent combinations, it can decode and build the original file.

Such encoding ensures that any piece uploaded by a given peer can be of use to any other peer. Peers do not need to find specific pieces in the system to complete, any subset encoded piece will suffice. This makes the system very robust as peers disconnect. Also, no peer becomes a bottleneck, since no block is more important than another. Finally, network bandwidth is efficiently utilized since the same information does not travel multiple times over bottleneck links.

And all this is achieved with zero-information of who has what, no knowledge of the network topology or available bandwidth, and negligible-overhead, which greatly simplifies the system design.

In our research papers we present a study of different file swarming strategies (i.e. random, local rarest, global rarest, source coding, and network coding) and show that significant benefits can be expected from using technology based on the Avalanche principles.

Security

The Avalanche model includes strong security to ensure content providers are uniquely identifiable, and to prevent unauthorized parties from offering content for download. The project also ensures content downloaded to each client machine is exactly the same as the content shared by the content provider.