Microsoft Gets Very Own BitTorrent

By Jon Newton 6/20/05

Two researchers, one from Microsoft, believe they’ve gone one (or two, or even three) better than BitTorrent.

And that’s interesting given that Bill and the Boyz have now firmly committed themselves to the Good Fight alongside the movie studio cartel, whose punch-drunk MPAA is spearheading a movement against BitTorrent.

The MStorrent p2p application is called Avalanche where Bram Cohen's choice of a metaphor for his BitTorrent was a tsunami wave.

Jon Newton

The MStorrent p2p application is from Christos Gkantsidis at the College of Computing Georgia Institute of Technology, and Pablo Rodriguez Rodriguez from Microsoft Research in Cambridge, England.

They don't touch on how the Microsoft BitTorrent would be ‘legal’ where the BT BitTorrent raises the wrath of the MPAA (Motion Picture Association of America). Nor do they have anything to say about DRM. So is Avalanche naught but smoke? And maybe mirrors?

David Hales and Simon Patarin recently published How to cheat BitTorrent and why nobody does, a paper which hit the virtual streets running and which is still going strong.

p2pnet asked Hales what he thought of Avalanche.

“From my quick scan of the paper, it looks like a clever way of keeping information moving between peers and avoiding bottlenecks (where everyone is waiting for one block) by re-coding blocks at peers incorporating information from several blocks,” he told us.

“But without a more detailed examination it's unclear to me exactly how this is being done and if the increases would be as dramatic as they say they would be - though it looks like in some contexts they would be.”

You can read the Microsoft paper here.

For now, here’s Gkantsidis’ and Rodriguez’s Summary and Further Directions.

Read on >>>>>>>>>>>>>>>>>>>>>>>>

We propose a new content distribution system that uses network coding. Unlike other systems based on network coding, our approach targets the distribution of large files in a dynamic environment where nodes cooperate. Our system does not require any centralized knowledge of the network topology and nodes make decisions of how to propagate blocks of information based only on local information.

The main advantage of using network coding for distributing large files is that the scheduling of the content propagation in the overlay network is much easier. Deciding on the correct block of information to transmit to another node is difficult without global information; the transmitted packet is useful to the receiving node, but, may not be useful to other downstream nodes. With network coding, each generated block is a combination of all the blocks available to the transmitter and thus, if any of them is useful downstream, then the generated block will also be useful.

We have demonstrated through extensive simulations the performance advantages of using network coding over transmitting unencoded information and over coding at the source only in scenarios of practical interest. Network coding performs better when the nodes have heterogeneous access capacities, when the arrivals and departures of the nodes are not synchronized, when there are natural bottlenecks in the overlay topology (that need to be utilized as best as possible), and when incentive mechanisms are in place to discourage freeriders. The performance benefits provided by network coding in terms of throughput are more than 20-30% compared to coding at the server, and can be more than 2-3 times better compared to transmitting unencoded blocks. Moreover, we have observed that with network coding the system is much more robust to server and node departures.

Despite the rich literature in network coding, we are not aware of any operational content distribution network that uses network coding. Based on the system presented in this paper, we have implemented Avalanche, a real system using network coding. Through Avalanche, we are currently investigating the benefits of using network coding to distribute very large files to a large number of users in realistic settings.

During the design and implementation of Avalanche we have identified various practical issues related to network coding. The most important of them is the speed of encoding and decoding. Recall that during encoding we combine all available blocks and this is an O(k) operation, where k is the number of the blocks of the file. During decoding, we invert a k×k matrix in O(k3) and then reconstruct the original file in O(k2). (In our system the reconstruction cost dominates the running time because it involves many reads of large blocks from the hard disk; whereas the inversion of the coefficient matrix can be done in memory.) We are currently considering techniques inspired from sparse codes to increase the encoding and decoding rates, which allow us to encode/decode files of more than 4 GB with very low overhead.

Another major concern in any content distribution scheme is the protection against malicious nodes. A malicious node can introduce arbitrary blocks in the system and make the reconstruction of the original file impossible. When the nodes do not perform coding, the server can digitally sign the packets transmitted and, thus, protect against malicious users. Digitally signing is more difficult when rateless codes are used, but recently demonstrated how homomorphic collision-resistant hash functions can be used to provide protection in that case. Similar schemes can be used to provide protection when network coding is in place. In Avalanche we use special sets of secure hash functions that survive network coding operations and consume very little computational resources, as opposed to traditional homomorphic hashes


Jon Newton is the editor of and is a regular contributer to MP3 Newswire. Jon's site is devoted to the politics of digital music and his insights as well as those of his co-writers can be read there. We urge you to explore it.


The Sony PSP is available on Amazon

Other MP3 stories:
MP3 Players for Summer 2005 Part I
MP3 Players for Summer 2005 Part II
Sony PSP As Personal Media Player - Review


Back to