毕业设计（论文）BitTorrent网络内容缓存服务器的设计与实现

《毕业设计（论文）BitTorrent网络内容缓存服务器的设计与实现》由会员分享，可在线阅读，更多相关《毕业设计（论文）BitTorrent网络内容缓存服务器的设计与实现（84页珍藏版）》请在装配图网上搜索。

1、北京邮电大学本 科 毕 业 设 计（论文）题目： BitTorrent网络内容缓存服务器的设计与实现 姓 名 学 院 信息工程学院 专 业 信息工程 班 级 0213101 指导教师 2006 年 6 月 北 京 邮 电 大 学本科毕业设计（论文）任务书学院信息工程学院专业信息工程班级0213101学生姓名指导教师姓名职称教授/博士生设计(论文)题目BT网络内容缓存服务器题目分类1、工程实践类 研究设计类 理论分析类 （1、2类中各选一项在内打）2、软件 硬件 软硬结合 非软硬件主要任务及目标：1、 完成翻译任务，学习P2P网络知识，包括P2P的基本特性、优点、不足，以及在国内外的的发展现状，

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

3、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 Rec.Shamir, A.: How to share

4、 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网络内容缓存服务器的设计与实现摘 要近年来，大量的研究结果表明现今的互联网网络流量已不仅仅由HTTP、FTP、POP3、SMTP等传统业务流量所组成，其中大部分是对等（Peer-to-Peer）网络产生的流量。P2P以其相对于C/S模式的巨大优势，不仅激发了信息技术领域科研人员的研究热情，而且也调动了普通用户对P2P的使用和期望。这些因素使P2P成为一个热门的前沿研究领域。P2P技术的迅速发展和投入

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

8、扑结构的不匹配，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-Peer network is a new type

10、 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 has been one of the most hot

11、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 Working Group Committee, P2

12、P 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 addition, user download resources

13、 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 are chosen randomly. So the

14、 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. First, we build simulation env

15、ioronment 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 performance. The cache server s

16、ystem can reduce the traffic between networks and the cost of network operators. KEY WORDS Peer-to-Peer cache-server-system topology-matching BitTorrent3目 录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叠加网51.3.3 混合型P2P叠加网52. P2P网络的位

17、置知晓性.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 内容缓存服务器概述244.2 提取识别资源原理分析244.

18、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打开了对等网络的大门，促使了后来各种P2P系统的发展。BT是目前最热门的下载方式之一，它

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

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

22、之上。对等网络具有许多优点，如健壮的大区域路由体系结构，数据搜索的高效性，附近节点的发现和选择，冗余存储，良好的可扩展性以及容错性等。与传统的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所示。给定一个索引，存储操作（put(key, value)）可将对应于该

26、索引的数据对象进行存储操作，同样查找检索操作（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）、分布式的（Decentralized）和混合型的。1.3.1 集中式P2P叠加网

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

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

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

31、索引节点获得搜索节点信息，之后用户节点就与获得的搜索节点相连，每一次查询都通过该搜索节点进行。当用户发出搜索请求后，如果和用户节点直接相连的搜索节点查询结果达到100个（这里的100个搜索结果，可以由用户自己来设定）就停止；如果不足100个，就向相邻的搜索节点发出请求，如果查询结果还不够，就继续向外快速散播，直到所有的搜索节点都被搜索到为止。这样，搜索过程就像在照着交通指示牌循序问路，而不是路上随便找个人问路，这样很大程度上提高了搜索效率，节约了带宽。15在混合模式中，如何将功能相似的节点聚集在一起，进而在此基础上制定完备的搜索算法，对这种P2P系统的性能与开销起着至关重要的作用。BT就是第三

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

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

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

35、P系统中，新节点加入时会先连接引导节点，获得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邻居节点之间的叠加层逻辑连接。节点S是发起查询的源节点。箭头

37、表示沿着逻辑连接传送的查询消息。可以看到，基于洪泛查询机制，每个节点接收到查询消息后，就转发给自己的所有邻居节点（除了消息发送节点），这样，每个节点都收到了多份相同的查询消息，这在网络上造成了大量不必要的重复消息。图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）部分的高效叠加层。消息只会经过所有物理链接一次。19研究结果表明，在Gnutella网络中

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

40、发机制的改进方法原理，对于分布式P2P系统来说就是，节点根据位置信息选择一部分邻居而不是所有的逻辑邻居来转发查询消息。22提出的有向BFS算法中，每个节点维护一个基于某些度量值的统计信息，例如从邻居获得的查询结果数量、与该邻居的链接时延。节点选择返回最多查询结果的邻居或者最近的邻居来转发查询消息。23提出的K-walker查询算法，源节点会发送k个不同的walker（转发邻居）。walker到达的节点，随机只选择一个邻居来转发该查询。而对于每个walker来说，查询过程是顺序处理的。24提出的混合周期洪泛（HPF）算法，根据多种度量值来选择转发邻居。强调部分覆盖问题，来平衡搜索开销和响应时间之

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

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

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

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

45、知名地标节点（如固定互联网服务器）的时延值。然后，每个节点根据时延的大小，排列这些地标。有着相同地标排列顺序的节点，就被归为一个集群。38也使用了地标节点，选择接近网络接入点的高性能节点来提供到其他集群的连接。但这需要在整个P2P网络范围进行测量，需要额外的地标支持，从而可能使这些站点过载。另一方面，精确度比较粗，比较接近的节点可能被分为一组。39提出试探法来解决集群问题。主机客户端可以调整直径D的大小。选择相互间距至少为D的称为marker的特殊主机，来代替知名地标。40则提出选用邻居充当动态地标。原因是比测量较远处的更加准确，并且可以减少网络开销。41提出一种基于相同需求的在P2P叠加网之

46、上的上层网络，其观点为，如果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应用BitTorrent3.1 BitTorrent工作原理

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

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

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

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

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

55、rent文件。一般来讲，发布.torrent文件的人就是想把自己的资源共享给别人的人，即是一个种子（Seed）。Piece分片。.torrent文件（Metainfo文件）中所描述的一份下载数据，可以由SHA1 hash码来校验。Block块。由Client向Peer所请求的一份数据；若干个Block共同构成一个Piece，之后Piece被校验。3.1.2 BT下载流程如图3-2所示，Client A下载的流程如下：图3-2 BT下载示意图1. 从Web Server上获取.torrent文件。.torrent记录了下载文件的所有信息，如文件名，目录名，长度以及分片（Piece）长度和分片的S

56、ha1校验码，表3-2为.torrent文件所获取的信息示例表3-2 .torrent包含信息示例Torrent文件Torrents超级2代电力公司精选 10.18.torrent特征码1d0d170d28532efbe30e0418b2878b7e6291d561分块大小256 KB总计大小311.09MB选择下载大小311.09MB备注服务器:8080/2. Client根据.torrent文件中服务器地址，连接发布服务器（Tracker），若连接成功，Tracker将记录连接Client的IP地址，并且放入该资源拥有者列表里，以供其他Client申请该资源时能够找到资源拥有者。同时，Cl

57、ient从Tracker处获得Peer列表，这样就得到了可下载地址。之后，Client在以下情况之一发生时，向Tracker发起连接： 根据tracker response中的interval定时发送 事件发生(stopped, completed)时发送 需要更多的peer列表时发送3. 连接Peer，开始下载自己所缺的Piece。BT Client的整个下载流程图如图3-3所示：图3-3 BT Client下载流程图当节点连接节点列表中的节点后的消息序列如图3-4所示，其中AZ和BT下载端都是BitTorrent网络中的用户节点，其中AZ拥有完整的文件资源，即种子，并主动发起连接，BT下载

58、端向种子节点索取下载资源。1. 由AZ发起TCP连接，完成三次握手之后，AZ发HandShake报文，该报文内容包括特征字段“BitTorrent protocol”，8byte保留字段”00000000”，20byte该种子的info_hash，20byte自己的peer_id。之后BT下载端发送HandShake报文，内容除了保留字段均一样。2. AZ和BC交换BitField报文，该报文含有节点所拥有的分片情况，1表示拥有该分片，0表示没有该分片。由于AZ是种子，因此为全1，同样，在开始BT下载端为全0。AZ的BitField报文内容如下：00 00 00 6e 05 ff ff ff

59、ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff

60、ff ff ff ff ff 80BT下载端的BitField报文内容如下：00 00 00 6e 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0

61、0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 003. BT下载端发送Interest报文，以告知AZ拥有其所需分片，请求下载。4. AZ发送Unchoke报文，表示接受下载请求。5. BT下载端发送5个Request报文，每一个Request请求一个块，一般为16K一块。之后AZ根据请求发送相应的块，连同包含piece信息的包在内一共分12个报文完成一个块的传输。BT下载端继续请求Request一个分片中的其它块。6. 当BT下载端下载完成一个分片中的所有块数据，即获取完整的一个分片之后，向AZ发送Have报文，以告知拥有该分片。7. 重复第5、6步，直到所有的分片全部下载完成。AZ发送FIN发起断开连接。图3-4 BT Client下载消息序列3.2 BT位置知晓性测量实验3.2.1 实验目的以校园网环境为测试平台，在校园网中部署BitTorrent用户，通过下载校园网内存在资源的文件，比较流入校园网的网络流量与源文件的大小，测量现有的BT软件的位置知晓性。若BT具有良好位置知晓性，则出入校园网的流量应与下载文件的大小相差不多，证明大部分流量是网内交换完成。3.2.2 实验原理在P2P网络中，文件下载可以分为两种情况。一是单点对单点之间的传输。这时