Avalanche: File Swarming with Network Coding

---

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.

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 this research paper and slides 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.

Contacts:

• Christos Gkantsidis, John Miller, Mitch Goldberg (MSR Cambridge)

Former members:

• Pablo Rodriguez (Now with Telefonica Research), Manuel Costa

Collaborators:

• Phil Chou, Kamal Jain (MSR Redmond)

Research Publications:

• "Comprehensive view of a Live Network Coding P2P system", C. Gkantsidis, J. Miller, P. Rodriguez, ACM SIGCOMM/USENIX IMC'06, Brasil. Oct 2006.

• "Anatomy of a P2P Content Distribution System with Network Coding", C. Gkantsidis, J. Miller, P. Rodriguez, IPTPS'06 Santa Barbara, CA, February 2006.

• "Network Coding for Large Scale Content Distribution", C. Gkantsidis, P. Rodriguez, IEEE/INFOCOM'05, Miami. March 2005. (Also Microsoft Research Technical Report, MSR-TR-2004-80).

Related Research Work:

• Seminal work on network coding by R. Ahlswede et al.

• Ralf Koetter's Network Coding page (http://www.networkcoding.info)

• Network Coding: an instant premier (Christina Fragouli et al.) 

• Phil Chou's Web page and tutorial on Network Coding

• Muriel's Medard (MIT) page on Random Network Coding with a good selection of papers.

• Rateless Codes (Petar Maymounkov)

• Digital Fountain (Michael Luby)

---

Note (22/07/05): 

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.

---