On a balanced neighbor selection strategy for tracker-based peer-to-peer networks

In this paper we introduce a novel neighbor selection strategy for tracker-based peer-to-peer systems like BitTorrent that can uniformly distribute the load among peers in the network. Our method is based on a balanced multiple choice algorithm which takes into account not only the actual load of a peer, but the possibility as well that it will be selected in the future. We first analyze the properties of the constructed overlay topology theoretically, proving that, the maximum degree in the constructed graph is O(1) while the diameter remains O(ln n), with high probability, where n is the number of nodes. Considering a randomized upload policy, we show that the full distribution of b blocks on the network generated by our neighbor selection strategy takes O(b + ln n) phases only, with high probability, which is optimal up to a constant factor. This result improves the previous upper bound of O(b+(ln n)²) by Arthur and Panigrahy (SODA´06). In order to adapt our algorithm in real BitTorrent networks only a slight modification of the tracker is necessary without any change in the clients. Besides theoretical analysis, thorough simulations have been done to validate our algorithm and show its applicability in real BitTorrent networks. To this end, we have extended the BitTorrent implementation of the PeerSim simulation framework with a new tracker using our balanced neighbor selection strategy and demonstrated that it can speed up the file-sharing process in heavy loaded situations.