（计算机应用技术专业论文）p2p网络的信任模型和激励机制研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着计算机网络的迅猛发展，i n t e r n e t 边缘上汇集了成千上万的计算资源、数据资源。 传统的基于c l i e n t s e r v e r 结构的资源共享方式已经不能满足人们的新需求。人们希望利 用p 2 p 网络技术把物理互连设备的计算资源、存储资源以及网络带宽等聚集起来，以实现 资源共享、协同工作和联合计算。p 2 p 网络使节点以更自由、更主动的方式加入和离开网 络，共享信息资源。p 2 p 技术给我们带来的不仅是机遇，还有挑战，因为p 2 p 网络中恶意 节点的存在，使得网络中出现的各种攻击成为威胁网络正常运作的主要因素。因此，如何 在p 2 p 网络中识别出恶意节点，约束和杜绝恶意节点的恶意行为成为目前的一个热点，其 中对节点的信誉值的研究越来越引起大家的关注。因为双方是否信任对方是双方进行交易 的前提，信誉值可以用来表示这个节点以往的行为是否适合参与某个网络社区的生活。同 时，p 2 p 网络因为建立在传统的网络之上并具有分布式非集中控制的特点，都使p 2 p 网络 的发展面临着安全机制和激励机制这两个亟待解决的问题。 本文在分析研究传统信任模型的基础上，结合近两年最热门的网络架构方式，建立了 一种新的带激励机制的p 2 p 网络信任模型。在该模型中，首先参考社会学的人际关系信任 模型，在p 2 p 网络中建立信任推荐机制，并利用d s 理论对推荐证据进行综合处理，给出 了信任模型中信任值的具体算法和实现算法。其次借助经济学中博弈理论对p 2 p 网络中的 参与者之间的交互行为进行分析，提出了一种基于差异服务质量的激励方案。 将本文带激励机制的信任模型与现有的全局信任模型e i g e n r e p 用仿真实验进行了比 较。通过分析，可以看到该模型对于冒名、协同作弊以及诋毁等行为有较好的抑制作用。 结果证明，当网络中恶意节点上升到一定比例后，本文模型仍然能保持较高的下载成功率， 本文基于推荐的信任模型具有较好的准确性、安全性和实用性。 关键词：p 2 p 网络，拓扑结构，信任模型，激励机制 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fn e t w o r k ，m i l l i o n so fc o m p u t i n ga n dd a t a r e s o u r c e sh a v e c o n v e r g e di ni n t e r a c te d g e t r a d i t i o n a lr e s o u r c es h a r i n gb a s e d o nc l i e n t s e r v e rm o d ec 黜o t s a t i s f yp e o p l e ，sn e e d s b yt h ep e e r - t o - p e e rt e c h n o l o g y ，i t i sh o p e dt h a tc o m p 施n gc a p a c i t i e sa n d m e m o r yc a p a c i t i e so ft h ei n t e r c o n n e c t i n gn e t w o r kd e v i c e sc a l la g g r e g a t et o g e t h e r t or e a l l z et h e r e s o u r c es h 撕n g ，c o o p e r a t i v ew o r ka n dj o i n tc o m p u t i n g i n t h ep e e r - t o p e e rn e t w o r kn o d e sc a n j o i na n dl e a v ef r e e i ya n da c t i v e l y t h ep e e r - t o - p e e rt e c h n o l o g yb r i n g s u sb o t ho p p o r t u m t l e sa n d t l l r e a t s h o wt oi d e n t i f y ， r e s t r i c ta n dp u te n dt ot h o s ev i c i o u sp e e r si sb e c o m i n gah o t s p o t ，a n d 恤r e s e a r c ho np e e r sf e p 似i o nh a sb r o u g h tm o r ea n dm o r ea t t e n t i o n b e c a u s et h e t r u s to fe a c h o t h e ri sad r e c o n d i t i o nf o rt h et r a n s a c t i o n ，r e p u t a t i o nc a nr e p r e s e n tw h e t h e rt h ep e e r sf o r e g o n e b e h a v i o ri ss u i t a b l et op a r t i c i p a t ei nt h en e t w o r kc o m m u n i t y a tt h es a m et i m e ，p e e r - t o 。p e e r n e t w o r ki sv e tf r a i l n l ei 诚np r o b l e mi n c l u d e st h ef o l l o w t w oi t e m s ：t r u s tm o d e l sa l l d1 n c e n t l v e m e c h a n i s m s t 1 1 i st h e s i sp r o p o s e dan o v e l t r u s tm o d e lw i t hi n c e n t i v em e c h a n i s m s b a s e du p o n p e e r - t o - p e e rn e t w o r ko n eo f t h em o s tp o p u l a ra n dr a p i d l yd e v e l o p e dn e t w o r k i n gs t r u c t u r e s i n t h i sm o d e l r e f e r r i n gt ot r u s tr e l a t i o n s h i pm o d e la m o n gs o c i a lp e o p l e ，t r u s tm o d e l b a s e do n r e c o m m e n d a t i o ne v i d e n c er e a s o n i n gw i t hd st h e o r yi sd e s i g n e df o rp e e r - t o 。p e e r n e t w o r k a f t e r t h ea n a l y s i so ft h ei n t e r a c t i o no fp e e r su s i n gi d e a sf r o mg a m et h e o r y ，ad i f f e r e n t i a ls e r v i c e 。b a s e d i n c e n t i v es c h e m ei sp r o p o s e d a t1 a s t ，t h r o u 曲s i m u l a t i o ne x p e r i m e n t s ，w ec o m p a r et h ei m p r o v e dc o m p u t a t i o na l g o r i t h m o ft r u s tp r o p o s e di nt h i st h e s i sw i t ht h ee x i s t i n gg l o b a lt r u s tm o d e le i g e n r e p t h r o u g h a n a l y s i s ， w ek n o wt h i sm o d e lc a nr e s t r a i nt h ec o n d u c to fc h e a t i n ga n di m i t a t i n g e x p e r i m e n tr e s u l tp r o v e s f j ) a f 研西铡曲en 埘n 6 e fo fv i c i o u sp e e r sh a sr e a c h e da c e r a t a i np r o p o r t i o n , t h ei m p r o v e da l g o r i t h m c a nk e e pah i g h e rs u c c e s s f u lr a t eo fd o w n l o a d t h es i m u l a t i o nr e s u l t sp r o v et h a to u rm o d e l h a v e b e t t e rp e r f o r m a n c ei nt e r m so fe v a l u a t i o na c c u r a c y , s e c u r i t ya n di m p l e m e n t a t i o n k e y w o r d s ：p 2 pn e t w o r k s ，t o p o l o g y , t r u s tm o d e l ，i n c e n t i v em e c h a n i s m n 南京邮电大学硕士研究生学位论文 图表清单 图表清单 图2 1 集中式p 2 p 系统9 图2 2 广播式p 2 p 系统1 0 图2 3 分布式p 2 p 系统1 1 图2 4p - g r i d 树的虚拟二叉树拓扑结构1 2 图2 5 改进后p - g r i d 树拓扑结构和搜索过程1 3 图3 1 信任关系2 0 表3 1 模型参数表2 9 表3 - 2d e m p s t e r 合成表3 0 图4 - 1 激励机制的基本算法流程4 6 图5 1 交易成功率对比5 1 图5 2 信任值对比5 2 图5 3 提供真实服务的节点成功下载比例( 不真实服务) 5 3 图5 4 提供真实服务的节点成功下载比例( 作弊评价) 5 3 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了中文特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南 京邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名：日期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本 人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其他复 制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在 保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研 究生部办理。 研究生签名 导师签名：龇日期： 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 本章主要对本论文选题的原因和背景资料进行了总结和归纳，主要内容包括： p e e r - t o p e e r ( p 2 p ) 1 1 网络的研究现状和热点，根据p 2 p 网络自身结构的特点，来说明p 2 p 网络中安全问题的重要性；其次对构建安全模型的相关关键技术进行了阐述，主要包括底 层的逻辑拓扑结构、p 2 p 网络信任模型相关研究和激励机制三个方面；最后介绍了本论文 的主要工作和结构安排。 1 - 1 研究背景 早在2 0 0 0 年，p 2 p 就已经成了一些技术性论坛上讨论的热门话题。p 2 p 是网络计算的 一种新技术，这种技术的目的是将网络中不同的计算机连接在一起，以充分利用互联网和 w e b 站点中任何地方的资源。p 2 p 技术在协同工作1 2 1 ，分布式信息或资源共享【3 】，大规模并 行计算 4 1 等方面显示出的独特优势，使其成为新的研究热点。 现在p 2 p 技术已经发展为网络世界中最流行和最有前途的技术之一，其网络模式正在 逐渐成为研究和应用的热点。在2 0 0 1 年评出的美国网络科技和电子商务发展的十大趋势 中，第一位就是p 2 p 技术。财富杂志更将p 2 p 列为影响i n t e m e t 未来的四项科技之一。 p 2 p 网络应用模式的兴起得益于i n t e m e t 的广泛普及、网络带宽的大幅增加以及基于 i n t e m e t 的端系统计算能力的迅速增强。上述因素促使原先在其它网络计算模式中通常被忽 视且广泛存在的终端用户设备成为一种宝贵的计算资源。与传统的客户端朋艮务器( c s ) 模式相比，p 2 p 技术有效利用网络上大量闲置的信息资源、存储空间、处理器周期等资源， 避免服务器带来的瓶颈问题，在降低服务器成本等方面也具有明显的优势。 目前，互联网上的各种服务，不论采用b s 模式还是采用c s 模式，都是以网络服务 器为中心的。网络用户向服务器发送请求，然后从服务器得到相应的回应信息，用户之间 的交流都是高度依赖于网络服务器，无法直接交流信息。而p 2 p 方式则是以用户为中心， 所有的用户都是平等的伙伴，相互之间可以直接交流信息，如图1 1 所示。 南京邮电大学硕士研究生学位论文 第一章绪论 c s 模式 p 2 p 模式 图1 1c s 模式和p 2 p 模式拓扑 人们对p 2 p 网络的研究涉及各个方面，主要包括：网络拓扑构造、安全与可靠性、分 布式数据存储、大规模并行计算等。 在p 2 p 网络中，每个用户参与网络是随机的、自愿的，并且不同的用户有不同的能力 和可靠性，因此p 2 p 网络具有高度的动态性、自治性和异构性，同时也带来了许多网络管 理和安全策略方面的问题。 ( 1 ) p 2 p 网络具有高度的自治性。p 2 p 网络中的节点可以根据自己的意愿选择行为模 式，没有外在的强制约束，p 2 p 网络的自治性对节点的自主行为给予了充分的尊重。 ( 2 ) p 2 p 网络具有高度的动态性。该特性决定p 2 p 网络难以保证拓扑的稳定性，并且 难以提供完全可靠的服务，造成p 2 p 网络动态性的两个主要原因：一是底层基础设施所提 供的不可靠服务；二是节点自身的自主性，用户随意开、关计算机或终止服务。 ( 3 ) p 2 p 网络中的节点具有异构性。造成节点异构的原因在于节点间广泛存在的计算 能力、存储能力和网络带宽等因素的差别。p 2 p 网络中的节点承担相同的职责，并采用对 等的通信模式。在纯p 2 p 网络中，系统的维护开销( 路由、消息转发、维护修复等) 由节 点共同来承担，但是每个节点的能力是不同的。 ( 4 ) 分布式的资源聚集及协作问题。在p 2 p 网络中，节点贡献自己的空闲资源，并 利用p 2 p 网络提供的资源定位功能发现其他节点的可利用资源，然后进行彼此之间的资源 共享。因此，p 2 p 网络提供将i n t e m e t 终端闲散资源聚集的能力并促成这些终端之间的协作， 如何有效的协调会是问题。 由于p 2 p 网络自身存在上述特点，如何建立个安全的p 2 p 网络环境成为目前p 2 p 研 究的热点。p 2 p 网络本质上是个工作在应用层的覆盖网( o v e r l a y ) 。所谓覆盖网，是指为 了实现特定的功能而建立在一个或多个已存在的网络之上的网络，该网络需要维护一些额 外的信息，例如网络中节点的连接关系、节点的位置信息等。以文件共享p 2 p 网络为例， 南京邮电大学硕士研究生学位论文 第一章绪论 其所实现的特定功能就是文件的定位及文件下载的组织。应用层覆盖拓扑特性，使p 2 p 网 络能够灵活容纳不同物理网络域的各种i n t e m e t 终端。所以如何构建个合理高效的逻辑 拓扑是研究其他问题的基础，因为只有在此基础上才能为其它应用提供安全保障。 在传统意义上，安全性是指保护信息、系统和服务免受恶意侵犯、误操作和灾难性事 件的破坏。对于传统网络环境，网络安全性是有认证、授权、数据完整性、保密性和不可 否认性等部分组成。针对不同的安全性，人们提出了一系列的安全策略来保证网络的安全。 然而，传统网络中的许多安全策略和机制不能直接用于p 2 p 环境。例如：传统网络环境和 应用中，信任关系的建立依赖于可信的第三方，但在p 2 p 环境中，大部分的网络结构是无 中心的，所以根本不存在可信任的第三方。这就导致了很多问题的出现，因此必须根据网 络自身的特点，重新研究改进以适用新的环境。 在p 2 p 的具体使用过程中，我们碰到的问题远不止这么简单。p 2 p 环境下，把握节点 真实的客观能力差异和网络动态性是很难的。因为p 2 p 环境下节点具有高度自治性，采用 直接方法是非常困难的，通常以间接的方式来衡量，但这一过程节点的自主性是不容忽视 的。例如，s e t i h o m e 基于运行在每个v o l u n t e e rp c 上的一个m i c r ob e n c h m a r k 例程的测 试结果来区分节点的计算能力。但与预期结果相反的是，最多高达5 0 的节点通过欺诈手 段改变了测试结果的真实性，以期获得更多的奖励【3 1 。 p 2 p 环境中，节点的资源共享是用户自愿行为，用户可以随意终止服务，甚至可能存 在欺诈行为，因而服务质量无法得到保证。为了保证服务质量，建立p 2 p 网络的信任机制 是十分必要的，有利于保证环境的高可用性和良性发展。 p 2 p 网络的对等通信模式及网络灵活自组织的特性，提供了真实生活中人与人直接进 行交流的网络环境，赢得了广大i n t e r n e t 终端用户的青睐，因而得到了蓬勃发展【4 1 。目前， p 2 p 流量已经占到了主干网流量的6 0 【5 j 。但同时，也正是因为这些特性使p 2 p 网络存在 以下一些问题： ( 1 ) f r e e r i d i n g 6 1 以及“公共物品的悲哀( t h et r a g e d yo ft h ec o m m o n s ) 1 8 ”问题。 f r e e r i d i n g 是指节点只消费其他节点贡献的资源，但并不共享自己的资源。以g n u t e l l ap 2 p 文件共享系统为例，7 0 的节点是f r e e r i d e r 。最新的监测也表明在e d o n k e y 文件共享网络 中，大约有8 0 t 7 的节点是f r e e r i d e r 。“公共物品的悲哀”指网络资源作为一种非排他的公 共资源，被大多数p 2 p 节点无节制的使用，据统计，p 2 p 数据流量占i n t e m e t 总流量达6 0 ， 并且在用户总数没有显著增长的情况下，p 2 p 数据流量仍然在快速持续增长f 9 j 。事实上， p 2 p 网络理性用户的根本目的是最大化自己效用，而并不考虑网络的整体性能。因此，设 计有效的激励机制鼓励p 2 p 网络中的节点进行有效的协作并合理使用网络资源是关系到 南京邮电大学硕士研究生学位论文 第一章绪论 p 2 p 网络进一步发展的重要问题。 ( 2 ) 不可靠的服务可用性。节点的自治性和底层物理网络的动态性造成了p 2 p 网络 高度的动态性，从而造成了p 2 p 服务难以控制管理，服务可用性无法保证的问题。p 2 p 网 络的动态性体现在以下两个方面1 0 】：底层物理网络的动态性。有研究表明，具有 i n t e m e t 连接的计算机的平均无故瞳射间( m t b f ) 为1 3 个小时左右，也就是说，在规模为 1 0 0 0 0 的网络环境中，平均每两分钟就有至少一个节点失效。节点能力的差异性：如前 所述，节点能力的差异性体现在节点间广泛存在的计算、存储能力以及网络带宽等方面的 差别。研究指出【1 2 】，目前存在于i n t e m e t 上的计算设备的网络连接能力呈p o w e r - l a w 分布。 在g n u t e l l a 和n a p s t e r ( ”】的文件共享系统中，节点在带宽、时延、可用性和连接度数有3 到5 个数量级的变化。事实上，研究和实验i i e n 刃 1 3 】【1 4 】，造成节点能力异构的主要原因并不 是节点自身在计算、存储以及网络带宽能力等方面的物理客观差异。相反地，节点的自治 性使得节点可以自主选择参与到系统中的程度，最终导致了p 2 p 节点能力上的异构性。p 2 p 网络中不仅存在着大量的f r e e r i d e r ，还存在着大量不可靠的服务以及欺诈行为。以众多的 文件共享应用为例，2 5 的文件是伪造文件( f a k e df i l e s ) 。节点的这种自主性造成的不合 作性严重影响了p 2 p 服务的可用性。因此，要提高p 2 p 服务可用性，必须充分考虑底层物 理网络的动态性以及节点的自主行为和相关的激励机制。目前主流的全分布式p 2 p 网络在 构造拓扑时都没有考虑节点的自主行为特征，节点在拓扑上的地位是相同的，这就降低了 节点获得服务的目的性。有鉴于此，建立有效识别节点的机制，充分考虑节点的行为特征， 构造具有优良拓扑的p 2 p 网络对提高p 2 p 服务的整体可用性具有非常重要的意义。 在p 2 p 环境中，每个节点具有两种角色：客户、服务器，即节点不仅要获得服务，同 时也要提供服务，而有些节点只获取而不提供，这就是p 2 p 网络中节点的自私行为。这种 自私行为对网络性能的影响是不可低估的。增强节点的合作机制分为两类：第一类是基于 激励的机制，第二类是基于惩罚的机制。惩罚机制虽然可以抑制节点的自私行为，但无法 做到增加高贡献节点的效用。 充分考虑节点异构性，促进节点之间的合作，提高p 2 p 网络服务可用性是关系到p 2 p 网络整体效益的重要问题，涉及到网络拓扑构造、资源发现机制、资源共享机制、信任模 型、激励机制等多个方面。本论文主要围绕拓扑构造、信任模型和激励机制展开研究。 1 - 2 研究目标和主要工作 本文在研究p 2 p 网络的拓扑结构以及传统社会科学领域中的信任模型的基础上，分析 4 南京邮电大学硕士研究生学位论文 第一章绪论 p - g r i d 树的拓扑结构，构建基于推荐证据的p 2 p 网络信任模型，对p - g r i d 树的路由机制进 行针对性修改，讨论建立信任系统要考虑的问题以及具体的实现过程，并引入激励机制。 这个模型充分利用了p - g r i d 树优良的逻辑特性，根据节点过去在网络中的历史经验，建立 了节点之间的信任关系，得出信任度算法，更加有效的去解决网络中信任关系，实现算法 比较简洁，比一些具有复杂算法的信任模型更适合在现实网络中应用。该模型能够增强网 络可用性，具有结构简单、可靠性强的优点。 论文致力于研究p 2 p 环境信任模型的构造及其实现的关键技术，包括p 2 p 信任模型的 拓扑设计、信任度算法研究、信任管理机制设计以及p 2 p 激励机制研究等内容，主要工作包 括： ( 1 ) p 2 p 网络结构化拓扑构造 根据对目前各种p 2 p 网络拓扑结构的分析研究，结合最新的研究成果，结合本文模型 的应用需求，考虑到p g r i d 树在结构性质方面的诸多优良特性，本文在p g r i d 树的基础上 构建信任模型，对底层逻辑拓扑方面进行了修改，主要是针对p g r i d 树的路由机制进行修 改，建立基于p g r i d 树拓扑结构的p 2 p 应用模型，并对相关的具体实现细节进行设计。 该工作是本文进行其它工作的前提和基础，最重要的作用是提供了一个简单且易于实 现的底层逻辑结构，为p 2 p 网络中节点的信息、信任机制中的信任信息以及激励机制中的 激励信息提供信息存放的基础。 ( 2 ) 信任模型的建立 由于p 2 p 网络先天的缺陷，安全信任问题一直是困扰p 2 p 网络进一步发展的焦点问题， 为了让p 2 p 网络良性发展，必须建立信任机制。在信任的基础上，才能够为网络中的节点 提供一个较为可靠的服务环境。本文在基于p - g r i d 树的p 2 p 网络拓扑结构下，对传统的信 任模型进行分析，根据信任模型的研究成果，建立本文基于推荐证据的信任模型，并且根 据设计信任模型的具体要求，对d s 证据理论进行研究，得出基于推荐的信任模型可信度 算法，最后详细的设计了模型实现的相关算法和步骤。 ( 3 ) p 2 p 激励机制的研究 分析了现有的激励机制之后，发现a d h o c 网络和p 2 p 网络有一定的相似性，而在 a d h o e 网络中，已经成功的将博弈理论应用在激励机制中，在此基础上，考虑到p 2 p 网 络与a d - h o c 网络的共性，本文也引入了博弈理论，在信任模型的基础上引入激励机制， 使信任模型更加完善，激励机制是对信任模型的补充和优化，最终建立起本文带激励机制 的信任模型。 南京邮电大学硕上研究生学位论文 第一章绪论 1 3 本文安排 第一章绪论，介绍论文背景，简单介绍了p 2 p 网络的相关研究动态；安全的相关知 识以及p 2 p 网络存在的问题，在此基础上提出了自己的研究目标；并给出本文研究的主要 内容，最后给出了本文的组织结构。 第二章p 2 p 网络结构化拓扑构造，主要内容包括：介绍什么是p 2 p 网络以及发展历史； 重点分析研究现在主流的p 2 p 网络拓扑结构和分类，及相应的优缺点；在分析研究的基础 之上，提出了本文的拓扑结构，完成模型的初始设计；对模型的关键点和具体应用过程进 行阐述，包括模型的建立过程，数据的存放，内在的逻辑结构。 第三章建立信任模型，是本论文研究的重点，首先简要的说明了信任模型在p 2 p 网 络安全中所处的地位层次；信任评价的方法；设计信任模型的要素要求。根据目前信任模 型存在的问题，运用d s 理论证据理论的知识，对信任模型中的核心部分，即信任度的计 算方法上，得出本文基于推荐证据信任模型信任度的具体数学表达，这是本文信任模型的 理论基础。其次在上一章所设计的拓扑结构下，指出建立信任模型要考虑的问题，对本文 基于推荐证据的信任模型进行了详细设计，设计了信任模型的相关关键点。 第四章引入激励机制，首先系统地研究了p 2 p 网络和a d h o e 网络的现有激励机制， 分析存在的问题以及现有的研究情况，在此基础上说明了建立激励机制的必要性；其次对 第三章所设计的信任模型进行进一步的修正，引入激励机制到信任模型；对引入激励机制 后的节点行为进行算法改进，建立带激励机制的信任模型，使信任模型更加完善。 第五章仿真结果分析，本章是全文的总结部分。一是对本文模型的一个验证，二是 与其他模型进行对比。 总结与展望，对本文工作进行了归纳总结，指出本文模型的不足和缺陷，同时对后续 的研究工作做了进一步的展望。 6 南京邮电大学硕士研究生学位论文 第二章基于二叉树的网络拓扑构造 第二章p 2 p 网络结构化拓扑构造 动态网络是p 2 p 系统存在的基石，形成动态网络是p 2 p 系统的典型特征，而互联网是 带有某些静态特性的网络，例如，连接到互联网的任何计算机都被分配一个唯一的i p 地址。 p 2 p 网络必须能唯一的标识动态网络上的所有对等节点和可用资源，因此p 2 p 系统必须定 义自己独立于i p 地址和d n s 的命名规则，创建虚拟名字空间。不同于d n s 等寻址方法中 采用的预定义或预配置方式，p 2 p 网络中的对等节点通过使用i p 地址或d n s 作为导航助 手来相互寻址，从而形成动态或虚拟网络。在p 2 p 网络中构造良好的动态拓扑是p 2 p 网络 应用的核心问题，在此基础上才能够采用相关的搜索机制，建立信任模型。 本章主要研究p 2 p 网络动态拓扑的构造，首先对p 2 p 网络的基础概念进行阐述，其次 分析目前p 2 p 网络拓扑结构方面的研究现状，重点是对结构化拓扑p g r i d 树进行分析，并 对其路由机制进行针对性修改，作为本文提出的信任模型和激励机制实现的基础。对改进 后的拓扑初始化和资源的使用，文中给出了详细设计。 2 1 p 2 p 的基本概念 目前研究界和工业界对p 2 p 尚无公认的严格定义，人们从不同的行业和视角对p 2 p 提 出了多种定义。为了避免混淆和便于查阅，本小节将介绍本文涉及到的一些p 2 p 基本概念。 o r a m 1 6 1 定义为：对等网络是对在互联网的边缘的可用存储资源、计算周期、内容等加 以利用的一类应用系统。 p 2 p 工作组【1 7 1 定义为：通过系统间直接交换来共享计算机资源和服务。 a l e xw e y t s e l u 6 1 定义为：以非客户端的方式使用i n t e m e t 的外围设备。 c l a ys h i r k y u 6 l 定义为：p 2 p 计算是指能够利用分布在i n t e m e t 边缘的大量计算、存储、 网络带宽、信息和人力等资源的技术。由于访问这些分散的资源是在不稳定链接和动态i p 地址的情况下进行的，p 2 p - - 1 4 - 一- 腻、， 月匕匕夕口出且于d n s 系统之外寻址并有相当部分乃至全部 的自治性。 这些定义从不同的侧面对p 2 p 进行了描述，本文倾向于采用一些典型特征来定义p 2 p 网络：节点之间可以直接访问资源，无须借助第三方；每个节点都要同时充当c l i e n t 和 7 量! 蔓塑皇查学硕三塑! 茎；壁垡鲨苎 笙三皇茎三三墨塑塑堕堡堑盐塑望 s e r v e r 的角色；能够动态自适应网络变化，i n t e m e t 边缘节点的不可控性、边缘连接的不 可靠必将导致节点的动态性；节点自治性，每个节点都有充分的自治性，p 2 p 计算系统是 在确保各节点的自治性的前提下达到系统目的的；无集中控制，没有全局视图；可扩展性 好，能够容纳巨大的节点数量。 以上并不是所有p 2 p 系统都必须要具备的特征，只需符合其中若干特征并支持节点直 接交互就可以被称为p 2 p 系统。广义的p 2 p 系统并不排斥部分功能的集中化实现，例如 n a p s t e r t l 8 1 中依靠集中服务器实现共享音乐的集中登记和搜索，b i t t o r r e n t 1 9 1 依靠t r a c k e r 服务器管理节点连接。 2 2p 2 p 网络的拓扑结构 建立p 2 p 网络的信任机制，首先要了解整个p 2 p 系统的架构，p 2 p 系统是分布式系统 家族的成员。如果对其进行分类，粗略地可将其分为纯p 2 p 系统( p u r ep 2 ps y s t e m ) 和混 合p 2 p 系统( h y b r i dp 2 ps y s t e m ) 1 2 0 。 ( 1 ) 纯p 2 p 系统。没有服务器的概念，所有的参与者都是对等者，存储、交换、搜 索都是在对等者上完成的。g n u t e l l a 系统就近似于纯p 2 p 系统口。纯p 2 p 系统克服了c s 模式服务器单点失效和瓶颈等问题，但一个节点的搜索请求要经过整个网络或者至少是一 个很大的范围才能得到结果，占用很多带宽，而且可能需要花费很长时间才能有返回结果。 ( 2 ) 混合p 2 p 系统。将分布式系统与集中式系统相结合，由位于网络中的服务器搜 集相关信息，作为索引节点，负责记录共享信息以及回答对这些信息的查询，而共享资源 则分布在各个节点上。对等者节点首先向服务器发出请求，获得相关对等者的地址信息， 之后信息交换仍发生在两个对等节点之间。n a p s t e r 系统就是这类系统的代表之一【1 5 】。这类 系统中，要求服务器必须能够处理大量的用户连接，拥有足够的内存和磁盘空间来维护和 搜索文件列表，并连续运行。 p 2 p 网络拓扑优劣的评估一般采用以下三个主要尺度： ( 1 ) 拓扑的可扩展性； ( 2 ) 拓扑的维护开销； ( 3 ) 拓扑的动态适应性。 拓扑的可扩展性是指基于拓扑的对象( 服务、数据等) 定位开销与网络规模的关系； 系统的维护开销一般主要指拓扑中节点邻居表的维护开销；动态适应性是指拓扑应付 a d h o c 环境的能力( 随机的节点失效、加入等) 。 8 南京邮电大学硕士研究生学位论文 第二章基于二叉树的网络拓扑构造 根据上述p 2 p 拓扑优劣的评估尺度，按照信息交换的方式，下面对常见的几种p 2 p 系 统的系统结构进行详细分析。 ( 1 ) 集中式p 2 p 该结构使用专门的中央索引节点，这些节点保留了在p 2 p 系统中可得到的活动节点信 息和其上的共享资源的目录信息。当一个节点加入p 2 p 系统时，该节点就发送一份其上存 储的所有文件的名单给中央索引节点，中央索引节点将保存每个用户加入系统时提供的文 件列表名单并进行动态更新。当请求一个文件时，用户要查询中央索引节点。在中央索引 节点收到查询请求时，就在它保存的索引文件列表中判别是否含有感兴趣内容的节点，如 果有，就将这些节点的i p 地址名单返回给用户。同时，中央索引节点会查找与查询匹配最 佳的对等节点( 最佳对等者可能是速度最快的、代价最低的、用户最容易得到的对等者， 最佳是由用户的需求来决定的) 。之后，用户与最佳对等者之间直接传送文件，而不再通 过中央索引节点。目前的典型代表是n a p s t e r 系统，如图2 1 所示。 臼一 s e r v e r 腓r q查询 r 应答 d 下载 图2 1 集中式p 2 p 系统 集中式p 2 p 系统，查询效率高，n a p s t e r 系统使用中央目录服务，只要一条消息就可以 解决一个查询。但中央索引节点容易受到攻击，对中央索引节点的要求也较高，集中式p 2 p 的主要缺点是索引服务器的单点失效问题。 ( 2 ) 广播式p 2 p 在这类系统中，对共享文件的搜索是通过向网络( 或其子集) 广播查询消息来工作， 以期找到与查询对应的结果。广播式p 2 p 系统的拓扑维护开销是o ( d ) ，定位开销是o 叫) ， 其中d 为系统设定的节点邻居个数，n 为系统规模。但是该类系统缺乏精确的对象定位机 制，因此往往只适用于文件共享类应用，如图2 2 所示。 9 南京邮电大学硕士研究生学位论文 第二章基于二叉树的网络拓扑构造 q查询 r 应答 d 下载 图2 2 厂播式p 2 p 系统 这种搜索机制的优点是简单强健，缺点是不适用于大规模系统，因为每产生一个查询， 就会由于消息在网络中泛滥而导致了大量的网络带宽损耗，而且不容易度量。 ( 3 ) 分布式p 2 p 这种结构的特点是在每个对等节点上都保存有部分索引信息，这些分布式索引表一般 要求很小，这些索引信息给出了文件所在的方向，而一般不是文件所在的真实位置，如图 2 3 所示，因而与传统的目的地索引不刚2 2 1 。而且，用户除了提交查询条件之外，还提交 停止条件( 例如所期望的结果数目，或所经过的节点数等) 。收到查询请求的对等节点首 先对照它自身存放的信息评估节点，并将结果返回给用户。如果没有达到停止条件，该节 点就根据自身的索引表选择一个或更多它的邻居，把查询请求( 还有一些状态信息) 传给 它们。每个邻居依次以类似的方式进行查询，把结果返回给用户，并把查询请求传给其邻 居节点。如此继续，直到达到停止条件，或者确知不可能达到停止条件，此时停止传递查 询，得到查询结果。 分布式拓扑的典型应用系统包括k a z a a 2 3 1 ，f a s t t r a e k l 2 4 1 以及g n u t e l l a 2 5 1 。实际的应用证 明，分布式p 2 p 网络充分利用了节点能力的差异性，既有c l i e n t s e r v e r 模式有效定位资源 的特点，又能够极为有效地消除纯p 2 p 结构中因为使用泛洪算法带来的网络拥塞等不利影 响，同时超级节点的引入能够在一定程度上起到负载均衡的作用，因而得到了广泛的应用。 另外一些网络如e d o n k e y 2 6 1 ，e m u l e t 2 7 1 ，和b r o c a d e 【2 8 1 也采用分布式的拓扑结构，如图2 - 3 所示。 1 0 南京邮电大学硕士研究生学位论文一 篁三至茎王三墨塑堕望垒堑盐塑i 生 _ _ _ _ - - _ - _ - _ - - - _ _ _ - - _ _ _ _ _ _ - l - - _ - - - _ - _ _ _ _ _ _ - _ _ _ _ _ _ _ - 一一一 q查询 r 应答 d 下载 图2 3 分布式p 2 p 系统 在分布式p 2 p 系统的研究中，目前研究界公认基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 【2 9 】【3 0 】 的c h o r d 和c a n 是两个典型的结构化全分布式拓扑，还有如p a s t r y 3 n 、k a d e m e l i a 【3 2 1 ， p g r i d 3 3 】1 3 4 1 也是这一类型。c h o r d 和c a n 的逻辑空间生成都借助于节点的i p 地址，因此 使得节点的逻辑地址与物理地址一一对应。存在的主要问题是它们对称的拓扑结构和广泛 存在的节点异构性不相适应。研究跚中指出，这类对称的结构化拓扑由于对节点差异的不 敏感导致在适应高度动态性和节点异构的网络环境时，在拓扑的稳定性和可用性上存在着 一定的局限。 各种不同架构的p 2 p 系统的主要区别体现在资源搜索和定位机制上，这也是p 2 p 网络 的主要应用和最频繁的操作，不同的p 2 p 类型，它的资源搜索和定位是有差别的。 一般地，基于无结构拓扑的p 2 p 应用往往采用基于广播的搜索机制，而结构化拓扑多 采用基于分布h a s h i n g 3 5 】的单播方式的对象定位机制( 也称作d h t 定位机制) 。 根据文献3 6 瑚】，广播搜索机制的优势在于支持模糊的对象匹配，从而为用户带来有益 的可选择性，而存在的问题在于它可能给底层的拓扑带来可扩展性问题。d h t 定位机制的 优势在于其单播方式较小的通信开销，但不支持模糊匹配，使定位机制缺乏对结果的可选 择性3 9 1 。 在现有的结构化d h t ( d i s t r i b u t e dh a s ht a b l e ) 拓扑中，p - g r i d 3 31 3 4 是具有非对称结 构特征的结构化拓扑结构，p - g r i d 采用树型结构。p - g r i d 结构使用虚拟二叉树的结构构造 d h t 拓扑。p - g r i d 树中的节点位置由节点在树中的路径( p a t h ) 决定，如图2 4 所示，节 点1 的位置为o o ，节点2 的位置为0 l 等等。p - g r i d 树中每个节点都含有一个路由表，每 一个路由表有很多项，每项指向一个同层的与他在某路径位上相反的一个其他节点，如图 2 4 中节点6 的路径为o o ，其两个路由指针分别指向与其路径第一位相反的节点5 以及第 南京邮电大学硕士研究生堂堡笙茎 笙三雯苎至三墨塑堕堡望塑堂! ! 生 二二一一。 二位相反的节点2 。p - g r i d 树的对象查询采用基于前缀的路由，例如当节点6 收到一个对 标识1 0 0 的查询时，由于其本身对应的第一前缀为0 ，因此将请求转给节点5 ，同理节点5 将请求转给节点4 ，直到查询成功或失败，如图2 4 中箭头所示。p - g r i d 的定位开销的消息 复杂度为0 0 0 9 2 n ) 。 图2 4p - g r i d 树的虚拟二叉树拓扑结构 p g r i d 树结构有如下特点： ( 1 ) p g r i d 树对拓扑中的节点的度做了明确的要求，可以使设计简化并有针对性。 ( 2 ) p g r i d 树逻辑上是二叉树，从它的路由表构造可以看出，节点路由表大小是不均 匀的，树上下层节点路由表的大小介于o ( 1 ) , - o ( 1 0 9 2 n ) 之间。 ( 3 ) p g r i d 树的构造简单，在最特殊情况下搜索复杂度最多达到o ( n ) ，n 为系统规 模，但在绝大多数情况下，它的搜索复杂度远小于o ( n ) 。对于网络使用中最频繁的搜索等 应用具有先天优势。 ( 4 ) p g r i d 树的另一个主要特点是可以充分利用节点的能力差异解决负载均衡问题， 根据p g r i d 的对象索引插入算法，其树的下层节点在最坏情况下放置的索引数量为上层节 点的l 0 9 2 n 倍，其下层节点的负载往往远大于上层节点，因此，该拓扑对一些节点的稳定 性有较高要求，随着电子技术的发展，终端处理能力的增强，可以利用节点的能力差异进 行解决。 ( 5 ) 虽然p - g r i d 树引入了信任管理机制，它是由以k a r la b e r e r 为首的