BitTorrent下基于文件可获得性的节点选择算法研究_硕士学位论文

硕士学位论文 BitTorrent下基于文件可获得性的 节点选择算法研究

学位申请人 ： 学科专业 ： 计算机软件与理论 指导教师 ： 答辩日期 ： A Thesis Submitted to Huazhong University of Science and Technology for the Degree of Master of Engineering

Research of Peer Selection Algorithm Based on File Availability in BitTorrent System

Candidate : He Jilao Major : Computer Software and Theory Supervisor : Prof. Lu Yansheng

Huazhong University of Science and Technology Wuhan 430074, P.R.China June, 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协议 II

Abstract Peer-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 protocol III

目 录 摘要 ........................................................................................................................................ I Abstract .............................................................................................................................. II 1 绪言

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 邻居节点选择算法 ................................................................................................ (21) 3.3 基于文件可获得性的改进策略 ........................................................................ (24) 3.4 本章小结 .................................................................................................................. (27) 4 原型系统设计与实现