（计算机软件与理论专业论文）基于gnutella协议的peertopeer网络连接管理.pdf

摘要 p e e r - t o - p e e r ( p 2 p ) 是通过直接交换共享计算机资源和服务的一种网络体系 结构。g n u t e l l a 作为一种典型的p 2 p 网络通信协议，具有智能发现节点、完全分 布式的特点，它能够有效的消除单点瓶颈，使网络具有很强的健壮性。与此同时， 该协议也产生了以指数级增长的冗余消息，效率低下，使之只能在小规模的网络 上使用，很难成为应用的主流。 本文从g n u t e l l a 协议的节点定位入手，提供了两种节点定位模型：网络模型 和多播模型。这两种模型都基于g n u t e l l a 网络完全分布式和动态性的特点，能够 实现节点之间的快速定位，从而获取有效的节点连接信息。我们详细解析了 g n u t e | l a 网络的广播机制，划分了g n u t e l l a 协议中四种消息的优先级，分析了丢 弃连接的必要性和可行性。在此基础上，我们提出了f - m e a s u r e 算法。同时，考 虑到g n u t e l l a 协议其下层的连接大多是基于t c p 和p p p 协议的，因此，本文还 借鉴了当前i n t e m e t 上广泛使用的数据流控制方法z i g z a g 算法，并对其进行 了改进，使其能够更好的辅助f - m e a s u r e 算法进行g n u t e l l a 网络的连接管理。实 验数据表明：我们的f - m e a s u r e 算法及其辅助管理手段能够极大地减少消息的冗 余量和极好地适应网络流量的动态变化。 关键词：p 2 p ，g n u t e l l a ，网络模型，多播模型，f - m e a s u r e 算法，缓冲时间 z i g z a g 算法 a b s t r a c t a b s tr a c t p e e r t o - - p e e ri st h ea r c h i t e c t u r eo fn e t w o r kb yd i r e c t l ye x c h a n g i n ga n ds h a r i n g r e s o u , r c e sa n ds e r v i c eo f c o m p u t e r g n u t e l l a a sa t y p i c a lp 2 p n e t w o r kc o m m u n i c a t i o n p r o t o c o l ，c a ni n t e l l i g e n t l yf i n dn o d e s m o r e o v e r i th a s e n t i r e l yd i s t r i b u t e dc h a r a c t e r i t c a l le f f e c t i v e l ya v o i di s o l a t i o nn o d e sb o t t l e n e c ka n dm a k en e t w o r km u c hm o r er o b u s t ， b u ta tt h es a r f l et i m e ，t h eg n u t e l l ap r o t o c o ia l s op r o d u c e se x p o n e n t i a l l yi n c r e a s i n g r e d u n d a n c em e s s a g ea n di t s e f f i c i e n c y i s v e r y l o w i to n l ya p p l yt h el o w - s c a l e n e t w o r ka n di ti sv e r yd i f f i c u l tt or u mt om a i n s t r e a ma p p l i c a t i o n t h ep a d e rs t a r t sf r o mt h eo r i e n t a t i o na m o n g s tt h ec r u n o d e so ft h eg n u t e l l a p r o t o c o la n dp u tf o r w a r dt ot w om o d e l so ft h eo r i e n t a t i o n t h e ya r en e t w o r km o d e l a n dm a l t ib r o a d c a s tm o d e l t h et w om o d e l sb o t hb a s eo nt h ee n t i r e l yd i s t r i b u t e da n d d y n a m i cc h a r a c t e r t h e yc a nf i n dt h en e i g h b o u rn o d e sq u i c k l ya n dg e tt h ec o n n e c t i o n i n f o r m a t i o no ft h en o d e 1 1 1 e p a d e r r e s o l v e st h en e t w o r k m e s s a g e b r o a d c a s t e d m e c h a n i s mo fg n u t e l l ai nd e t a i l ，d i v i d e sp r i o rl e v e lo ft h ef o u rk i n d so f m e s s a g ea n d a n a l y s et h en e c e s s i t ya n df e a s i b i l i t yo fd i s c a r d i n gt h ec o n n e c t i o n w eb r i n g sf o r w a r d f - m e a s u r ea l g o r i t h m a tt h es a m e t i m e ，t a k i n gt h et c p a n dp p pi n t oa c c o u n tw h i c h a r et h eb a s e so ft h eu n d e r l a y e ro fg n u t e l l ap r o t o c o l ，w eu s et h et h o u g h to fd a t af l o w f o rr e f e r e n c ew h i c hi sw i d e l ya p p l i e di nt h ei n t e m e t w em o d i f yt h ez i g - z a g a l g o r i t h m i no r d e rt oh e l pf m e a s u r ea l g o r i t h mm a n a g en e t w o r kc o n n e c t i o n t h ee x p e r i m e n t d a t as h o w st h a to u rf - m e a s u r ea l g o r i t h ma n da s s i s t a n tm a n a g i n gm e a n sc a nh u g e l y d e c r e a s et h ea m o u n to fr e d n n d a n c em e s s a g ea n db e t t e rf i tt l l e d y n a m i cc h a n g eo f n e t w o r kf l u x k e yw o r d s ：p 2 p , g n u t e l l a , n e t w o r km o d e l ，m u l t i b r o a d c a s tm o d e l f m e a s u r e a l g o r i t h m ，b u f f e r - t i m e ，z i g - z a ga l g o r i t h m i i 基于g n u t e l l a 协议的p e e r t o - p e e r 网络连接管理 序吾 p 2 p ( p e e r t o p e e r ) 是通过直接交换共享计算机资源和服务的- - e e 网络体系 结构，它引导网络应用的核心从中央服务器向网络边缘的终端设备扩散。p 2 p 目 前的应用主要集中在对等计算、协同工作、引擎搜索和文件交换上。 g n u t e l l a 是a o l 的n u l l s o f t 部门开发的一个能寻找和下载任何种类计算机 文件的软件。它基于完全分布式的思想，支持点对点的、没有中心的信息搜索。 g n u t e l l a 网络中的节点执行联系服务器和客户端的双重任务，每个客户端都是 服务器，每个服务器又都是客户端。 完全分布式使g n u t e l l a 网络能够很好的消除单点瓶颈，具有很好的健壮性。 但是同时，它也使基于g n u t e l l a 协议的网络难以扩充，因为网络中产生了海量 的冗余消息。芝加哥大学的研究小组对g n u t e l l a 网络进行彻底的研究后发现，它 的基础架构不符合互联网最基本的拓扑学原理，其网络节点是其效率低下的主要 原因。 本文从研究基于g n u t e l l a 协议的节点定位入手，提出了两种有效的节点定位 模型：网络模型和多播模型。这两种模型能够使g n u t e l l a 网络中的节点快捷地找 到其直接相连的邻居节点，从而获取有效的连接信息。我们详细解析了g n u t e l l a 协议的消息广播机制和网络连接机制，在此基础上，提出了f m e a s u r e 算法。在 f - m e a s u r e 算法中，f m e a s u r e 参数代表的是丢弃对应连接，消息仍能够到达网 络中其他结点的比率。根据我们的算法，能够有效的计算出f m e a s u r e 参数值， 进而可以确定丢弃不同连接的代价。但是，考虑到g n u t e l l a 网络中消息的优先级 别，我们需要设立一个缓冲时间，用于接收r e s p o n s e 消息，尽量减少网络的损耗。 对于缓冲时间，我们可以通过网络的连接速率、连接数目、1 v r l 值和缓冲区的大 小等参数来进行有效的计算，从而保证缓冲时间设置的合理性。同时，由于 g n u t e l l a 协议其下层的连接大多是基于t c p 和p p p 协议的，因此，本文还借鉴 了当前i n t e m e t 上广泛使用的数据流控制思想，改进了z i g - z a g 算法，使其能够 更好的辅助f - m e a s u r e 算法进行g n u t e l l a 网络的连接管理。 本文的主要内容共分为六个部分： 第一章是p 2 p 简介。该章简要介绍了p 2 p 的兴起和发展、p 2 p 的主要应用、 p 2 p 的未来和当前p 2 p 亟待解决的问题。 基于g n u t e l l a 协议的p e e r - t o p e e r 网络连接管理 第二章是g n u t e l l a 网络概述。该章主要介绍了g n u t e l l a 协议，g n u e l l a 的消 息机制和g n u t e l l a 网络的基本特征，最后分析了g n u t e u a 网络的效率。 第三章是g n u t e l l a 网络中的节点定位。该章主要提出了用网络模型和多播模 型来进行g n u t e l l a 网络中的节点定位，使网络中的每个节点能够快速地得到其直 接连接信息。 第四章是f m e a s u r e 算法。该章在分析了g n u t e l l a 网络消息机制和g n u t e l l a 网络丢弃连接必要性的基础上，讨论了g n u t e l l a 网络的四种消息的优先级，提出 了f - m e a s u r e 算法，最后给出了一个应用f - m e a s u r e 算法的实例。 第五章是f - m e a s u r e 算法的深入探讨。该章主要讨论了f m e a s u r e 算法的平 衡性，提出了设定缓冲时间和应用改进后的z i g - z a g 算法来辅助f - m e a s u r e 算法 进行基于g n u t e l l a 协议的网络连接管理。 第六章是总结和展望。对我们在本文中所作的工作进行了总结和概括，并提 出了进一步的工作。 基于g n u t e l l a 协议的p e e r - t o - p e e r 网络连接管理 第1 章 p 2 p ，英文p e e r t o p e e r 的缩写， 迅速发展的一种网络体系结构。 1 1 p 2 p 兴起与发展 p 2 p 简介 中译为对等互联或点对点技术，是近年来 p 2 p 的兴起源于n a p s t e r “。n a p s t e r 是由肖恩范宁在1 9 9 9 年设计开发的 用于交流m p 3 文件的软件。n a p s t e r 提供了一种基于全新思想的软件供音乐迷 们在自己的硬盘上共享歌曲文件、搜索其它用户共享的歌曲文件、并可到其它也 使用n a p s t e r 服务的用户硬盘上下载歌曲，然而n a p s t e r 服务器上却没有一首歌 曲。n a p s t e r 虽然在短时间里吸引了5 0 0 0 多万用户，但是最终却因侵犯版权被 五大唱片商推上了被告席。 尽管n a p s t e r 网上音乐共享服务激起了各大唱片公司的愤怒，但是它的成功 与声名鹊起，却宣告了一场互联网界革命的开始p 2 p 。长久以来，人们习惯 了互联网的中心服务模式，即c s 模式。这种模式以服务器为中心，客户向服务 器发送请求，然后服务器回应给客户需要的信息。现今互联网上流行的即是这种 c s 结构，它以一些大的门户网站为中心，不同地域的个人终端通过连接到服务 器上来进行信息的浏览和下载。但是，互联网的本质应该是以用户为中心，所有 的用户都应该是平等的伙伴，相隔万里的用户可以通过直接互联而共享电脑硬盘 上的文件、目录乃至整个硬盘。p 2 p 技术正是第一次让个人计算机和高贵的服务 器平起平坐，让p c 焕发了新的活力。 p 2 p 直接将人们联系起来，让人们通过互联网直接交互，它使得网络上的沟 通更容易、共享和交互更直接，真正地消除了中间商。尽管p 2 p 的无服务器文件 共享技术并非刚刚问世，但近年来因特网的爆炸性发展使这一理念以新的形式出 现，它是互联网整体架构的基础。互联网最基本的协议t c p i p 并没有客户机和 服务器的概念，所有设备都是通讯中平等的一端。所以，p 2 p 使互联网技术返璞 归真，重返“非中心化”，把权力交还给用户。 p 2 p 的广泛使用由n a p s t e r 率先触发，然后是g n u t e l l a “，现在各种各类的 p 2 p 软件风起云涌，国内外目前有很多有一定规模的p 2 p 应用软件，如i c q 、 基于g n u t e l l a 协议的p e e r - i o p e e r 网络连接管理 a o li n s t a n tm e s s e n g e r 、y a h o op a g e r 、微软的m s nm e s s e n g e r 以及o i c q 等都是 流行的p 2 p 应用。和以前在网络上被动接受网络资源相比，从技术角度而言， p 2 p 提供了利用大量闲置资源的机会，能够有效的消除仅用单一资源造成的瓶颈 问题；p 2 p 还提供了方便的资源交换功能，能够利用p 2 p 的分散式计算通过互联 网进行合作创建媒体或软件、在线直接交谈、组建在线社区以及社区节点合作进 行病毒探测和报警等。 p 2 p 引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核心从 中央服务器向网络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、p c 机到p c 机，p c 机到w a p 手机所有网络节点上的设备都可以建立p 2 p 对话。 它使人们在i n t e m e t 上的共享行为被提到了一个更高的层次，使人们以更主动深 刻的方式参与到网络中去。 1 2 p 2 p 当前的主要应用 p 2 p 目前的主要应用体现在大范围的共享和搜索等方面。它能够更好的解决 网络上四大类型的应用：对等计算、协同工作、搜索引擎、文件交换。 ( 1 ) 对等计算 通过众多计算机来完成超级计算机的功能，一直是科学家梦寐以求的事情。 采用p 2 p 技术的对等计算，可以把网络中的众多计算机暂时不用的计算能力 连结起来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理 的行业都可从对等计算中获利，如天气预报、动画制作、基因组的研究等。 有了对等计算之后，就不再需要昂贵的超级计算机了。对等计算的发展本质 上是以p c 机资源的有效利用为根本出发点的，通过网络共享c p u 资源。 ( 2 ) 协同工作 公司机构的日益分散，给员工和客户提供轻松、方便的消息和协作的工具， 变得日益重要。网络的出现，使协同工作成为可能。但传统的w e b 方式实 现，给服务器带来了极大的负担，造成了昂贵的成本支出。p 2 p 技术的出现， 使得互联网上任意两台p c 都可建立实时的联系，建立了这样一个安全、共 4 苎主鱼! ! 型! ! 塑坚盟! ! ! ! ：! ! ：! ! ! ! 塑竺垄堡笪里 一一 享的虚拟空间，人们可以进行各种各样的活动，这些活动可以同时进行，也 可以交互进行。p 2 p 技术可以帮助企业和关键客户，以及合作伙伴之问建立 起一种安全的网上工作联系方式，因此基于p 2 p 技术的协同工作也受到了极 大的重视。 ( 3 ) 搜索引擎 p 2 p 技术的另一个优势是开发出强大的搜索工具。p 2 p 技术使用户能够深度 搜索文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式 和宿主设备的限制，可达到传统目录式搜索引擎( 只能搜索到2 0 一3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有开放的信息资 源) 。 以p 2 p 技术发展的先锋g n u t e l l a 进行的搜索为例：一台p c 上的g n u t e l l a 软 件可将用户的搜索请求同时发给网络上另外l o 台p c ，如果搜索请求未得到 满足，这1 0 台p c 中的每一台都会把该搜索请求转发给另外1 0 台p c ，这 样，搜索范围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台 p c 上的信息资源。可以说，p 2 p 为互联网的信息搜索提供了全新的解决方 案。 ( 4 ) 文件交换 文件交换的需求直接引发了p 2 p 技术热潮。在传统的w e b 方式中，要实现 在某个网站上搜索所需要的文件，然后下载，这种方式的不便之处不言而喻。 电子邮件虽然方便了个人间文件传递问题，但却无法解决大范围的交换。这 也是w e b 的重要缺陷，n a p s t e r 就是在此情况下横空出世，抓住人们对m p 3 喜欢的需求，n a p s t e r 的m p 3 交换直接引发了网络的p 2 p 技术革命。 1 3p 2 p 的未来 p 2 p 在电子商务领域有光明的前景，因为这项技术在直接联系买主与卖主方 面拥有巨大的潜力n 5 3 。 p 2 p 最大的长处是在出售日用品与数字货物方面。如果p 2 p 可以提出有效的 5 基于g n u t e l l a 协议的p e e r - t o p e e r 剧络连接管理 方法，满足消费者获得价格适中的内容的愿望，以及内容制造者与提供者赢利的 愿望，那么p 2 p 可以作为一项商业化的文件共享技术而大获成功。随着人们对 p 2 p 功能越来越多的认识，p 2 p 将成为重要的商业经营模式，因为它能够有效地 利用资源，并减少客户机服务器网络所必需的管理。可以预言，p 2 p 在未来 几年将会成为一项现实可行的商业技术。 然而有一些分析家则认为，p 2 p 不会流行开，因为分散的模式与许多商业联 系模式背道而驰。个人软件分析家t a r t e r 表示，公司喜欢的是分层的计算模式， 该模式应该有准入规则与限制。许多c e o 不愿意使用p 2 p 提供的公司内部准入 模式，因为他们想对某些信息的获取施加限制。此外，p 2 p 要求高标准的带宽， 而这一标准超出了许多公司在联络方面愿意达到的带宽水平，所以p 2 p 的流行 将在客户间而不是公司间。 对于p 2 p 是否足够强大、精致、有效，以至于可以解决复杂的业务问题，我 们还须拭目以待。归根结底，p 2 p 的成功取决于它对企业与个人的价值，如果 p 2 p 能够为客户提供一个独一无二的答案，他们就会采用它，而购买解决方案的 人不会在意这是不是p 2 p 的解决方案。 1 。4p 2 p 亟待解决的问题 虽然p 2 p 是一片充满赢利希望的热土，但为什么多数渴望暴富的投资者面 对p 2 p 的诱惑却踌躇不前呢? 除了他们在经历纳斯达克的风雨洗礼后变得更加 谨慎之外，除了p 2 p 的赢利模式尚处在无法验证的摸索过程以外，p 2 p 本身也存 在着许多亟待克服的困难： ( 1 ) p c 的计算能力 在复杂的p 2 p 应用项目上，使用的个人电脑与工作站需要很强的计算能力， 以便进行联系，并满足安全功能需要的额外开销，而这些原来是由服务器来 处理的。因此，这就要求p c 具有很好的计算能力。 ( 2 ) 安全因素 由于某些p 2 p 应用项目使一些计算机可以进入其它机器的硬盘，因此必须考 6 基于g n u t e l l a 协议的p e e r - t o p e e r 网络连接管理 虑安全因素。从其它机器上下载文件，使系统在抵制病毒方面很脆弱；另一 个关键问题则是：计算机能否验证与其连接的机器身份。然而，真正的安全 问题也许是文化上的。人们对于隐私与安全问题非常关注，一旦意识到某一 技术会导致秘密爆光，就不愿意采用，因此p 2 p 需要一个更加安全的基础结 构，来缓解这样的忧虑，从而带来更广泛的应用”1 。 ( 3 ) 先进的互用技术 与p 2 p 系统连接的计算机会使用各种各样的操作系统、网络技术以及其它平 台，特别是在商业领域。如今的p 2 p 系统只承担相对简单的职能，例如传送 m p 3 音乐文件，聊天，在线直接交谈以及组建在线社区等。因此它们可以 与翻译编排程序、软件包装以及因特网现在使用的其它互用技术兼容。但是， 在未来，p 2 p 可能需要更先进的互用技术以执行更加复杂的任务，这就要求 我们采用更加先进的互用技术。 ( 4 ) 网络带宽 p 2 p 允许用户从电脑上下载大型文件，因此这项技术可能需要大量的带宽， 而这一点可能会为p 2 p 的推广制造障碍。例如，由于非常多的学生收发音乐 文件，以至校园网拥堵，一些大学被追阻断了对n a p s t e r 的连接。要想缓解 上述顾虑，我们需要采用和发展更高水平的宽带网络技术，提高网络带宽。 ( 5 ) 节点定位方法 当前，p 2 p 最大的挑战是如何在一个缺乏中央服务器的计算模式下各自发现 对方。p 2 p 要求同位体可以访问分散的资源，而这些资源往往并没有永久的 地址，因为它们并非总是与因特网连接。因此，p 2 p 需要一个新的找寻i p 地址的程序，来进行节点间的快速定位。 ( 6 ) 版权问题 就像n a p s t e r 的出现冲击着唱片公司的利益一样，大多数p 2 p 服务都将不可 避免地和知识产权发生冲突。尽管美国唱片协会等一些组织在寻找一种新的 基于g n u t e l l a 协议的p e e r - t o - p e e r 网络连接管理 方式来保护知识产权，但是，每一个提供文件共享服务的p 2 p 公司都不得不 认真审视p 2 p 网络面临的版权问题。 ( 7 ) 病毒问题 当前流行的p 2 p 软件对源代码的加密并不可靠，很容易被反向汇编得出源代 码，这些源代码最终像开放源代码软件一样在网上随处可得。这一方面会有 利于人们针对不同的操作系统平台和功能需求重新编译这些程序；另一方 面，一些居心不良的黑客也能借机篡改软件源代码，为将来的不义之举留下 方便之门。尽管这需要一个黑客具备相当的编程经验和技巧，但总能有少数 “专家级”的黑客能随心为之。可以想象，这些系统隐患将来会象瘟疫一样 在黑客组织里扩散传播，成为p 2 p 软件的附骨之蛆。因此，病毒问题也是 p 2 p 广泛应用急需解决的问题之一。 1 5 小结 本章我们主要回顾了p 2 p 的兴起与发展、介绍了p 2 p 当前的主要应用、p 2 p 的未来前景以及p 2 p 要走向大规模商业应用所亟需解决的问题。我f 1 n - i 以从中了 解p 2 p 的发展脉络、发展方向和应用前景，为我们进行p 2 p 的研究和应用开发 奠定基础。 8 苎主鱼! ! 型! ! 堡坚塑! ! ! ! ! ! ：! ! ! ! 旦竺垄堡笪堡一 第2 章g n u t e l i a 网络概述 g n u t e l l a 是一种能够智能发现节点，完全分布式的p 2 p 网络通信协议。其 完全分布式的优点使基于g n u t e l a 协议的p 2 p 软件越来越多，比较典型的有 g n u c l e u s 和b e a r s h a r e 。对于因特网上的任何一台机器，只要运行一个基于 g n u t e l l a 协议的p 2 p 软件，就可以成为g n u t e l l a 网络中的一员。 2 1g n u t e l i a 网络协议 g n u t e l l a 支持传统的c s 查询模式，但是本质上它是p 2 p 的、非中心化的 模型。在这个模型中，每个客户机都是服务器，每个服务器又都是客户机。 g n u t e l l a 网络中的每一个角色既有服务器的功能又有客户机的功能，被称为 s e r v e n t 。s e r v e n t 一方面提供客户机界面使用者借以提交查询请求、浏览 查询结果，同时接收来自其它s e r v e n t 的查询请求、在本地数据集中查找匹配信 息、给出适当的应答。 g n u t e l l a “协议定义了s e r v e n t 在网络上相互通信的方法。它包括一个描述 符集和一个规则集：描述符集用于s e r v e n t 间的数据通信，规则集用于管理 s e r v e n t 间的描述符交换。g n u t e l a 通信协议主要包括五种类型的消息，其类型 和描述如图2 1 所示： 消息种类描述 p i n g用来动态的发现g n u t e l l a 网络中的主机。当一个主机收到一个p i n g 消息后，应该返回一条p o n g 消息作为回应消息。 p o n gp i n g 消息的回应消息。包括已经连接主机的地址以及该主机可以向 网络提供的共享数据的数量信息。 q u e r y分布式g n u t e l a 网络的主要的查询机制。当一个主机收到一个 q u e r y 消息，它将根据消息中的信息搜索本地的数据列表，如果发 现要查询的数据，它需要返回一条回应消息。 q u e r y h i t 是q u e r y 消息的回应消息。包括获取查询到的数据的足够信息。 p u s h 一种允许防火墙内的主机也能够共享自己的文件数据机制。 图2 - 1 ：g n u t e l l a 消息描述图 9 基于g n u t e l l a 协议的p e e 卜t o - p e e r 网络连接管理 在图2 - 1 中p i n g 和p o n g 用于主机的动态发现；q u e r y 和q u e r y h i t 用于数 据查询；p u s h 用于穿越防火墙的主机和文件探测。 g n u t e l l a 协议中的消息主要由两部分组成，即消息头和数据。消息头的格式 如图2 - 2 所示，其描述如图2 3 所示。 p a y b a dp a y l o a d i m e s s a g e i dt t l h o p s d e s c r i p t o rl e n g t h 图2 2g n u t e l a 消息头格式 消息头字段描述 m e s s a g e i d 一个1 6 位的字符串，唯一标识该消息标识符 p a y b a d用来表示该消息的类型。 d e s c r i p t o ro x 0 0 = p i n g 0 x 0 1 = p o n g o x 4 0 = p u s h 0 x 8 0 = q u e r y 0 x 8 1 = q u e r y h i t t t l 描述消息在g n u t e l l a 网络中向前传递的次数。每个客户端在将包 向前传递前将t t l 减一。当t t l 等于0 ，消息将不再被向前传递 h o p s描述消息在g n u t e l l a 网络中向前传递的次数。每个客户端在将包 向前传递前将h o p s 加一。满足关系式t t l ( 0 ) = t t l ( i ) + h o p s ( i ) p a y l o a d负载长度，表示紧接着头部后面的部分的长度。 l e n g t h 图2 - 3g n u t e l l a 消息头描述 g n u t e l l a 网络的查询是泛滥式( f l o o d i n g ) 的，如图2 - 4 所示。即当某一主 机a 提出查询请求时，该主机将把包含查询信息的q u e r y 消息发送给它所有的直 接邻居，它的直接邻居收到该q u e r y 消息后，首先检索本地共享的数据列表，如 果该列表中存在要查询的数据，它将返回一条q u e r y h i t 消息，然后再把该q u e r y 1 0 基于g a u t e l l a 协议的p e e r t o p e e r 网络连接管理 消息发送给它所有的直接邻居；否则，直接将该消息发送给它的直接邻居。 图2 4g n u t e l l a 网络查询图 2 2g n u t e ll a 网络的消息机制 在g n u t e l l a “”协议的查询机制中，主机节点只需简单的将收到的消息向直 接相邻的节点扩散出去。如果不考虑其它的一些因素，那么这种查询机制将会是 一种简单有效的传播机制。但在实际中却行不通，因为如果不加以适当的控制， 那么g n u t e l l a 网络中消息的数量就会呈指数倍数增长，网络的带宽将会被很快 的吞噬掉。为了防止这种灾难性结果的发生，g n u t e l l a 协议采用三种机制来控 制消息数量的指数增长。 机制一：消息生存时间( t t l ) 消息生存时间t t l ( t i m e t o l i v e ) 是指消息在网络中传播时能够生存的时 间。它是包含在消息头中的一个字段，在消息生成时被赋予一个初始值。当消息 被发送出去，其它接收到该消息的主机节点，首先检查它消息头中的t t l 值，如 果为1 ，则不转发该消息。否则，将该消息的t t l 值减1 ，然后再转发给它的邻 居节点。t t l 值越大，消息能传播的距离就越远，反之，就越近。 机制二：消息的唯一标识符( u i d ) 消息的唯一标识符u i d ( u n i q u e l e s s a g ei d e n t i f i c a t i o n ) 是为了避免一个 消息在同一个主机节点重复传播而设计的。u i d 也包含在消息头中，每个不同消 息的标识符都是不一样的。当消息被发送出去，接收到该消息的主机节点，首先 基于g n u t e l l a 协议的p e e r - t o p e e r 网络连接管理 取出它消息头中的u i d 字段，然后同本地记录的u i d 列表相比较，如果该消息的 u i d 已经在列表中，则直接将该消息丢弃掉。否则，该主机节点将这条消息的u i d 存储到本地u i d 列表，然后再将该消息广播出去。 机制三：路经标识符( p i d ) 路径标识符p i d ( p a t hi d e n t i f i c a t i o n ) 是为了防止消息循环出现和使消息 按源路径返回而设置的。路径标识符是一个地址列表，记录了该消息所经过节点 的地址。当一个主机节点接收到一条消息后，首先检查自己的主机地址是否在该 消息的地址列表中，如果在，则该主机节点就将这条消息直接丢弃。否则，将自 己的地址加入该消息的地址列表中，然后再将该消息广播出去。 2 3g n u t e il a 网络的基本特性 基于g n u t e l l a 协议的网络和社会网络很相像，都具有集体性的特点，就像p 2 p 应用软件用户彼此之间随机的相连一样。由于g n u t e l l a 网络具有很高的动态特 性，在这种环境下，即使一个简单的协议也会导致难以预料的复杂的通讯过程。 为此，我们必须很好的理解基于g n u t e l l a 协议的网络拓扑结构。 p 2 p 网络拓扑具有以下特征：小世界特征和幂定律。p 2 p 网络的这些特征可 以用来验证人工生成的网络拓扑能不能代表实际的网络拓扑。 2 3 1 小世界特征 小世界现象：世界上互不相识的两个人之间的距离其实并不远，如果在他们 之间通过朋友关系建一个关系链，那么其中最短的那条并不像人们想象的那么 长，这种现象被称为小世界现象。 对小世界现象进行建模的方法之一就是画一张无向图，图的顶点表示人，图 的边表示两个人相互认识，这种图称为人际关系图。它具有小直径性质，也即是 说它的直径与l o gn 是同一个数量级( n 表示图的大小) 。而且，人际关系图也 表现出高聚集性。聚集性是对一个节点和其所有邻居节点之间相互连接的稠密程 度的度量。高聚集性几乎是人际关系图所固有的，因为如果两个人有共同的朋友 那他们很可能也互相认识。 1 2 基于g n u t e l l a 协议的p e e r t o p e e r 网络连接管理 w a t t s 矛 j s t r o g a t z ”1 就是用小直径性和高聚集性来定义称之为小世界图的那 一类图。w a t t s 和s t r o g a t z 认为很多生物、技术和社会网络都具有小世界特征。 在w e b 超链接图”中，节点表示静态主页，边表示这些主页间的超链接关系。 l e d aa d a m i c 认为w e b 超链接图也是一个小世界图，并说明了如何利用这一特点 改进w e b 搜索引擎的性能。 除了小直径性和高聚集性，很多小世界网络还有其它一些重要的性质。 稀疏性：这类图的边与其大量的顶点相比相对较少。准确地说，在小世界图 中边数更接近于点数，而不是最大可能边数。例如，在著名的好莱坞图中，有1 3 0 亿条边，远小于2 2 5 万个点的完全图中的2 5 0 亿条边。 自组织性：大多数小世界网络并非是精心打造的，而是自然形成的，有其发 展演变的过程。一个好的理论模型必须能反映这一过程的性质，只有这样，才能 产生逼近真实的小世界拓扑结构。 小世界现象最简单的模型是随机图：随机图具有小直径性质，却没有聚集性。 为解决这一问题，w a t t s 和s t r o g a t z 提出了一种对完全规则性和完全随机性进 行折衷的模型。该模型从一种高度规则的环形格拓扑结构开始，把一个圆上n 个 顶点中的每个顶点与其k 个最近的邻居相连( k 是个小整数常量) ，形成一个环 形格。环形格中每一条边都有可能有一个顶点被改变，发生这种改变的可能性为 p ，而新的顶点的选择是完全随机的。这种方法使得拓扑图的设计者可以在完全 规则( p = o ) 和完全无序( p = 1 ) 之问进行调整，从而能够研究中间性质( o p 1 ) 的 拓扑图。由于人们对于中间性质的拓扑图几乎一无所知，因此可以换一个方式看 这种模型的构造过程，开始时构造的环形格表示各顶点的本地联系，在后来的调 整过程中加入了一些远地联系。w a t t s 和s t r o g a t z 发现加入一些这种远地联系 以后，拓扑图的直径会迅速减小，而且原来的环形格的聚集性被保留下来。尽管 w a t t s s t r o g a t z 模型仍然是最流行的小世界模型之一，但是大多数近来的科学 研究都使用由n e w m a n 和s t r o g a t z 提出的该模型的新版本。在这个新的版本中， 不是改变原有的联系( 边) ，而是加入新的联系( 边) 。这样就消除了图的一部 分与其它部分失去联系的可能性，从而大大简化了分析工作。后来，k l e i n b e r g 引入一个参数对该模型进行泛化，从而定义了随机网络的整个家族。k l e i n b e r g 的研究表明，在这个网络模型家族中非中心算法的性能有很大差异，而且存在唯 基于g n u t e u a 协议的p e e r - t o - p e e r 网络连接管理 一一个模型在其上非中心算法是有效的n 2 1 。 2 3 2 幂定律模型 幂定律( p o w e r l a w s ) 3 是指许多大型自组织网络的一些图度量的分布为 y = x 。，其可以定义如下： 幂定律1 ( 秩指数 r a n ke x p o n e n t 拧) ：节点v 的出度d 。正比于它秩的r 次幂， 即：谚一r 8 ( 斤是常数) 。如果把图中所有节点按照 出度大小递减的j 顿序排成一列，那么节点v 的索引值就 是它的秩t 。 幂定律2 ( n 撇 o u t d e g r e ee x p o n e n t 0 ) ：出度d 出现的频率z 正比于出度d g o 次幂：六一d 。( 妫常数) 。 幂定律3 ( 间隔指数 h o p p l o te x p o n e n t ) ：间隔不超过h 的所有节点对的总数 p ( h ) 正比于h 的h 次幂，即p ( h ) 一办”，h 远小于图的直 径万。p ( h ) 是所有间隔不超过h 的节点对的总数：节点 自己形成一对，计算一次；所有其它节点对计算两次。 幂定律4 ( 特征指数 e i g e ne x p o n e n t , $ ，：一个图的特征值兄和序数i 的常数指数 s 成正比，即允一f 5 几个研究小组都在w e b 图中发现了同样的幂定律。由于这些发现是在不同规 模和不同粒度层次的图中得到的，所以只能认为是w e b 图的近似特性或局部特性。 令人特别感兴趣的是，所有研究小组报告的第二个幂定律的指数惊人的一致，都 在2 1 和2 2 2 _ 问。因此，有人建议用幂定律中的指数来划分不同的图系列，并说 明了如何用这些指数来粗略地估计图的重要度量值，如节点数、边数、平均邻居 数和有效直径。a l b e r t ，j e o n g ，和b a r a b a s i 认为幂定律的规模不变性表明：大 型网络具有自组织能力“1 ，能自动形成参数与规模无关的状态，所有现有的随机 图模型都无法预期这一特性。 这些幂定律的重要意义在于：它明确地指出了上面所提到的小世界模型不能 1 4 基于g n u t e l l a 协议的p e e r - t o - p e e r 网络连接管理 体现大型网络的本质特征。主要原因在于这些模型都不能解释幂定律2 的一个简 单结果：图中存在度数很高的节点。幂定律的发现使得人们开始寻找能产生逼真 的网络拓扑模型。 基于以上发现，人们提出了一些模型来产生具有上述幂定律的拓扑图。其中 有些是把幂定律作为经验事实人工再造出来，有些则试图解释这些现象的根源。 一个比较新的例子是由b a r a b a s i 和a l b e r t 提出的模型“1 。b a r a b a s i 和 a l b e r t 认为很多实际网络中的幂定律源于这些网络的两个重要性质：生长的连续 性和添加的有选择性。生长的连续性描述了很多实际网络的动态特性，在这些网 络中不断有新的节点加入。添加的有选择性描述了实际网络中这样的一个事实： 新的节点更可能连接到原节点中度数大的那些节点上，并最终导致所谓的富者越 富的现象。 例如在w e b 链接图中这两个性质是很显然的：每天都有新的网页加入，而 且在新网页中一般都有超链接与一些已经同很多网页相连并因而访问率较高的 网页相连。b a r a b a s i 和a l b e r t 的模型的建立过程如下：首先，图中只有少数几个 顶点，没有边；然后，每次加入一个新顶点，原系统中的m 个顶点与新顶点相连， 每个原顶点与新顶点相连的概率与它的度数成正比。 这个过程产生的图能达到一种稳定状态，在该状态下的图具有在实际网络中 发现的相同的幂定律。注意，如果没有新顶点的不断加入，该模型最终会产生一 个完全图，因为所有顶点最终会全都连在一起。实际上b a r a b a s i 和a l b e r t 已经 证明，对于实际网络行为的正确建模而言，生长的连续性和添加的有选择性都是 必需的：生长的连续性能够确保静态的幂定律；添加的有选择性能够确保其参数 分布的规模无关性。b a r a b a s i - - a l b e r t 模型具有与生俱来的吸引力，尤其是在对 很多基于g n u t e l l a 协议的p 2 p 网络进行建模的时候。 2 3 3 g n u t e l l a 网络特征的意义 以上分析的网络特征可以用来验证人工生成的网络拓扑能不能代表实际的 网络拓扑。同时，这些特征也是精确的构建p 2 p 网络拓扑模型的重要组成部分， 这些特征应该在p 2 p 模型中得到反映。 基于g n u t e l l a 协议的p e e r - t o p e e r 网络连接管理 根据心村中采用的网络爬行者算法对g n u t e l l a 协议的网络拓扑进行的分析， 我们可以知道g n u t e l l a 网络具有小世界和幂定律的性质。这些特性可以被利用来 改进一些算法的性能，如搜索算法。而且，对于构建基于g n u t e l