Title :
Analysis of Content Availability Optimization in BitTorrent
Author :
Wu Chehai ; Lu Xianliang ; Duan Hancong ; Tang Hui ; Zhou Xu ; Zhao Zhijun
Author_Institution :
Univ. of Electron. Sci. & Technol. of China, Chengdu
Abstract :
BitTorrent now is one of the most popular peer-to-peer content distribution networks. In BitTorrent, peers exchange content pieces with their neighbors on an overlay to distribute content. In order to accelerate the distribution, content availability, the overall disjointness of content pieces among peers on the overlay, should be optimized. In this paper, we investigate the problem of maximizing content availability in BitTorrent. Using computing theory we first prove that this optimization problem is an NP-optimization problem and so no polynomial time algorithm is available unless P=NP. Further, we employ probability theory to analyze BitTorrent´s solution to the problem, which is just a simple random overlay. We find that BitTorrent´s random overlay has near-optimal content availability with high probability as well as good adaptivity to the real Internet environment, so we infer that the random overlay is enough for content availability optimization. Finally, a simulation-based comparison with an existing heuristic algorithm is presented to validate our analysis and findings
Keywords :
Internet; computational complexity; content management; optimisation; peer-to-peer computing; BitTorrent; NP-optimization problem; peer-to-peer content distribution networks; probability theory; simple random overlay; Acceleration; Acoustics; Algorithm design and analysis; Analytical models; Availability; Games; Internet; Mathematical model; Peer to peer computing; Polynomials;
Conference_Titel :
Hybrid Information Technology, 2006. ICHIT '06. International Conference on
Conference_Location :
Cheju Island
Print_ISBN :
0-7695-2674-8
DOI :
10.1109/ICHIT.2006.253538