BitTorrent网络内容缓存服务器的设计与实现

1、北京邮电高校本 科 毕 业 设 计（论文）题目： BitTorrent网络内容缓存服务器的设计和实现 姓 名 李科丁 学 院 信息工程学院 专 业 信息工程 班 级 0213101 指导老师 聂荣/雷震明 2006 年 6 月 78 / 84北 京 邮 电 大 学本科毕业设计（论文）任务书学院信息工程学院专业信息工程班级0213101学生姓名李科丁指导老师姓名雷振明/聂荣职称教授/博士生设计(论文)题目BT网络内容缓存服务器题目分类1、工程实践类 探讨设计类 理论分析类 （1、2类中各选一项在内打）2、软件 硬件 软硬结合 非软硬件主要任务及目标：1、 完成翻译任务，学习P2P网络学问，包括P

2、2P的基本特性、优点、不足，以及在国内外的的发呈现状，存在的问题和将来的发展趋势；2、 学习java语言，通过研读BT代码，搞清晰BT具体怎么对文件分块，客户端是依据什么来选择文件块进行下载，多个客户端之间是如何进行交互通信的，种子具体是怎么生成的，以及BT下载的流程；3、 最终希望能通过共同努力实现一个改进版本的BT程序，制定更有效的路由机制和搜寻算法使之能在网络检索效率等方面有所改善，并能达到更有效更平安更符合用户需求。主要内容：1 通过查看资料学习了解P2P的相关学问，以及国内的发呈现状，存在的问题和将来的发展趋势；2 学习java语言，通过研读代码，网络抓包弄懂运用BT下载的流程。3

3、设计并运行BT客户端下载的位置知晓性测量试验。4 阅读BT客户端源码的Tracker通信模块，进行位置知晓性上的改进。主要参考文献；张孝祥.JAVA就业培训指导.清华高校出版社阎菲. JAVA程序设计教程.中国水利水电出版社M. Bawa, B. F. Cooper, A. Crespo, N. Daswani, P. Ganesan, H. Garcia-Molina, S. Kamvar, S. Marti, M. Schlosser, Q. Sun, P. Vinograd, and B. Yang. Peer-to-peer research at Stanford. SIGMOD R

4、ec.Shamir, A.: How to share a secret. Communications of the ACM, 22:612-613, 1979.进度支配：第一阶段（1-3周）：学习并驾驭P2P网络基础学问，选择题目，完成开题报告；其次阶段（4-7周）：翻译外文技术资料，设计测量试验；第三阶段（7-10周）：起先测量试验，整理、分析数据；第四阶段（11-15周）：阅读BT源码，进行Tracker通信模块、堵塞和优化疏通算法（Choking and Optimistic Unchoking）的代码设计和编写工作。第五阶段（16-18周）：撰写开发文档及毕业论文。 指导老师签字日

5、期年 月 日注：一式三份，学院、指导老师、学生各一份。北 京 邮 电 大 学本科毕业设计（论文）答辩决议书学生姓名李科丁专 业信息工程班 级0213101学 号021169毕业设计论文题目BitTorrent网络内容缓存服务器的设计和实现评定成果指导老师姓名指导老师职称指导老师评语：（主要包含选题背景、意义；论点是否正确、论据是否翔实、论证是否充分；设计（论文）成果、价值；论文写作、文本规范；工作量、工作看法；不足和希望等方面） 指导老师评分签字日期年 月 日答辩小组评语：（主要包含选题背景、意义；论点是否正确、论据是否翔实、论证是否充分；设计（论文）成果、价值；论文写作、文本规范；答辩状况；

6、不足和希望等方面） 答辩小组评分： 组长职称： 签字： 成员职称： 签字： 成员职称： 签字： 成员职称： 签字： 成员职称： 签字： 年 月 日 到校外做毕业设计（论文）的学生答辩成果校内指导老师复议看法：校内指导老师签字： 年 月 日BitTorrent网络内容缓存服务器的设计和实现摘 要近年来，大量的探讨结果表明现今的互联网网络流量已不仅仅由 、FTP、POP3、SMTP等传统业务流量所组成，其中大部分是对等（Peer-to-Peer）网络产生的流量。P2P以其相对于C/S模式的巨大优势，不仅激发了信息技术领域科研人员的探讨热忱，而且也调动了一般用户对P2P的运用和期望。这些因素使P2P

7、成为一个热门的前沿探讨领域。P2P技术的快速发展和投入应用，给现今的互联网带来了巨大的流量冲击，大量的网络带宽被P2P应用消耗。由于对等网络较松散的组织方式，导致大量的冗余网络流量，奢侈了带宽。依据Peer-to-Peer Working Group Committee的定义，P2P在商业上的应用主要有文件共享、边界服务、分布式计算，但文件共享是目前最重要的一个应用。BitTorrent文件共享系统作为典型的P2P技术的应用，采纳了多源下载机制，下载速度快，资源享用免费，得到了用户的广泛青睐，成为我国最热门的下载方式之一，同时，也给网络带来了沉重的流量负担。通常P2P网络很少考虑底层物理网络，

8、随机选择逻辑邻居节点，导致P2P网络和底层物理网络间拓扑结构的不匹配，P2P网络性能因此受到严峻制约，大量奢侈了底层物理网络的资源。本文探讨和探讨BitTorrent的对等网络(P2P)的位置知晓性问题。首先，以校内网环境为试验平台，测试BitTorrent应用的位置知晓性，通过测量试验的数据论证了BT网络也存在确定的位置知晓性问题。其次，对该问题的优化，探讨现有的改善位置知晓性的解决方案。第三，依据网络环境的实际状况，提出缓存服务器系统，采纳基于内容缓存的方式改善BitTorrent对等网络的位置知晓性问题，并且通过在校内网中部署缓存服务系统，进行试验测试，以验证该系统可以削减P2P下载过程

9、中的网络间流量，减轻网络运营商的负担。关键字 对等网络 缓存服务器 拓扑匹配 BitTorrentDESIGN AND IMPLEMENT OF A CACHE-SERVER-SYSTEM IN BT-LIKE PEER-TO-PEER NETWORK ABSTRACTRecently, lots of research reveal that the traffic on the network is not only composed of the traditional types of traffic such as FTP, Pop3, SMTP and so on. Peer-to

10、-Peer network is a new type network that users take advantage in resource share. P2P, as a new network scheme prior to the existing C/S scheme, has inspired not only many researchers worked in the information technology field, but also been attractive to many other people. And now, P2P technology ha

11、s been one of the most hot research fields which leading the science. P2P technology significant influences traffic because it consume much of bandwith. A big portion of P2P traffic is repeated and unnecessary because of its loose management architechture.According to the definition of Peer-to-Peer

12、Working Group Committee, P2P can be used in the file sharing, distributed computing and so on. But file sharing is the dominant P2P application.BitTorrent is an popular P2P application which is focus on file sharing. It uses muti-sources download mechanism to get great download performace. In additi

13、on, user download resources totally for free. Therefore, it becomes one of the most popular download application. Meanwhile, traffic genarated by BT makes the network over burdened. P2P networks are often constructed without considering the underlying physical network and the logical neighbor peers

14、are chosen randomly. So the P2P overlay network mismatch the physical network. The mismatching problem limits greatly the performance gain from P2P and abuses the resource of the physical network infrastructure. This paper discusses the location-awareness problem in BitTorrent-like P2P networks. Fir

15、st, we build simulation envioronment based on campus network and the location-aware problem in BT network is proved by a measurement study. Sencond, we study other work about location-aware problem. Third, we propose a method named cache server system, which is based on caching, improve network perf

16、ormance. The cache server system can reduce the traffic between networks and the cost of network operators. KEY WORDS Peer-to-Peer cache-server-system topology-matching BitTorrent目 录1. 绪论.21.1 P2P网络概述21.2 P2P叠加网的第一种分类21.2.1 非结构化P2P叠加网21.2.2 结构化P2P叠加网31.3 P2P叠加网的其次种分类41.3.1 集中式P2P叠加网41.3.2 分布式P2P叠加网5

17、1.3.3 混合型P2P叠加网52. P2P网络的位置知晓性.72.1 叠加层上的重复消息72.2 拓扑不匹配造成的重复消息82.3 改善位置知晓性相关工作93. 非结构化P2P应用BitTorrent.133.1 BitTorrent工作原理133.1.1 BT网络概述133.1.2 BT下载流程153.2 BT位置知晓性测量试验183.2.1 试验目的183.2.2 试验原理193.2.3 试验设备203.2.4 测量工具203.2.5 试验步骤203.2.6 试验结果214. BT缓存服务器的设计改进方案.234.1 缓存服务器系统原理234.1.1 TMA功能概述234.1.2 内容缓

18、存服务器概述244.2 提取识别资源原理分析244.3 缓存服务器系统部署264.4 部分源码284.4.1 BT客户端模块分析284.4.2 Azureus2084源码总体分析324.4.3 缓存服务器下载部分源码说明334.4.4 缓存服务器上传部分源码说明334.4.5 缓存服务器IP过滤部分的源码说明444.4.6 缓存服务器和TMA服务器之间的通信问题454.4.7 Az和5Q Tracker通信问题474.5 试验结果48参考文献.51致 谢.561. 绪论1999年，Napster首次提出了对等（Peer-To-Peer）网络的概念，构建了包括一个集中书目服务器的对等文件共享网络

19、。它是首个可从多个节点而非一个服务器上下载热门文件的系统。这种P2P系统完全是自组织的，并且加入的人越多，其下载实力就越强。Napster是集中式系统，存在一个仅仅存储拥有资源的各个节点的地址书目的集中书目服务器。这对服务器端的带宽要求就特别低，大大减轻了服务器的流量负担。但是，该系统有一个不行复原的点，假如书目服务器端出现问题，整个系统将无法工作，尽管资源仍旧存在于网络，用户由于无法访问书目服务器则不能定位资源。不过，由于Napster网络中存在的资源是流行音乐，因此，由于版权问题，美国唱片联合会（RIAA）迫使Napster关门歇业。但是，Napster打开了对等网络的大门，促使了后来各种

20、P2P系统的发展。BT是目前最热门的下载方式之一，它的全称为“BitTorrent”简称“BT”，中文全称“比特流”。BT（BitTorrent）是第三代混合式P2P网络的典型代表，它采纳了“多源文件传输协议”(MFTP，the Multisource FileTransfer Protocol)，可以通过检索分段从多个用户那里同时下载文件，最终将下载的文件片断拼成整个文件，实现了多源文件的高速下载。协议定义了传输、压缩和打包的标准。每个文件都运用md5-hash算法所获得串标识，这使得文件可以运用较短的一串数据标识其唯一性。据探讨机构Cachelogic调查，BT占了全球网络流量的三分之一。

21、而当BT用户选择Peer下载资源时并不对其位置信息进行过滤。以校内网为例，当校内主机拥有资源，而当其他用户下载该资源时，并不会优先下载校内资源，而是以同样的概率从校内和校外的资源下载，这样，事实上奢侈了校内网的出口带宽。类似的状况也发生在运营商的角度，由于BT不具有位置知晓性，其网络流量不仅占用大量出口带宽，运营商还须要为网间流量付出高额的费用。因此，假如将位置知晓功能加入BT，不仅能节约带宽，还能降低运营商的费用，提高网络利用率，同时，不影响BT运用者的用户感受。1.1 P2P网络概述对等叠加网络的结构是分布式的，并且没有任何分层次的结构或中心限制机制，加入对等网络的节点完全是自主组织的，并

22、构架在IP（Internet Protocol）网络之上。对等网络具有很多优点，如健壮的大区域路由体系结构，数据搜寻的高效性，旁边节点的发觉和选择，冗余存储，良好的可扩展性以及容错性等。和传统的C-S（Client-Server）模式不同，加入对等网络的节点既从网络获得资源，又供应资源，同时具备客户端和服务器的功能。P2P叠加网络可以看做是在现有的通信网络架构上的网络模型，是一个完全分布式的，具有互操作性的自组织系统。图1-1所示，为P2P叠加网络的基本架构图。网络通信层描述了桌面系统连接到因特网的网络性质，本文所探讨的P2P网络构架在IP网络上。叠加网节点管理层涵盖节点的管理，包括节点发觉以

23、及最优路由算法选择等。功能管理层包括网络平安性、牢靠性、容错性以及资源有效性等。服务层为底层P2P结构供应支持，通过并发任务、内容以及文件管理供应服务级的组件。数据内容管理描述P2P节点存储的数据内容以及位置信息。应用层描述在P2P叠加网络结构之上所实现特定功能的工具、应用和服务。图1-1 P2P叠加网络架构示意图1.2 P2P叠加网的第一种分类P2P叠加网络依据搜寻定位资源的方式可分为两种：结构化的（Structured）和非结构化的（Unstructured）。1.2.1 非结构化P2P叠加网非结构化的P2P网络是以Ad-Hoc的方式来组织的。叠加网以平面的或分层的（例如，超级节点层）方式

24、组织节点，采纳洪泛、随机步进等方式进行资源的搜寻定位。每个收到查询的节点将查询和自己拥有的资源进行比照，支持困难的查询。这是一种低效的查询方式，由于数据位置和拓扑之间没有联系，所以查询不得不将发送给较多的节点。本节将介绍几种常见的非结构化的P2P叠加网：Gnutella8，FastTrack9/KaZaA10，BitTorrent11，eDonkey20001213，本节介绍Gnutella，FastTrack/KaZaA，eDonkey2000，BitTorrent将在后文具体介绍。1.2.2 结构化P2P叠加网结构化指的是P2P叠加网的拓扑结构是可严格限制的，资源并不是随机分散存储 在节点

25、上，而是以一种能使得查询更加有效的方式来存储的。这样的结构化系统运用分布式哈希表（Distributed Hash Table，DHT），将数据实体位置信息以一种确定的方式分布在P2P网络之上，节点的标识符（NodeID）对应数据实体的唯一索引（key）。这种基于DHT系统随机的将NodeID安排给节点，NodeID从一个较大空间的标识符库中选取，另外，安排给数据实体的标识符叫做索引（key），同样也从相同的标识符库中选取。通过叠加网协议，将索引唯一的映射到叠加网中的唯一节点。P2P叠加网通过索引，值（key, value）这样的映射对，支持可扩展的存储和检索，如图1-2所示。给定一个索引，存

26、储操作（put(key, value)）可将对应于该索引的数据对象进行存储操作，同样查找检索操作（value=get(key)）则可实现通过索引对数据对象的路由恳求。图1-2 基于DHT的结构化P2P叠加系统的应用接口示意图每个节点维护一个很小的路由表，只存储邻居节点的NodeID和IP地址。查询消息步进式的在叠加网上转发给NodeID和索引接近的相应的节点。不同的基于DHT的系统有不同的数据对象组织形式，索引空间和路由策略。理论上，基于DHT系统可将任何数据对象的查找跳数平均限制在O(logN)条之内，N表示整个系统中的节点数。底层网络的两节点之间的路径可能跟叠加网的路径大大不同，即叠加层和

27、物理层的网络不匹配。这样，查询延迟会特别大，会严峻影响运行的应用程序的效率。典型的结构化P2P应用有以下几种：Content Addressable Network (CAN)1，Chord2，Tapestry3，Pastry4。图1-3 Pastry节点路由表，叶子集合表和邻居集合表。尽管结构化的P2P网络更加高效，更具有可扩展性，但是它的开销远远大于非结构化P2P网络，因此，在现实的因特网世界中，非结构化P2P网络得到了更广泛的应用。1.3 P2P叠加网的其次种分类另外，P2P网络依据是否存在中心服务器的原则还可分为以下三种：集中式的（Centralized）、分布式的（Decentral

28、ized）和混合型的。1.3.1 集中式P2P叠加网集中式P2P模式由一个中心书目服务器来负责记录对等节点的地址信息和所保存数据的共享信息。典型代表就是Napster。Napster 是以C/S方式，也就是节点向特定的文件服务器询问来取得文件位置。集中式P2P可供应中心服务器书目检索、管理服务和标准的点到点通信，具有高效的检索和低效的交换服务的特点。集中式P2P对小型网络而言在管理和限制方面占有确定的优势，但对大型网络并不适合。集中式P2P模型存在很多问题：中心服务器的瘫痪简洁导致整个网络的崩溃，牢靠性和平安性较低；随着网络规模的扩大，中心书目服务器维护和更新的费用将急剧增加，所需成本过高；中

29、心服务器的存在引起共享资源在版权问题上的纠纷，这也是干脆导致Napster破产的缘由。1.3.2 分布式P2P叠加网分布式模式不存在中枢书目服务器，每个节点都既是服务器又是客户端，必需依靠所在的分布网络来查找文件和定位。对等机通过和相邻对等机之间的连接遍历整个网络体系。理论上，搜寻范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台PC上的信息资源。Gnutella模型是现在应用最广泛的分布式P2P非结构化拓扑结构，它解决了网络结构中心化的问题，扩展性和容错性较好，但是Gnutella网络中的搜寻算法以泛洪的方式进行，限制信息的泛滥消耗了大量带宽并很快造成网络拥塞甚至网络的不稳定。同时，局

30、部性能较差的节点可能会导致Gnutella网络被分片，从而导致整个网络的可用性较差，另外这类系统更简洁受到垃圾信息，甚至是病毒的恶意攻击。1.3.3 混合型P2P叠加网混合式P2P结合了集中式和分布式P2P的优点，在分布式模式的基础上，将用户节点按实力进行分类，使某些节点担当特殊的任务。其速度要比纯P2P模式快得多。节点共分为3种：用户节点：一般节点，它不具有任何特殊的功能。 搜寻节点：处理搜寻恳求，从自己的“孩子”节点中搜寻文件列表搜寻节点，管理着所属用户的文件列表。索引节点：连接速度快、内存足够的节点可以作为索引节点。索引节点用于保存节点信息，并搜集状态信息，维护网络结构信息。就像搜寻引擎

31、一样，只是搜寻和所需数据相关的地址14。用户节点通过索引节点获得搜寻节点信息，之后用户节点就和获得的搜寻节点相连，每一次查询都通过该搜寻节点进行。当用户发出搜寻恳求后，假如和用户节点干脆相连的搜寻节点查询结果达到100个（这里的100个搜寻结果，可以由用户自己来设定）就停止；假如不足100个，就向相邻的搜寻节点发出恳求，假如查询结果还不够，就接着向外快速散播，直到全部的搜寻节点都被搜寻到为止。这样，搜寻过程就像在照着交通指示牌循序问路，而不是路上随意找个人问路，这样很大程度上提高了搜寻效率，节约了带宽。15在混合模式中，如何将功能相像的节点聚集在一起，进而在此基础上制定完备的搜寻算法，对这种P

32、2P系统的性能和开销起着至关重要的作用。BT就是第三代混合式P2P网络的典型代表。它要求供应Web发布服务器，以供发布和搜寻资料。在客户端，它通过一个IE插件供应下载、上传管理。BT把一份大文件切割成碎片，为每一个碎片标上特殊标识，用户无需到一个固定地点（例如传统网络的中心服务器）上下载完整的文件，系统会自动找寻、随机下载具有相同标识的文件碎片，将其加以整合成为完整的文件。BT不须要指定服务器，服务器称为Tracker。用BT下载，须要得到一个扩展名是.torrent的文件，这个文件很小，存放了发布文件的描述信息、该运用哪个Tracker、文件的校验信息等。BT采纳了“多源文件传输协议”(MF

33、TP，the Multisource FileTransfer Protocol)，可以通过检索分段从多个用户那里同时下载文件，最终将下载的文件片断拼成整个文件。在协议中，定义了一系列传输、压缩和打包的标准。每个文件都有md5-hash的超级链接标示，这使得该文件独一无二，在整个网络上都可以追踪得到。而且，只要你得到了一个文件片断，系统就会把这个片断共享给大家，支持断点续传。BT运用了HASH算法，致使下载时不像其它常用下载软件在写入硬盘数据前起用了高速缓冲，而是干脆就写入硬盘，造成硬盘损害，提早结束硬盘的寿命。新推出的BT程序，都已经供应调整缓存的功能，可将缓存设成10MB、20MB。2.

34、P2P网络的位置知晓性P2P网络的位置知晓性，主要是指对节点的物理网络位置的知晓（比如距离的远近），以及叠加层和物理网络层之间的拓扑结构的匹配。资源搜寻是P2P网络中特别重要的构成部分，同时也带来了很大的网络开销，另外，搜寻过程中查询消息须要在叠加层的网络拓扑中路由，更多的涉及到了叠加层和物理网络层之间的匹配问题，因此，当前对P2P网络的位置知晓性问题的探讨都集中在P2P网络的搜寻问题。P2P叠加层的拓扑建立很少考虑到物理网络的拓扑结构，这就造成了叠加层和底层物理网络的拓扑结构不匹配的问题。例如Gnutella和Kazaa等分布式P2P系统，并不考虑到节点的实际物理网络位置。所以同一消息可能会

35、多次穿越相同的物理链接，带来大量多余流量。分布式P2P系统中，新节点加入时会先连接引导节点，获得P2P网络中的在线节点的IP地址列表，然后尝试连接到这些节点，假如连接胜利，新节点就获得邻居节点。之后，新节点会定期ping其它节点，获得网络中其它节点的IP地址，并缓存下这些地址。当节点离开网络后再次加入时，将首先尝试连接缓存中的IP地址。而在分布式P2P系统，这个过程多采纳洪泛查询机制，即节点将接收到的查询消息，转发给自己的全部邻居节点。这种节点随机加入和离开的洪泛搜寻的加入机制，形成了一个和底层物理网络不匹配的低效的P2P叠加网络，会引起大量不必要的流量。同时，随着网络规模的增加，须要进行交互

36、的节点个数增多，所须要的搜寻消息数量也会成指数级的增加。Gnutella网络是应用最广的典型的分布式P2P系统。而只有50000个节点的Gnutella网络，就会产生了330TB/月的流量17。同时，Gnuetella网络中只有25的节点位于同一自治系统（AS）中，而超过40的节点都位于前10大AS18。这表明大部分的P2P网络流量都要跨越AS边界，增加了网间流量，给网络运营商带来更大的成本和压力。叠加层网络和实际物理网络的不匹配所产生的问题，分两种状况：叠加层上的重复消息和拓扑不匹配造成的重复消息。2.1 叠加层上的重复消息图2-1显示的一个P2P网络的叠加层拓扑结构。实线表示P2P邻居节点

37、之间的叠加层逻辑连接。节点S是发起查询的源节点。箭头表示沿着逻辑连接传送的查询消息。可以看到，基于洪泛查询机制，每个节点接收到查询消息后，就转发给自己的全部邻居节点（除了消息发送节点），这样，每个节点都收到了多份相同的查询消息，这在网络上造成了大量不必要的重复消息。图2-1 P2P叠加网络示意图1图2-2是图2-1的一部分。B2节点转发查询消息给B1、B4，B4又转发给B3。因为B1和B3都不知道对方是否接受到了相同的查询，所以它们仍会相互转发。这样，就在叠加层上产生了一个重复的消息。图2-2 P2P叠加网络示意图22.2 拓扑不匹配造成的重复消息除了在叠加层会产生重复消息，由于叠加层和物理网

38、络的不匹配问题，相同的消息也可能多次穿越相同的物理链接，从而引发大量不必要的流量。图2-3中，（a）和（b）是（c）这个物理网络拓扑上的两个叠加层拓扑。C1和C3位于相同的AS内，而C2和C4位于另一个AS。假设C1和C4的物理链接时延是（c）图中的全部链接时延最长的。那很明显，（a）的叠加拓扑结构比较低效，C3发送的查询消息会4次穿过最长的链接C1C4（C3-C4、C3-C2、C2-C1、C4-C3），而（b）这种叠加网就高效得多，查询消息只穿越C1C4链路1次。这就是叠加层和底层物理网络的拓扑结构不匹配所造成的问题。而假如可以构架一个如图2-3中（b）部分的高效叠加层。消息只会经过全部物理

39、链接一次。19探讨结果表明，在Gnutella网络中，只有2-5%的节点处在同一个自治域内。2021的仿真结果表明，Gnutella网络中也许75%的路径都存在着拓扑结构不匹配的问题。图2-3 拓扑不匹配问题。(a)低效的叠加网，(b)高效的叠加网 (c)底层物理拓扑2.3 改善位置知晓性相关工作依据底层网络状况建立起一个高效的叠加网，可以获得有着低开销和很少的额外网络流量的更好的性能。针对不同结构的网络，利用其网络结构的规律性，实行相应的路由优化策略。现有，对P2P系统搜寻效率的改进方法可以分为4类：基于转发机制、基于集群化、基于叠加层拓扑优化以及基于缓存。这四种方法可以一起运用，相互补充。

40、目前已有的相关工作，如下所述：A 基于转发机制基于转发机制的改进方法原理，对于分布式P2P系统来说就是，节点依据位置信息选择一部分邻居而不是全部的逻辑邻居来转发查询消息。22提出的有向BFS算法中，每个节点维护一个基于某些度量值的统计信息，例如从邻居获得的查询结果数量、和该邻居的链接时延。节点选择返回最多查询结果的邻居或者最近的邻居来转发查询消息。23提出的K-walker查询算法，源节点会发送k个不同的walker（转发邻居）。walker到达的节点，随机只选择一个邻居来转发该查询。而对于每个walker来说，查询过程是依次处理的。24提出的混合周期洪泛（HPF）算法，依据多种度量值来选择转

41、发邻居。强调部分覆盖问题，来平衡搜寻开销和响应时间之间的关系。利用节点的连接听从指数分布（大多数节点只有很少的连接，只有少量节点有大量的连接）的特性，每次广播时只发给节点度大（和其他节点的连接多）的节点，由它再发给相邻的节点。对于结构化P2P系统来说，25对于Pastry的第一个改进是路由时考虑备份表项。路由表中的每一表项运用10个节点。每个表项变为有着候补节点的3维向量。依据延时和路由跳数，在10个节点中选择，改善路由性能。其次个改进是，依据路由表项可能就是消息的目的端来进行下一跳的选择。当目的关键值和路由表中的一些节点的ID距离小于该节点的邻居节点的ID空间平均距离c倍时，最近的候补节点被

42、选择作为下一跳。为了近似估算ID空间中邻居节点的平均距离，每个节点运用叶子集合中的邻居节点的平均距离来代替。B 基于集群化限制节点的交互是限制住资源搜寻流量的关键问题。而将节点集群、分组是一个很有效的方法。首先，先对集群化进行理论描述2627。通过估算互联网上随意两台主机间的近似距离（采纳IP网的时延来代表距离），生成加权图，加权值就是主机间的距离。这样，网络的集群化问题就被定义为图的最优化划分。用图论公式描述为：给定加权图G（V, E）和直径D，将整个图划分为最少的K个集群，集群的总和覆盖全图。随意一个集群中，两个节点的间距小于D。这样形成的志向网络结构是，大部分叠加层逻辑连接位于同一集群的

43、各主机之间，而集群之间只通过少数逻辑连接来连通。集群化的最简洁解决方法，是基于主机IP地址的匹配长度来划分。有着相同的n比特IP地址的客户端归为同一集群2829。但IP地址中的网络前缀的长度通常不固定，同时有着相同网络前缀的主机所在的网络可能位于不同的地理位置，如采纳了VPN技术。30提出一个运用网络前缀并协作运用BGP网络掩码信息的方法，从而供应了较好的集群化方法。而3132提出了将运用相同的本地DNS服务器的主机，划分为一个集群内。但上述这些方法所需获得的信息对于终端用户来说，都难以干脆获得。同时，这样划分出来的主机集群也比较固定。33将多个位置相近、处于同一AS的节点归为一个集群，每个集

44、群安排一个集群ID，并且至少有一个书目节点。书目节点除了具有一般节点的功能外，还额外供应两个功能，1）将不能处理的查询转发给其他的节点集群；2）新节点加入系统时，接收它们汇报的网络带宽、CPU速度、内存和硬盘存储空间，运用这些度量值在集群中选择一个书目节点。节点加入网络时，运用BGP报告34，依据自己的IP地址，解析得到自己的AS号。35提出名为GNP（global network positioning）的网络架构，基于坐标来测量网络距离。网络中的每个节点都安排了一个的多维坐标空间坐标。两个主机间的网络距离可以通过距离公式来获得。36 37提出的方法是地标重新分级（landmark binn

45、ing）策略。须要测量全部节点测量到一系列相对稳定的知名地标节点（如固定互联网服务器）的时延值。然后，每个节点依据时延的大小，排列这些地标。有着相同地标排列依次的节点，就被归为一个集群。38也运用了地标节点，选择接近网络接入点的高性能节点来供应到其他集群的连接。但这须要在整个P2P网络范围进行测量，须要额外的地标支持，从而可能使这些站点过载。另一方面，精确度比较粗，比较接近的节点可能被分为一组。39提出摸索法来解决集群问题。主机客户端可以调整直径D的大小。选择相互间距至少为D的称为marker的特殊主机，来代替知名地标。40则提出选用邻居充当动态地标。缘由是比测量较远处的更加精确，并且可以削减

46、网络开销。41提出一种基于相同需求的在P2P叠加网之上的上层网络，其观点为，假如A节点拥有一个B节点所需的文件，那么它很有可能拥有B所需的其它文件。假如节点间存在多个文件的供需关系，即一个节点拥有多个另一节点所需的多个文件，则在其间建立捷径。这个过程扩展到全网，建立起捷径查询网。当节点须要查询时，首先通过捷径查询网定位，若查不到所需资源，再回到P2P叠加网的查询方式，例如Gnutella的洪泛方式。假如捷径命中率较高，则可提高查询的胜利率，从而削减查询的流量。试验结果表明，Gnutella和KaZaA的捷径命中率可达到53%-58%。C 基于叠加层拓扑优化的方法。目前，有很多工作都是通过运用小

47、范围的测量消息，来获知该范围内的拓扑信息，然后进行叠加层的拓扑优化。4243提出了LMT算法，是在Gnetella0.6P2P协议基础上，设计了叫做TTL2的探测消息类型。探测消息的TTL值设为2，所以只能经过2个节点。探测消息从源节点发出后，干脆到达的节点，叫一跳节点，该消息也叫一跳消息；经一跳节点转发后，到达的节点叫二跳节点，消息叫二跳消息。探测消息包含了源节点IP和发出时间戳、一跳节点IP、一跳节点接收到探测消息的时间戳。每个节点定期洪泛TTL2探测消息。接收到探测消息的节点，通过TTL2探测消息的时间戳来计算时延值。不同的拓扑结构，节点接收到的TTL2探测消息的个数和类型不同。依据延时

48、信息，接收节点可以发觉并切断大多数低效和冗余的逻辑连接，并将更接近的节点添加到邻居中。LTM算法是分布式的，全部节点做相同的LMT操作。LTM对整个网络造成的开销是O（n）。同时，全部节点的时钟必需同步。44也采纳了相像的两跳来优化分布式P2P拓扑。4546则是采纳测量来回时延的方法，避开了时钟同步问题。47将这种两跳消息用于结构化P2P系统中。D 基于缓存的方法基于缓存的，包括数据索引缓存和内容缓存。集中式P2P系统供应集中索引服务器，保存全部节点的共享文件索引。KaZaA运用合作式的超级节点，每个超级节点保存一部分节点的文件索引。有些系统将保存索引这一功能分发到全部的节点。在本地节点机制中

49、49，每一个节点维护和自己确定跳数之内的节点的内容索引信息。当节点收到查询时，它可以代表确定跳数之内的全部节点处理该查询。基于具备位置知晓性查询的基础，50、51的作者进一步提出每个节点缓存流经它的查询字段和结果。52对比了三种不同的在多个节点上复制数据的策略（文件内容或查询响应）。这三种策略不同点在于，依据不同的查询率采纳不同的安排率。透亮查询缓存53提出，基于视察网关之内的节点的查询位置，在网关处缓存查询。缓存文件内容也有所探讨。例如，54在KaZaA建立一个志向的缓存（无限容量）模拟试验，缓存文件内容。试验结果证明缓存能够在大型P2P系统中削减流量和带宽需求。3. 非结构化P2P应用Bi

50、tTorrent3.1 BitTorrent工作原理BitTorrent是集中式P2P系统，采纳集中的方式管理用户的下载恳求。文件分布网络采纳完全对等的方式，即当用户主动索取资源时，也将自动的贡献自己资源，这种协议有利于打击只想索取而不付出的“白食”用户。上传速率高的用户将优先获得较高的下载速率，得到较高的带宽利用。假如用户限制上传速率，其下载速率也将受到限制。这也保证了文件能够扩散到节点中去，以提高牢靠性。 BT网络概述BT网络架构中包含一个中心服务器，叫Tracker服务器，用户下载了.torrent文件后可获得Tracker服务器的地址。用户通过Web方式发布.torrent文件，其他用

51、户可通过简洁的 下载获得.torrent文件。.torrent文件除了包含Tracker服务器的地址，还包含应用的文件信息：文件长度、文件名、文件哈希值等。如图3-1所示，Tracker服务器跟踪全部拥有文件资源（完整资源或部分拥有都记录在内），并监控全部节点下载或上传连接行为。Tracker服务器运用 协议，下载者用以发送正在下载的文件信息以及端口号，Tracker服务器收到下载者的文件信息后，回复一个随机生成的同样在下载该文件的用户列表，下载者获得该列表后依据列表的名单依次连接这些节点，实现多源下载的机制。若下载者拥有完整的文件资源，则称其拥有一个种子（Seed）。图3-1 BitTorr

52、ent网络架构BitTorrent将文件分割成固定大小的分片（Piece），一般为256Kbytes或512Kbytes。每一个下载者都必需告知其他下载者其所拥有的分片，运用SHA1来哈希包含在.torrent文件中的全部的分片。当一个节点完成一个分片的下载并通过哈希匹配，他就向全部的其他节点宣布自己已拥有该分片，该过程可验证数据的完整性。节点的连接是完全对称的，两节点建立连接后，相同的消息可在两个方向传输，同样数据也是双向传输的，双方各取所需。当数据传输之后，下载者向上传者持续发送几个分片恳求，上传者可将这些恳求送入队列，以获得更佳的TCP传输性能，我们称这个过程为管道线（pipelinin

53、g）。不能立刻送入TCP缓存的恳求将不会送入应用层网络缓存，而是缓存和内存队列，当堵塞（choke）发生时，它们可以被干脆丢弃掉。所谓的堵塞（choking）事实上是短暂的拒绝上传，当发生堵塞时，下载者仍可接着保持连接，当取消堵塞时，下载者不须要重新建立连接。当一次发送过多连接，TCP堵塞限制性能会急剧下降。确定的堵塞算法可使得用户得到持续的下载速率。一个好的堵塞算法应达到以下几点：1. 限制同时上传的连接数，保证良好的TCP性能；2. 避开堵塞和取消堵塞的频繁发生，称之为连接抖动；3. 优先服务有所贡献的节点；4. 跟踪找出当前空闲未用连接，测试其性能是否比当前连接更优，称之为 优化堵塞。B

54、itTorrent所涉及到的术语以及功能如表3-1所示：表3-1 BT运用术语Tracker服务器结点。但它只起资源定位的作用（并不存放资源本身），为Client供应Seed及其他Clients的位置，因此负载比较低。Client客户结点。也是下载者（Downloader）。和传统的Downloader不同的是Client在下载的同时也供应上传。Seed种子。供应完整资源文件的节点。Hash哈希。把一个随意长度的字节串变换成128位的信息摘要（message-digest），以验证它的完整性，防止被篡改。BT运用SHA1 hash主要来验证文件的完整性，并用以标识Piece在BT网络中的唯一性

55、。Announce发布.torrent文件。一般来讲，发布.torrent文件的人就是想把自己的资源共享给别人的人，即是一个种子（Seed）。Piece分片。.torrent文件（Metainfo文件）中所描述的一份下载数据，可以由SHA1 hash码来校验。Block块。由Client向Peer所恳求的一份数据；若干个Block共同构成一个Piece，之后Piece被校验。 BT下载流程如图3-2所示，Client A下载的流程如下：图3-2 BT下载示意图1. 从Web Server上获得.torrent文件。.torrent记录了下载文件的全部信息，如文件名，书目名，长度以及分片（Piece）长度和分片的Sha1校验码，表3-2为.torrent文件所获得的信息示例表3-2 .torrent包含信息示例Torrent文件特征码1d0d170d28532efbe30e0418b2878b7e6291d561分块大小256 KB总计大小311.09MB选择下载大小311.09MB备注服务器 :/:8080/2. Client依据.torrent文件中服务器地址，连接发布服务器（Tracker），若连接胜利，Tracker将记录连接Client的IP地