一种基于P2P文件共享应用的片段选择算法

A piece selection algorithm for Peer-to-Peer file sharing applications

深入分析了P2P（Peer-to-Peer）文件共享应用中BitTorrent片段选择算法——在Seed的片断分配过程中采用随机的第一个片段选择（Random First Piece，RFP）和最少优先（Rarest First，RF）选择算法来完成对整个文件所有片断的下载的特点，提出了基于Seed控制的片段选择算法（PSASC）。与BitTorrent片段选择算法不同，PSASC通过在Seed上对片段的选择加以控制，从而避免了片段选择的重复性。利用集合覆盖问题和贪婪近似算法对BitTorrent片段选择算法和PSASC算法时间复杂度进行理论分析，并进行了仿真实验。结果表明：PSASC算法的时间复杂度优于BitTorrent片段选择算法，大大缩短了Seed上的所有片段分发到P2P网络中的时间。

Having investigated the features of piece selection algorithm of BitTorrent, Random First Piece （RFP） and Rarest First （RF）, a new piece selection algorithm, the Piece Selection Algorithm based on Seed Control （PSASC） is presented in this paper. Compared with the piece selection algorithm of BitTorrent, the PSASC requires Seed to control the piece selection to avoid the repetition of piece selection. The-set-covering problem and greedy approximation algorithm are utilized to analyze time complexities of piece selection algorithm of BitTorrent and PSASC, and the simulation is given. Results demonstrate that time complexity of PSASC outperforms that of PRF and RF of BitTorrent, and the PSASC can greatly shorten the time that all pieces on Secd are allocated into P2P （Peer-to-Peer） networks.