Analyzing BitTorrent and Related Peer-to-Peer Networks

We analyze protocols for disseminating a collection of data blocks over a network of peers with a view towards BitTorrent and related peer-to-peer networks. Unlike previous work, we accurately model the distribution of the individual data blocks, a process which is critical to the parallelism that makes Bit Torrent successful in practice. We also consider multiple network topologies and routing algorithms. We first demonstrate several routing algorithms that distribute b data blocks on a network with diameter d and maximum degree D in O(D(b + d)) phases of concurrent downloads with high probability. This is tight within a factor of D. We also specialize to the networks used by Bit Torrent and we improve this bound to O(b In n) phases where is the number of clients. Finally, we discuss several practical extensions to BitTorrent, one of which improves the bound to a near-optimal O(b + (In n)(2)) phases.