Balanced Neighbor Selection for BitTorrent-Like Networks

摘要

In this paper we propose a new way of constructing the evolving graph in BitTorrent (BT) as new peers join the system one by one. The maximum degree in the constructed graph will be O(1) while the diameter will remain O(ln n), with high probability, where n is the number of nodes. Considering a randomized upload policy, we prove that the distribution of b blocks on the overlay generated by our neighbor selection strategy takes O(b + lnn) phases only, with high probability, which is optimal up to a constant factor. It improves the previous upper bound of O(b + (lnn)~2) by Arthur and Panigrahy (SODA'06). Besides theoretical analysis, thorough simulations have been done to validate our algorithm and demonstrate its applicability in the BT network.