（计算机软件与理论专业论文）frgnet网络模型及其实现方案.pdf

! ! 翌生塑堡苎型墨基塞翌查鲞y ：6 3 5 2 蔓蛊 摘要 g n u t e l l a 网络是典型的完全无中心的文件共享的p 2 p 网络，近年来发展非常 迅速。但是，g n u t e u a 网络的可扩展性差，大量的冗余消息加重了网络负载，这 些缺陷限制了g n u t e l l a 网络的进一步发展。 本文针对这些缺点提出一种新的p 2 p 网络模型f rg n e t 。与g n u t e l l a 网络 相比，f rg n e t 网络具有良好的可扩展性、减少冗余消息等优点。本文提出了 f rg n e t 的三种实现方案。它们分别给g n u t e l l a 协议附加上一个连接管理子协 议。我们对这些连接管理予协议进行了形式化的描述和验证，并设计模拟程序分 别按照这三种实现方案模拟构造f r _ g n e t 网络：f r _ g n e t a 、f r _ g n e t b 、 f rg n e t c ：并对构造得到的网络进行测试。通过模拟试验发现这三种实现方案 都能提供对于f r _ g n e t 较满意的实现，而且f r _ g n e t - a 、f r _ g n e t b 、 f ro n e t c 的各种参数没有太大的差别。 关键词：p 2 p ，g n u t e l l a ，冗余消息，可扩展性，f r _ g n e t ，u p p 从l ，时间自动机， 自动验证 f rg n e t 网络模型段其实现方案 a b s t r a c t a sa t y p i c a ld e c e n t r a l i z e df i l e - s h a r i n gp 2 pn e t w o r k ，g n u t e l l an e t w o r kh a sb e e n g r o w i n gr a p i d l y i nr e c e n ty e a r s b u ti nt h ep r o c e s so fi t s d e v e l o p m e n t ，g n u t e l l a n e t w o r k sd r a w b a c k sa r e e x p o s e d ：b a ds c a l a b i l i t y , l a r g e n u m b e r so fr e d u n d a n t m e s s a g e s t h e s e d r a w b a c k sa r ei nt h ew a yo fg n u t e l l an e t w o r k w e p r e s e n tan e wp 2 pn e t w o r km o d e l f r _ g n e t c o m p a r e dw i t hg n u t e l l a n e t w o r k ，f r _ g n e th a sb e t t e rs c a l a b i l i t ya n df e w e rr e d u n d a n tm e s s a g e s w ep r e s e n t t h r e ei m p l e m e n t a t i o n so ff r _ g n e t e a c ho ft h e ma d d sak i n do fl i n ka d m i n i s t r a t i o n p r o t o c o lt og n u t e l l ap r o t o c 0 1 w eg i v e s p e c i f i c a t i o n so f t h et h r e ep r o t o c o l s 、i t l lt i m e d a u t o m a t aa n dv e r i f i c a t i o ns o m ep r o p e r t i e so ft h e mw i t hu p f l a a i a f t e rd e m g n i n g s i m u l a t o r sf o rt h et h r e ef r _ g n e t s ( f r _ g n e t - a ，f r _ g n e t - b ，a n df r _ g n e t c ) ，w e u s et h e mt oc r e a t es o m en e t w o r kt o p o l o g i e s ，a n dt h e ng e te x p e r i m e n td a t ab yr u n n i n g t e s tp r o g r a mo nt h en e t w o r kt o p o l o g i e sc r e a t e d t h ee x p e r i m e n td a t as h o w t h a ta l lt h e t h r e e i m p l e m e n t a t i o n s a r es a t i s f a c t o r y , a n dt h e e x p e r i m e n t d a t aa b o u t t h et h r e e i m p l e m e n t a t i o n s h a v el i t t l ed i f f e r e n c e k e y w o r d s ：p 2 p , g n u t e l l a , r e d u n d a n tm e s s a g e ，s c a l a b i l i t y , f r _ g n e t ，u p p a a l ，t i m e d a u t o m a t a , a u t ov e r i f i c a t i o n l i f r _ g n e t 网络模型及其实现方案 第1 章p 2 p 简介 1 1 什么是p 2 p ? 1 9 9 9 年1 8 岁的肖恩范宁( s h a w nf a n n i n g ) 开发出用于交流r a p 3 文件的软 件n a p s t e r 。n a p s t e r 是一种基于全新思想的软件，通过它m p 3 的爱好者们可以共 享自己硬盘上的歌曲文件、直接下载保存在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 技术的关注。 p 2 p 是p e e r t o - p e e r 8 】的缩写，通常指对等网络或技术。在英语中，p e e r 是伙 伴的意思。从字面上理解，p e e r - t o p e e r 是指网络中的各个节点可以直接合作。 网络节点之间的合作其实就是资源的共享。p 2 p 是一种与c s ( n 务器) 完全不 同的资源共享模式【6 i 。因此，在进一步介绍p 2 p 技术之前，需要回顾c s 的资源 共享模式。 在p 2 p 技术兴起之前，限于p c 机的性能，并基于易管理性和安全性考虑， 那些架构在i n t e r n e t 上的软件大多采用了c s 模式的结构，比如浏览器和w e b 服务器，邮件客户端和邮件服务器等。在c s 的共享模式下，能够共享的资源都 集中在服务器上，服务器是资源的提供者，客户机是资源的使用者。图1 1 形象 地描述了c s 的资源共享模式。在这种模式中，服务器处于中心地位，客户机处 于从属的地位。 c 图1 1c s 的资源共享模式 + 表示资源的流向 f r _ g n e t 网络模型及其实现方案 c s 的资源共享模式有易于管理的优点，但是随着i n t e m e t 规模的不断扩大， 其缺点也越来越明显。首先，由于服务器的资源越来越多，不得不配置复杂的数 据库系统，提高服务器的性能和各种配置。其次，尽管服务器的性能已经很高， 仍然难以满足用户的需要。再者，从网络流量的分布来看，服务器成为网络的瓶 颈，服务器周围的网络流量很大，有时甚至会出现堵塞现象。最后也是最重要的 一个问题是，大量的资源散布于网络的边缘节点，不能加以利用。 p 2 p 的资源共享模式是无中心的，如图1 2 所示。所有的节点处于相同的地 位，既可以从其它节点获取资源，也可以为其他节点提供资源，可以共享的网络 资源分布于各个节点上。 卜 表示资源流向 图1 2p 2 p 的资源共享模式 下面的表格显示了p 2 p 与传统的c s 模型统计数据之间的对比 性能p 2 p 模型d s 模型 数据发布好差 数据接收 由 好 数据互动性好差 数据即时性( 传输速度)好差 数据安全性差好 数据更新好差 数据质量( 价值) 由 好 数据覆盖率和数量( 价值)差好 数据成本控制好 差 数据管理方便性差好 2 f rg n e t 网络模型及其实现方案 由上面的统计数据可以看出，p 2 p 模型在数据的互动性、即时性、数据更新 等方面表现很好，但在安全性、管理简易性、数据覆盖率和数量等方面表现不如 c s 模型，这是由于p 2 p 模型的特征造成的，是必然的。 简单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使 得网络上的沟通变得容易、更直接，真正地消除了中间商。每个人可以直接连接 到其他用户的计算机交换文件，而不是像过去那样连接到服务器去浏览与下载。 p 2 p 另一个重要特点是改变互联网以大网站为中心的状态、重返“非中心化”，并 把权力交还给用户。 虽然，p 2 p 近年来才刚刚兴起并得到广泛关注，却不是新概念。p 2 p 是互联 网整体架构的基础。互联网最基本的协议t c p p 并没有节点和服务器的概念， 所有的设备都是通讯的平等的一端。在十年前，所有的互联网上的系统都同时具 有服务器和节点的功能。当然，后来发展的那些架构在t c p i p 之上的软件的确 采用了节点朋匣务器的结构：浏览器和w e b 服务器，邮件客户端和邮件服务器。 但是，对于服务器来说，它们之间仍然是对等联网的。以e - m a i l 为例，互联网 上并没有一个巨大的、惟一的邮件服务器来处理所有的e m a i l ，而是对等联网的 邮件服务器相互协作把e - m a i l 传送到相应的服务器上去。另外，用户之间e m a i l 则一直是对等的联络渠道。 这里我们借用i b m 为p 2 p 下的定义来系统地解释什么是p 2 p ：p 2 p 系统由 若干互联协作的计算机构成，且至少具有如下特征之一：系统依存于边缘设备的 主动协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中的成 员同时扮演服务器与客户端的角色；系统的用户能够意识到彼此的存在，构成一 个虚拟或实际的群体。 1 2p 2 p 系统的分类 对p 2 p 系统进行分类的方法主要有：( 1 ) 根据系统中共享资源的种类进行分 类；( 2 ) 根据系统非中心化的程度进行分类。 根据系统中共享资源的种类可以把目前已经出现的p 2 p 系统分为即时通信 系统，文件共享系统，协同计算系统。常用的即时通信系统有i c q 、a o l i n s t a n t 3 f r g n e t 网络模型及其实现方案 m 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 。它们允许 用户互相沟通和交换信息、交换文件。这类系统共享的主要是网络节点的网络通 信资源。这些网络节点都处于i n t e r n e t 中，本来具有相互访问的能力。在c s 共 享模式下( 如邮件系统中) ，这种资源被闲置起来，各节点都通过服务器( 如邮 件服务器) 进行交流。而在即时通信系统中这种通信资源被重新利用起来。 常见的文件共享系统有很多，这类系统发展很快。从引起p 2 p 研究热潮的 n a p s t e r ，到完全无中心的g n u t e l l a 及其各个变种以及同样是完全无中心的 f r e e n e t ，再到号称第三代p 2 p 系统的b t ，都是以文件为主要共享资源的。 协同计算系统主要共享网络节点的计算资源( 即c p u 资源) 。d i s t r i b u t e n e t 和s e t i h o m e 就属于这类p 2 p 系统。 根据系统非中心化的程度可以把目前已经出现的p 2 p 系统分为完全无中心 的p 2 p 系统和混合式的p 2 p 系统。完全无中心的p 2 p 系统中所有节点的角色完 全相同，没有一个在资源共享中处于特殊地位的节点。g n u t e l l a 和f r e e n e t 就是 这类系统。图1 _ 3 中是一个完全无中心的p 2 p 网络。图中的连接是虚拟的逻辑的， 也是双向的，主要用于发现网络中的节点的地址信息和资源所在的位置。这类系 统的优点是容错能力强，不存在网络瓶颈，某个节点的失败不会对整个网络产生 重大影响。 图1 3 一个完全无中心的p 2 p 网络 图1 4 中是一个混合式的p 2 p 系统。在混合式的p 2 p 系统中，各节点之间可 以直接建立连接，但是需要借助服务器来构建网络，建立索引机制。然而这里的 4 f r _ g n e t 网络模型及其实现方案 服务器仅用于辅助对等节点之间建立连接，一旦连接成功，服务器不再起作用， 对等节点之间直接进行通信。这不同于p 2 p 模式中的服务器，也可以认为是弱 化了服务器的作用。这种p 2 p 网络模型和完全无中心的网络相比，易于发现网 络节点、易于管理且安全性较好，但也有类似c s 模式的缺陷，如容错能力差 等。n a p s t e r 以及大部分的即时通信系统是典型的混合式的p 2 p 系统。 + + 表示节点地址信息和资源索引信息的交换 i d a 表示资源流动 图1 4 一个混合式p 2 p 网络 当然，还有其他的分类方法，这里不一一介绍了。本文的研究对象g n u t e l l a 网络是一种完全无中心的文件共享网络。 1 3p 2 p 网络面临的技术方面的问题 p 2 p 网络的发展面临着各种各样的问题【1 9 】，这些问题既有社会方面的，如 版权i a - j 题，也有技术方面的问题。社会方面的问题需要社会各方面的智慧去解决。 这里主要介绍p 2 p 网络面临的各种技术方面的问题。 ( 1 ) 管理困难 p 2 p 网络的精髓在于其“乌托邦”式的管理方式，这种方式给了用户更多的 自由，但是这也陷入了“无政府主义”的匿境。可以想象，缺乏管理的p 2 p 网 5 f p g n e t 网络模型及其实现方案 络将会成为病毒、色情内容以及非法交易的温床。许多p 2 p 公司打算通过p 2 p 网络开展电子商务，但是付费问题、流量计算、商品价值的验证等等都是一时很 难克服的困难。 ( 2 ) 垃圾信息 由于p 2 p 网络的用户众多，当某个用户进行搜索时，自然会得到大量的搜 索结果。而除了少数有用的信息以外，其它大多数的信息可能都属于垃圾信息。 在缺乏统一的管理的情况下，p 2 p 网络很难对按索结果进行排序，用户将不可避 免地陷入垃圾信息的汪洋大海。现在已经有公司尝试着将人工智能技术、专家数 据库技术引入p 2 p 网络中，希望能够克服垃圾信息的困扰。 ( 3 ) 吞噬网络带宽 p 2 p 使网络变得空前活跃，大多数用户愿意利用p 2 p 网络在计算机之间传 送文件，这将大量吞噬网络带宽，特别是在大多数用户更喜欢传送大体积的m p 3 文件、视频文件的时候，这个问题更加不容忽视。 ( 4 ) 安全问题 安全问题永远能跟上互联网的发展节奏。像美国在线的“即时信使”和眼下 的几种p 2 p 软件对源代码的加密并不可靠，很容易就会被反向汇编得出源代码， 这些源代码最终像开放源代码软件一样在网上随处可得。这一方面会有利于人们 针对不同的操作系统平台和功能需求重新编译这些程序。另一方面，一些居心不 良的黑客也能借机篡改软件源代码，为将来的不义之举留下方便之门。尽管这需 要一个黑客具备相当的编程经验和技巧，但总能有少数“专家级”的黑客能随心 为之。 由于p 2 p 技术在对等计算、协同工作方面的强大优势，今后肯定会在这两 个方面迅猛发展；将p 2 p 技术和c s 模式的互联网结合起来，在搜索引擎、文 件共享方面国内外已经有不少商业化产品投入使用。 6 f rg n e t 网络模型及其实现方案 第2 章 g n u t e ii a 网络简介 2 1 g n u t e l l a 协议简介 g n u t e l l a 协议”。_ 5 ”主要包括三部分：第一部分规定节点( s e r v e n t ) 如何同网络 中其他节点建立连接；第二部分规定消息的格式、作用及节点接收到该消息时的 响应：第三部分规定消息在网络中的传播机制。 一个节点要加入g n u t e l l a 网络必须同某个已经加入网络中的节点建立 g n u t e l l a 连接。协议没有规定尚未加入网络的节点如何寻找已经加入网络的节点。 通常的办法是，节点维护一个节点列表( h o s tc a c h e ) ，该表中存放着一些节点的 i p 地址和端口号。节点依次尝试同表中的节点建立g n u t e l l a 连接。加入网络以后， 节点可以使用p i n g 消息探查网络中有哪些的节点，可以更新它的节点列表。同 时，每个节点维护n 个连接，若连接数目少于n 个，它会尝试建立新的连接。因 此，g n u t e l l a 网络拓扑结构有其随机性的一面。 g n u t e l l a 协议的消息都有一个消息头，熏要数据都保存在消息头中。消息头 的格式定义如图2 1 所示： m e s s a g ei d d e s 蔷p l o r m h o p s l ：蔷h 图2 1 g n u t e l l a 消息的消息 m e s s a g ei d ：一个1 6 位的字串，唯一标识了一个消息。 p a y l o a dd e s c r i p t o r ：定义了消息的类型，不同的值代表了不同的消息类 型。 1 l ：消息生存时间，描述消息在g n u t e l l a 网络中向前传递的h o p 数。 每个客户端在将消息向前传递前将1 几减1 。当t t l 等于0 ，消息将不再 被向前传递。 h o p s ：消息被向前传递的次数。作为一个消息向前传递，头部的t r l 和h o p s 字必须满足条件：盯u o ) = i t l ( i ) + h o p s ( i ) 。 p a y l o a dl e n g t h ：负载长度，表示紧接着头部后面的数据部分的长度。 7 f r _ g n e t 网络模型及其实现方案 g n u t e l l a 协议有五种消息类型：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 。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 用于允许 防火墙中的客户端向网络提供基于文件的数据文件的机制。这五种消息类型的 p a y l o a dd e s c r i p t o r 分配如表2 1 所示。消息头中p a y l o a dd e s c r i p t o r 占8 个二进制 位，为g n u t e l l a 协议的扩展留下了空间。 表2 1 g n u t e l l a 协议的5 类消息 消息类p a v l o a d 型 d e s c r i p t o r 描述 用来动态的发现g n u t e l l a 网络中的主机。当一个主机收 到一个p i n g 消息后，应该源路返回一条p o n g 消息作为 p i n g 0 x 0 0回应消息。 p i n g 消息的回应消息。包括已经连接主机的地址以及该 p o n g o x 0 1主机可以向网络提供的共享数据的数量的信息。 分布式g n u t e l l a 网络的主要的查询机制。当一个主机收 到一个q u e r y 消息，它将根据消息中的信息搜索本地的 数据列表，如果发现匹配数据，它需要源路返回一条回 q u e r y 0 x 4 0应消息。 是q u e r y 消息的回应消息。包括了获取查询到的数据的 q u e r y h i t o x 8 0足够的信息。 一种允许防火墙内的主机也能够共享自己的文件数据 p u s ho x 8 1的机制。 g n u t e l l a 网络采用洪泛式消息广播机制在网络中传播查询消息( 包括p i n g 消 息和q u e r y 消息) ，即：节点把其自身产生的查询消息发给它所有的直接邻居： 节点收到查询消息后，首先检查是否以前已经收到过该消息，如果不是首次收到 该消息，就把它丢弃；如果是首次收到该消息，就把消息的m 值减1 ，把消息的 h o p s 值增加1 ，如果减1 后消息的n l 值为0 ，则把该消息丢弃，否则，将该消息 转发绘它的所有直接邻居( 把该消息传送过来的那个直接邻居除外) 。 8 f rg n e t 网络模型及其实现方案 2 2g n u t e l l a 网络的优缺点 2 2 1 g n u t e l l a 网络的优点 1 丰富的信息资源 任何g n u t e l l a 网络用户能够扫描活动节点并搜索需要的信息，然后直接从这 个节点上下载信息。用户可以在他们的机器上把下载的信息共享出来，这样，请 求率高的文件能够很快地在许多节点上扩散开来，g n u t e l l a 网络因此能够很快积 累相当丰富的信息。 2 容错和鲁棒性 g n u t e l l a 网络采用f l o o d i n g 机制传播查询消息，即使随时有节点离开网络， 整个网络仍然能够正常运行，不会出现单点失效问题。 3 基于内容的寻址 在w e b 上，u r l 地址并不能直接反映出它们的内容。但在g n u t e l l a 网络 中，存储特定信息的节点地址对于用户是透明的，用户向网络提交查询请求时， 请求信息中便包括需要查询的信息，g n u t e l l a 软件把请求转化成存放这些信息的 节点地址，这更易于信息资源的查找。 2 2 2 g n u t e l l a 网络之不足 1 网络中对等点的查找和定位比较复杂 g n u t e l l a 网络中对等点的查找和定位是通过f l o o d i n g 机制来实现，因此与集 中式的n a p s t e r 模式相比，较为复杂1 1 7 j s l 。 2 网络的可扩展性不好 随着网络规模的扩大，通过f l o o d i n g 机制定位对等点的方法将造成网络流量 急剧增加，从而导致网络拥塞【1 ，2 】。根据a i p 2 公司最近的一项研究显示，5 6 k 调制解调器用户在一秒之内最多处理2 0 个查询消息。当网络节点个数超过1 0 0 0 以后，这个处理极限很轻易地就被突破了，随着这部分节点的失效，将会导致 c m u t e l l a 网络被分解，从而使得查询访问只能在网络的很小的一部分进行。 3 安全性不高 g n u t e l l a 网络如同其它p 2 p 网络面临的问题一样，易遭受恶意攻击，如攻击 者发送垃圾查询信息，造成网络拥塞等。 4 吞噬网络带宽 9 f rg n e t 网络模型及其实现方案 g n u t e l l a 网络通过f l o o d i n g 机制来进行网络节点的定位和文件的查找，使得 网络中充斥着大量的冗余消息。这些冗余消息不仅是导致g n u t e l l a 网络的可扩展 性差的重要因素，而且也加重了网络的负载。 f r _ g n e t 网络模型及其实现方案 第3 章f r _ g n e t 网络模型及其实现 3 1f rg n e t 网络模型 g n u t e l l a 协议的洪泛式( f l o o d i n g ) 广播机制的最大问题是导致冗余消息的 产生。当节点接收到同一个查询消息的多个副本时，除了在第一次收到该消息时 进行广播外，对后到达的几个副本仅做抛弃处理。因此，我们说后至u 达的几个消 息副本都是冗余消息。显然，冗余消息的存在是对网络资源的虚耗。下面我们从 实例入手介绍冗余消息的产生。 一src d e s t 图3 。1 冗余消息的成因 图3 1 所示是一个冗余消息的产生过程。节点s r c 把一个消息同时发给它的 两个直接相邻节点a 和b ，节点a 和b 分别在接收到该消息时，向节点d e s t 转发 该消息，最后节点d e s t 接收到该消息的两个副本，其中后到达的那个就是冗余 的。可以看出，产生冗余消息的原因在于网络中存在环形路径。如果节点s i c 和 节点d e s t 之间没有环路，那么节点d e s t 就不会收到源于节点s r g 的冗余消息。 图3 2 短路效应 目前的g n u t e l l a 网络冗余消息的影响非常严重。不仅增加了网络的负担， f r _ g n e t 匝络模型及其实现方案 而且会引起短路效应( s h o r t c i r c u i t i n g ) 。下面给出一个实例简要介绍短路效应及 其成因。图3 2 中的节点a 发出一个查询消息m ，并指定t t l 值为4 。我们用m l 表示该消息的经由路径1 的副本，用m 2 表示该消息的经由路径2 的副本。如果 m l 先到达节点b ，那么节点d 能够接收到消息m 。但是如果m 2 先到达节点b ， 那么，当m l 到达节点b 时被作为冗余消息丢弃，而m 2 到达节点c 时也会因 为t t l 值被减到1 而不能被转发到节点d ，这样节点d 就不能接收到消息m 。这 种情况会导致消息i t i 的可达性减小，即引起了短路效应。f l o 深入研究了短路效 应对查询可达性( r e a c h a b i l i t y ) 的影响，并给出了实验数据，其中一项试验的结 果是短路效应导致查询可达性平均下降5 5 。 短路效应的成因在于冗余消息的存在和网络传输延迟的差异。如果消除了 冗余消息，也就不可能产生短路效应。所以，我们从消除冗余消息入手，解决短 路效应问题。下面我们分析消除冗余消息的必要条件，从而为解决该问题找到理 论依据。 为了找到消除冗余消息的必要条件，我们首先假设网络中所有节点发出的 消息都把t t l 值指定为同一个值t r l 。实际上，所有g n u t e l l a 的实现都为t t l 给定 了一个缺省值，而且用户很少改动t t l 值。 图3 3g n u t e l l a 网络中的一条环 引理1 ：设g n u t e l l a 网络中有两个节点s t c 和d e s t ，从节点s r c 发出t t l 值为 t t l 的消息m ，节点d e s t 接收到了消息m 的多个副本( 即收到冗余消息) ，则节 点s r c 和d e s t 之间必定存在周长不大于2 + 1 1 l 的环路。 证明：采用反证法容易证明该定理。 假设节点s r c 和d e s t 之间存在一个由路径p a t h l 和p a t h 2 组成的环路( 如图 3 3 所示1 ，节点d e s t 接收到分别从路径p a t h l 和p a t h 2 到达的消息m 的副本，但 f rg n e t 网络模型及其实现方案 是该环路的周长大于2 4 t 1 乙。用l 1 表示路径p a t h l 的长度( 即h o p 数) ，用l 2 表示路径p a t h 2 的长度。该环路的周长为u + l 2 。 节点d e s t 接收到从路径p a t h l 到达的消息m 的副本，根据g n u t e l l a 网络的 消息广播机制可以推断：l 1 s t r l 。同理，可以推断：l 2 - c 1 几。所以有u + l 2s 2 + t t l 。 出现矛盾。 从引理1 可以得出如下结论：对于一个周长不大于2 + 1 阻的环路，如果环 路上的某个节点发出一个t t l 值为t r l 的消息，则该环路上必定有一个节点接收 到该消息的冗余消息。因此，我们称周长不大于2 + 1 几的环路为r _ t r l 环，b 口 t t l 值为1 l 的消息在该环路上必定能产生冗余消息( r e d u n d a n tm e s s a g e s ) 。图 3 2 中节点a 和节点b 之间形成一个i l 3 环，也就是说，环上的任意节点如果广 播一个t t l 值为3 的查询消息，该环上必定会有一个节点接收到该消息的冗余消 息。 定理1 ( 冗余定理) ：设若g n u t e l l a 网络中消息的t 值不大于t r l ，如果 网络中不存在rt r l 环，则网络中不会出现冗余消息。 冗余定理告诉我们要想消除网络中的冗余消息，必须消除网络中的带来冗 余消息的环( 即r _ t i l 环) 。 根据冗余定理，没有r - t 1 l 环的g n u t e l l a 网络中不存在冗余消息，即f r e e o fr e d u n d a n tm e s s a g e s 。因此，我们用f r _ g n e t 表示不存在r _ i r l 环的g n u t e l l a 网络。f rg n e t 是一种改进的g n u t e u a 网络。 3 2 f r _ g n e t 网络模型的几种实现方案 g n u t e l l a 网络具有高度的动态性，各节点可以自由地加入或退出，因此要建 立理想的f r _ g n e t 是很难做到的。本文给出f r _ g n e t 的三种实现方案。这三种 实现方案都只对g n u t e l l a 协议加以扩充，附加用于管理节点连接的机制，相当于 提出三种连接管理子协议。本章的相应章节分别对这三种方案进行描述和解释， 并定义了一些新的消息类型。下一章我们给出这些连接管理子协议的形式化描 述，并加以验证。 3 2 1 回顾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 r _ g n e t 网络模型及其实现方案 需要加入或退出网络。网络就在节点的不断加入、不断离开之中灵活地变化、演 进，它的规模也随之不断变化。因此，我们从单个节点的角度回顾一下它与网络 的相互作用。 当在一个计算机上安装一个实现g n u t e l l a 协议的软件的时候，这台计算机就 成为g n u t e l l a 网络的一个节点。在安装软件中会记录某些的m 地址和端口号。 这些节点一般情况下会一直在g n u t e l l a 网络中，称为s e e d 。在安装过程中，安装 软件会同这些s e e d 建立g n u t e l l a 连接，然后发出p i n g 消息，并根据接收到的 p o n g 消息更新自己的h o s t c a c h e 。以后节点加入网络时，为了减轻s e e d 的负担 不再同s e e d 建立连接，而是依次尝试同h o s t c a c h e 中记录的节点建立连接。同网 络中的某个节点建立了连接以后，它就已经处于g n u t e l l a 网络中了。加入g n u t e l l a 网络以后，节点能通过发出p i n g 消息来探知网络中的其他节点。节点把得到的 其他节点的地址信息记录在h o s t c a c h e 中，以备建立新的连接。节点通常维护若 干个连接，如果连接数目不够，它会主动建立新的连接或接受别的节点的建立连 接的请求，如果连接数目已满，则不会建立新连接。离开网络时仅仅把它的所有 g n u t e l l a 连接断开即可，不需要跟任何节点协商，也不需要通知网络中的任何节 点。 建立g n u t e l l a 连接的过程如图3 4 所示。图中的c n 表示发出的t c p 包的内 容是g n u t e l l ac o n n e c t n n ，要求同接收方 建立g n u t e l l a 连接；c n 表示发出的t c p 包的内容是g n u t e l l a o l ( 、n n ，同意 对方的建立g n u t e l l a 连接的请求。图中的0 k 表示节点n l 向节点n 2 发出一个建 立g n u t e l l a 连接的请求，节点n 2 的连接数目不足，所以它接受了该请求，从而， 一个新的g n u t e l l a 连接建立起来。 图3 4 建立g n u t e l l a 连接的过程 1 4 f rg n e t 网络模型及其实现方案 g n u t e l l a 网络的构建机制包括s e e d 、h o s t c a c h e 、g n u t e l l a 连接的建立过程和 收集网络节点信息的p i n g p o n g 消息。为了实现f rg n e t 而提出的这几种方案 中，上述机制都继承了下来，都只是增加了一些新的机制。 3 2 2 实现方案a - - - 后馈式f r _ g n e t 网络 第一种实现方案是后馈式的，其设计思想是：当已经加入c m 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 连接，即依次尝试同h o s t c a c h e 中记录的节点建立一个 g n u t e l l a 连接，有时可能需要发出p i n g 消息探知网络中的节点以补充h o s t c a c h e ； 新的g n u t e l l a 连接建立以后，有可能导致网络中出现r _ t r l 环。因此需要检查 网络中是否出现了r _ t r l 环，如果有r j t l 乙环出现就断开该环。简而言之，就 是先建立g n u t e l l a 连接，随后进行检查，若有r _ t r l 环出现，就进行纠正。 这一方案的设计涉及以下几个润题： ( 1 ) 如果新建连接是节点的唯一一条连接，则不必对它进行检查。因为这 种节点不会出现在环路上，更不可能使得网络出现rr r l 环。因此，仅当连接 数目大于1 时才需要进行检查。 ( 2 ) 节点已经加入网络后再建立一条新连接，网络中可能因为该连接的建 立而出现多个rt t l 环。显然，应该由建立这条连接的节点把它断开，从而同 时断开由于这条连接的建立两产生的所有r l 环， ( 3 ) 条连接的建立涉及两个节点，这两个节点分别对该连接进行检查的 结果是一样的。因为从rt r l 环上任意一个节点都能发现该r _ t r l 环的存在。 所以，我们规定由要求建立该连接的节点负责对该连接进行检查。 ( 4 ) 根据冗余定理，如果忽略网络的动态性，网络中出现冗余消息就意味 着网络中出现了r1 l 环。一种非常直接的方法是，当节点建立一个新的连接 后，向网络中发出一条消息，如果网络中某个节点接收到该消息的多个副本时， 就可以断定网络中出现了r1 t l 环。 ( 5 ) g n u t e l l a 协议定义的5 种消息中，只有p i n g 消息和q u e r y 消息是 按照f l o o d i n g 机制传播的，因此也只有这两种消息可能出现冗余。但是，不能利 用p i n g 消息来探测网络中的r j 广r l 环，因为p i n g 消息的任务是探知网络中 的节点信息，当网络中的节点接收到p i n g 消息时会源路返回一个p o n g 消息( 在 f rg n e t 网络模型及其实现方案 p a y l o a d 中附上自己的i p 地址和端口号) ，并且按照转发该p i n g 消息，如果让 p i n g 消息再肩负探测网络中的r 1 阻环的任务，则发出p i n g 消息以探测网络 中是否存在r _ t t l 环的节点将收到大量的p o n g 消息，这不仅增加了网络负载， 而且占用了网络节点大量的资源。类似的道理，也不能利用q u e r y 消息来探测 网络中的rt t l 环。 因此，我们为g n u t e l l a 协议增加了种专门用于探测网络中是否存在r1 y l 乙 环的消息，称为h e l l o 消息。h e l l o 消息按照f l o o d i n g 机制在网络中传播。 假设节点n 建立了一个新的连接，然后向它的所有连接发出个h e l l o 消 息( 它们的消息i d 相同，t l l 域设为t t l ) 。当某个节点发现网络中出现了r _ t t l 环，它就应该通知节点n 把它新建的连接断开。因此，我们又为g n u t e l l a 协议 增加了一种消息，称为b a d 消息。b a d 消息按照源路返回机制回到发出相应的 h e l l o 消息的节点。h e l l o 消息和b a d 消息的消息头分别如图3 5 和图3 6 所示，h e l l o 消息的p a y l o a dd e s c r i p t o r 为0 x 0 2 ，b a d 消息的p a y l o a dd e s c r i p t o r 为0 x 0 3 。 p a y ) o a op a y l o a d m e s s a g ei d d e s c r i p t o r t i h o p sl e n g t h 1 51 61 71 82 2 图3 5h e l l o 消息的消息 p a y l o a dp a y l o a d m e s s a g e i d d e s c r i p t o r t t l h o p s l e n g t h 图3 6b a d 消息的消息头 由于h e l l o 消息在网络中按照f l o o d i n g 机制传播，我们不能预先知道有没 有或者有多少b a d 消息返回。因此，在发出h e l l o 消息以后，如果在一段时 间w a i tt i m e 之内没有b a d 消息返回，就不再等待，立即根据需要再建立一条 新的连接。因为发出的髓l l o 消息的t 1 1 值设为t 1 l 所以正常情况下如果有 b a d 消息返回，必定在h e l l o 消息发出后的2 + 1 f 1 儿* m a x _ d e l a y 时间之内回到， 其中m a x _ d e l a y 表示两个节点间的最大时延。这段时间w a i u i m e 应该设置为 1 6 f r _ g n e t 网络模型及其实现方案 2 8 t r l * m a x _ d e l a y 。 但是，例外情况即有b a d 消息在h e l l o 消息发出后的2 * t r l * m a xd e l a v 时间之后才回到也是有可能发生的。如果节点r l 发出h e l l o 消息后，接收到 针对它以前发出的h e l l o 消息而返回的b a d 消息，那么它断开刚剐建立的连 接是不合理的。因此，应该对h e l l o 消息加以区分。可以在h e l l o 消息的 p a y l o a d 域记录要检查的新建连接的信息该连接所连的节点的碑地址。网络中 的节点接收到冗余的h e l l o 消息时，要返回一条b a d 消息。它把用h e l l o 消息的p a y l o a d 域的数据填充b a d 消息的p a y l o a d 域。 图3 7 说明如何使用h e l l o 消息和b a d 消息发现r _ t t l 环并通知导致该 rt r l 环出现的节点。图中的c m u t e l l a 网络设定1 ；3 ，虚线段表示节点d 建 立的新连接。在该新连接建立之前，该网络是个f rg n e t 网络。节点d 在建 立该新连接后，广播一个t t l 值为3 的h e l l o 消息。该h e l l o 消息到达节点b 和节点c 时停止向前传播，因为t t l 已经减小到o ；然而，当该h e l l o 消息到达 节点a 时，节点a 发现出现冗余，从而断定网络中出现r _ 3 环，并沿源路返回 一个b a d 消息( 如图中的虚线箭头所示) 。节点d 在接受到b a d 消息后应该丢 弃刚刚建立的新连接，并再次开始建立新连接的尝试。 b 图3 7h e l l o 和b a d 消息的路由 按照本方案规定的网络构建机制动态构建的网络并不是理想的f rg n e t ，因 为g n u t e l l a 网络是高度动态的，网络节点的加入和离开是随意的，从f r _ t t l 环 的出现到断开需要一段时间，从整个网络的角度看在任意时刻网络中可能存在着 1 7 f r g n e t 网络模型及其实现方案 一定数量的f r _ 1 t l 环。从这个考虑出发，我们又提出了第二种实现方案，希望 建立的新连接尽量避免引入f rt r l 环。 3 2 3 实现方案b - - - 前馈式f r _ g n e t 网络 第二种实现方案是前馈式的，其设计思想是：当节点n 加入g n u t e l l a 网络 以后，它首先寻找网络中h o p 距离较大的节点n 7 ，如果n7 的连接数目不足， 它们就可以建立一条g n u t e l l a 连接。 这一方案的关键是如何找到这种远距离的节点。我们为g n u t e l l a 增加一种称 为y e l l 的消息，专门用于这种任务。l l 消息的消息头格式如图3 8 所示。 y e l l 消息发出时t t l 域设为3 + r r l ，p a y l o a d 域记录发出节点的i p 地址和端口号。 它在网络中按照f l o o d i n g 机制进行传播。 p a