基于bittorrent文件可获得性策略

分类号学号2005612100177学校代码10487密级硕士学位论文BITTORRENT下基于文件可获得性的节点选择算法研究学位申请人贺记牢学科专业计算机软件与理论指导教师卢炎生教授答辩日期2007年6月2日ATHESISSUBMITTEDTOHUAZHONGUNIVERSITYOFSCIENCEANDTECHNOLOGYFORTHEDEGREEOFMASTEROFENGINEERINGRESEARCHOFPEERSELECTIONALGORITHMBASEDONFILEAVAILABILITYINBITTORRENTSYSTEMCANDIDATEHEJILAOMAJORCOMPUTERSOFTWAREANDTHEORYSUPERVISORPROFLUYANSHENGHUAZHONGUNIVERSITYOFSCIENCEANDTECHNOLOGYWUHAN430074,PRCHINAJUNE,2007独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。学位论文作者签名日期年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密，在_年解密后适用本授权书。不保密。（请在以上方框内打“”）学位论文作者签名指导教师签名日期年月日日期年月日本论文属于摘要对等计算P2P相关的应用在因特网上非常成功。BITTORRENT系统是目前因特网上最大的P2P文件共享系统，据统计2004年，BITTORRENT协议相关的流量占了因特网总流量的35。BITTORRENT系统区别于其他P2P系统的关键特点是将文件分成粒度更小的数据分块。只拥有部分文件的用户节点也能向其他用户提供数据分块。这个特性释放了处于下载过程中的用户节点的服务能力，整个BITTORRENT系统中服务提供者的数量大大增加，系统的服务能力随着用户数的增加呈指数级增长，可扩展性好。BITTORRENT协议中的核心算法是分块选择算法和邻居节点选择算法。大量研究工作表明BITTORRENT协议中分块副本数量最少优先RARESTFIRST策略和阻塞CHOKE算法在实际运行中接近于最优，是BITTORRENT系统成功的关键因素。分块副本数量最少优先RARESTFIRST策略使各数据分块的副本在PEER节点之间均匀分布，尽可能的增大PEER之间交换数据的可能性，避免了数据瓶颈的出现。阻塞CHOKE算法则帮助PEER找到合适的服务提供者，加快下载速率。BITTORRENT协议中分块选择算法只考虑了数据分块副本的数量，而忽视了数据分块的可获得性。邻居节点选择算法则近似于一种盲目寻找的策略，可能需要很长的搜寻时间才能找到合适的服务提供者，算法的不确定性、随机性很强。针对文件可获得性，改进了PEER选择服务提供者的策略，帮助PEER在尽可能短的时间内找到更合适、更优秀的服务提供者，提高下载速率。实验证明，改进策略在实际运行中比标准策略能提高平均下载速率2030。关键词对等计算文件共享BITTORRENT协议ABSTRACTPEERTOPEERAPPLICATIONSAREEXTENSIVELYUSEDONINTERNETNOWADAYS,ANDBITTORRENTISONEOFTHEMOSTSUCCESSFULP2PFILESHARINGSYSTEMSTATISTICSINDICATESTHATBYTHEENDOF2004,35OFTHEINTERNETTRAFFICSARECAUSEDBYBITTORRENTPROTOCOLTHECHARACTERISTICTHATBITTORRENTDIFFERSFROMOTHERP2PSYSTEMSISTHATITSPLITSTHEFILESINTOSMALLERPIECESCLIENTSTHATDONOTHAVETHEWHOLEFILECANALSOPROVIDESOMEPIECESTOOTHERNODESOTHECLIENTSWHOAREINTHEPROCESSOFDOWNLOADINGCANALSOBESERVICEPROVIDERSTHISREMARKABLYINCREASESTHEQUANTITIESOFSERVICEPROVIDERSINBITTORRENTSYSTEM,ANDTHUSGREATLYIMPROVESTHEPERFORMANCEOFTHESYSTEMTHEKEYALGORITHMSINBITTORRENTPROTOCOLSAREPIECESELECTIONANDNODESELECTIONPLENTYOFSTUDIESSHOWTHATTHERARESTFIRSTSTRATEGYANDTHECHOKEALGORITHMWORKWELLTHEFIRSTBALANCESTHENUMBEROFCOPIESOFEACHDATAPIECEAMONGTHEBITTORRENTNODESTOHELPPEERSEXCHANGEDATA,ANDTOAVOIDTHEBOTTLENECKTHELATTERISUSEDBYPEERSTOFINDTHEAPPROPRIATESERVICEPROVIDERANDSPEEDUPTHEIRDOWNLOADINGWEPROPOSETHECONCEPTOFFILEAVAILABILITYBASEDONINVESTIGATIONSOFTHEBITTORRENTPROTOCOLTHERARESTFIRSTPIECESELECTIONALGORITHMOFBITTORRENTPROTOCOLONLYTAKESTHENUMBEROFPIECECOPIESINTOCONSIDERATIONREGARDLESSOFTHEIRAVAILABILITYNEIGHBORNODESSELECTIONALGORITHMISASTRATEGYTHATSEARCHITSNEIGHBORPEERBLINDLY,ANDMAYTAKEQUITEALONGTIMETOREACHITSAPPROPRIATESERVICEPROVIDERSBASEDONFILEAVAILABILITY,WEIMPROVETHESERVICEPROVIDERSELECTIONSTRATEGIESTOHELPPEERSFINDTHERIGHTSERVICEPROVIDERSINARELATIVELYSHORTTIMEEXPERIMENTRESULTSSHOWTHATTHISAPPROACHCANSPEEDTHEDOWNLOADINGRATESUPTO30KEYWORDSP2PCOMPUTINGFILESHARINGBITTORRENTPROTOCOL目录摘要IABSTRACTII1绪言11研究背景112国内外研究现状313本课题研究的目标和意义614本文结构62BITTORRENT协议概论21BITTORRENT网络概览822BITTORRENT协议1023BITTORRENT特点分析1424本章小结183分块和节点选择算法31分块选择算法1932邻居节点选择算法2133基于文件可获得性的改进策略2434本章小结274原型系统设计与实现41原型系统设计思想2842原型系统设计与实现关键技术2843实验与性能分析3444本章小结365结束语51本文总结3752下一步工作38致谢39参考文献401绪言11研究背景111对等计算PEERTOPEER,P2P现在，互联网上各种对等计算P2P的应用早已屡见不鲜。但是在业界，却始终没有一个对P2P的统一的定义。P2P相关的概念几乎同时在计算机研究界和产业界产生。1999年，ZHANGHUI1和PAULFRANCIS分别由IP层多播研究提出了应用层多播APPLICATIONMULTICAST的概念。应用层多播的概念出现后不久，计算机网络研究界又提出了覆盖网OVERLAY的概念。几乎在同一时期，计算机产业界中出现了几个非常有影响力的系统，NAPSTER和GNUTELLA，其里面用到的技术就是现在对等计算技术的前身。应用层多播和覆盖网在随后的研究中相互渗透，慢慢融合，并和计算机产业界的技术相结合，产生了对等计算技术。对等计算技术的涵义十分广泛，从不同角度可以得到不同的理解。INTEL将P2P计算定义为“通过系统间的直接交换所达成的计算机资源与信息的共享”，这些资源与服务包括信息交换、处理器时钟、缓存和磁盘空间等；IBM则给P2P赋予更广阔的定义，把它看成是由若干互联协作的计算机构成的系统并具备如下若干特性之一系统依存于边缘化非中央式服务器设备的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中成员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在构成一个虚拟或实际的群体。从已有的研究成果来看2,3,4,5,6,7，大致可以归纳出P2P技术具有以下一些共同特性1分布式对等网络由分布在各处的节点组成，节点之间没有任何联系。节点之间可以直接建立连接，传播消息和数据，不需要中间实体或者服务器的介入，属于纯分布式系统。2规模大，可扩展性好在P2P网络中，PEER之间通过消息维护一种松散的连接状态，PEER完全通过自组织SELFORGANIZE构成系统。随着用户的不断加入，服务的需求随之增加，而同时，整个系统的资源和服务能力也得到了扩充。因此，P2P网络不会出现随着用户增加而服务容量也迅速饱和的情况。理论上来说，P2P网络的服务容量是无限的。3动态性强在P2P网络中，PEER可以随时加入和退出网络。且由于PEER节点多是普通用户，和专门配置的服务器相比，主机故障和网络故障的概率较高，节点可靠性差。P2P网络必须能快速调整拓扑结构，适应网络的动态变化。P2P技术打破了传统的客户机/服务器模式，在对等网络中每个节点的地位都是相同的，具备客户端和服务器双重身份，可以同时作为服务的使用者和服务的提供者而存在。112因特网数据传输数据传输是因特网的核心应用。广义的数据包括所有二进制形式的数据，狭义的数据包括文本、图片、语音、多媒体等各种格式的文件。早期的数据传输基本上都是客户/服务器模式。一个或多个服务器给大量的客户提供服务。随着客户数量的快速增长，数据量的极速膨胀，服务器端的负载越来越重，不堪重负。服务器处理性能和出口带宽的增长远远落后于客户请求增长的速度。内容分发网络CONTENTDELIVERYNETWORK,CDN8,9技术的出现一度缓解了客户端和服务器日益扩大的供需矛盾。通过在因特网上配置大量的边缘服务器，将用户请求定向或重定向到相应的边缘服务器，实现了在大量边缘服务器之间负载均衡，（扩展）提升了整个服务器群的处理请求能力，大大提高了服务器群可同时服务的客户端数，提高了服务质量。随着各种新的应用的出现，在大文件分发给CDN网络带来了巨大的挑战。一个文件动则数百兆，服务一个用户通常需要数小时，这种情形大大限制了CDN网络服务的用户数。仅仅依靠服务器，再多的服务器也会被飞速增加的用户蚕食。服务器端性能再次成为数据传输的瓶颈。对等计算技术能有效的解决这个问题。通过把终端客户自组织起来，利用终端客户之间的协作，PEER之间相互提供服务，系统总服务能力随着终端客户的数量成指数级增长，有效的对抗了客户请求的增长。113对等计算技术的主要应用当前对等计算P2P技术主要应用在以下领域流媒体分发利用对等计算技术来分发实时性很强的流媒体数据，P2P直播和点播技术目前已非常成熟，有大量的商用系统出现，提供可靠、稳定的服务。还有VOIP，通过P2P技术，在因特网中传输实时话音数据，虽然和电信骨干网能提供的话音服务尚有差距，但当前VOIP系统的服务质量已大大改善，已能满足大多数用户的需求。文件存储将对等计算技术和传统的文件系统技术相结合，利用P2P网络中终端用户的带宽和硬盘空间资源，可以构造出一个容量和服务能力巨大的存储系统。文件共享利用对等计算技术来分发大文件，在大量终端用户之间共享文件。将大量终端用户组织在一起，形成应用层覆盖网OVERLAY，PEER之间通过应用层消息来定位文件和传输文件数据，构成一个大型的文件共享、分发系统。12国内外研究现状本文的研究对象是BITTORRENT这一当前因特网上最大，最成功的P2P文件共享系统。2003年，BITTORRENT协议的创造者BRAMCOHEN10在BITTORRENT软件发布一年多之后，发表了一篇短文，详细介绍了他在BITTORRENT协议中采用的核心算法。自此之后，BITTORRENT系统因其巨大的成功在计算机软件产业界和研究界产生重大的影响，越来越引起研究界的关注，相关的研究工作大致可以分为如下几个方面。1系统整体性能建模和测量QIU11等在以前研究12基础上提出用流体模型FLUIDMODEL对BITTORRENT类似系统建模，理论上分析了BITTORRENT系统在系统处于稳态时的性能。他们的分析结果表明大量PEER节点加入BITTORRENT系统并不会影响PEER的平均下载完成时间，单个PEER从系统中获得的下载服务并没因其他PEER的加入而降低，说明整个系统的服务能力随着PEER节点的增加在随之增长，BITTORRENT系统充分利用了系统中所有PEER的服务能力和上传带宽，可扩展性非常好。GUO13等做了大量的测量工作，他们和因特网服务提供商ISP和因特网用户接入端合作，截获了大量BITTORRENT协议的流量数据，对数据进行分析和理论回归，得到了BITTORRENT系统的各种系统参数，并利用这些参数对QIU等提出的模型进行了改进。指出随着加入某一TORRENT的用户数越来越少，下载完成的用户逐渐退出系统，分发某一文件的TORRENT会慢慢死亡，即该TORRENT内不再拥有一份完整的文件数据副本，不能给用户提供完整的下载服务。针对这一缺点，他们提出在多个TORRENT之间协作，延缓TORRENT的死亡，提升BITTORRENT系统的性能。香港中文大学的TIAN14等对从BITTORRENT系统PEER拥有数据量多少的角度出发，对处于不同下载阶段PEER数的分布进行了建模分析，他们的模型结果揭示了系统处于不同下载状态的PEER数呈U型分布，即系统中处于下载初期，拥有数据少的PEER和下载末期，拥有数据多，快结束下载的PEER占很大部分比例，处于下载过程中期的PEER数则相对较少。2系统核心算法的研究ARNAULDLEGOUT15等大量的实际测量数据出发，提出了BITTORRENT协议中核心算法在实际运行中接近于最优的观点，并详细分析大量实际测量数据证明其观点。他们开发了一个功能增强的BITTORRENT协议客户端。从实际因特网中挑选代表性比较强的下载任务，把他们的客户端加入到实际的数据分发网络中，主动的收集BITTORRENT协议相关的消息和数据，观测BITTORRENT协议实际运行的数据。他们的实验证明RARESTFIRST的分块选择算法和TITFORTAT的阻塞和解除阻塞的算法在真实因特网环境中表现十分优异，接近于最优。由于在真实因特网环境下，实际测量很难覆盖整个完整的BITTORRENT系统。ASHWINBHARAMBE16等完全从仿真的角度出发，构造了一个BITTORRENT协议仿真平台。通过改变仿真系统的各种参数，分析了各种情形下BITTORRENT系统的各种性能指标。他们的仿真研究虽然与实际运行结果有区别，但更详细的揭示了BITTORRENT协议中各种系统实际参数对系统性能的影响，对理解BITTORRENT协议的运行情况大有帮助。3激励机制和安全性研究大量的研究工作表明，现存的P2P文件共享系统，如GNUTELLA，天网MAZE等，大多存在节点自私行为FREERIDER的问题17,18,19,20，即部分PEER节点只从P2P系统中获取服务，下载数据，却从不向系统贡献他们的数据和带宽。自私节点FREERIDER的存在，严重影响P2P文件共享系统的整体服务能力和性能。因此，对于P2P文件共享系统，协议中很重要的一部分就是通过各种激励机制来对抗节点的自私行为，提高系统服务能力。最近一两年有许多关于BITTORRENT协议的激励机制和安全性工作2026。ARNAULDLEGOUT等的研究工作和实际测量表明BITTORRENT协议中基于TITFORTAT的阻塞和解除阻塞算法是一种目前比较有效的激励机制，能有效的增强系统中PEER之间的相互贡献，相互协作。也有其他一些研究工作证实BITTORRENT协议中基于TITFORTAT的阻塞和解除阻塞算法并不能完全杜绝节点的自私行为。NLIOGKAS24和MICHAELSIRIVIANOS等分别报告了多种BITTORRENT协议的漏洞，这些漏洞可被恶意PEER节点用来实现他们的自私行为。国内关于P2P文件共享系统的研究也非常多。北京大学计算机网络和分布式系统实验室，以教育网内最大的文件共享系统MAZE为实验研究平台20,27。MAZE系统是该实验室完全自主研制和运营的P2P文件共享系统，在教育网内拥有广泛的用户群。通过对整个MAZE系统的控制和监测，该实验室获得了因特网上P2P文件共享系统运行行为的大量真实数据，在系统数据的基础上，对系统中用户的动态加入、退出特性变化，用户自私行为FREERIDE，和文件共享系统激励机制等方面研究很深，取得了国内领先的成就。13本课题研究的目标和意义本课题来源于海装预研项目，网格环境下信息管理和发布技术的研究。块数据传输和文件分发一直是因特网数据传输相关研究的热点。BITTORRENT系统是当前因特网上最成功的P2P文件共享系统，有大量的研究工作与之相关28,29,30。本文对BITTORRENT系统展开了详细的研究，先分析了系统整体服务模型，然后分析和评价BITTORRENT协议中的核心算法，并对核心算法进行改进。通过详细的研究，试图回答以下问题1BITTORRENT系统服务能力强，整体性能好的原因2BITTORRENT系统用哪些核心技术来对抗因特网数据传输面临的问题3BITTORRENT系统存在的缺点和改进。4BITTORRENT协议的成功对今后因特网数据传输协议设计的启示。14本文结构本文第一章介绍P2P技术，当前P2P技术的核心应用领域。详细介绍了BITTORRENT系统相关的国内外研究现状和本文的研究目标。第二章介绍BITTORRENT协议，该协议元数据文件的生成，客户端和追踪服务器通信协议，客户端之间通信协议三部分。然后分析了BITTORRENT系统的特点。第三章介绍BITTORRENT协议中的核心算法，并提出文件可获得性的概念，针对文件可获得性对核心算法进行改进。第四章实现改进策略的BITTORRENT协议客户端。并设计了一系列实验来验证改进策略的有效性。第五章总结全文，指明今后的研究方向。2BITTORRENT协议概论21BITTORRENT网络概览BITTORRENT内容分发网络是一个基于BITTORRENT文件分发协议的应用平台，是目前世界上最大的P2P文件共享系统，据统计2004年因特网上70多的网络流量由P2P应用占用，40的网络流量由BITTORRENT协议数据，同时在线的BITTORRENT用户达数千万。BITTORRENT网络是2003年由BRAMCOHEN设计的，一经问世，便以其简单、稳定、高效率的数据传输模式而风靡全球，和其他P2P文件分发协议如NAPSTER，GNUTELLA，EDONKEY/EMULE和KAZAA等一起成为因特网文件共享和分发的杀手级应用KILLERAPPLICATION，在业界引起了巨大的反响。以BITTORRENT为代表的P2P应用在因特网上的巨大成功，引发了计算机网络研究界对P2P内容分发技术的研究热潮。研究界广泛而深入的从各个角度和侧面来分析、研究和改进P2P系统。近7年来，各类学术会议和杂志上研究P2P相关技术的学术论文已达数千篇之多，直接以BITTORRENT系统为研究目标的高档论文也有数十篇。这些论文涵盖了BITTORRENT相关的各个议题，诸如BITTORRENT系统测量与建模，系统动态性分析，BITTORRENT核心协议分析与扩展，P2P系统安全和BITTORRENT协议漏洞分析等等。211BITTORRENT网络的基本组成一个WEB服务器；一个描述该共享文件的元数据文件；一个BITTORRENT追踪服务器TRACKER；一个拥有完整文件的上传者；下载该文件的所有下载客户；下载客户端WEB浏览器。212客户端下载流程终端用户加入BITTORRENT内容分发网络的目的是下载其他用户所共享的文件。终端用户下载文件的过程如下1终端客户浏览WEB站点，下载TORRENT元数据文件；2启动BITTORRENT协议客户端，解析TORRENT文件，连接追踪服务器TRACKER，并定时从TRACKER处获得处于当前TORRENT中其他PEER节点信息。3BITTORRENT客户端通过客户端之间数据传输协议和其他PEER处上传和下载，交换数据，直至下载完成或客户端主动退出。213相关术语BITTORRENT协议一种对等计算P2P的文件分发协议。BITTORRENT系统所有运行BITTORRENT协议的PEER节点相互连接所构成的网络系统。TORRENT同时下载某一文件的PEER节点构成一个TORRENT，只有同一TORRENT内的PEER节点之间才能相互交换该文件数据。SEED种子，指已下载完成整个文件，给其他下载用户上传文件数据的PEER节点。LEECH普通下载PEER节点。PIECEBITTORRENT协议中，文件被分成粒度更小的分块PIECE，分块大小一般为256K。INTERESTEDORNOTBITTORRENT协议中，若PEERB有PEERA所需要的数据分块，则PEERA对PEERB的数据感兴趣，反之则不感兴趣。CHOKEORNOTBITTORRENT协议中，若PEERA不愿向PEERB提供数据，则阻塞CHOKEPEERB，不接受PEERB的数据请求，反之则解除阻塞UNCHOKEPEERB。PEERSET所有和PEERA建立了BITTORRENT协议连接的PEER都属于PEERA的PEER节点集，也称为邻居PEER节点集。LOCALPEER本地PEER，即本地的BITTORRENT协议客户端或本地下载客户。REMOTEPEER和本地PEER建立了BITTORRENT协议连接的PEER，连接的另一方，也称对方PEER。ACTIVEPEERSET每个本地PEER只和其邻居PEER集中的少量PEER交换数据，邻居PEER集的这一子集被称为活跃PEER集。本文中PEER、节点和终端用户等术语之间不做严格区分，可互相替代、混用。22BITTORRENT协议BITTORRENT协议是一个简单、开放的应用层文件分发协议。协议包含三部分元数据信息编码格式，元数据文件格式；客户端和追踪服务器TRACKER通信协议；客户端之间数据传输协议。221元数据信息编码格式元数据文件里面只有四种格式的元素，分别是字符串元素，整型元素，列表元素和字典元素。字符串元素由前缀十进制字符串长度加冒号再跟原字符串组成，比如4SPAM就代表着字符串“SPAM”。整型元素的表示是前面加I，后面加E，中间是十进制数。比如I3E就相当于3，I3E就是3。0只有一种编码方式I0E。整型元素没有长度限制。列表元素的表示以字符L开头，结尾字符E，中间是一系列编码后的元素，子元素可以是字符串元素、整型元素、列表元素和后面将要描述的字典元素。例如L4SPAM4EGGSE代表字符串列表“SPAM”,“EGGS”。字典元素以字符D开头，结尾字符E，中间包含一系列键值KEY，和与键值对应的元素值。字典元素中的子元素值也可以是字符串元素、整型元素、列表元素和字典元素。例如D3COW3MOO4SPAM4EGGSE代表着“COW”“MOO”,“SPAM”“EGGS”，D4SPAML1A1BEE相当于“SPAM”“A”,“B”。字典元素键值KEY必须是字符串元素。222元数据文件的格式元数据文件被编码成字典元素，且必须包含以下键值KEY，和该键值所对应的元素。ANNOUNCE该键值所对应的元素值是追踪服务器TRACKER的URL地址。当有多个追踪服务器的时候，应包含ANNOUNCELIST键值和对应的追踪服务器列表。INFO该键值对应的元素是所共享文件的相关信息。该键值对应的值是一个字典元素。该子字典元素必须包含如下键值NAME其元素值是一个字符串元素，代表默认的共享文件或保存目录的名字。该名字只是纯粹建议性的。PIECELENGTH其元素值是整数，代表所共享文件分块后的每个分块的字节数。除了最后一块可能被文件尾截断一些外剩下的大小不足一个分块，所有的分块大小都相同。分块大小一般都是2的幂值，通常是218256K。PIECES该元素值是字符串元素，由各分块的SHA1字符串依次连接而成。每个分块数据的SHA1校验码是长度为20的字符串，该字符串元素的长度是20的整数倍。LENGTH和FILES，这两个键值只能出现一个，且只能出现一个。当LENGTH出现时说明该元数据文件代表单个文件共享，否则说明共享了多个文件。单文件情况下，LENGTH键值所对应元素的值是所共享文件的大小，以字节数表示。若共享的文件有多个，FILES键值对应一个文件列表，所有的文件按文件列表中的顺序连成一个大文件看待。每个所共享的文件包含一个LENGTH键值，代表该文件的大小，一个PATH键值，代表该文件所在的子目录和文件名。元数据文件中还可以包含其他一些键值，如相关注释COMMENT，创建日期CREATEDATE之类。223客户端和追踪服务器交互协议客户端和追踪服务器TRACKER之间的消息传输使用HTTP协议。客户端向追踪服务器按GET方式发送一个HTTP请求，客户端提交的HTTP请求中必须包含如下信息INFO_HASH该值是对元数据文件INFO键值所对应元素值的SHA1校验码。对所有加入同一个TORRENT，使用同一个TORRENT元数据文件的客户端而言，该INFO_HASH值是一致的。追踪服务器用该INFO_HASH值来唯一标识一个TORRENT。PEER_ID该客户端标识，20字节长的字符串，是每个客户端开始下载时随机生成的标识。IP该客户端的IP地址。PORT该客户端网络服务监听的端口。UPLOADED该客户端已累计上传的字节数，编码格式为十进制ASCII码。DOWNLOADED该客户端已累计下载的字节数，编码格式为十进制ASCII码。LEFT该客户端剩余所需下载的字节数。这个数不能通过文件长度和已下载计算出来的，因为文件可能是续传的，还可能有一些已经下载的数据不能通过完整性检查必须被重新下载。EVENT可选键值，代表客户端的下载状态。追踪服务器TRACKER给客户端返回的数据被编码成一个字典元素。如果出错，则该字典元素包含一个FAILUREREASON的键值和其对应的出错原因。通常则包含如下键值INTERVAL其值是一个整型元素，是客户端给追踪服务器发送请求的时间间隔，以秒为单位。PEERS其值为一个列表元素，包含下载同一文件的TORRENT中其他PEER节点的信息。对每一个PEER节点，包含PEER_ID，IP和PORT，分别对应PEER标识、IP地址和监听端口号。224客户端之间数据传输协议客户端定期从追踪服务器TRACKER处获得当前TORRENT中其他PEER节点信息，然后与一些PEER节点建立应用层连接，交换应用层消息和传输数据。PEER节点之间交换消息和传输数据时使用TCP作为网络传输层协议。PEER之间的应用层连接是对称的，消息可以在两个方向上传递，数据也可以在任何一个方向流动。在每个PEER端，有2个比特位来指示连接状态阻塞与否CHOKEORNOT，是否感兴趣INTERESTEDORNOT。阻塞与否指本地PEER是否被对方PEER阻塞了，若被阻塞CHOKE，则不能向对方请求数据，除非对方PEER解除阻塞UNCHOKE。是否感兴趣INTERESTEDORNOT指对方PEER拥有本地PEER所需要的分块数据。如果本地PEER状态变为感兴趣INTERESTED，且对方PEER解除阻塞UNCHOKE本地PEER，本地PEER就可以向对方PEER发送请求数据分块的消息，双方开始数据传输。BITTORRENT协议定义了如下几种PEER之间的消息HANDSHAKEPEER节点之间的握手消息，也是PEER之间所发的第一个消息。PEER之间相互发送一次握手消息，才算握手成功。KEEPALIVEPEER之间每隔2秒，发送一次KEEPALIVE消息，表示双方仍是活跃状态。与数据传输相关的消息有CHOKE本地PEER阻塞对方PEER。UNCHOKE本地PEER解除阻塞对方PEER。INTERESTED对方PEER拥有本地PEER所需要的分块数据。NOTINTERESTED对方PEER没有本地PEER所需要的分块数据。HAVE本地PEER下载完一个数据分块后，向所有建立了连接的邻居PEER发送一个拥有该分块的HAVE消息，通知对方。BITFIELD标示本地PEER所拥有的数据分块的状态。若本地PEER拥有某一个数据分块，用一个比特1来表示，否则用比特0表示。本地PEER和对方PEER建立连接，握手成功之后，所发的第一个消息就是BITFIELD消息，双方交换各自所拥有的数据分块的状态。REQUEST本地PEER向对方PEER请求某一数据分块或数据分块的一部分。PIECE本地PEER在收到对方PEER的REQUEST消息后，向对方PEER发送其所请求的文件数据。CANCEL本地PEER向对方PEER发送CANCEL消息，撤销之前所发REQUEST消息中对某一数据分块的请求。23BITTORRENT特点分析快速、有效的数据传输是因特网的核心应用。广义的数据包含文件、语音、图片等。对文件传输而言，其过程可分为两部分，一是文件的定位，二是文件数据传输。文件的定位是定位文件在因特网上存在的地址。文件数据传输是通过网络将文件从源地址传输到目的地址。有大量应用层协议来解决文件传输的问题，如HTTP，FTP，SMTP等，还有P2P相关的应用层协议如GNUTELLA，EDONKEY/EMULE，BITTORRENT等。231客户机/服务器模式HTTP、FTP等是传统客户机/服务器C/S模式下的应用层文件传输协议。在C/S模式下，服务器负责处理所有用户的请求，当客户数量不断增加时，服务器端的负载增长的非常快，要求服务器有非常高的处理能力和出口带宽。由于负载主要集中在服务器端，服务器往往成为整个系统的瓶颈，服务器的处理能力和出口带宽限制了其可以服务客户机的数量和客户机的下载速率。服务器是系统中唯一的服务提供者，系统服务能力的提升全部依赖于服务器性能的提升，系统可扩展性差，当服务器出现故障时，整个系统也随之瘫痪，系统健壮性差。客户机/服务器系统服务模式见图21。图21客户机/服务器系统服务模式232P2P模式P2P模式的核心理念是终端用户之间的协作COOPERATION。通过各终端用户之间的协作，终端用户之间相互服务，降低服务器在整个系统中地位的重要性，服务器不再是系统中唯一的服务提供者，大量的终端用户也可以向其他终端用户提供服务，整个系统的服务能力大大提高，服务器的性能和带宽不再是系统中的瓶颈，系统可扩展性高，能服务更多的用户，系统健壮性也大大加强。早期的P2P系统，如GNUTELLA，DHTDISTRIBUTEDHASHTABLE31,32等，终端用户间的协作体现两方面，一是如何进行定位文件这一过程。P2P文件搜索算法有洪泛式FLOODLIKE，随机漫步式RANDOMWALK，DHT文件路由FILEROUTING等。各PEER节点之间通过各种协议，中转寻找、定位文件的请求，实现了在大量PEER节点间共享文件定位信息，极大的扩展了定位文件的范围。终端用户间协作的第二方面体现在文件数据传输的过程。终端用户之间的文件数据传输仍是客户机/服务器模式。不过，此时服务器是系统中其他拥有该文件的PEER节点。早期的P2P系统虽然大大提高了系统的服务能力，但还不够理想。原因是在这些系统中，终端用户PEER之间的数据传输是以整个文件为单位。终端用户向其他服务提供者一次性请求整个文件，只有拥有完整文件的终端用户才能成为服务提供者。这种模式存在如下缺陷1系统中服务提供者的数量不够多，拥有部分文件的终端用户不能向系统贡献其服务能力。2终端用户一般只能从一个源地址处下载数据，且请求整个文件。因此选择合适的服务提供者非常重要，不合适的终端用户和服务提供者之间传输数据的带宽依旧很低。对终端用户而言，其下载带宽未充分利用，而对服务提供者而言，其上传带宽未充分利用。图22以整个文件为传输单位的P2P系统服务模式虽然这种模式的系统仍有不小的改进的余地，但是和纯C/S模式相比，系统的可扩展性和服务能力都有显著的提高。同时，弱化了服务器的中心地位，系统的可靠性也有很大的提高。以整个文件为传输单位的P2P系统服务模式见图22。233BITTORRENT系统BITTORRENT系统对文件共享方式的改进主要体现在文件数据传输部分。在BITTORRENT系统中，文件的定位利用集中式服务器的方法。使用追踪服务器TRACKER，所有下载同一文件的PEER节点被组织成一个TORRENT，TORRENT内PEER节点之间通过应用层消息相互通信，相互提供服务，交换文件数据。新加入的PEER节点从追踪服务器处获得TORRENT信息，加入TORRENT。在BITTORRENT系统中，文件被分成若干固定大小的分块PIECE。分块是PEER之间传输数据的最小单位。不同PEER一般拥有不同的数据分块。每个PEER能同时和多个PEER之间交换分块数据。BITTORRENT系统是目前最成功的文件共享系统，我们认为将文件分块是其主要特点，而将文件分块后带来的诸多特性，使该系统其具有如下优点1PEER之间交换数据的单位更小，由整个文件变为固定大小的小分块。拥有部分文件的PEER也能拥有多个完整的数据分块，能向其他PEER提供服务，释放了拥有部分文件PEER的服务能力。系统中服务提供者的数量大大增加，整个系统的服务能力也随着系统中PEER数的增加成指数级数增加，系统的可扩展性几乎最优。2PEER能同时从其他多个PEER处下载数据，当某个PEER服务质量下降时，能快速找到替代者。单个服务提供者的功能被弱化，能随时被替代，系统更加健壮，这点对于动态性非常强的P2P系统尤为重要。3PEER节点能从多个邻居PEER处同时请求不同的数据分块，并行下载，充分利用本地PEER的下载带宽和对方PEER的上传带宽，大大加快了文件下载的速率。这种多源并行下载的蠕虫似SWAMLIKE文件分发方式，是BITTORRENT系统中每个PEER都能保持很高的下载速率，系统成功的关键因素之一。BITTORRENT系统中基于分块的服务模式见图23。图23BITTORRENT系统中基于分块的服务方式234BITTORRENT系统性能指标下面给出我们认为衡量BITTORRENT系统性能的指标。在系统级，衡量系统的性能有如下指标同时服务的用户数；所有PEER的平均下载速率；系统在高动态性、低网络质量等情形下的服务质量。对每一个PEER，期望达到高下载速率，同时保持低负载CPU、内存占用率低，上传带宽小。而对于因特网网络层，则希望尽量减少骨干网流量。24本章小结本章详细介绍了BITTORRENT协议。在BITTORRENT服务模式下，文件分成粒度更小的数据分块，增加了系统中服务提供者的数量，系统服务能力的提升有效的对抗了快速增长的客户请求。最后介绍了BITTORRENT系统衡量指标。3分块和节点选择算法上一章介绍了BITTORRENT协议，本章将介绍和分析BITTORRENT协议中的核心算法。31分块选择算法23节指出将文件分成粒度更小的数据分块，是BITTORRENT协议最主要的一个特点，分块是PEER之间数据交换的最小单位，这种模式释放了大量处于下载过程中PEER的服务能力。围绕数据分块设计的分块PIECE选择算法和节点PEER选择算法是BITTORRENT协议成功的关键。分块选择算法由每个PEER在其本地执行的调度策略，系统中所有PEER分块选择调度的结果就是各个数据分块在所有PEER上的分布情况。分块选择算法对BITTORRENT系统的性能影响非常大。下面先介绍BITTORRENT协议中的分块选择算法，再对该算法进行分析。BITTORRENT协议中有三种分块选择算法10。1严格的优先级如果一个分块PIECE里面有一部分已被调度，那么该分块中剩下的部分优先级最高，最先被调度。这样能尽快下载一个完整的分块，才能向其他PEER节点提供该数据分块。2分块副本数量最少优先RARESTFIRST在调度选择分块PIECE时，分块副本数量最少的优先选择。该策略执行步骤如下对本地PEER需要的每一个数据分块PIECE，统计当前所有邻居PEER节点集中该分块PIECE副本的数量。调度分块副本数量最少的。3随机分块选择当PEER节点新加入到TORRENT时，该PEER没有任何文件数据，为了尽快的向该PEER提供一些数据分块，促使其能尽快和其他PEER进行数据交换，这样处于初始状态的PEER先执行随机分块选择策略。一般来说，对于拥有者少的分块，PEER获得该分块的速率会因数据源少，而低于获得其他分块的速率。所以PEER前N个分块的调度采用随机分块选择策略，当这N个分块下载完成后，转换到分块副本数量最少优先RARESTFIRST策略。311分块选择算法的分析下面我们先分析分块选择算法影响BITTORRENT类似系统的性能的原因。BITTORRENT系统成功的关键之一就是多源并行下载，充分利用每一个PEER节点的上传带宽和下载带宽，来优化整个系统中所有PEER节点的下载速率。下列两种情形的出现会影响节点的下载速率1PEERA有多余的上传带宽，其他PEER对其数据分块不感兴趣，没有数据传输出现，PEERA的上传带宽没有被充分利用，没能贡献给其他PEER。2PEERA有多余的下载带宽，其他PEER没有PEERA所需要的数据分块，PEERA的下载带宽没有被充分利用，既影响PEERA自身的下载速率，也影响了PEERA下载成功后向系统提供的服务能力，进而影响了整个TORRENT中的数据传输。上述两种情形我们称为数据瓶颈CONTENTBOTTLENECK。数据瓶颈CONTENTBOTTLENECK一词的概念最早出现于PRIME33一文中。分块选择算法的目的就是要使各数据分块的副本在PEER之间均匀分布，尽可能的增大PEER之间交换数据的可能性，充分利用PEER之间的上传带宽和下载带宽，避免数据瓶颈的出现。分块副本数量最少优先RARESTFIRST策略是一个局部启发式策略。每个PEER在调度时，只考虑其自己邻居PEER集合中各数据分块副本的数量，调度算法只考虑这一个参数。同时，是一种局部性算法，而没有考虑全局性因素。BITTORRENT类似的P2P系统，节点数量多，系统规模大，每个PEER能随时加入和退出TORRENT，系统动态性强。且每个PEER只能定时和追踪服务器通信，同时通过和邻居PEER交换消息，来获得关于当前TORRENT系统的部分最新信息，整个TORRENT系统消息传递实现了一种GOSSIP协议类似的传播方式。PEER用其邻居PEER集中观测到的局部信息来预测整个TORRENT的全局信息。整个TORRENT全局信息包括当前活跃的PEER节点数量，PEER的上传下载带宽分布，各数据分块在PEER节点上的分布情况等。PEER无法获得当前整个TORRENT系统的全部信息，也无法实现理论上全局最优的分块选择算法。启发式策略的有效性由于P2P系统的复杂性而很难从理论上得到证明，目前几乎所有实用的P2P系统中，调度策略都采用简单的局部启发式策略。文献15通过大量的实际测量数据，证明了分块副本数量最少优先RARESTFIRST策略非常有效，在多种实际情形下接近于最优。每个PEER局部的调度策略，其调度结果会影响当前PEER拥有哪些数据分块，整个系统中所有PEER调度策略的结果叠加COLLECTIVEBEHAVIOR起来，就是各个数据分块副本数量在整个TORRENT中的分布，而数据分块副本的分布，会直接影响到PEER之间交换数据的概率，从而影响系统的整体服务性能。32邻居节点选择算法BITTORRENT协议是一个分布式协议，每个PEER节点都试图去达到自己最大的下载速率，因此每个PEER节点都要为自身寻找一些合适的服务提供者，尽可能的快速从服务PEER处下载数据。PEER之间怎么选择其他服务PEER节点呢这就是PEER节点选择算法所要解决的问题。下面先介绍BITTORRENT协议中PEER节点选择算法10。321阻塞和解除阻塞策略在BITTORRENT协议中，每个PEER都大概和80个邻居PEER节点建立连接，但并不是和其中每个PEER都会交换数据。每个PEER节点有两种状态，阻塞CHOKE和解除阻塞UNCHOKE。PEER不想上传数据给对方，就将对方阻塞CHOKED，不接受对方的数据请求。当PEER打算给对方提供服务时，就将对方解除阻塞UNCHOKE，响应对方的数据请求消息。同时，PEER也会被对方PEER阻塞或解除阻塞。BITTORREN协议采用一种TITFORTAT的阻塞和解除阻塞算法。该算法类似于博弈论中囚徒困境理论，具体算法如下每隔10秒，PEER统计当前所有邻居PEER在上一个10秒的调度间隔中的平均上传速率；解除阻塞UNCHOKE上传速率最高的3个邻居PEER节点，阻塞其他PEER。BITTORRENT协议阻塞CHOKE和解除阻塞UNCHOKE算法严格按照上一个调度周期10秒内各邻居PEER的上传速率的执行。其理念是哪个对方PEER给本地PEER提供服务最多，本地PEER就优先给该对方PEER提供服务，以此来加强PEER之间数据共享的协作性。在该策略下上传速率高的PEER节点被解除阻塞的机会打，激励PEER向系统中其他PEER贡献其上传带宽，同时他也能由自己的贡献而获得更多的解除阻塞的机会，获得更多的服务，提高其自身的下载速率。阻塞和解除阻塞是单向、非对称的策略。本地PEER根据策略可以阻塞或解除阻塞对方PEER，对方PEER也执行相同的动作。策略的具体结果由双方各自当时的实际调度情况决定。322随机乐观解除阻塞策略上一节介绍了根据邻居PEER当前上传速率来阻塞CHOKE和解除阻塞UNCHOKE的PEER节点选择算法。仅仅依靠上述算法有一个缺陷。PEER总是被动的根据对方PEER的上传速率来做出选择，而不能主动的发现和寻找潜在、更优秀的PEER来作