分 类 号 学 号 2005612100177学校代码 10487 密 级 硕士学位论文BitTorrent 下基于文件可获得性的节点选择算法研究学位申请人 ： 贺记牢学科专业 ： 计算机软件与理论指导教师 ： 卢炎生 教 授答辩日期 ： 2007 年 6 月 2 日A Thesis Submitted to Huazhong University of Science and Technology for the Degree of Master of EngineeringResearch of Peer Selection Algorithm Based on File Availability in BitTorrent SystemCandidate : He JilaoMajor : Computer Software and TheorySupervisor : Prof. Lu YanshengHuazhong University of Science and TechnologyWuhan 430074, P.R.ChinaJune, 2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名：日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密 ，在_年解密后适用本授权书。不保密。（请在以上方框内打“” ）学位论文作者签名： 指导教师签名：日期： 年 月 日 日期： 年 月 日本论文属于I摘要对等计算(P2P)相关的应用在因特网上非常成功。BitTorrent 系统是目前因特网上最大的 P2P 文件共享系统，据统计 2004 年，BitTorrent 协议相关的流量占了因特网总流量的 35%。BitTorrent 系统区别于其他 P2P 系统的关键特点是将文件分成粒度更小的数据分块。只拥有部分文件的用户节点也能向其他用户提供数据分块。这个特性释放了处于下载过程中的用户节点的服务能力，整个 BitTorrent 系统中服务提供者的数量大大增加，系统的服务能力随着用户数的增加呈指数级增长，可扩展性好。BitTorrent 协议中的核心算法是分块选择算法和邻居节点选择算法。大量研究工作表明 BitTorrent 协议中分块副本数量最少优先 (rarest first)策略和阻塞(choke)算法在实际运行中接近于最优，是 BitTorrent 系统成功的关键因素。分块副本数量最少优先(rarest first)策略使各数据分块的副本在 peer 节点之间均匀分布，尽可能的增大 peer 之间交换数据的可能性，避免了数据瓶颈的出现。阻塞(choke)算法则帮助peer 找到合适的服务提供者，加快下载速率。BitTorrent 协议中分块选择算法只考虑了数据分块副本的数量，而忽视了数据分块的可获得性。邻居节点选择算法则近似于一种盲目寻找的策略，可能需要很长的搜寻时间才能找到合适的服务提供者，算法的不确定性、随机性很强。针对文件可获得性，改进了 peer 选择服务提供者的策略，帮助 peer 在尽可能短的时间内找到更合适、更优秀的服务提供者，提高下载速率。实验证明，改进策略在实际运行中比标准策略能提高平均下载速率 20%-30%。关键词： 对等计算; 文件共享; BitTorrent 协议IIAbstractPeer-to-Peer applications are extensively used on internet nowadays, and BitTorrent is one of the most successful P2P file sharing system. Statistics indicates that by the end of 2004, 35% of the internet traffics are caused by BitTorrent protocol.The characteristic that BitTorrent differs from other P2P systems is that it splits the files into smaller pieces. Clients that do not have the whole file can also provide some pieces to other node. So the clients who are in the process of downloading can also be service providers. This remarkably increases the quantities of service providers in BitTorrent system, and thus greatly improves the performance of the system.The key algorithms in BitTorrent protocols are piece selection and node selection. Plenty of studies show that the rarest first strategy and the choke algorithm work well. The first balances the number of copies of each data piece among the BitTorrent nodes to help peers exchange data, and to avoid the bottle-neck. The latter is used by peers to find the appropriate service provider and speed up their downloading.We propose the concept of file availability based on investigations of the BitTorrent protocol. The rarest first piece selection algorithm of BitTorrent protocol only takes the number of piece copies into consideration regardless of their availability. Neighbor nodes selection algorithm is a strategy that search its neighbor peer blindly, and may take quite a long time to reach its appropriate service providers. Based on file availability, we improve the service provider selection strategies to help peers find the right service providers in a relatively short time. Experiment results show that this approach can speed the downloading rates up to 30%.Keywords: P2P computing; file sharing; BitTorrent protocolIII目 录摘要 .IAbstract .II1 绪言1.1 研究背景 .(1)1.2 国内外研究现状 .(3)1.3 本课题研究的目标和意义 .(6)1.4 本文结构 . (6)2 BitTorrent 协议概论 2.1 BitTorrent 网络概览 .(8)2.2 BitTorrent 协议 .(10)2.3 BitTorrent 特点分析 .(14)2.4 本章小结 .(18)3 分块和节点选择算法3.1 分块选择算法 .(19)3.2 邻