上海交通大学硕士学位论文大规模对等网络中节点统计特性分析及应用姓名：孟世聪申请学位级别：硕士专业：计算机应用指导教师：俞勇20061201摘摘摘要要要目前各类P2P网络的规模越来越大。对于文件共享的P2P网络，同时在线的用户数通常可以达到数百万，而即时消息类的P2P网络则拥有更多的并发用户数，但随之而来的很多问题也逐步出现，其中包括：(1)人们目前对大规模P2P网络发展的情况和特点并不十分了解，这种情况的出现往往使得研究工作缺乏针对性；(2)由于缺乏真实P2P系统中网络结构、用户行为等信息，很多模拟环境往往只能通过一些启发式的模型来生成，因此与真实系统中的情况存在不一致的可能；(3)缺乏现有系统运行中的各类性能指标和统计数据严重影响了未来P2P系统的设计。上述这些现象很好的说明了当前P2P网络统计特征分析的迫切性和必要性。为了解决这些问题，我们在当前流行的Gnutella0.6平台上开展了相应的统计特征分析工作，并提出了一些应用，其内容包括：(1)设计了一个高效的分布式协作P2P爬虫系统，解决了Gnutella0.6协议上的统计数据收集问题；(2)从节点在线时间、节点角色选择、节点连接情况、共享文件以及查询消息分布等方面较为全面的分析了Gnutella系统的统计特征；(3)从时间序列的角度分析了Gnutella系统中查询消息流的特性，并研究了查询消息数量的可预测性；(4)提出了Gnutella系统中基于该模型的结果缓存机制和Chord系统中同样基于该模型的动态负载均衡机制。我们的工作的主要意义在于(1)发现了Gnutella0.6中新出现的一些重要的现象和问题，如节点角色的选择问题等，为将来的研究提供了基础；(2)提供了很多精确的统计数据，为今后的P2P系统建模提供了重要的依据；(3)作为P2P系统流数据的挖掘方面的首个尝试，提出了从时间序列角度研究P2P数据流的方法；关关关键键键词词词 对等网络，统计特征分析，Gnutella，查询、结果缓存、负载平衡2AbstractThe population of peers grows much large than ever before in todays peer-to-peernetwork, i.e., the number of online peers of a popular file sharing P2P system oftenreaches several million, while instance message system has much more users. However,many problems emerge during this period, including: Researchers do not precisely know the current status of peer-to-peer network, whichalso makes some research aimless. Lack of the information of peer-to-peer network structure as well as user activities,many simulation studies can only be performed based on heuristic models, whichare very likely to be unrealistic. The design for future P2P system can not be started or be beneficial withoutdetailed performance statistics.As the above phenomenon clearly suggested, P2P network statistical study andcharacterization is indispensable. To address the problems mentioned above, we per-formed a statistical study over a popular file sharing system, Gnutella 0.6, and proposedsome related applications. Our work mainly includes:(1) Designing and implementing an efficient distributed collaborative peer-to-peercrawling system, which provides a solution for collecting statistic information ofGnutella 0.6.(2) Analyzing the characteristics of Gnutellas query message stream from a time seriesaspect, and evaluated the predictability of Box-Jenkins models for the number offuture query messages.(3) Proposing two applications based on Box-Jenkins models, one is collaborative re-sult caching in Gnutella, the other is enhanced dynamic load balancing in Chord.The contribution of our work mainly lies in the following areas:(1) Discovering new and important phenomena in Gnutella 0.6, such as peer roleselection, which provides target for future research.(2) Providing reliable statistic data for modeling and simulating of peer-to-peer net-work.3英文摘要(3) Analyzing the characteristics of Gnutellas query message stream from a time seriesaspect, which is, to the best of authors knowledge, the first work regarding thestreaming mining in peer-to-peer system.Keywords: Peer-to-Peer Network, Statistical Analysis and Characterization, Gnutella,Query, Result Caching, Load Balancing4 上海交通大学上海交通大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 孟世聪 日期： 2007 年 1 月 18 日 上海交通大学上海交通大学 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密保密，在 年解密后适用本授权书。 本学位论文属于 不保密 不保密。 （请在以上方框内打“” ） 学位论文作者签名：孟世聪 指导教师签名：俞勇 日期：2007 年 1 月 18 日 日期：2007 年 1 月 24 日 第一章引言1.1对等网络应用的起源和发展互联网的出现使得分布在地球各个角落的计算机获得了互连互通的能力。然而它对这些计算机如何交互既没有做任何限制，也没有做任何向导。也就是说，虽然机器之间可以互通了，但它们并不知道该和哪些机器进行互通。?(a)?(b)图图图 1-1客户端服务器构架和对等网络构架，(a)客户端服务器构架；(b)对等网络构架Fig. 1-1Client-Server and Peer-to-Peer Architecture. (a)Client-Server Architecture. (b)Peer-to-Peer Archi-tecture.客户端服务器构架（图1.1(a)）提供了一种解决方案一台服务器发布信息/服务，其它机器作为客户端去获取信息/服务。在此基础上，互联网开始有了各种各样的应用，如：DNS、WWW、FTP、Email等等。随之而的一些问题也逐渐被发现，其中最主要的问题就是服务器过载和服务器故障。由此又引出一些负载平衡的技术，通过设立多台服务器并将客户端的请求均匀的分散到各个服务器上去处理，从而解决这些问题1。近年来，互联网上兴起了另外一种思路来解决和谁互通的问题，它抛弃了服务器和客户端这样的角色划分，那就是基于对等（Peer-to-peer, P2P）网络（图1.1(b)）的应用。P2P的定义有很多个版本。Intel P2P工作组的定义是“通过在系统之间直接交换信息来共享计算机资源和服务”的系统。Aberdeen大学的Alex Weytsl的定义是“以非客户端的方式利用Internet周边的设备” 2。Ross Lee Graham通过三个基本要求来定义P2P：1)具有可运作的服务器能力；2)具有独立于DNS的寻址系统；3)能够处理各种连通性3。OReilly &http:/www.p2pwg.org/1第一章 引言Associate的Clay Shirky使用下面的定义：“P2P是一类利用资源存贮、周期、内容、人力因素等特性的应用。由于要获取这些分布式的资源意味着在一个具有不稳定连通性、不可预见IP地址特性的环境中操作，P2P节点必须在DNS系统之外运作，并且对中央服务器大部分或彻底匿名”4。这些定义虽然各自表述不同，但都或多或少的提到了对等网络构架和以前客户端服务器构架的不同。由于日益提升的普通PC机性能使它们本身也可以提供信息/服务，对等网络便将原先需要在服务器上进行的运算和存贮负载分布到整个网络中，从而大大降低对服务器的性能要求，甚至不需要服务器。或者说，每一台计算机都既是信息/服务的供应者，又是信息/服务的消费者。从最早1996年用于寻找外星球智慧的SETIhome5，到后来让大众熟悉对等网络的Napster6，再到采用纯对等结构的Gnutella7，这些应用都充分利用了对等网络构架相对于客户端服务器构架的优点，而将原本在客户端服务器构架时代不可能做到的愿望变成现实。SETIhome到目前已经成功的让5,414,992个用户贡献了2,286,333.963年的CPU计算时间，计算了6.849777 1021次浮点运算。如果这些运算让目前世界上运算能力最强大的超级计算机来做，也要至少花费3年的时间。这个项目非常成功的用很低的成本来获得了这些计算能力。Alfred W. Loo认为这种应用模式将会成为对等网络的未来8。除了分布式运算，对等网络还广泛应用于文件共享9和协作通讯等领域。Napster 6、Gnutella 7、BitTorrent10、eMulek等等都是有很大用户群的文件共享系统。而协作通讯的应用更是不计其数，如ICQ、MSN Messenger、Yahoo Messen-ger等。1.2P2P网络的统计特性分析的引入尽管对等网络的应用有着非常美好的前景，其发展并不是一帆风顺的。除了一些诸如用户隐私和版权方面的问题11外，还存在很多其他的问题。目前各类P2P网络的规模越来越大。对于文件共享的P2P网络，同时在线的用户数通常可以达到数百万(如Gnutella2.1.3)，SETI (Search for Extraterrestrial Intelligence) 是一整套以寻求外星智慧为目标的研究项目。SETIhome5 是这些项目中的一个，它利用数百万连入Internet机器的空闲计算能力来分析从卫星天线上收集到的无线电波。http:/www.napster.com/数 据 来 自 于SETIhome官 方 网 站2005年5月9日6点33分43秒 时 的 统 计 ， 最 新 数 据 参 见http:/setiathome.ssl.berkeley.edu/totals.html。根据Top 500 超级计算机站点公布的最新数据计算而得。截至2004年11月底，世界上计算能力最强大的超级计算机是IBM的BlueGene/L DD2 beta-System，具有每秒计算7.072 1013次浮点运算的能力。有关最新的超级计算机运算能力排名可以参考http:/www.top500.org/lists/current.php。http:/www.bittorrent.com/khttp:/www.emule-project.net/http:/www.icq.com/http:/messenger.msn.com/http:/messenger.yahoo.com/2第一章 引言而即时消息类的P2P网络则拥有更多的并发用户数。很多P2P系统在设计之初往往没有考虑到网络会有今天的规模，而且P2P系统中没有中央管理(协调)机制的特点使得一些关于整个网络的重要统计数据很难获得，由于以上这些原因，人们目前对大规模P2P网络发展的情况和特点并不十分了解。这种情况的出现往往使得研究工作缺乏针对性，如非结构化P2P系统一直被人们认为缺乏可扩展性(Scalability)，但是却鲜有刻画这一特点的统计数据。因此，研究工作者往往只能根据实验室中的模拟系统来寻找现有系统的问题。另外，为了验证方法的正确性，研究人员还经常需要构建模拟环境，但由于缺乏真实P2P系统中网络结构、用户行为等信息，这些模拟环境往往只能通过一些启发式的模型来生成，因此与真实系统中的情况存在不一致的可能。最后，就未来P2P系统的设计来说，把握住现有系统运行中的各类性能指标和统计数据也是一个必要条件。上述这些问题逐步使人们意识到P2P网络统计特征分析的重要性，因此，从2001年开始，一些研究人员就开始在各类流行的P2P系统上收集统计数据并分析网络中存在的现象和问题。他们的工作被人们广泛的接受和引用，特别是一些典型的文件、查询的分布模型(如Power-Law模型)也成为人们普遍接受的用来模拟P2P系统的经典模型。3第二章相关领域研究现状2.1对等网络应用的构架2.1.1应用构架的分类和进化过程对等网络经过近几年的发展，在节点角色分配和网络结构上均有所发展12, 13。早期的对等网络应用带有强烈的服务器/客户端构架的印记。这些应用系统无一例外的保留了服务器的角色，并且引入了对等网络的思想，称为部部部分分分对对对等等等网网网络络络应应应用用用。例如SETIhome5、Napster 6、ReachOut14等系统。随后，Gnutella7的出现将对等网络应用引入完完完全全全对对对等等等网网网络络络应应应用用用阶段。它舍弃了服务器的角色，系统中各个节点的地位都完全对等。但是很快Gnutella就发现在这种构架下系统的性能有问题(主要是泛洪的带宽问题)，于是又引入超节点(super peer)的概念，形成了层层层次次次对对对等等等网网网络络络应应应用用用，KaZaA15和Edutella16也都采用了这种构架。也有人提出另外一种解决方案，就是通过分布式哈希表的方法，将对等网络有结构的组织起来，这类应用叫做结结结构构构化化化对对对等等等网网网络络络应应应用用用，典型的系统有CAN17、Chord18、Pastry19、Tapestry20等。?SETIhome,Napster,ReachOutKaZaA,Edutella,GnutellaCAN,Chord,Pastry,TapestryGnutella?图图图 2-1对等网络构架的分类和进化过程Fig. 2-1The Classification and Evolution of Peer-to-Peer Network图2-1画出了对等网络进化的过程。总的来说，对等网络的发展呈现两大趋势。第一，是角色分类从部分对等，到完全对等，再到层次对等，这一趋势使得对等网络中的节点分工越来越复杂，而整个系统的性能越来越好。第二，是网络结构从没有结构到有结构，这一趋势从另一个角度来优化对等网络的性能。目前，这种结构主要是通过分布式哈希表的方法，但这并不意味着只能通过这种方法，社区模型也是一种可行的途径。后面四小节将分别按照对等网络应用的构架介绍前面提到的各个系统。4第二章 相关领域研究现状2.1.2部分对等网络应用1.SETIhomePC/MACUNIX?SETIhome?5?0.25MBInternet?PC/MACUNIXPC/MACUNIX图图图 2-2SETIhome框架图Fig. 2-2The Architecture of SETIHome.SETIhome项目使用了两个主要组件：数据库服务器和客户端。项目组提供了许多操作系统上可运行的客户端工具，包括Windows、Linux、Solari和HP-UX (参见图2-2)。他们的数据库已经被证明非常稳定并具有很强的扩展性。客户端软件被嵌入屏幕保护程序(尽管也有单独的程序)，而且没有利用第三方的技术。该系统客户端的容错性也是系统的一个主要价值。由于一个数据的批处理可能需要好几个小时才能完成，客户端必须能保证在任何时候都可以被打断(用户可能在任何时候登陆进系统，从而中止屏幕保护的运行)，并可以在未来某个时刻继续运行。甚至在用户重新启动机器以后还能继续上一次的批处理。SETIhome客户端利用checkpoint机制，每个十分钟保存一下系统环境参数，以便以后继续。也就是说，一旦程序被打断，下一次程序将从上一个checkpoint继续运行。这个简单的机制仅给运算过程带来了一点点负担和复杂性，但却使整个程序变得非常可靠。作为比较原始的对等网络系统，SETIhome项目对负责给各个用户分发工作和收集运算结果的服务器非常依赖。系统的横向扩展性(用户数量)非常优秀。而它的纵向扩展性却是瓶颈，因为它仅用一台单一服务器负责所有的协调事务。然而，这台服务器还足以应付目前用户的负担。和SETIhome类似的应用还有计算蛋白质折叠的Foldinghome和计算基因组的Genome-home21等。http:/folding.stanford.edu/http:/www.stanford.edu/group/pandegroup/genome/5第二章 相关领域研究现状2.Napster?图图图 2-3Napster框架图Fig. 2-3The Architecture of Napster.Napster6是一个共享MP3音乐的系统。其结构如图2-3。系统有服务器记录各个节点上共享的文件，并且建立索引。当一个节点想要查找并下载一个MP3的时候，它首先向服务器发送查询请求，然后服务器把结果送回，结果里包含目前可以从那些节点上下载这个文件的信息。然后，它再从这些节点下载文件。Napster的结构非常简单，但是在上个世纪90年代末却在美国得到广泛应用。其最鼎盛时期大约有6000万名用户。2001年，由于牵涉音乐版权问题，美国法院下令要求关闭Napster的免费的歌曲交换服务。现在，Napster已经开始提供新的不违反美国版权法律的歌曲有偿下载服务。3.小结上述几个系统都具有对等网络系统的一些典型特征，包括：(1)管理成本和资源共享成本较低。通过使用对等网络构架削减和平摊了维护服务器的成本，对等网络系统的成本大大降低。(2)整体的高价值性。对等网络可以通过低成本的协同工作将资源聚集在一起，使得整个系统的效能大大提高。(3)匿名和隐私。通过在对等网络系统和应用中的特殊设计，节点对资源的访问和管理可以做到匿名。当然，部分对等网用的广泛应用也让人们发现一些问题。这些问题既有技术上的，也有非技术的。技术上的问题它依然采用了服务器，一旦服务器出现故障，整个系统就处于瘫痪6第二章 相关领域研究现状状态，也就是所谓的“单点故障”问题；而一旦没有服务器，就必须找到有效的方法来定位用户需要的资源(这里的资源包括：文件共享系统中的文件、分布式计算系统中的计算能力以及通讯与协作系统中的人力资源)。非技术上的主要是法律问题，就像Napster被指控违反版权法那样。2.1.3完全对等网络应用完全对等网络应用以Gnutella的早期7为代表。它也是文件共享系统，并且没有服务器。也就是说所有加入系统的节点都是完全对等的。也正因为如此，每个节点需要维护一个邻居列表，以便和系统中的其它节点进行通讯。?A?C?D?B?(a)?A?C?D?B?(b)?A?C?D?B?(c)?A?C?D?B?(d)图图图 2-4Gnutella的查询过程，(a)发送请求；(b)请求转发-1；(c)请求转发-2；(d)收到回复Fig. 2-4The Search Process of Gnutella. (a)Sending Request. (b)Forwarding Request - 1. (c)ForwardingRequest - 2. (d)Receiving Response.在这个系统中的文件搜索过程如图2-4。一个节点作为请求方在查找文件的时候，首先向它的邻居节点(节点A和节点B)发送查询请求，如图2.4(a)；节点A和节点B发现自己无法回答请求的时候，再把请求发送到它们各自的邻居那里，如图2.4(b)；这种方法称为泛洪算法，因为搜索请求会像泛洪那样向整个网络散播，并且对于同一个查询请求，同一个节点可能会收到多次，如图2.4(c)；当节点发现自己具有该查询请求所需要的文件的时候，就按原路返回把请求的回应传送到请求方，如图2.4(c)和2.4(d)所示。泛洪算法的确能够在完全对等网络中进行文件查询，但是其缺点也是十分明显的。它使7第二章 相关领域研究现状用了非常多的网络带宽来完成一次查询，并且一次查询会牵涉到网络中的所有节点。在大规模的对等网络里这么做，可能会使整个网络处于瘫痪状态。因此出现了一种受限的泛洪算法。它采用了类似IP协议中的TTL机制，给每个查询加上一个生存期，限制其在网络中转发的次数，以缩小一个查询牵涉到的节点范围。还有一些研究通过在网络中存放多份文档副本来优化查询性能22或加入缓存机制23，但是这些都没有改变泛洪算法的本质。Gnutella得到了广泛应用。根据Matei Ripeanu等人的测算，2001年3月份的时候，Gnutella网络的流量（不包括文件传输部分）已经达到330 TB/月24。而根据Gnutella客户端Limewire的官方网站公布的统计，网络上使用Gnutella的在线用户一直保持在一百多万的水平。完全对等网络应用还有Freenet25, 26，它的原理和Gnutella相同，用缓存机制来优化搜索性能。2.1.4层次对等网络应用?E?B?D?F?C?A?2?2?B?图图图 2-5层次对等网络资源定位机制Fig. 2-5The Resource Locating Mechanism in Structured Peer-to-Peer Network.在Gnutella的新协议中，已经将完全对等的网络结构改变为层次对等网络结构了。不同之处在于引入了超节点的概念。在这样的对等网络中，资源定位不再像泛洪算法那样盲目，而是由超节点负责建立挂靠在超节点下面的节点所拥有资源的索引，参见图2-5，查询仅在超节点之间进行转发的。当节点A要查询文档2的时候，它首先向它的超节点发送请求，然后由超节点来负责查询的工作，并将结果返回给节点A，然后节点A根据返回的节点进行文件下载。采用这种结构的应用系统还有FastTrack、KaZaA15、Edutella16等。由于超节点的引入，使得这些系统的性能比完全对等网络应用系统的性能要高许多，因此可扩展性也更高。但是，层次对等网络应用引入的超节点被一部分研究人员认为实际上就是服务器，因此这种构架并不被所有人接受为对等网络的构架。另外，这种结构依然没有彻底解决在完全对参见：http:/www.limewire.com/english/content/uastats.shtmlhttp:/rfc-gnutella.sourceforge.net/src/Ultrapeers 1.0.htmlhttp:/www.fasttrack.au/8第二章 相关领域研究现状等网络中遇到的搜索性能问题，在一次搜索过程中，查询还是只能在网络中一部分节点的范围内进行。2.1.5结构化对等网络应用1.概述?API?:Put(key,value)API?:Remove(key)API?:Value=Get(key)Value?图图图 2-6基于分布式哈希表的对等网络应用Fig. 2-6Application Based on DHT Network.结构化对等网络对完全对等网络提出了另外一种改进的方法，那就是通过分布式哈希表将整个对等网络有效的组织起来。这种类型的应用提供了几个通用的API接口，包括：Put(Key,V alue)、Remove(Key)和V alue = Get(Key)，如图2-6。系统将资源通过哈希算法将资源和一个标识对应起来。每个节点按照一定的策略负责对一部分标识的资源进行索引。当系统中加入新的资源的时候，就通过Put(Key,V alue)来实现；查找资源的时候通过V alue = Get(Key)就可以获得资源；相应的，Remove(Key)可以删除资源。理论上说，基于分布式哈希的应用能保证定位资源牵涉的节点数最多为O(logN)，式中N是网络中的节点数目。结构化带来的好处是显而易见的，它的定位机制非常有效；但是它也有缺点。在有结构的情况下，节点的加入和退出需要一些额外的操作。每个节点的加入和退出都会导致系统的结构发生变化。在高度动态的对等网络中，维护结构就成为一种负担。不过，这种负担在现在的系统中都还能够承受。2.CANCAN17是一个自组织的结构化对等网络应用。它将分布式哈希表的标识设计为d维逻辑空间中的点。每个系统中的节点维护一小块空间的索引工作。当一个节点加入网络的时候，先随机产生一个空间的点，然后通过CAN的路由机制路由到当前负责这个点所在空间的节点，并且和该节点平分空间。图2-7举了一个两维空间CAN网络的例子。图2.7(b)显示了节点维护的邻居集合。CAN的每个节点仅维护和自己相邻的节点，在两维空间里，就是上下左右的点。因此节9第二章 相关领域研究现状ABCDEX?X?E?(a)?X? = A B D Z?Z? = A C D XABCDEZX(b)图图图 2-7两维空间的CAN网络举例，(a)路由方法；(b)邻居集合和节点加入机制Fig. 2-7An Example of Two-Dimension CAN Network. (a)Routing. (b)Peer Joining.点X的邻居集合就是A,B,D,Z，而节点Z的邻居集合就是A,C,D,X。有了这些信息，每个节点对于某个特定的标识，就知道应该把接力棒交给那个方向的邻居，从而达到对标识的路由。图2.7(b)显示了一条从节点X到节点E的路径，当然，这样的路径可能不止这一条。图2.7(b)还显示了节点Z加入的情形。假设节点Z加入系统，它从一个已知的节点便可以路由到负责该随机产生的点坐标所在的小块空间索引工作的节点这里，假设这个节点是X，于是X负责Z那里一半空间的索引工作。由于点的坐标是随机产生的，所以整个空间的划分是均匀的，各个节点的负载比较均衡，网络中节点之间的平均路径长度为O(n1d)，也就以为着对于一个确定的资源，CAN可以在较短的时间内找到，中间仅牵涉O(n1d)个节点。相对于泛洪算法，这是已经是很大的提高了。CAN的节点推出系统时，它的邻居要负责该节点原先负责索引的小块空间。如果这个节点是正常退出，那么就由周围负载空间最小的节点来负责。如果是突然退出，那么有就由周围最先发现该节点不存在的节点来负责。因此，CAN的节点和邻居节点之间要保持通信，但这个通信量很小。目前已经有一些实用的存储系统应用了CAN模型，包括OceanStore 27、Farsite28和Publius 29等。3.ChordCAN利用了分布式哈希提高了资源定位的性能，但它的算法性能是和空间维度d相关的，而这个维度却不能在系统运行过程中改变。Chord环18解决这个问题。在一个稳定的N节点Chord系统中，每个节点只需要维护O(logN)条到其它节点的路由信息就可以使整个系统具有能力完成任何两节点之间的路由工作。Chord环使用一致哈希算法（Consistent Hash 30）来分配节点和资源的标识。该算法基于SHA-131，给每个节点和10第二章 相关领域研究现状资源分配的标识是m位的二进制数，整个系统可以容纳2m个节点，标识分别从0到2m 1。每一个资源的索引建立在其标识的后继节点上。后继节点(successor(k)是环中从标识k开始顺时针走遇到的第一个节点。当一个节点加入系统时，要从该节点标识的后继节点处，拿回应该新节点负责索引的数据部分。而当它退出时，应该把这部分数据转交给后继节点处理。因此节点加入/退出系统时候的消耗是O(log2N)的。N4N8N14N21N32N38N42N48N51N56K54K38K30K24K10?(K54)(a)+2?N8+1N14N8+2N14N8+4N14N8+8N21N8+16N32N8+32N42N4N8N14N21N32N38N42N48N51N56+1+4+8+16+32(b)图图图 2-8Chord环举例，(a)索引方法；(b)路由方法Fig. 2-8An Example of Chord Ring. (a)Indexing. (b)Routing.图2-8是一个m = 6的Chord环，因此总共可以容纳26= 64个节点，现在一共有10个节点，它们的标识前都标有字母N。字母K后面的标识是文件的标识。根据Chord环的设计，10号文件的索引由14号节点负责，38号文件的索引有38号节点来负责，见图2.8(a)。图2.8(b)显示了8号节点维护的路由表，它维护了从自己的标识开始的6个节点信息，分别是8 + 2i（i=0,1,.,m-1），其它各节点也都有相应的路由表。当8号节点想查找54号资源的时候，它首先查询自己的路由表，发现54 8 = 46 32，于是就将请求发给42号节点；然后42号节点再查询自己的路由表，发现8 54 42 = 12 16，便将请求转发给51号节点；51号节点在做同样的工作，最后定位到56号节点；56号节点再将索引信息按原路返回给8号节点。这样就完成了一次资源的定位工作。Chord环的路由机制非常依赖于正确的路由信息，也就是说每个节点都需要经常看看路由信息是不是还能用，否则就会有路由上的问题。这可以通过多维护一些后继节点的路由信息来降低系统瘫痪的概率。假设一个节点失效的概率是p，那么维护r个后继节点信息就可以使系统失效的概率降低到pr。Chord模型已经被CFS32和Chord-based DNS33等系统应用。11第二章 相关领域研究现状4.Pastry和TapestryPastry19和Tapestry20是两个很相像的模型，只是在具体的网络定位和数据复制方面稍有差别，这里仅介绍Pastry。Pastry和Chord一样，也是环状构架。不过Pastry的标识是128位的二进制数，并且是在节点加入系统的时候随机分配的。一个含有N个节点的Pastry环的路由过程会牵涉到少于logBN个节点，其中B = 2b，b是一个系统参数，一般取4。另外Pastry的路由表也比Chord要复杂。199ABC28989C26722122114519902D16228A12216711345B5213EA510A0C290A0B279DE0490CDE4881AB47781046710A3912CD390AF037890A3612AB2670AB245AD01B34671A223B37A0FE37A0FC37A0FB37A0FA37A0F837A0F637A0F437A0F237A07737A06637A05537A04437A03337A02237A01137A00137ADF137AFx37AEx37ADx37ACx37ABx?37A2x37A1x37A0x37Fx37Ex?37Bx37Ax?372x371x370x3Fx3Ex?38x37x?32x31x30xFxExDx?4x3x2x1x0x?B57B2DB581F1B578D6B573ABB5324FB24EA337A0F1B57B2D?图图图 2-9Pastry环举例Fig. 2-9An Example of Pastry Ring.图2-9是一个Pastry环的例子。每个Pastry环的节点维护一张路由表、一个邻居节点集合和一个叶子节点集合。路由表是一个logBN行、B 1列的表格。第i行的B 1个单元格记录着和当前节点的标识前i位相同但i + 1位不同的节点标识和IP地址。b的大小会影响到路由表（有(logN) (B 1)个单元格）的大小和路由牵涉到的节点数（logBN），需要做一个权衡。在106个节点的Pastry环里，如果b = 4，那么路由表有75个单元格，每次路由牵涉到的节点数为5。邻居节点集合里面记录了|M|个和当前节点IP接近的节点标识和IP。叶子节点集合里面分别记录了|L|/2个标识小于但接近当前节点标识的节点和|L|/2个标识大于但接近当前节点标识的节点。|L|和|M|通常取值B或者2B。由于维护的信息比Chord多，节点加入和退出在Pastry环中的消耗也相对较多；但是对邻居节点集合的维护却使得Pastry考虑到了节点之间网络传输的延时，使系统在实际应用中有更好的效果。目前，基于Pastry和Tapstry的应用包括Scribe34、Squirrel35、PAST 36和12第二章 相关领域研究现状Pastiche37等。2.1.6四种构架的比较表表表 2-1四种对等网络构架的优缺点Tab. 2-1Comparison Between Different Types of Networks构架优点缺点部分对等网络有服务器，应用结构简单服务器故障会导致系统瘫痪完全对等网络系统模型简单系统性能较低层次对等网络性能要比完全对等网络好没有彻底解决完全对等网络的低性能问题结构化对等网络通过分布式哈希表提升资源定位能力哈希丢失了部分信息四种对等网络构架的出现基本上符合技术发展的先后顺序，每次技术的变革都解决或部分解决了老技术的问题，同时又带来了新的问题。表2-1简单列出了各个构架的优劣。在资源定位的性能上，结构化对等网络的性能最好，这是由于它采用的哈希算法带来的好处；但是哈希也损失了一部分信息，把原先相似的资源打散分布到整个网络各处，这使得模糊查找无法进行。2.2对等网络的统计特性分析2.2.1对等网络中统计特性分析的起源和分类随着Peer-to-Peer(P2P，对等网)技术的不断发展，越来越多的用户被吸引到花样繁多的P2P应用系统中，同时也使得各类P2P网络的规模越来越大。对于文件共享的P2P网络，同时在线的用户数通常可以达到数百万，而即时消息类的P2P网络则拥有更多的并发用户数。很多P2P系统在设计之初往往没有考虑到网络会有今天的规模，而且P2P系统中没有中央管理(协调)机制的特点使得一些关于整个网络的重要统计数据很难获得，由于以上这些原因，人们目前对大规模P2P网络发展的情况和特点并不十分了解。从2001年开始，陆续的有一些研究人员开始着手于P2P网络的统计特性分析工作，从早期的文件共享类P2P系统如Napster、Gnutella(0.4)等到今天广泛使用的即时消息类P2P系统如Skype等，目前这方面的工作已经积累了一些宝贵的统计数据和模型，其中的一些被其他研究人员广泛的使用在了P2P环境模拟和系统设计上。在本文中，我们将按照收集统计数据的技术来给这些工作分类。按照这种划分，现有13第二章 相关领域研究现状的统计特性分析工作一般为两种，一种是基于P2P爬虫技术的统计特性分析；另一种是基于Netflow信息的统计特性分析。其中前者为现有工作中较为主流的方法。2.2.2基于P2P爬虫技术的统计特性分析Sariou等人分析了Napster和Gnutella(0.4版协议)两个系统38。他们发现在2001年5月6日到9日四天期间，在546,401个IP上发现了509,538个Napster节点，在1,180,205个不同的IP上发现了1,239,487个Gnutella节点。在节点的带宽方面，在当时的Napster系统中，大约有25%的用户使用窄带连接（小于64kbps），50%的用户使用宽带连接(Cable、DSL、T1/T3)，其余用户具有大于3MBps的连接；在Gnutella系统中，约有8%的用户使用窄带连接，60%的用户使用宽带连接，其余用户具有大于3MBps的连接。他们还统计了Free Rider39的比例。在Gnutella中约有25%的节点不共享任何文件，有7%左右的节点共享超过1,000个文件。在Napster中和Gnutella有类似的情况，但是Free Rider的比例稍微低一些。他们还绘制出了2001年2月17日Gnutella网络中的1171个节点拓扑结构图，见图2-10。Evangelos P. Markatos 23通过在各大洲采集数据发现了类似的结果。AlexanderKlemm等人在Gnutella 0.6版本协议上也分析出相似的数据40。Eytan Adar41侧重于FreeRider的分布分析了Gnutella网络中节点共享文件的情况，认为Free Rider是对P2P系统的威胁甚至大过版权法规的约束。Sai Ho Kwok和Christopher C. Yang42对Gnutella网络的分析则是侧重于用户查询的分布，根据他们的结论，大多数Gnutella的查询都是重复的，并且查询内容的平均长度高于WWW搜索引擎中查询的平均长度。值的注意的是，上述研究工作绝大多数是在Gnutella 0.4上进行的，而目前Gnutella已经升级到了Gnutella 0.6，新版本的协议从网络结构到查询转发都有了巨大的变化。2.2.3基于Netflow信息的统计特性分析除了P2P爬虫技术外，还有一类技术是分析大范围网络中的Netflow数据来实现统计数据收集的。这方面的代表工作是Subhabrata Sen和Jia Wang43在2004对几种流行的P2P系统所作的数据收集和分析。他们通过在ISP的路由器上收集Netflow数据，获得了大范围网络中几个P2P系统中IP层的流量信息。由于这些数据覆盖了这些系统中很大一部分P2P的节点，并且还记录了很多P2P爬虫难以获取的底层网络流量，相对过去的工作来说，他们的分析为人们提供了一个更大范围内P2P网络的一个全景图。不过也正因为由于这些IP层Netflow信息是被动监听获得的，所以很多涉及节点属性和行为的信息都缺失了。2.2.4小结综上所述，虽然过去已经有一些研究工作者通过P2P网络爬虫或ISP级别的网络探针来不共享文件、只下载文件的节点称为Free Rider。Internet Service Provider，Internet服务提供商一种最早由CISCO公司提出的流量描述格式14第二章 相关领域研究现状(a)(b)(c)图图图 2-102001年2月17日Gnutella网络中的1171个节点拓扑结构，(a)拓扑结构；(b)(a)图中随机去掉30%节点后的拓扑结构；(c)(a)图中去掉4%最高度数节点后的拓扑结构Fig. 2-10Topology of the Gnutella network as of February 16, 2001 (1771 peers). (a)Original Topology.(b)Topology of the Gnutella network after a random 30% of the nodes are removed. (c)Topology of the Gnutellanetwork after the highest-degree 4% of the nodes are removed.收集P2P网络的一些统计数据，并且在此基础上从各个侧面对P2P网络的特性和问题作了分析，但是可以看到，随着P2P系统用户的不断膨胀以及P2P系统平台的更新，这些结论中的很多部分可能已经不再精确；其次，过去的分析工作往往忽略了用户行为以及时间序列方面的分析，而这些方面的特征则更多的决定了P2P网络中负载的分布情况。因此，在该领域内，还有很多值的去做的工作，如何设计和实现高性能的P2P爬虫系统；如何在新的协议中(Gnutella 0.6)取各项统计数据(共享文件分布、用户查询分布、网络结构以及节点行为等)；如何从这些数据中挖掘出新的现象和问题，并提出新的模型；以及如何从时间序列的角度来分析用户的查询并加以应用都具有重要的研究意义。15第三章统计数据获取3.1Gnutella平台3.1.1简介Gnutella是一个当前非常流行的P2P共享文件系统，其并发用户数达到了100万左右，并且由于Gnutella无中心的特点，它躲过了被关闭的命运，成为当前流行的无结构P2P文件共享系统的代表之一。Gnutella平台发展至今曾有过两套协议，即Gnutella 0.4和Gnutella 0.6。较早出现的Gnutella 0.4是一个纯粹的P2P协议，系统中所有节点都享有同等的地位。消息传送和文件传输都在节点之间进行。然而，由于Gnutella 0.4采用洪泛技术(Flooding)来实现查询，随着用户数的不断增多，Gnutella也因为其产生的大量的消息流量而受到批评。随后，Gnutella的开发者们又提出了Gnutella 0.6以解决Gnutella 0.4难以扩展的问题，目前，多数Gnutella系统已由0.4版本全面升级为0.6版本了。Gnutella 0.6版本在0.4版本的基础上加上了超节点(UltraPeer)，超节点的加入使得Gnutella网络变得有层次，系统更加高效。Gnutella将是我们要研究的P2P文件共享系统。由于Gnutella是当前最流行的P2P文件共享系统之一，对于它的研究将能获得很多重要的数据为以后进一步的研究做准备。3.1.2架构概述Gnutella是当前比较流行的一个P2P文件共享系统。据统计，Gnutella的同时在线用户数达到100多万，是一个有着众多用户的系统，它的节点的统计信息相比于OpenNap可能有着更高的统计意义。虽然Gnutella和Napster都属于第一代的Unstructured的P2P结构，但是它们的网络拓扑结构完全不同。Napster是一种混合型的P2P系统，而Gnutella则是一个纯粹的P2P系统。虽然在Gnutella 0.6协议中引入了UltraPeer（一种超节点）的概念，使得网络节点功能有了分化，但是Gnutella中任何满足条件的节点都能成为UltraPeer，而网络中并不存在专门的中心服务器。这是和Napster的本质区别。由于Gnutella中没有中心服务器，Gnutella中的节点通过和一组邻接节点保持点对点的连接来构成整个网络。为了找到一个指定的文件，节点通过泛洪的方式向所有的邻接节点发送查询消息。当一个节点收到一个查询请求时，它首先检查自己共享的文件中是否有满足查询条件的文件。如果有，则沿原路返回一个查询应答消息。不管是否找到满足条件的文件，此Gnutella 0.6出现后有一部分技术人员在Gnutella 0.6基础上提出了Gnutella2，由于其用户数有限，故不作讨论。这里的可扩展性是指系统的性能不受用户数目变化的影响。16第三章 统计数据获取节点都会将次查询消息向其邻接节点广播。当一个节点接到一个查询应答消息时，它首先检查是否是自己发送的查询的应答。如果不是，它将检查此应答所对应的消息的来源，并将其按原路返回。为了控制消息的传播的范围，每条消息都有一个TTL域。每传播一次，TTL减一，而当TTL为0时，消息不再传播。图3-1显示了Gnutella中文件定位的方式。图图图 3-1Gnutella的文件查询过程Fig. 3-1The Search Process in Gnutella由于Gnutella没有专门的中心服务器，另外一个迫切需要解决的问题就是一个节点怎样发现并连接到其它节点上。Gnutella采用了以下解决方法：首先节点可以通过GWebCache来找到一些在线节点。GWebCache实时更新着一些在线UltraPeer的信息。如果一个节点没有任何在线UltraPeer的信息，那么它就要通过GWebCache来确保得到在线节点的信息以连入Gnutella网络。尤其对于初次安装的节点来说，它没有任何关于Gnutella中节点的信息。这样，为了连入Gnutella网络它就必须要通过GWebCache来获取在线UltraPeer的信息。节点在本地保存一个UltraPeer的列表。当节点下次连接到网络时，它首先通过尝试连接到这些UltraPeer上以接入Gnutella网络。那些被保存在本地文件中的UltraPeer都是经过挑选的，具有较长的在线时间。这样就增加了节点连接成功的可能性，节点连入Gnutella网络的速度加快了。同时，这样节点每次上线时就不一定都要从GWebCache上获取在线UltraPeer信息了，减轻了GWebCache的负担。一个节点尝试连接的UltraPeer有可能会因为连接的节点数到达了其连接的上限而拒绝新的连接。此时，可以通过和UltraPeer握手时读取X-Try和X-Try-Ultrapeers来得到其它在线UltraPeer的IP信息。Gnutella同时还提供了专门的节点机制。通过Ping/Pong消息来询问网络中在线节点的情况。在Gnutella0.6协议中，节点的类型分为UltraPeer和LeafPeer。UltraPeer是一种超节点，它们承担了更多的职责。因此我们认为Gnutella的网络可以看成双层结构，如图3-2。17第三章 统计数据获取UltraPeerLeafPeerUltraPeer ConnectionLeafPeer Connection图图图 3-2Gnutella 0.6网络结构Fig. 3-2The Overlay Structure of Gnutella 0.63.1.3协议分析Gnutella协议主要有0.4和0.6版本。当前Gnutella网络中主要使用的是0.6版本的协议。0.6版本和0.4版本的最主要的区别在于0.6版本中将节点的角色分为UltraPeer和LeafPeer两类。在对节点的功能进行分类后，提高了整个系统整体的性能。我们所关注的Gnutella是当前被广泛使用的0.6版本，因此，如不特别说明，下文中的Gnutella协议所指的均是Gnutella 0.6。Gnutella协议主要涉及了系统的启动，节点连接时的握手协议，消息传递机制，以及系统优化部分。另外Gnutella为了方便系统统计信息的收集专门提供了相应的机制。Gnutella的系统启动部分已经在前面作了详细讨论，在此不再详述。我们将重点讨论一下节点的握手协议和消息机制等节点间相互交互的规范。在分析Gnutella的节点交互规范之间，有必要首先了解其最具特色UltraPeer和LeafPeer模型。在Gnutella0.4版本中，所有的节点都随机的和其他节点建立连接。这种方式对于高带宽的节点效果相对来说比较好，而对于那些使用modem等低带宽的节点来说就不太理想了。目前网络中仍然存在着大量的低带宽用户，因此需要一种新的架构来解决这个问题。一种解决方案就是通过一种更加结构化的模式来组织网络。采用UltraPeer模型的系统就能够达成这个目的。它通过将节点划分为LeafPeer和UltraPeer来使得Gnutella网络形成层次结构。一个LeafPeer只保持与UltraPeer的少量连接，而和其它LeafPeer没有连接。而UltraPeer则作为LeafPeer连接到Gnutella网络的代理。每个UltraPeer随机和一定数量的UltraPeer连接，同时允许一定数量的LeafPeer连接到其上。这样，绝大多数的消息的路由和处理都是由UltraPeer来完成，从而减少了网络开销使得网络的伸缩性更好。握手协议在Gnutella中起着非常重要的作用。节点之间通过握手来确立连接，交换信息。只有UltraPeer接受连接，LeafPeer则不接受连接。当一个LeafPeer想要连接18第三章 统计数据获取到UltraPeer时，UltraPeer首先判断其上连接的LeafPeer是否已经到达其连接数的上限，如果没有到达上限则接受连接。而当UltraPeer A想要连接到UltraPeer B时，如果B已经连接的UltraPeer的数量达到其连接数的上限，则B询问A是否愿意作为LeafPeer连接。如果A没有LeafPeer连接其上，则A作为LeafPeer接入B，否则断开与B的连接。而如果B连接的UltraPeer数没有达到上限，它就正常地接受A做为UltraPeer接入。在握手过程中，被连接的节点将通过X-Try和X-Try-Ultrapeers告知连接节点其它在线的节点（UltraPeer）的IP和端口。通过握手协议，节点之间建立连接，从而建立起整个Gnutella网络。Gnutella协议只有Ping, Pong, Query, Query Hit, Bye和Push六类消息。消息的格式如下：Message ID/GUIDPayload TypeTTLHopsPayload LengthPayload其中，GUID是一个16字节的全局消息ID。为了避免同一条消息被一个节点反复转发，需要一个GUID来标示每一条消息。而如果不同的消息的GUID相同，那么有可能会被误认为同一条消息而被扔掉。所以GUID采用16字节的随机数来表示，这样GUID冲突的概率将非常小。Payload Type标示了消息的类型，占一个字节。分别为：0x00 = Ping，0x01= Pong，0x02 = Bye，0x40 = Push，0x80 = Query，0x81 = Query Hit。TTL是消息从网络中被移除前可以存在的时间。节点在传递消息之前将TTL减一。当一个节点收到的消息TTL为0，则节点将不再传递此消息。Hops是消息已经被传递的时间。消息每传递一次，Hops加一。Payload Length占3个字节，指明了消息体的长度。Ping和Pong消息是用来发现网络中在线的节点的。节点通过向其连接的节点发送Ping消息来查找网络中其它的节点。收到Ping消息的节点首先将自己的一些信息组成一个Pong消息返回，然后将其保存在Pong cache中的Pong消息同时返回给Ping消息的发出者。在原来的0.4协议中节点收到Ping消息会将此Ping消息转发给其他的节点，这样就会无谓地耗费很多的网络带宽。而采用Pong cache机制后，通过定期更新保存在cache中的Pong消息，既达到了Ping/Pong的功能又节省了网络带宽。Query是用于查询文件的，Query Hit是对于查询的应答。当LeafPeer查询文件时，它向其连接的UltraPeer发送Query。UltraPeer接到Query先和自己共享的文件进行比较，如果有匹配的文件，它就形成Query Hit消息沿原路返回。同时，UltraPeer将Query转发给其它跟它连接的UltraPeer。另外由于LeafPeer一般性能较差，如果UltraPeer将Query全部转发给LeafPeer将极大地增加LeafPeer的负担。为此Gnutella引入了Query Routing Table。每个LeafPeer都要发给连接着的UltraPeer一个Query Routing Table，这个QueryRoutingTable是将其共享的文件分解成单个单词后得到的。UltraPeer接到Query时通过比较查询关键字和LeafPeer的Query Routing Table来决定是否向其转发Query。这样做将大大地减轻LeafPeer负担。同时，Gnutella通过保存Query，Query Hit等方法来避免反复转发同一个Query。19第三章 统计数据获取需要指出的是，Gnutella还提供了所谓的Browse机制。当一个节点发送一个4个空格的关键字时，接收到的节点将返回自己共享的所有的文件。节点共享的文件类型的分布也是我们关心的一个统计数据，通过Browse，节点共享文件的详细信息将很容易获得。Push只有在一些特殊情况下才会用到。当上传节点在防火墙后面时，下载节点无法直接和上传节点建立连接。这是下载节点向上传节点发送Push消息，上传节点然后和下载节点建立连接，向其传送文件。Gnutella还另外提供了一些专门机制供网络爬虫收集其统计信息。其一是CrawlerPing。当一个Ping的TTL=2,Hops=0时，即被称为Crawler Ping。当节点接收到一个CrawlerPing时，此节点将与之相邻节点的信息组成Pong返回给查询节点。这对于了解Gnutella的网络结构很有意义。除此之外，不同的Gnutella软件也提供了它们自己的网络爬虫机制。比如比较流行的LimeWire就在握手协议中为网络爬虫提供了专门的机制。当一个标识为“Crawler”的节点A与另外的一个节点B握手时，节点B将其连接的UltraPeer和LeafPeer返回给节点A，同时结束与A的连接。这样，对于爬虫来说，其收集网络中在线节点的过程将变得很容易，只需要通过不断地握手过程就行了。Gnutella协议对于消息的扩展提出了相应的规范，在此就不一一指出了。在Gnutella统计信息收集的过程中，我们主要涉及了Gnutella协议的上述部分。3.1.4LimeWire实现分析LimeWire44是当前最为流行的Gnutella软件，据LimeWire的供应商统计，Gnutella大概有100多万的同时在线用户，而其中绝大部分都是LimeWire的用户。而且LimeWire的核心源代码是开源的。我们对于LimeWire源代码的分析有助于我们更好的了解Gnutella的运行机制。同时还能利用LimeWire提供的一些自身的机制来帮助我们进行统计。我们对于LimeWire的分析主要集中在消息与连接功能模块，以及节点搜索与消息路由功能模块。1.消息及连接模块Message类是一个抽象类，它是所有类型的Gnutella消息的父类。在前一节中，我们分析了消息的格式，其中消息头的各类数据都保存在Message中，包括GUID, Payload Type,TTL等。这些都是所有消息的共同部分。Message的各种子类代表了各类Gnutella消息，包括：QueryRequest (Query)，QueryReply (Query Hit)，PingRequest (Ping)，PingReply(Pong)，PushRequest (Push)，如图3-3所示。这些类每个都有两个构造函数，分别对应于接受到的消息和发送出去的消息。例如，当用发送一个查询请求时，QueryRequest的第一个构造函数被调用，它的参数是查询关键字和最小速度。第二个构造函数则是从网络上读取一条查询请求时被调用，它的参数是消息的内容。Connection类实现了简单的消息连接。它也有两个构造函数，分别对应于连入和连出。Connection类提供了方法来读写消息，它们是通过分别代理给Message.read和Message.-write来实现的。20第三章 统计数据获取图图图 3-3LimeWire的消息实现Fig. 3-3The Implementation of LimeWire Message2.节点连接及消息路由模块ManagedConnection是Connection的子类，相比于Connection它主要增加了一下3个功能。(1)自动存储和刷新发出的消息。这样就不用在调用send(message)后调用flush()了。它还专门实现了一个写线程和一个简单的流量控制。如果连接的节点不能及时反应，它将按照以下顺序丢弃消息：PingRequest，PingReply，QueryRequest，QueryReply，Push-Request。(2)实现了一个loopForMessage的方法来自动读取消息。(3)提供了一些数据的统计。ConnectionManager类保存了所有ManagedConnection类的实例。当需要时，Connection-Manager负责连接其他节点。它从HostCacher中得到存储着的节点地址。Connection-Watchdog负责监控那些一段时间内没有发送或接受任何数据的节点。如果这些节点对于TTL=1的Ping消息没有任何反应，它将断开与这些节点的连接。MessageRouter负责处理消息。每一条由loopForMessage读取得消息都交由它来处理。MessageRouter将Query和Ping广播给ConnectionManager保存的所有Connection，并设置应答路由表。通过这些路由表，查询应答将路由给相应的连接。MessageRouter只是实现了消息的路由等功能，而对于不同消息的处理则是由其子类StandardMessageRouter来完成的。图3-4详细描述了这一模块的实现。21第三章 统计数据获取图图图 3-4LimeWire的节点连接和消息路由实现Fig. 3-4The Implementation of LimeWire Connection and Message Routing3.2Gnutella 0.6爬虫3.2.1总体设计Gnutella爬虫的目标：发现尽可能多的Gnutella网络的在线节点，收集这些节点的相关信息。当前在众多实现了Gnutella协议的软件中LimeWire是最为流行的，并且它提供了开源代码。我们将使用LimeWire4.8的内核来实现Gnutella爬虫与Gnutella网络通讯的基本功能。在以前的研究中38由于Gnutella的网络的规模不是很大，Gnutella网络爬虫可以直接收集所有发现的节点的相关数据。然而当前Gnutella网络中的同时在线节点数超过1,000,000个，其数量非常大。同时，由于Gnutella的高度动态性，每个时间段内都有大量的节点上下线。这就使得采用传统的方法收集节点的数据几乎不可能。为了能够尽可能多得收集Gnutella节点的信息，并保证收集的Gnutella节点的信息尽可能全面，我们将统计数据获取的主要任务分为三类，对于每一类任务，我们都专门设计了相应的爬虫。对于Gnutella爬虫角色的分工所带来的最大好处就是能够收集更多Gnutella中节点的信息。通过不同角色的Gnutella爬虫间的合作来完成对于Gnutella网络中节点的各类信息的收集工作。通过角色的分工，每一类爬虫的功能更有针对性，从而提高其效率来最大限度地收集数据。首先，负责节点发现的爬虫尽可能多去发现Gnutella网络中在线的节点，并将它们的IP地址和端口记录下来。而负责收集节点元数据和负责收集查询消息的爬虫分别通过收集到的节点地址信息来进一步收集其它的信息。22第三章 统计数据获取GnutellaNetworkPeer Address SetGWebCacheHandshakingDiscovery CrawlersProbing CrawlersQuery Logging CrawlersPeer Filter(Discovered?)SeedSelectorQuery SetStatus SetGnutella Overlay ProbingTCP/IP Layer ProbingSending Fake QRT (Query Routing Table)Receiving QueriesCrawler Ping图图图 3-5Gnutella爬虫的结构Fig. 3-5The Topology of Gnutella Crawler3.2.2节点发现由于Gnutella网络巨大规模及其高度动态性，我们不可能发现并收集所有在线节点的信息。因此，对于节点的选择有两种策略。1）节点分布于整个Gnutella网络中。在此策略下，收集到的节点具有统计意义。2）节点集中于Gnutella网络中的一部分，即随机选取Gnutella网络的一个子网络，并收集这个子网络中节点的全部信息。在此策略下，我们能够获取节点间协作的信息，这是策略1所不能完整获得的。然而策略2最大的问题是局部信息不一定有统计意义；另外由于Gnutella网络的高度动态性，选取的子网络一直处在变化之中，在不同时刻我们所监测的子网络很可能是两个完全不同的实体。基于上述考虑，我们主要采用策略1来发现节点。我们通过Gnutella协议提供的各种节点发现机制来尽可能多地发现节点。1）通过GWebCache发现在线节点。这种方法发现的都是UltraPeer。虽然数量不多，但是在绝大多数情况下这些节点都是有着较长在线时间的节点。2）通过Gnutella握手协议中交换的节点地址信息来发现在线节点。3）Gnutella的Ping/Pong机制能用于发现在线节点。4）Gnutella协议的扩展机制也可以用来发现节点。例如，在LimeWire中使用”Crawler”的角色来和其他节点握手，其它节点会返回和它相连的所有的节点的信息，包括UltraPeer和LeafPeer。由于通过这种方式不用和节点建立连接，其速度是几种方式中最快的一种。由于获得了节点间的连接情况，通过这种方法我们还能够得到Gnutella网络的拓扑结构。通过上述方法，我们总共累计发现了3,595,203个节点，其中683,334个节点为UltraPeer，即UltraPeer数量占所有节点数的19%左右。23第三章 统计数据获取3.2.3节点元数据获取在Gnutella中有两类节点：UltraPeer和LeafPeer。对于UltraPeer信息的收集相对来说比较简单。我们可以通过主动连接这些节点然后收集这些节点的信息。然而由于LeafPeer不接受任何连接他们的尝试，主动地去获取这些LeafPeer的信息就不可能了。为了获取LeafPeer的统计信息，我们用一些角色为UltraPeer的爬虫专门等待LeafPeer来连接。为了使得尽量多的LeafPeer发现并连接它们，这些爬虫大量连接网络中其它的UltraPeer以达到大范围广播其地址信息来提高其被LeafPeer连接的概率。通过此方法获得的LeafPeer相比于全部的LeafPeer只是一小部分，但是由于未对LeafPeer做任何选取，从统计学的角度来讲，实验获得的数据不存在偏差。我们所关注的节点的元数据主要包括：网络延时，带宽，共享文件数量，所有的共享文件名和文件大小，节点的连接度等信息。Gnutella中节点在Pong消息中报告它共享文件数量和数据量。而共享文件的详细信息则是通过向节点发送浏览请求来获得，即发送内容为4个空格的文件查询消息。通过Crawler的握手协议可以得到节点的连接度和网络拓扑结构。另外，通过使用已有的测量工具SProbe45来测量节点的网络延时和带宽。1.延时的测量网络延时是一个非常重要的特性。一般来说，在P2P系统中交换最多的是MP3，大概4M左右。这样在选择下载节点时，节点间的网络延时是一个非常重要的考量。虽然对于特定的节点，网络延时和测量者的位置有关系。但是我们认为从不同的测量点获得的网络延时的分布存在着某种简单的转化关系。这样，我们测量到的数据仍然有其意义。我们通过爬虫获取节点的IP地址和端口。然后通过计算与之建立TCP连接所需要的时间，就是我们所想要得到的网络的延时。2.生命周期的测量节点在线的时间是一个非常重要的特性。它可能和节点对于P2P网络的贡献（共享文件数），节点发送的查询消息数量，节点网络特性等其他特性有某种内在的联系。我们对于节点生命周期的关注，主要就是为了挖掘这些特性之间的内在联系。在Gnutella中，我们需要通过不断的监控节点才能获得其在线情况。我们主要对Gnutella中节点在线时间和节点在这个过程中发送的查询请求之间的关系感兴趣。也就是说我们所感兴趣的是节点和我们的爬虫连接的时间，不管是UltraPeer还是LeafPeer。而且一般来说，节点间建立的连接会直到一个节点离开网络时才回断开。我们通过记录连接时间来得到其生命周期。当然，由于在发现节点前节点在线情况无法获得，称其为生命周期并不确切，但是对于数据统计没有影响。24第三章 统计数据获取3.网络带宽的测量节点的网络带宽是其另外一个重要的特性。在文件下载时，高带宽的节点相对来说是更好的选择。如果系统中高带宽的节点数量比较多，那么系统的性能也就会比较好了。在Gnutella中查询应答消息中带有系统自己测到的节点带宽，因此不存在欺骗的情况。节点的可提供带宽是实时改变的，因为个人计算机用户可能有多个并发的需要利用本地Internet带宽的应用。因此一次测量到的数据可能不太精确。我们将通过多次测量求其平均值来确定其网络带宽。这么做有其局限性，但是没有其他更好的方法来解决这个问题。我们使用了一个专门的带宽测量工具来测量爬虫获取的节点的网络带宽。其原理是：通过向节点发送不同大小的TCP包，然后根据接收到的应答间的时间差来计算出节点的网络带宽。这种方法不是很精确，但是相比于节点可供网络带宽本身的动态性来说可以忽略的。3.2.4查询消息获取在Gnutella0.6协议中，查询消息都交由UltraPeer来处理。只有当UltraPeer认为一个Leaf-Peer有可能回答某个查询时，他才会将查询消息转发给它。每个LeafPeer都会将其共享的文件组成一个查询路由表传给和它相连的UltraPeer。当UltraPeer收到查询消息时，它首先比较查询消息和LeafPeer的查询路由表。如果发现匹配，则将消息转发给相应的LeafPeer。为了获取UltraPeer收到的所有的查询消息，爬虫需要建立一张伪造的查询路由表，使得每次匹配都能成功。查询消息和查询路由表的匹配比较简单，只是简单地比较查询路由表中是否有表项和查询消息关键字的部分内容匹配。我们使用26个字母加上10个数字全排列，形成46656（36*36*36）个3字符的项（查询关键字要求至少为3个字符）。这些项包括了所有可能出现的正常的查询关键字，由此爬虫能够获得其连接着的UltraPeer收到的所有的查询消息。3.3爬虫实现和实际数据获取情况在LimeWire原有开源内核的基础上，我们用Java实现了上面论述的Gnutella爬虫系统，并一共在8台IBM PC工作站上部署了爬虫系统，每台工作站配备了一颗Intel Pentium IV2.4GHz的处理器，1GB的内存和40GB的硬盘。此外，我们还使用了两台安装了SQL Server2000的服务器来收集采集到的数据，每台服务器配备了四颗Intel Xeon MP 2.0GHz的处理器，4GB内存以及1TB的SCSI硬盘。我们的爬虫系统在三个不同的时间段一共记录了Gnutella系统9天的节点活动数据。在实验中，我们一共发现了3,595,203个不同的Gnutella节点，其中大约19%的节点(683,334)在超级节点模式下运行。部分功能如测量节点延迟和带宽在Linux上由脚本实现。这三个阶段即2005年4月的前三周，每周记录从周二开始到周三的所有节点活动25第四章统计数据分析和统计特征刻画4.1节点在线时间我们首先分析Gnutella的节点在线时间。处于比较的目的，我们还引入了OpenNap，Napster的继承者，的在线时间。图4-1显示了Gnutella和OpenNap节点的在线时间的CDF图。从图4-1中，我们发现Gnutella和OpenNap节点的在线时间分布有明显的不同，即Gnutella节点的在线时间普遍比OpenNap节点的在线时间要短。对于这种现象的解释可能有以下几种。首先，OpenNap节点的在线时间是由服务器报告的，那么这些数据将会相当精确；而Gnutella节点的在线时间我们是通过爬虫来测量得到的，这些节点在被发现以前的在线时间就无从获得了，从而造成了测量的误差。其次，Gnutella和OpenNap的用户群不同。OpenNap的用户相对来说比较少，那些用户很可能是忠实的Napster支持者，这些人趋向于花更多的时间上网。还有一种可能就是由于OpenNap的节点比较少，单个节点要花更多的时间来搜索和下载文件，直接导致了节点在线时间的增加。同时，相比于以前的数据38，我们发现Gnutella的节点在线时间明显增长了。一方面，用户的计算机设备及网络环境的改善可能会使得用户不必过多地考虑长时间上网所带来的影响，因此他们可能更倾向于长时间在线。另一方面，Gnutella的同时在线节点数从30,000个左右增加到了1,000,000多个，Gnutella网络中共享的资源也随之大幅度增加。Gnutella节点能更多得下载文件，使得他们的在线时间普遍提高。节点在线时间的提高有利于P2P网络提供更好的服务。就此而言，Gnutella在向有利于其自身的方向发展。4.2节点角色选择Gnutella 0.4和Gnutell 0.6的一个显著区别就是Gnutella 0.6定义了两种不同的节点角色，即超节点和叶节点。在Gnuella 0.6设计者最初的构想中，具有较好Internet连接速度的节点应作为超节点为整个网络提供消息路由服务，其他节点则作为叶节点。由于超节点的质量好坏很大程度上决定了整个网络的稳定性和性能，超节点的选择就显得尤为重要。虽然一个优秀的节点角色选择算法至少应该基于节点的带宽和延迟，我们却发现基于这两个参数的节点角色聚类结果和实际的节点角色分布有很大的差异。为了避免过多的节点影响聚类结果的可读性，我们首先从节点库中随机选择了1,000个节点，包括176个超节点和824个叶节点。值得注意的是，随机的节点选取不一定能保证超节点和叶节点数目1:4的关系，因此，我们将这个关系作为选择结果是否可接受的判断依据之一，从而保证了上述比例。如图4.2(a)所示，我们使用K-Means算法根据节点的传输延迟和带宽将节点聚为两类。圆圈所代表的是有较高传输带宽和较低传输延迟的节点，即具有较好Internet连接的、适26第四章 统计数据分析和统计特征刻画1011001011021031041050102030405060708090100Cumulative Online Time(Minute)Percentage(%)GnutellaopenNap图图图 4-1Gnutella和OpenNap的节点在线时间分布比较Fig. 4-1Comparison of Peer Online Time between Gnutella and OpenNap合作为超节点的节点。圆点所代表的是有较低传输带宽和较高传输延迟的节点，即具有较差Internet连接的、适合作为叶节点的节点。图4.2(b)则向我们展示了节点的实际角色选择情况，其中圆圈代表超节点而圆点代表叶节点。通过于图4.2(a)比较，我们可以发现有相当一部分叶节点实际上只具有一般或较差的Internet连接，显然，这样的节点是不适宜做为超节点来为其他节点服务的。更精确的试验数据告诉我们，图4.2(b)中有20.45%的超节点在图4.2(a)中是由圆点表示的，这意味着这些节点没有选择正确的角色。此外，我们还发现只有55.7%的超节点的在线时间是超过平均水平的。Gnutella 0.6网络的性能很大程度上取决于其核心的性能，即由超节点组成的网络的性能，目前的节点选择算法显然影响了Gnutella网络的实际性能和稳定性。为了更加直观的了解不良的角色选择算法对系统性能的影响，我们接下来将比较理想的节点选择和现实的节点选择对整个Gnutella系统节点流量的影响。首先，我们根据聚类结果找出没有正确选择角色的节点，然后我们根据以下公式估计出理想情况下节点都被正确赋予角色时系统整体提高的流量，TrafficVolume =Xi(Bi DOTi)(4-1)其中节点i属于我们在上面提到的没有被正确赋予角色的节点集合，Bi和Di分别是节点i的带宽和平均在线时间。我们发现即使是对于在图4.2(b)中的31个赋予了错误角色的节点，如果给与正确的角色分配，其对系统整体吞吐量的提高也达到了3.23GB。值得注意的是，这个估计也只是一个保守的估计，事实上，高质量的超节点还能够接纳更多数量的叶节点，从而提高系统的整体性能。27第四章 统计数据分析和统计特征刻画101102103102103104105Bandwidth(Kbps)Latency(Milliseconds)Peers Should Be LeafpeerPeers Capable To Be Ultrapeer(a)101102103102103104105Bandwidth(Kbps)Latency(Milliseconds)LeafpeerUltrapeer(b)图图图 4-2节点角色选择，(a)根据带宽和延迟的聚类结果；(b)节点实际角色分布Fig. 4-2Peer Role Selection. (a)Peer Clustering By Latency and Bandwidth (log-log scale). (b)Peer Classi-fication By Real Role (log-log scale).对于目前Gnutella系统中不良的节点选择效果，有很多可能的原因。比如，用来作为判断依据的本地信息可能存在误导，目前的选择算法没有很好的被实现。事实上，我们发现很多流行的客户端都只实现了一个非常简单的超节点选择机制，如LimeWire就允许所有拥有公网IP的节点成为超节点。4.3节点连接情况节点的连接度是另外一个重要的特性。节点间相互连接情况直接影响到网络拓扑结构，以及此结构的网络中消息机制的效率。自有演化的P2P系统的网络拓扑结构展现出Power-law的特点。我们所关心的是：在当前Gnutella0.6协议下，节点的连接度是否仍然表现出Power-law的特点。我们从图2所展示的Gnutella网络拓扑结构可以看到，Gnutella网络中UltraPeer构成了网络的主体部分，UltraPeer的连接情况直接决定了Gnutella的拓扑结构。因此，我们将着重分析UltraPeer的连接度的分布情况。图4-3显示了Gnutella中UltraPeer的连接度的分布情况，我们发现，UltraPeer所连接的其它UltraPeer数量的分布存在一个明显的波峰。我们认为这种现象背后的原因和Gnutella0.6协议以及实现了Gnutella0.6协议的LimeWire的特点有关。根据44中的统计数据，在Gnutella网络中超过70%的用户都使用了LimeWire，因此其性质必然影响到整个Gnutella网络的特性。LimeWire4.8中规定，LeafPeer连接的UltraPeer数的上限为3，而UltraPeer连接的其它UltraPeer的数量的上限为32。节点会定期检查其连接的UltraPeer数以确保其连接了足够多的UltraPeer。当所连接的UltraPeer数小于其上限时，节点将试图连接新的UltraPeer。由于节点的动态性，不断有UltraPeer加入或离开Gnutella网络，这样就使得UltraPeer连接的其28第四章 统计数据分析和统计特征刻画它UltraPeer数在靠近32的区域内动态变化着。事实上通过对于UltraPeer的UltraPeer连接度的计算，我们的得到其平均值为23。01020304050607080100101102103104DegreeNumber of PeersThe Distribution of Peers Degree in GnutellaTotal DegreeLeaf DegreeUltra Degree图图图 4-3Gnutella中UltraPeer连接度的分布Fig. 4-3The Distribution of Ultrapeer Connection Degree in Gnutella另外，从图中很容易看出，绝大多数UltraPeer所连接的LeafPeer数在0到32之间分布比较均匀，并非一贯认为的power-law分布。我们认为产生这一现象的原因和Gnutella网络的双层结构有关。在UltraPeer层中，任何一个UltraPeer所连接的UltraPeer数都相近，因此它们地址被传播的范围大小相近。而LeafPeer所获得的关于UltraPeer的信息主要来源于UltraPeer层，因为LeafPeer和LeafPeer间不能建立连接而无法交换信息。那么LeafPeer选择UltraPeer连接时，所有UltraPeer被连接的可能性均相等。Gnutella协议规定：UltraPeer只能等待LeafPeer连接它，而不能主动连接LeafPeer；同时，LimeWire中UltraPeer所连接的LeafPeer数的上限为32个。因此UltraPeer上连接着的LeafPeer数在0-32之间较为均匀地分布。当然并非所有的节点都使用LimeWire连入Gnutella，我们注意到也有少数的UltraPeer拥有的LeafPeer连接数超过了32，这是因为这些节点没有使用LimeWire。我们还注意到UltraPeer的LeafPeer连接度和节点的总连接度的分布的形状相似。这一现象的主要原因是因为所有UltraPeer的UltraPeer连接度基本相同，使得UltraPeer的总连接度相当于其LeafPeer连接度向右平移。4.4共享文件P2P文件共享系统中节点共享的文件的特性也是我们所感兴趣的。P2P系统主要用于在节点之间共享资源，而在P2P文件共享系统中共享的资源就是文件。这些共享文件的大小、重复率以及分布情况等特性都将直接影响到文件的查询、下载等的效率，从而将直接影响到29第四章 统计数据分析和统计特征刻画系统的性能。在实验中，我们从Gnutella的340,673个节点上（大概是所有发现节点的10%）收集了30,044,693个文件的相关信息，包括文件名和文件大小。4.4.1共享文件的类型我们通过浏览节点共享文件的信息来获取节点共享文件的文件名和大小等详细信息。如图4-4所示，我们发现Gnutella节点共享的文件以音频文件为主，占79%。Jeffrey Miller46通过对查询消息的分析发现：在能辨别的44%的消息中，有21%的音频文件，20%的视频文件，图片文件为1%，程序和文档占2%。这与我们发现的节点共享文件类型的分布有很大的差异。查询中，视频文件占了很大一部分，几乎和音频文件一样多。而节点共享的文件中，音频文件占了绝大多数。造成这种情况的原因是因为视频文件相比于音频文件大很多，其占用的用户系统资源比较大。用户更倾向于共享相对较小的音频文件。Program6%Archive2%Picture4%Document4%Video5%Audio79%图图图 4-4Gnutella共享文件的类型Fig. 4-4The Distribution of Shared Files in Gnutella Regarding to Different Types4.4.2文件重复率在P2P文件共享系统中，文件的重复率对于系统的性能有很大的影响。如果一个文件在系统中只存在一个副本，那么当一个用户查询该文件时查询效率将非常低。同时一些P2P文件共享系统（包括Gnutella）支持多点下载。如果系统中存在多个文件副本，将提高文件下载的速度。我们分析了整个Gnutella系统中文件的重复情况，其结果如图4-5所示，其中图4.5(a)是其CDF图，而图4.5(b)是其分布图。我们所收集到的文件信息是其文件名和文件大小。对于那些文件名和文件大小相同的文件，我们简单地认为它们是同一个文件的副本。而同一个文件的两个副本完全有可能被赋予不同的文件名。我们所作的简化会造成结论和实际情况一定程度上的偏差，更精确的结论有待于我们以后进一步的研究。从图4.5(a)中可以看到，73.3%的文件只有一个副本，而96.2%文件的副本数不超过10个。只有极少数的文件有较高的副本率。在我们收集到的数据中，副本数最多的一30第四章 统计数据分析和统计特征刻画1001011021031041050102030405060708090100Number of Files CopiesPercentage(%)The Repetition of Shared Files(a)101100101102103104105100101102103104105106107Repetition of Shared Files in GnutellaNumber of Files CopiesNumber of Filesk = 2.05 (b)图图图 4-5Gnutella共享文件的重复率，(a)Gnutella中共享文件重复率的CDF图；(b)Gnutella中共享文件的Power-law分布Fig. 4-5The Duplication of Shared Files in Gnutella. (a)CDF of The Duplication Rate of Shared Files inGnutella. (b)The Power-law Distribution of Duplicated Shared Files in Gnutella.个文件的副本数为393237。可见，在Gnutella中绝大多数的文件的重复率很低，只有极少数的文件有较高的重复率。当然那些只有一个副本的文件有可能是一些垃圾文件或者是一些极为冷僻的文件。然而在对文件类型为mp3的文件的分析中我们发现其结果与上述结果类似。大概有68.2%的文件只有一个副本，而95.0%的文件的副本数不超过10个。考虑到Gnutella系统中主要共享的文件是以mp3文件为主的音频文件，我们有理由相信Gnutella系统中共享文件的重复率非常低。图4.5(b)中的X轴是一个文件的在Gnutella中的副本数，Y轴是Gnutella中具有相同副本数的文件的数量。从图中我们可以得到：Gnutella中的共享文件的重复率满足power-law47的分布。在Gnutella文件共享系统中，节点共享的文件是其最重要的资源。而文件副本率的大小将极大地影响系统所提供的服务。从我们的分析来看，共享文件的重复率过低。由于绝大多数的共享文件只有一个副本，一旦唯一的副本被删除，Gnutella系统中将再也找不到这个文件。这是一个非常严重的现象，会直接影响到Gnutella作为文件共享系统的作用。为了克服这一弊端需要在Gnutella引入相应的机制来提高文件的重复率。例如可以在每个节点上建立一个副本区，副本区主要由Gnutella系统管理。系统按照一定的策略在副本区保存一些其它节点的共享文件的副本用来提高整个系统的文件副本率。31第四章 统计数据分析和统计特征刻画4.4.3单个节点的共享文件类型分布一般而言，节点共享的文件反映了该节点的兴趣。如果能够使具有相同兴趣的节点组成一个社区48，那么将有利于提高文件查询的效率，因为具有相同兴趣的节点更有可能满足其查询请求。我们希望通过分析节点共享的文件能够初步验证节点的兴趣相对集中。我们认为节点共享文件的类型和节点的兴趣存在相关性。例如，扩展名为CPP的文件对应于编程方面的兴趣，而扩展名为MP3的文件对应于音乐方面的兴趣。虽然CPP和JAVA对应于不同的编程语言，但它们同时也对应于编程这一较为通常的兴趣。由于建立并分析兴趣的层次较为复杂、同时也不在本文的讨论范围之内，我们只是简单地将不同类型的文件看作不同的兴趣来研究节点的兴趣。100101102100101102103104105106Number of Files TypeThe Distribution of Files Type in Peersk2 = 2.7 k1 = 0.55 (a)00.511.522.533.500.20.40.60.811.21.41.61.82x 105Entropy of Shared FilesEntropyNumber of Peers(b)图图图 4-6Gnutella中单个节点共享文件分布，(a)单个节点的文件类型分布；(b)节点共享文件的熵Fig. 4-6The Distribution of Shared Files on Single Peer. (a)The Distribution of Shared Files on Single Peerwith Regarding to File Types. (b)The Entropy of Shared Files on Single Peer.图4.6(a)显示了单个节点上共享文件类型种类的分布情况。其中X轴是单个节点上共享文件类型的数量，Y轴是节点的数量。从图中，我们可以看到文件类型的分布为分段power-law分布。两段power-law分布的指数分别为k1 = 1.56k2 = 7.69，其值相差较大。我们认为有两方面的原因使得节点共享的文件类型数量符合分段power-law分布。首先，不同兴趣所对应的文件类型的数量不同，很可能符合power-law的分布。例如，扩展名为C，CPP，JAVA，VB等很多文件类型都对应于编程这个兴趣；而音乐这个兴趣只有MP3等少数几个文件类型相对应。在两个都只有一个兴趣的节点中，对编程感兴趣的节点的共享文件的种类就要比对于音乐感兴趣的节点的共享文件的种类多。那么，当节点的兴趣较少时，各个不同兴趣所对应的文件类型数直接影响了节点的共享文件类型数。从图9中我们看到，在Gnutella网络中共享的文件绝大多数是音乐类文件，相应的共享音乐类文件的节点较多，但音乐所对应的文件类型较少；而文档类的共享文件数较少，相应的共享文档类文32第四章 统计数据分析和统计特征刻画件的节点较少，而文档对应的文件类型很多。因此对于那些兴趣较为单一的节点，兴趣的差异直接表现为较多的节点共享较少类型的文件，而较少的节点共享较多类型的文件，呈现为power-law的分布。同时，不同节点的兴趣的数量也很可能符合power-law分布。少数节点具有较多的兴趣，而多数节点的兴趣比较单一。尤其当节点的兴趣数量较多时，由兴趣差异造成的文件类型数量差异不再是影响节点共享文件类型数的主要因素了，此时节点的兴趣数将决定节点的共享文件类型数。图11中右半段的power-law分布就是节点兴趣数分布的具体表现。由于上述两个power-law分布的指数差异较为明显、同时其作用域也有差异，在两个因素的共同作用下，使得结果呈现为分段power-law分布。另外，我们通过计算节点共享文件的熵来进一步分析节点兴趣的集中情况。熵的计算公式如下：Entropy =NXi=1Pi log(Pi)其中，Pi是节点共享的某种文件的数量占此节点共享的所有文件的比重，N为节点共享文件的种类。结果如图4.6(b)所示，绝大多数节点的熵为0；熵越高，节点的数量越少。由于熵越低节点共享文件的类型越集中，从图中我们明显可以看出绝大多数节点的共享文件的类型都非常集中。社区是当前P2P研究领域的一个热点。社区将具有相同兴趣的节点聚集在一起来提高查询效率、降低网络开销。因此建立社区的关键在于节点兴趣的相对集中。如果每个节点的兴趣都很分散，那么建立社区就没有任何意义了。我们的分析证实了P2P文件共享系统中节点的兴趣较为集中，从而证实了建立社区的可行性。4.5查询消息分布我们的爬虫在40个小时左右的时间内从218,842个UltraPeer上收集了70,876,100条文件查询消息。我们的爬虫同时连接2000个左右的UltraPeer，并记录下这些UltraPeer转发给爬虫的所有的文件查询消息。4.5.1消息的TTL（time to live）的分布在Gnutella系统中，查询消息是通过泛洪机制在节点间传播的，其数量将呈指数级增长。为了控制消息的传播范围，每个消息都用一个Hop字段来记录消息传播的路径长度、TTL字段来记录消息还能传播的路径长度。当TTL为0时，消息不再传播。表1统计了各个不同Hop的消息的数量，通过拟合我们得到了消息数量的增长公式：y = 4411.3x(4-2)33第四章 统计数据分析和统计特征刻画表表表 4-1查询消息的Hop分布Tab. 4-1The Distribution of The Hop of QueriesHop(TTL)Number of Query4(0)67,091,2363(1)4,929,5832(2)142,7681(3)5,9700(4)394其中，x为查询消息的Hop值，y为查询消息的数量。由于查询消息一旦转发给LeafPeer，则LeafPeer不再转发此查询消息。而我们是从UltraPeer上收集消息的，因此我们所收集到的查询消息都只在UltraPeer间转发的，公式4-2中的x的底数应该对应于UltraPeer连接度的平均值。从4.3节中我们知道节点的平均UltraPeer连接度约为23，而101.3 20，两者较为接近。这一方面证实了4.3节中的结论，另一方面说明了我们所收集的查询消息的分布情况和整个系统中所有查询消息的分布情况基本相同。4.5.2查询关键字的重复率在Gnutella中，查询消息是通过泛洪方式在节点间进行转发的。而不同节点发送的查询消息的关键字重复率很高的话，将造成不必要的网络带宽的浪费。我们希望知道不同查询的关键字的重复情况。101100101102103104105100101102103104105106107Repetition of Queries(without spreading repetion)Number of Repeated QueriesNumber of Distinct Queriesk = 2.16 图图图 4-7查询关键字的重复率Fig. 4-7The Duplication Rate of Queries34第四章 统计数据分析和统计特征刻画在Gnutella中，转发的消息和被转发的消息具有相同的ID。通过消息的ID我们就能区分不同的查询了。图4-7展示了消除由转发产生的重复后查询关键字的重复率。其中X轴是同一个关键字所对应的查询消息的数量，即查询消息的重复数；Y轴是具有相同重复数的查询关键字的数量。从图中我们看到，查询关键字的重复率的分布很好地符合power-law分布。即绝大部分的关键字只有少量的重复或者没有重复，而少数关键字则又较高的重复。过去一些研究曾提出在Gnutella中引入对于查询结果的cache机制来提高查询的效率。就目前我们对于Gnutella现状的分析来看，在Gnutella中引入对于查询结果的cache机制只能在一定程度上降低查询对于网络造成的消耗。我们还注意到，整个Gnutella系统中共享文件的重复率也满足power-law分布，其指数k = 2.05。而查询关键字的重复率同样满足power-law分布，其指数k = 2.16。我们发现这两个power-law分布非常接近。在Gnutella中，节点通过查询来下载共享文件，而下载后的文件默认为共享文件。因此，查询的重复率和共享文件的重复率很可能存在内在的联系。而上述对相关数据的分析确认了这种联系。由于在不同时间段内节点所感兴趣的文件不同，查询消息的关键字的内容也会不同，而节点共享文件也会相应的发生变化。例如，一首流行的新歌刚发布，很多节点会去搜索、下载；一开始P2P系统中该文件的副本很少，而经过一段时间后该文件的副本将很多。对于查询关键字的重复率与文件的重复率之间的内在关系需要长时间、深入的数据收集与分析。我们将在后续工作中继续研究这一现象。35第五章时间序列分析5.1背景和目的在前面的讨论中，我们已经发现Gnutella系统中查询消息服从Power-law分布。然而，通过进一步的分析，我们还发现消息的重复的数量随着时间的变化也表现出很大的差异。在以后的讨论中，我们将更多的从时间序列的角度来考虑查询消息的统计特性。具体来说，我们将分别统计Gnutella系统中每个查询消息在一段固定时间内的数量，并且为每个查询消息构造这样一个在连续的多个时间段内其消息数量的一个序列，从而得到每个查询消息在数量上的时间序列。14:0016:3019:0021:300:002:305:00050001000015000Time(Sat Apr 16, 2005, CST)Number of Queries(a)12 3456 789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3002468101214Duplication NumberQuery ID(b)图图图 5-1查询消息数量的时间序列分布. (a)查询“Saint Ange”数量上的变化情况；(b)查询消息数量变化情况Fig. 5-1Query Time Series. (a)Time Series of “Saint Ange”. (b)The Distribution of Number Over Time作为一个直观的例子，图5.1(a)显示了我们在2005年4月16日在大约2,000个超节点上所观察到的查询消息“Saint Ange”数量的变化情况。根据图中数量的变化曲线，我们很难看出该曲线服从某些明显的规则。另外，图5.1(b)用方盒图列出了任意选择的30个查询消息的数量变化情况。每个方盒内的横线标明了中位数的位置，方盒的顶端和底端的横线则分别标明了第25%和75%的数的位置，而向上和向下延伸的虚线则标明了第2.5%和97.5%的数的范围，最后，方盒中的圆圈则标明了查询消息数量在不同时刻内的均值。无论是用四分位数范围还是用最大值来衡量，这些查询消息数量的序列都清晰的表现出很高的可变性，其四分位数范围通常都和均值大小相当，而最大值甚至会达到均值的4至5倍。由于我们所考察的用户查询消息已经去处了系统本身的影响，因而能够代表大量用户的查询行为，换句话说，我们所观察到的用户查询消息数量随着时间的不同出现较大变化的这36第五章 时间序列分析一现象不仅仅是Gnutella系统才具有的，对于其他系统，如在DHT上实现的文件共享系统，也同样会有这样的特性。值得注意的是，查询消息的这一特性对于过去提出的很多依赖于较为平稳的时间序列的算法都是不利的。比如，为了缓解以Gnutella为代表的非结构化P2P系统由于消息洪泛所造成的可扩展性差的问题，一些研究人员提出了利用结果缓存4951来减少对查询消息洪泛的数量。由于总体消息的数量非常庞大，所以为所有查询消息缓存查询结果并不切合实际，所以基于最近最少使用，即LRU(Least Recent Used)，的策略被应用到了结果缓存中来。遗憾的是，根据我们所发现的查询消息数量在不同的时间段的存在很大差异的这一现象，基于LRU的结果缓存很难达到较高的缓存命中率。作为另一个例子，结构化P2P系统，如Chord18，存在着负载不均衡的问题，尽管近年来研究人员提出了很多达到负载平衡的算法，但其中绝大多数都需要根据系统过去的负载情况来作出调整的决策，同样，我们所发现的这一现象也会严重的影响到这类算法的实际效果。要缓解这一现象，最重要的是要降低查询消息数量变化带来的影响，根据这一思路，我们将考虑如何能够预测出查询消息未来的数量。如果这一预测足够准确，现有的很多算法就可以不加修改的在这一预测结果的基础上执行，从而减轻甚至避免数量差异带来的负面影星。因此，我们所要考虑的问题主要有以下几个：查询消息的数量是不是能够被稳定的预测？如果是，我们应该用哪一类的预测模型来完成这一任务？对于同一类预测模型，它们在预测准确性和计算代价上的差异又如何？当我们找到理想的预测模型后，我们应该如何应用这一模型？这一模型能提高系统的哪方面性能？在下面的讨论中，我们将逐一回答这些问题。5.2Box-Jenkins模型在继续讨论模型的选择之前，我们首先对将要作为研究重点的Box-Jenkins模型做一个简要的介绍。我们使用Box-Jenkins模型来预测查询消息数量的基本思路是将查询消息数量的时间序列zt看作随机过程的一个实例，其中随机过程能够用白噪声驱动的线性过滤器来建模，并且其中的参数能够通过对以往序列的观测来估计。如果序列中绝大多数的变化能够可以由这样的过滤器来产生，那么我们就能够通过这些参数以较小的均方误差来估计未来的序列。我们将要检验的Box-Jenkins模型包括以下几种：AR(p)模模模型型型，AR(p)模型(自回归模型)能够表示为zt=1(B)at=11 1B 2B2 pBpat+ (5-1)其中是序列的均值，B是后退操作符，即Bdzt= ztd。AR(p)模型用序列中过去值的线性叠加以及白噪声at来表示未来的取值。AR(p)模型的一个非常好的性质是它能够在一个确定37第五章 时间序列分析的时间内拟合给定的数据。即使对于较大的p，使用Yule-Walker技术也可以在瞬间完成计算。AR(p)模型的另一个优点是非常的稳定。MA(q)模模模型型型，MA(q)模型(滑动平均模型)可以表示为zt= (B)at(5-2)(B) = 1 1B 2B2 qBq(5-3)。MA(q)模型对于系统设计者来说通常并不是一个理想的选择，其原因在于使用该模型拟合数据所花费的时间无法事先确定。不同于AR(p)模型的是，拟合一个MA(q)模型需要一个二次系统，而不是原来的线性系统。在我们的实现中，我们采用了52中介绍的迭代搜索算法来最小化t + 1时刻预测误差的平方和，其中达到收敛所需要的迭代的次数取决于数据，因而是是不确定的。ARMA(p,q)模模模型型型，ARMA(p,q)模型(自回归滑动平均模型)可以表示为zt=(B)(B)at(5-4)其中(B)和(B)和前面所定义的一样，并分别具有p和q个参数。通过合并AR(p)和MA(q)模型，ARMA(p,q)希望能够利用更少的参数达到足够好的拟合效果。站在系统设计者的立场上说，这一点也许非常重要，至少一个简洁的模型有可能会减少拟合所花费的时间。和MA(q)模型相同，ARMA(p,q)模型使用相同的拟合算法，并且需要花费的时间也是不确定的。ARIMA(p,d,q)模模模型型型，ARIMA(p,d,q)模型(自回归差分滑动平均模型)有如下表示zt=(B)(B)(1 B)dat(5-5)直观地说，分量(1 B)d实际上将对应的ARMA(p,q)模型的输出作了d阶差分。虽然这样使得过滤器不再稳定，但却让对非平稳序列(事实上非平稳序列是最常见的)的建模成为可能。非平稳序列往往会在一个无限的范围内变化，并且通常没有自然平均，虽然查询消息的数量不可能为无穷，但其确实没有一个自然平均。ARIMA(p,d,q)模型的拟合首先要对原有的序列做d次差分，之后再拟合ARMA(p,q)模型。在下面的讨论中，我们还会研究ARI(p,d)和IMA(d,q)模型，这两个模型时通过分别将ARIMA(p,d,q)模型中的q和p设为0得到的。其其其他他他用用用于于于比比比较较较的的的简简简单单单模模模型型型，为了比较的目的，我们还实现了三种简单的线性模型，分别为MEAN，BM和LAST模型。MEAN模型可以表示为zt= ，也即MEAN给出的预测为过去观测值的平均值，对于一个没有自相关性的序列来说，MEAN模型是最好的预测器，因为它给出的预测具有最小的均方误差，此外，我们也用MEAN来计算实际查询消息数量序列的方差。BM模型可以通过将AR(p)模型中所有的参数设为1来得到，它给出的预测是过去观察到的p个值的平均，即一个简单的窗口平均，另外，p的取值能够最小化对t + 1时刻预测的均方误差。最后，LAST模型的预测值为上一次的观测值，也即BM(1)。38第五章 时间序列分析5.3挖掘Gnutella查询流5.3.1方法为了评价不同模型的预测能力，我们没有采用传统的时间序列分析方法，而是使用了一套基于序列的随机方法53，该方法首先用查询消息数量序列中的一段来拟合每种模型，之后再用后继的序列来检验预测效果。我们很快就意识到在本文的研究背景下检验不同模型的预测能力是一个非常复杂的任务，其主要原因在于要搜索一个非常巨大的参数空间。这些参数包括：序列的选择，模型的种类，模型中参数的数量以及分布，预测的时间跨度，用于模型拟合的序列的长度以及对序列的单位时间的设定。此外，我们还想尽量避免由于对序列中特定区域过多使用所造成的偏倚。为了能够公平的搜索这样一个参数空间，我们使用算法1实验了大量的随机生成的测试序列。产生测试序列的方法如下：对于一个给定的序列，首先在其上选择一个随机的交叉点，tcross，然后选择一个在50到100间的随机数，m，由此产生的序列，ztcrossm,ztcrossm+1,.,ztcross1，称为拟合区间，也即8.3小时至16.7小时的一个序列。在这m个序列值之后，我们再选择一个在20到50之间的随机数，n，相应得到的序列，ztcross,ztcross+1,.,ztcross+n1，称为测试区间。在完成测试序列的生成后，我们用每一个模型，即AR、MA、ARMA、ARIMA、ARI、IMA、MEAN、BM和LAST，和不同的参数个数来拟合前面生成的拟合区间的序列，在拟合完成后，我们将根据拟合好的模型生成一个预测器，该预测器首先接收拟合区间的序列以使其完成初始化，之后，对于测试区间中的每个值，我们将该值输入预测器，再利用预测器产生不同时间跨度，k(取值在1至12之间)，的预测，最后根据这些预测输出，计算出k步预测的误差。在拟合和测试的同时，我们还记录计算所使用的时间，以方便对不同模型的计算代价做出比较。值得说明的是，我们对拟合区间长度下限(50)的设置是很常见，Box-Jenkins模型通常只需要这么多的数据就能够成功的拟合。另外，我们没有将上限设置的很大的原因是，在实际环境中，节点很难收集到很长的查询消息数量序列。我们将模型的参数数目都控制在16以内，其原因是更多的参数将导致MA和ARMA模型的拟合变得极为缓慢，对于实际的系统来说是不现实的。但是对于AR模型，由于其拟合时间很短，我们还考察了具有32个参数的AR模型的预测能力。5.3.2挖掘结果在这一节中，我们将回答以下问题：查询消息的数量是否是稳定可预测的？如果是，不同模型之间的区别是什么？哪一类模型最为合适？我们的讨论将主要集中在预测结果的均方误差上，原因在于我们主要关心的是模型的预测能力，而不是如何来解释这种能力。39第五章 时间序列分析Algorithm 1 Evaluating model predictability 算法1 验模型的预测能力Require: 50 m 100 20 m 50tcross A random cross point within the tracem A random number between 50 and 100n A random number between 20 to 50for every model doUse the model to fit m samples before tcross.Give a predictor.end forfor i = m to 1 doStep the predictor with ztcrossi.end forfor i = 0 to n 1 doStep the predictor with ztcross+i.for k = 1 to 12 doProduce zktcross+i(the prediction of ztcross+i+k)Compute the prediction error akt+i.end forend forMEANAR(16)ARI(16,1)ARMA(8,8)ARIMA(8,1,8)MA(16)IMA(1,16)05101520Mean Squared ErrorDifferent Models(a)MEANAR(16)ARI(16,1)ARMA(8,8)ARIMA(8,1,8)MA(16)IMA(1,16)5101520Mean Squared ErrorDifferent Models(b)MEANAR(16)ARI(16,1)ARMA(8,8)ARIMA(8,1,8)MA(16)IMA(1,16)51015202530Mean Squared ErrorDifferent Models(c)图图图 5-2高度重复的5%查询预测均方误差分布(16阶). (a)1步(10分钟)；(b)6步(1小时)；(c)12步(2小时)Fig. 5-25% Duplicated Queries MSE(16-parameter) (a)1-step(10 min) (b)6-step(1 h) (c)12-step(2 h)查查查询询询消消消息息息的的的数数数量量量是是是稳稳稳定定定可可可预预预测测测的的的。对于一个能够稳定的预测未来查询消息数量的模型来说，它必须能够满足两个条件：(1)首先，和实际查询消息的方差相比，该模型给出的预测必须有非常小的均方误差期望；(2)其次，该模型预测准确程度不应随着序列的不同而出现大范围的变化。40第五章 时间序列分析050100150200250102030405060708090Lead Time (minutes)Average Variance Reduction (%)ARI(16,1)ARI(32,1)ARIMA(8,1,8)IMA(1,16)(a)0501001502002500102030405060Lead Time (minutes)Average Variance Reduction (%)ARI(16,1)ARI(32,1)ARIMA(8,1,8)IMA(1,16)(b)050100150200250220200180160140120100Lead Time (minutes)Average Variance Reduction (%)LASTBM(8)BM(16)(c)图图图 5-3方差减小量比较. (a)高度重复的5%查询(BJ)；(b)所有查询(BJ)；(c)所有查询(简单模型)Fig. 5-3Variance Reduction (a)Top 5% Duplicated Queries(BJ) (b)All Queries(BJ) (c)All Queries(SM)直观的说，第一个条件确保了平均意义上好的预测，而第二个条件则保证了所有的预测都接近这个平均。在考察查询消息数量的时间序列特性时，我们发现序列的方差(假定正态分布)和最大值正相关于序列的均值。因此，具有较大数量的查询消息也倾向于拥有较大的方差和最大值，这一现象也说明对于数量较大的查询消息来说，预测模型能够更好的降低方差。所以，我们将从具有较大数量的查询消息开始考察模型的预测能力。图5.2(a)说明了查询消息数量确实是稳定可预测的，这里的方盒图向我们展示了使用Box-Jenkins模型在数量最大的5%的查询消息上的1步预测的均方误差分布。值得注意的是实际查询消息序列的平均方差大约是13.0，而所有具有16个参数的模型的平均均方误差均达到了3.0甚至更小，同时，各预测模型均方误差的变化也明显小于MEAN的变化。例如，最大的实际序列方差的接近25.0，而所有模型的预测均方误差上限都没有超过5.0。图5.2(b)和5.2(c)展示了6步(1小时)预测和12步(2小时)预测的效果。我们仍然可以看到，除了MA模型，所有Box-Jenkins模型的预测均方误差比实际序列的方差要小。另一方面，虽然除了MA模型外其他模型都有类似的预测精度，但差分模型要比非差分模型效果好，特别是在给出步长较大的预测时。AR模模模型型型更更更为为为合合合适适适。在实现一个流处理系统时，我们不仅要考虑输出的准确性，同时还要考虑相应的计算代价。因此，在我们最终决定使用哪种模型做预测之前，我们还需要就各模型的计算代价做一个比较。为了评价计算代价，我们使用一台配备了Pentium IV 2.4GHz的IBM PC机测量了一个模型在拟合100个数据组成的序列，创建一个预测器，以及给出1步预测所耗费的CPU时间。另外，除了窗口大小超过16的BM模型，其他简单模型没有被考虑到比较中，因为我们发现这些模型通常只需要少于1毫秒的时间来拟合。最后，差分模型也没有参与比较，其原因在于一旦序列差分后，差分模型和非差分模型的计算并没有差异。图5-4揭示出AR模型拟合的计算代价非常小，即使是对高阶的AR(32)来说也是这样，这41第五章 时间序列分析?图图图 5-4计算消耗的CPU时间比较Fig. 5-4Comparison of Required CPU Time.一特点对于在线预测系统来说具有很大的优势。对于MA和ARMA模型来说，它们拟合数据时的计算代价要高很多。例如，MA(16)需要大约0.87秒来拟合由100个数据组成的序列，而AR(16)模型只需要0.02秒。此外，图中还可以看出所有模型在给出1步预测时所消耗的时间都非常少。因此，具有合理阶数的AR模型与MA和ARMA模型相比，其拟合的代价要小得多。虽然图?中AR模型的表现在所有具有同样阶数的模型中不是最好的，我们将在接下来的讨论中说明高阶的AR模型具有很好的预测效果。另外，由于AR模型的拟合还具有确定的计算时间，与其他计算时间不确定的模型相比，我们认为AR模型最为适合预测查询消息未来的数量。我们也注意到查询消息之间的数量差距是很大的，有时候甚至达到几位数的差距。不幸的是，均方误差的大小是和查询消息的数量相关的，对于数量小的查询消息来说，即使模型的预测效果很差，其均方误差也可能很小。因此，使用均方误差来考察模型在所有查询消息上的预测能力是不合适。为了解决这个问题，我们采用了一个新的量来衡量模型的预测性能，即方差减小量的百分比期望。使用这一指标的好处在于，它将模型在数量级别不同的查询消息序列上的表现正则化，从而使得其比较成为可能。图?使用上述方差减小量的百分比期望分别在数量最多的5%的查询消息序列以及所有的查询消息序列上对ARI(16,1)、ARI(32,1)、IMA(1,16)和ARIMA(8,1,8)模型作了比较。图中的每条曲线描绘了一个模型平均的方差减小百分比。值得一提的是，MEAN模型的减小百分比是0%，一个模型只有在给出0均方误差的情况下才能达到100%的方差减小百分比。如图所示，对于16阶模型来说，IMA模型给出了最好的预测，其次是ARIMA和ARI模型。这三个模型在给出多步预测时，其预测准确度也有类似的下降。尽管如此，我们发现高阶的ARI模型同样有很好的预测效果，甚至比低阶的ARIMA模型还要好。更重要的是，高阶ARI模型在给出多步预测42第五章 时间序列分析时，其预测准确度的下降速度相比其他模型要慢得多。同时不难看出，Box-Jenkins模型在数量最多的5%的查询消息序列上的预测效果要好于在所有查询消息序列上的效果。例如，ARI(32,1)和IMA(1,16)在前者上的1步预测的方差减少率超过了80%。这一特点对于我们所考虑的场景是非常有利的，正如我们前面所提到的，对数量较大的查询消息的预测至关重要，因为这些查询消息是系统通信开销的主要成分。最后，我们还比较了简单窗口模型和Box-Jenkins模型的预测效果，毕竟简单模型的具有最低的拟合代价并且非常容易理解和实现。在图5.3(c)中我们看到，LAST和BM模型的效果非常不理想，两者甚至都没有产生正的方差减少百分比。显然，这些模型不适合用来做预测，虽然它们的计算代价很小。43第六章应用6.1预测增强的P2P结果缓存为了将Box-Jenkins模型的预测能力应用到Gnutella的查询流中，我们提出了Gnutella中基于预测的协作结果查询系统，pCoCa54。pCoCa是一个完全分布式的系统，每个节点根据本地观察的查询流作出预测，并通过投票产生最终的缓存策略。6.1.1系统设计由于在Gnutella0.6中只有超节点负责查询消息的路由，pCoCa被设计为部署在超节点之上。我们将节点的在线时间划分为长度固定的快照，当节点连入网络时，pCoCa首先会收集当前查询消息数量的情况，并在此基础之上快速的构建预测模型并对未来的查询消息数量作出预测，这些预测的结果随后在节点间进行投票，并形成最终的缓存策略。初初初始始始化化化，为了收集初始的查询消息序列信息，新连入网络的节点会向其邻居节点询问对方所维护的查询消息序列。在假设查询消息以恒定速度到达节点的条件下，节点可以将收集到的查询消息序列合并为本地的查询消息序列。数数数据据据拟拟拟合合合，在初始化之后，pCoCa用ARI(32,1)模型拟合本地生成的查询消息序列，并产生相应的预测器，该预测器随后将产生对今后查询消息数量的预测。消消消息息息缓缓缓存存存，在预测器对今后的查询消息数量给出预测后，pCoCa则将本地的预测结果以投票的形式发送给邻居节点，同时接受邻居节点的预测结果，最终的缓存策略则是在本地的预测结果和邻居节点的预测结果之上综合作出的。在随后的检验部分我们可以看到，这样的投票机制对于分布式缓存是极为重要的。pCoCa中的投票是一个由K + 1-元组构成的列表，其中K是预测的最大步长。每个元组包含查询消息的内容以及一些列预测结果，即1步预测至k步预测的结果。同时，为了避免投票带来过高的网络传输开销，列表的长度也受到限制。考虑到洪泛所产生的查询消息的数量是指数增长的，有投票所产生的消息数量与pCoCa所减少的消息数量相比则几乎可以忽略。避避避免免免多多多级级级缓缓缓存存存，过去提出的缓存机制49, 51从其分布式的本质中继承了多级缓存的问题。由于这些机制仅仅沿用了Gnutella原有的查询消息，节点无法区分接受到的查询结果是来自其他节点的缓存还是当前新产生的。因此，节点用来更新本地缓存的查询结果也有可能是已经被多个节点多次缓存后，实际上早已失效的查询结果。为了解决这一问题，我们根据Gnutella通用扩展协议(GGEP)7实现了一种新的查询消息，即缓存更新查询。当pCoCa接收到缓存更新查询消息时，它会像普通Gnutella节点接受到查询消息一样来处理在我们的模拟实验中，我们将K的值设定为4。44第六章 应用该消息。因此，通过这一机制，我们就避免了查询结果的多级缓存，保证了查询结果的有效性。6.1.2效果检验我们实际并实现了一个由序列驱动的模拟器，该模拟器以实际的Gnutella查询消息序列为输入，对我们提出的缓存机制进行模拟，并统计和记录相应的效果和效率。我们所使用的数据集包括Gnutella网络中节点的连接数据、节点在线时间、共享文件分布以及在218,842个超节点上观察到的40小时的查询消息记录(共70,876,100条查询消息)。有了这些数据，我们的模拟器就可以真实的“回放”超节点间的查询消息路由，从而使得我们的模拟和检验符合实际情况。为了进行比较，我们的检验还包括过去提出的Gnutella缓存系统49和基于LRU的缓存系统。在我们的比较中，所涉及的衡量指标包括数据包的减少百分比和内存使用量。前者用以表征缓存机制的实际效果，而后者则用来评价缓存策略的资源使用效率。图6.1(a)中，“interval”指的是快照的时间长度，“Top n%”指的是被缓存的查询消息(按预测值由大到小排序)的比例，也即缓存的大小。不难看出，“top 60%”曲线所产生的查询消息减少量最为显著，在快照时间长度大于10分钟的情况下，其消息减少的比例甚至超过了60%。另外，虽然“top 40%”曲线的效果略差于SC曲线，但对较短的快照(少于10分钟)来说，“top 40%”和“top 60%”曲线的效果均比SC曲线要好。这一事实说明，基于预测的缓存策略能够很好的适应高度动态的Gnutella网络。此外，SC的缓存性能还受到本地信息的局限，因为节点无法侦测到邻居节点上正在出现的某些查询消息数量的激增。而通过投票机制，pCoCa能够处理这样的情况。从图中还可以看出，所有的LRUC曲线的效果要比SC曲线差，其原因在于SC并不限制缓存的使用量。尽管如此，当快照的时间长度增加时，LRUC曲线的效果逐渐和pCoCa曲线的效果接近，这是因为较长的时间间隔有助于LRUC作出正确的缓存策略，但是在实际系统中考虑到节点的平均在线时间都很短，较长的快照是不实际的。在处理连续的数据流是由两个参数是需要我们重点考虑的，一个是单位数据项处理时间，另一个是内存使用量。在前面的讨论中，我们已经了解到AR模型由于其较低的计算代价，因而有很好的单位数据项处理时间。在这里，我们发现pCoCa与其他结果缓存机制相比，还具有内存使用量少的优点。如图6.1(b)所示，SC曲线所代表的内存使用量的增长远远超过pCoCa曲线。例如，当快照的时间长度为15分钟时，SC曲线的内存使用量已经接近25MB，而对于pCoCa的三条曲线来说，其内存使用量分别是10MB，7MB和4MB。6.2预测增强的P2P负载平衡负载均衡，也即被处理数据项(或其他负载形式)在节点间的均匀分配，使结构化P2P系统所面临的一个重要问题。过去研究人员对于Chord18曾经提出了一些我们称之为“动态负在下文中，我们用“简单缓存(SC)” 来表示。由于LRUC的内存使用量和pCoCa相同，因此没有被放到图中。45第六章 应用051015202530354020253035404550556065Interval(Minute)Packet Reduction Percentage(%)Simple CachepCoCa Top 20%pCoCa Top 40%pCoCa Top 60%LRU TOP 20%LRU TOP 40%LRU TOP 60%(a)051015202530354000.511.522.533.5x 104Interval(Minute)Used Memory Size(KB)Simple CachepCoCa Top 20%pCoCa Top 40%pCoCa Top 60%(b)? ? ? ? ? ? ? ? ?(c)?(d)图图图 6-1检验结果，(a)数据包减少量(b)缓存使用(c)负载方差减少量(d)节点资源使用率Fig. 6-1Evaluation (a)Packet Reduction (b)Memory Usage (c)Variance Reduction (d)Peer Utilization载平衡”的负载平衡的实现方法55, 56，这些方法根据过去的负载分布情况调整节点的虚拟地址以达到负载平衡的目的，然而，这样做的同时也使得该类方法依赖于历史负载和未来负载的近似分布。在我们前面的讨论中，我们已经发现，某些类型负载的分布，如查询消息消息的负载，具有很高的动态性，一旦上述的负载均衡算法运用到这样的环境中，其实际的运行效果将受到很大的影响。为了解决这个问题，我们提出了一个针对动态负载平衡算法的一个通用增强机制，该机制使用Box-Jenkins模型来预测未来负载的分布，从而成为Box-Jenkins模型在结构化P2P系统中的一个应用。46第六章 应用6.2.1系统设计我们的预测增强负载均衡系统对原有的负载均衡算法并没有作任何改动，实际上，我们只是将原来输入这些算法的历史负载改变为预测的负载。由于该方法的系统无关性，尽管我们指在动态负载平衡的一种算法上检验了它的实际效果，它还可以被应用到其他动态负载平衡算法中。在下面的实验中，我们选择了Karger和Ruhl为Chord所提出的负载平衡协议? 来验证我们的方法。选择该协议的原因在于，他们的算法的代价范围经过了严格的理论证明，因此有较强的理论基础。在很多情况下，Chord所维护的每个数据项在其负载上并不是均等的。例如，在搜索的环境中，不同关键字所带来的搜索负载并不相同，某些热门关键字所带来的负载可能远远超过一些较为冷门的关键字。为了能够将这一现象在我们的模拟实验中重现，我们为每个关键字k分配了一个权重w(k)，来表示该关键字所带来的负载。不过这样做仍然有一个明显的缺陷，节点间的负载交换只能以关键字为单位。例如，考虑系统中有这样的两个节点，一个节点所维护的关键字的权重为1，而另一个维护的关键字的权重为100。如果这两个节点进入了负载交换状态，那么将没有任何交换方法可以平衡这两个节点的负载。为了进一步解决这一问题，我们还未每个关键字分配了一个虚拟地址范围，该范围的具体形式为占整个地址空间的百分比。这样，当用户在向系统提交搜索的时候，我们为其搜索中的每个关键字分配一个在前面所提到的地址范围内均匀分布的偏移量。最终每个关键字所对应的节点地址就是原有该关键字的hash值加上该偏移量。这样，我们就实现了将一个关键字所带来的负载均匀的分配到一个地址范围内的节点上，从而确保了节点间对一个关键字的负载交换能够有效地进行。6.2.2效果检验我们在前面介绍的序列驱动的模拟器上验证了我们提出的基于预测的负载均衡的增强算法(下文简称pLB)，同时，我们还与Karger和Ruhl提出的动态平衡算法(下文用LB简称)作了比较。在检验中我们使用了两种评价指标，一个是负载方差，即假定负载整台分布的情况下，节点间负载分布的方差；另一个是节点资源的利用率，即每个节点上的实际负载l与负载上限C的比例。前者主要用来衡量节点间负载分布的均匀程度，而后者主要考察是否存在过载的节点，因为过载节点的存在将严重影响系统的稳定性。在图6.1(c)中，是我们前面提到的关键字的偏移范围参数，而是判断两节点是否进入负载交换状态的评价指标，也即如果两节点间的负载之比超过，则两节点进入负载交换状态。如图所示，pLB的表现在 = 0.01, = 0.4时最好，其方差减小量达到了23.1%。在同样的参数配置下，图6.1(d)显示了节点的平均利用率，在我们的模拟实验中，我们将C设置为2Ln，其中L是系统的整体负载之和，而n是节点的总数。如图所示，pLB所产生的节点负载更为均衡，更为重要的是，过载的节点在pLB所增强的系统中要远少于LB所增强的系统，47第六章 应用其减少率接近83.3%。因此，上述结果说明，对未来负载的预测能够很好的减轻大动态负载所带来的负面影响。48第七章总结与展望7.1论文工作总结在本文中，我们首先介绍了P2P网络统计特征分析的意义和相关工作，并指出了目前该方面已有研究工作仍存在的一些问题。接着，我们从介绍Gnutella这样一个大规模的P2P系统开始，逐步分析了如何在这样一个平台上高效的收集统计数据的细节，并设计了一个分布式的协作爬虫系统。基于该爬虫系统所收集的海量数据，我们从节点在线时间、节点角色选择、节点连接情况、共享文件以及查询消息分布等方面较为全面的分析了Gnutella系统的统计特征。同时，我们注意到Gnutella查询消息的数量有着很大的动态性，因此我们又从时间序列的角度分析了Gnutella系统中查询消息流的特性，并研究了查询消息数量的可预测性，找到了能够提供准确预测同时具有较小计算代价的AR(p)模型。最后，我们提出了Gnutella系统中基于该模型的结果缓存机制和Chord系统中同样基于该模型的动态负载均衡机制，并获得了较好的效果。本文所涉及的研究工作的意义在于：(1)为Gnutella0.6设计了一套创新的统计数据收集方案，其中包括对查询消息的全面收集；(2)发现了Gnutella0.6中新出现的一些重要的现象和问题，如节点角色的选择问题等，为将来的研究提供了基础；(3)提供了很多精确的统计数据，为今后的P2P系统建模提供了重要的依据；(4)爬虫系统所收集的数据集使得更为精确、更为接近真实的模拟成为可能；(5)提出了从时间序列角度研究P2P数据流的方法，并揭示了P2P查询消息数量的可预测性；(6)所提出的基于预测的查询结果缓存和动态负载均衡是对以往工作的一个补充，同时为今后类似应用的提出做了铺垫。此外，在研究的过程中，我们先后在国际会议上发表了两篇相关的论文57, 58。7.2未来工作展望我们对未来工作的展望主要有两个层面：一是对目前工作的延伸；二是对相关领域的探讨。首先，我们认为目前的工作可以在以下几个方面加以改进和完善：49第七章 总结与展望进一步整理和完善已有的数据集，其内容应至少包括两方面，一方面是节点的静态元数据(在线时间、地址、带宽、延迟、邻居节点、共享文件等)；另一方面是节点的动态活动数据(包括发出的查询消息、转发的查询消息等)。目标是为P2P系统提供一套通用的实验数据集。进一步完善目前的模拟器，使之具有通用性，能够提供较为完善的借口，方便用户完成可能的模拟任务，另外应该能够根据提供的数据集自动生成模拟环境；开展对另一些当前拥有庞大用户群的P2P系统的统计特性分析工作，如通信类Skype等。其次，由于P2P统计特征分析设计到P2P领域研究的方方面面，对于未来的工作，我们至少可以在下面几方面开展进一步研究工作：当前P2P领域中一个研究的热点是安全问题，我们可以从当前拥有的数据出发，对用户的行为进行分析和建模，特别是和安全相关的方面，如病毒的扩散、攻击的监测以及共享文件的破坏等；由于互联网上不断涌现的各种流数据的应用，目前流数据的挖掘和处理正得到人们越来越多地重视，因此，开展对P2P系统中各种流数据的挖掘和处理将是一个新的研究方向；目前的分布式计算和网络领域中的另一个趋势是将P2P领域中一些先进的技术运用到无线网络、感应器网络和互联网基础架构设计方面，在我们目前统计数据的基础上，通过引入不同环境中的新的影响因素，我们能够逐步开展对其他网络领域的统计分析和建模。50参 考 文 献1 Andresen, D., Yang, T., Holmedahl, V., Ibarra, O.H.: Sweb: Towards a scalable worldwide web server on multicomputers. In: IPPS 96: Proceedings of the 10th InternationalParallel Processing Symposium, Washington, DC, USA, IEEE Computer Society (1996)8508562 Group, A.: There is no p-to-p market.but there is a market for p-to-p (2001)3 Graham, R.: Traditional and non-traditional applications. Peer-to-Peer Networks. Lec-ture (2001)4 Shirky,C.:Whatisp2p.andwhatisnt.OReillyNetwork(2001)http:/www.openp2p.com/ lpt/a/p2p/2000/11/24/shirky1-whatisp2p.html.5 Sullivan III, W.T., Werthimer, D., Bowyer, S., Cobb, J., Gedye, D., Anderson, D.: A newmajor SETI project based on project serendip data and 100,000 personal computers. In:Proceedings of the Fifth International Conference on Bioastronomy, Editrice Compositori,Bologna, Italy (1997)6 Gehl, J.: Question time: Napster. Ubiquity 1 (2000) 47 Ripeanu, M.: peer-to-peer architecture case study: gnutella network. In: First Interna-tional Conference on Peer-to-Peer Computing (P2P 01). (2001) 998 Loo, A.W.:The future of peer-to-peer computing. Communications of the ACM 46(2003) 56619 Joseph, S., Hoshiai, T.: Decentralized meta-data strategies: effective peer-to-peer search.IEICE Transactions on Communications E86-B (2003) 1740175310 Izal, M., Urvoy-Keller, G., Biersack, E.W., Felber, P., Hamra, A.A., Garcs-Erice, L.:Dissecting bittorrent: Five months in a torrents lifetime. In: Proceedings of Passive andActive Network Measurement: 5th International Workshop, PAM 2004. Volume 3015.(2004) 1 1111 Milojicic, D.S., Kalogeraki, V., Lukose, R., Nagaraja1, K., Pruyne, J., Richard, B., SamiRollins 2, Z.X.: Peer-to-peer computing. Technical Publications Department, HP LabsResearch Library, technical report HPL-2002-57 20020315 (2002)51参 考 文 献12 Androutsellis-Theotokis, S., Spinellis, D.: A survey of peer-to-peer content distributiontechnologies. ACM Computing Surveys 36 (2004) 33537113 Lua, E.K., Crowcroft, J., Pias, M., Sharma, R., Lim, S.: A survey and comparison ofpeer-to-peer overlay network schemes. In Submission to IEEE Communications Surveyand Tutorial (2004)14 Ribak, A., Jacovi, M., Soroka, V.: “ask before you search”: peer support and communitybuilding with reachout. In: Proceedings of ACM CSCW02 Conference on Computer-Supported Cooperative Work. Social navigation (2002) 12613515 Good, N.S., Krekelberg, A.: Usability and privacy: a study of kazaa p2p file-sharing. In:CHI 03: Proceedings of the SIGCHI conference on Human factors in computing systems,New York, NY, USA, ACM Press (2003) 13714416 Nejdl, W., Wolf, B., Qu, C., Decker, S., Sintek, M., Naeve, A., Nilsson, M., Palmer,M., Risch, T.: Edutella: a p2p networking infrastructure based on rdf. In: WWW 02:Proceedings of the 11th international conference on World Wide Web, New York, NY,USA, ACM Press (2002) 60461517 Ratnasamy, S., Francis, P., Handley, M., Karp, R., Schenker, S.:A scalable content-addressable network. In: SIGCOMM 01: Proceedings of the 2001 conference on Ap-plications, technologies, architectures, and protocols for computer communications, NewYork, NY, USA, ACM Press (2001) 16117218 Stoica, I., Morris, R., Liben-Nowell, D., Karger, D.R., Kaashoek, M.F., Dabek, F., Bal-akrishnan, H.: Chord: a scalable peer-to-peer lookup protocol for internet applications.IEEE/ACM Transactions on Networking 11 (2003) 173219 Rowstron, A., Druschel, P.: Pastry: scalable, decentralized object location, and routingfor large-scale peer-to-peer systems. In: Proceedings of the 18th IFIP/ACM InternationalConference on Distributed Systems Platforms. (2001) 32935020 Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.D.:Tapestry: A resilient global-scale overlay for service deployment. IEEE Journal on Se-lected Areas in Communications 22 (2004) 415321 Larson, S.M., Snow, C.D., Pande, V.S.:FoldingHome and GenomeHome: Usingdistributed computing to tackle previously intractable problems in computational biology.In: Modern Methods in Computational Biology. Horizon Press (2003)52参 考 文 献22 Cohen, E., Shenker, S.:Replication strategies in unstructured peer-to-peer networks.In: SIGCOMM 02: Proceedings of the 2002 conference on Applications, technologies,architectures, and protocols for computer communications, New York, NY, USA, ACMPress (2002) 17719023 Markatos, E.P.: Tracing a large-scale peer to peer system: An hour in the life of gnutella.In: Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computingand the Grid (CCGRID02), IEEE (2002) 56 6524 Ripeanu, M., Foster, I.T.:Mapping the gnutella network: Macroscopic properties oflarge-scale peer-to-peer systems. In: IPTPS 01: Revised Papers from the First Interna-tional Workshop on Peer-to-Peer Systems, London, UK, Springer-Verlag (2002) 859325 Ian Clarke, Oskar Sandberg, B.W., Hong4, T.W.:Freenet: A distributed anonymousinformation storage and retrieval system. White Paper (1999)26 Clarke, I., Miller, S.G., W.Hong, T., Sandberg, O., Wiley, B.: Protecting free expressiononline with freenet. IEEE INTERNET COMPUTING 6 (2002) 404927 Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels, D., Gummadi,R., Rhea, S., Weatherspoon, H., Wells, C., Zhao, B.:OceanStore: an architecture forglobal-scale persistent storage. In: ASPLOS-IX: Proceedings of the ninth internationalconference on Architectural support for programming languages and operating systems,New York, NY, USA, ACM Press (2000) 19020128 Adya, A., Bolosky, W.J., Castro, M., Cermak, G., Chaiken, R., Douceur, J.R., Howell, J.,Lorch, J.R., Theimer, M., Wattenhofer, R.P.: Farsite: federated, available, and reliablestorage for an incompletely trusted environment.ACM SIGOPS Operating SystemsReview 36 (2002) 11429 Waldman, M., Rubin, A.D., Cranor, L.F.: Publius: a robust, tamperevident, censorship-resistant,web publishing system. In: Proceedings of the Ninth USENIX Security Sympo-suim, Denver, CO, USA (2000)30 Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., Lewin, D.: Consistenthashing and random trees: distributed caching protocols for relieving hot spots on theworld wide web. In: STOC 97: Proceedings of the twenty-ninth annual ACM symposiumon Theory of computing, New York, NY, USA, ACM Press (1997) 65466331 of Standards, C.N.I., Technology: Federal information processing standards publication180 (1993 may 11): specifications for the secure hash standard (shs). (1995) 879253参 考 文 献32 Dabek, F., Kaashoek, M.F., Karger, D., Morris, R., Stoica, I.:Wide-area cooperativestorage with cfs.In: SOSP 01: Proceedings of the eighteenth ACM symposium onOperating systems principles, New York, NY, USA, ACM Press (2001) 20221533 Russ Cox, Athicha Muthitacharoen, R.T.M.: Serving DNS using chord. In: Proceedingsof the first international workshop on peer-to-peer systems. (2002) 17818434 Castro, M., Druschel, P., Kermarrec, A.M., Rowstron, A.:Scribe: A large-scale anddecentralized application-level multicast infrastructure. IEEE Journal on Selected Areasin Communications, 20 (2002) 10011035 Iyer, S., Rowstron, A., Druschel, P.: Squirrel: a decentralized peer-to-peer web cache. In:PODC 02: Proceedings of the twenty-first annual symposium on Principles of distributedcomputing, New York, NY, USA, ACM Press (2002) 21322236 Rowstron, A., Druschel, P.:Storage management and caching in past, a large-scale,persistent peer-to-peer storage utility. In: SOSP 01: Proceedings of the eighteenth ACMsymposium on Operating systems principles, New York, NY, USA, ACM Press (2001)18820137 Cox, L.P., Murray, C.D., Noble, B.D.: Pastiche: making backup cheap and easy. ACMSIGOPS Operating Systems Review 36 (2002) 28529838 Saroiu, S., Gummadi, K.P., Gribble, S.D.: Measuring and analyzing the characteristicsof napster and gnutella hosts. Multimedia Systems 9 (2003) 170 8439 Adar, E., Huberman, B.A.: Free riding on gnutella. First Monday 5 (2000)40 Klemm, A., Lindemann, C., Vernon, M.K., Waldhorst, O.P.: Characterizing the querybehavior in peer-to-peer file sharing systems. In: IMC 04: Proceedings of the 4th ACMSIGCOMM conference on Internet measurement, New York, NY, USA, ACM Press (2004)556741 Adar, E., Huberman, B.A.: Free riding on gnutella. First Monday 5 (2000)42 Kwok, S.H., Yang, C.C.: Searching the peer-to-peer networks: The community and theirqueries. JASIST 55 (2004) 78379343 Sen, S., Wang, J.:Analyzing peer-to-peer traffic across large networks. IEEE/ACMTransactions on Networking 12 (2004) 21923244 : Limewire. http:/www.limewire.com (2004)54参 考 文 献45 Saroiu, S., Gummadi, P.K., Gribble, S.D.: Sprobe: A fast technique for measuring bottle-neck bandwidth in uncooperative environments. In: Infocom 2002 Technical Conference.(2002)46 Miller, J.:Characterization of data on the gnutella peer-to-peer network. In: IEEEJOURNAL ON SELECTED AREAS IN COMM. Volume 21. (2003) 995100247 Bu, T., Towsley, D.F.: On distinguishing between internet power law topology generators.In: INFOCOM. (2002)48 Khambatti, M., Ryu, K.D., Dasgupta, P.:Peer-to-peer communities: Formation anddiscovery. In: PDCS. (2002) 16116649 Markatos, E.P.: Tracing a large-scale peer to peer system: An hour in the life of gnutella.In: CCGRID, IEEE Computer Society (2002) 657450 Patro, S., Hu, Y.C.:Transparent query caching in peer-to-peer overlay networks. In:IPDPS, IEEE Computer Society (2003) 3251 Wang, C., Xiao, L., Liu, Y., Zheng, P.:Distributed caching and adaptive search inmultilayer p2p networks. In: ICDCS. (2004) 21922652 Ljung: 10.2. In: System identification: Theory for user. Prentice Hall, NJ (1999)53 Dinda, P.A., OHallaron, D.R.: Host load prediction using linear models. Cluster Com-puting 3 (2000) 26528054 Meng,S.:Predicting-basedcollaborativeresultscachingsystempcoca.Technicalreport,APEXDataMiningandKnowledgeManagementLab,http:/apex.sjtu.edu.cn/download/pcoca.pdf (2005)55 Rao, A., Lakshminarayanan, K., Surana, S., Karp, R.M., Stoica, I.: Load balancing instructured p2p systems. In: IPTPS. Volume 2735 of Lecture Notes in Computer Science.(2003) 687956 Karger, D.R., Ruhl, M.:Simple efficient load balancing algorithms for peer-to-peersystems. In Gibbons, P.B., Adler, M., eds.: SPAA, ACM (2004) 364357 Meng, S., Shi, C., Han, D., Zhu, X., Yu, Y.: A statistical study of todays gnutella. In:APWeb. Volume 3841 of Lecture Notes in Computer Science. (2006) 18920058 Meng, S., Shi, C., Han, D., Yu, Y.:Mining and predicting duplication over peer-to-peer query streams. In: Workshops of International Conference on Data Mining(ICDM).(2006)55致谢我首先要感谢我的导师俞勇教授在我攻读硕士研究生期间给我的指导和帮助，他给我创造了非常优越的学习和研究的环境，并言传身教，教会我应该以什么样的态度去面对学习和研究工作。他还给了我很多的实践机会，包括一些专业的培训和项目，我在这些实践机会中增长了许多见识，锻炼了各方面的技能，并积累了许多经验。让我感到非常幸运的是，我能够成为APEX实验室的一员。在这样一个非常有研究气氛的实验室里，能够在师兄们的研究方向指引下，研究热情的感召下开展工作，我确实学到了许多东西，甚至包括在受到失败和挫折后怎样总结，分析问题，进一步完善自己的工作。我特别要感谢研究小组组长朱星和韩定一同学，应该说，是他给我指明了研究的方向，向我解释了很多的疑惑，并指导我开展了很多的研究工作。和小组内的成员朱伟斌、曹华梁、施聪和刘光灿一起讨论问题是充满乐趣的，因为我总能从这些讨论中得到启发。另外，我还要感谢张雷、薛贵荣、朱海平、包胜华、吴贤、张杰、吴晓圆等师兄和同学，他们给了我很大的帮助。我还要感谢我的父母，他们不仅养育了我，教会了我很多做人的道理，还不断地在学习上鼓励我，本文也献给他们。56已发表论文(1) Shicong Meng，Cong Shi，Dingyi Han，Xing Zhu，Yong Yu, ”A Statistical Study ofTodays Gnutella”, in Proceeding of 8th Asia-Pacific Web Conference (APWeb2006):189-200, Harbin, China.(2) Shicong Meng，Cong Shi，Dingyi Han，Yong Yu, ”Mining and Predicting Dupli-cation over Peer-to-Peer Query Streams”, in Workshops of 2006 IEEE InternationalConference on Data Mining (ICDM2006), Hongkong, China, to appear.(3) Shicong Meng，Cong Shi，Xinyao Hu, Dingyi Han，Yong Yu, ”Predicting Query Du-plication with Box-Jenkins Models and Its Applications”, in Proceedings of InternationalConference on Communications (ICC2007), Glasgow, Scotland, to appear.57