（通信与信息系统专业论文）对等网络中的激励策略研究.pdf

中国科学技术大学硕士学位论文 摘要 摘要 作为分布式系统的一个应用 对等网络正以其高扩展性获得越来越多的关 注 对等网络又称为p 2 p p e e r t o p e e r m 络 p 2 p 网络不采用传统的c s 架构 在p 2 p 中单个节点既充当服务器又充当客户 因此可以充分利用闲职在网络边 缘的客户节点资源 提高了资源利用率 增强了系统扩展性 但是由于p 2 p 系 统的分布式特点 单个节点可能选择提供服务 也可能选择不提供服务 或者选 择提供低质量的服务 甚至提供虚假或者恶意的服务 攻击 由此引入了更多的 公平性问题和安全问题 我们因此需要一种有效的机制激励用户提供高质可靠的 服务 在传统网络中 服务总是由服务器节点提供 这个问题并不突出 为了更好的激励用户提供服务 我们引入了信誉度维护机制 通过对每个用 户计算和维护一个信誉度 表征用户 以往对系统的贡献 以此提供区分服务 激 励用户提供服务 通俗的说 信誉度高的节点获得更高质量的服务 信誉度低的 节点获得低质量的服务 在这个框架下 我们面对如下几个问题 1 如何进行 区分服务 即 在得知某些节点的信誉度和其它系统参数下 向哪些节点提供怎 样的服务 2 如何计算和更新信誉度 在一个节点提供服务后 如何根据本次 服务的好坏以及该节点的历史信誉度 计算得到新的信誉度 3 如何维护信誉 度 由于p 2 p 系统的分布式特性 信誉度应当被安全的分布式维护 分布式特 性引入很多安全问题 我们需要保证信誉度不被恶意节点窜改 本文第l 章介绍了p 2 p 系统出现的背景 分类及其应用 重点针对文件共享 系统和流媒体系统进行介绍 第2 章引出我们需要解决的问题 如何激励用户提 供可靠高质的服务 我们介绍已有研究 给出了博弈论和应用密码学两个理论基 础 以及它们在信誉度维护中各自扮演的角色 第3 章利用博弈论的思想 提出一种针对r e c e i v e r d r i v e np 2 p 流媒体的计费 算法 该算法主要目的是在博弈论的框架下降低流媒体系统的服务开销 通过更 好的选择服务节点来降低开销 通过搏弈论设计的计费算法来保证服务节点正确 汇报自己的开销 防止服务节点的错误报价 以此真正降低服务开销 激励节点 提供服务 该计费算法对博弈论中的v c g 算法进行改进 本章实际上讨论了如 何利用信誉度进行区分服务的问题 给定一些潜在的服务节点 如何选取服务节 点和如何进行计费 第4 章提出一种利用双重信誉度抵制w h i t e w a s h i n g 攻击的算法 所谓 w h i t e w a s h i n g 攻击 是指现有的p 2 p 系统大多鼓励新节点加入网络 因此赋予新 节点较高的信誉度 但是恶意节点可以在信誉度降低之后重新更换身份进入网 络 危害系统性能 双重信誉度算法可以用于文件共享或者流媒体系统中 基本 思想是通过对新加入节点维护两个信誉度 一个信誉度表征其获取服务的能力 另一个信誉度表征其提供服务的能力 一方面激励它提供服务 一方面对它采取 不完全信任的策略 以此过滤掉新加入节点中的不良节点 防止w h i t e w a s h i n g 中圈科学技术大学硕士学位论文摘要 现象 本章实际上针对新加入节点讨论了如何更新计算信誉度的问题 第5 章提出一种基于h a s h c h a i n 的链式信誉度存储方案 在p 2 p 系统中 单 个节点的信誉度必须维护在其它节点上 信誉度维护节点存在窜改自己维护的信 誉度的可能 链式存储方案基本思想是通过h a s h 算法让信誉度维护节点维护的 交易信息彼此相关 防止维护节点丢弃任何信誉信息 这种方案可以更好的保证 信誉度维护节点不能破坏自己维护的信誉度 防止节点之间的勾结和恶意诋毁 本章实际上讨论了p 2 p 系统如何安全维护信誉度的问题 第6 章进行总结 并提出下一步工作计划 关键字 p 2 p 信誉度 博弈论 w h i t e w a s h i n g h a s h 算法 中国科学技术大学硕士学位论文 a b s t r a c t p 2 p p e e r t o p e e r n e t w o r k sa l eo b t a i n i n gm u c hm o r ea t t e n t i o nt h a n k st oi t s e n h a n c e ds e a l a b i l i t y i np 2 pap e e ra c t sb o t ha ss e r v e ra n dc l i e n t t h u st h ew h o l e s y s t e mc a nb e t t e ru t i l i z er e s o u r c e sf r o ma l lo v e rt h en e t w o r k h o w e v e r i ns u c ha d i s t r i b u t e da r c h i t e c t u r e as e l f i s ho rm a l i c i o u sp e e rc a l lc h o o s et op r o v i d el i t t l eo rn o s e r v i c e s e r v i c ew i t hl o wq u a l i t y o re v e nm a l i c i o u ss e r v i c ew h i c hi sh a r m f u lt ot h e w h o l es y s t e m t h e s ep e e r st h u si n t r o d u c em o r es e v e r ef a i r n e s so rs a f e t yp r o b l e m s t h a nt r a d i t i o n a ln e t w o r k s i nw h i c ho n l ys e r v e r sc a np r o v i d es e r v i c e p r o p e r m e c h a n i s m sa r et h e r e f o r ei nd e m a n df o rt h e s ep r o b l e m s i nt h i st h e s i sw ec o n t i n u eo t h e r s r e s e a r c ho np 2 pr e p u t a t i o nm a n a g e m e n t i n s u c ha r c h i t e c t u r ee a c hp e e ri sa s s o c i a t e dw i t hac o m p u t e dr e p u t a t i o n w h i c hr e f l e c t s i t sp r e v i o u so v e r a l lp e r f o r m a n c ea n dc o n t r i b u t i o nt ot h ew h o l es y s t e m b e n i g np e e r s c a l lo b t a i nh i g h e rr e p u t a t i o n a n dv i c e v e r s a w ep r o v i d ed i f f e r e n t i a t e ds e r v i c et o p e e r sb a s e do nt h i sr e p u t a t i o n b e n i g np e e r sc a nt h e r e f o r eo b t a i nb e t t e rs e r v i c e i n t h i sw a yw ei n c e n t i v a t ep e e r st op e r f o r mb e t t e ri nt h es y s t e m 1 r h i sr e p u t a t i o nb a s e da r c h i t e c t u r eo b v i o u s l yi n t r o d u c e st h r e em a i nr e s e a r c h d i r e c t i o n s 1 h o wt od i f f e r e n t i a t et h es e r v i c et op e e r sg i v e np e e r s r e p u t a t i o n sa n d o t h e rf a c t o r s 2 h o wt ou p d a t et h er e p u t a t i o na f t e ras e r v i c ec o m p l e t e d o r h o wt o c o m p u t ean e wr e p u t a t i o n 3 h o wt om a i n t a i nt h er e p u t a t i o ni n ad i s t r i b u t e d e n v i r o n m e n t m a k i n gi ti n v u l n e r a b l et om a l i c i o u sa t t a c k e r s t h et h e s i si so r g a n i z e di n t os e v e nc h a p t e r s i nc h a p t e ro n e w ei n t r o d u c ep 2 p n e t w o r k i t sc o r em e r i ta n dv a r i o u sa p p l i c a t i o n s w ef o c u so np 2 pf i l es h a r i n ga n d s t r e a m i n gs y s t e m s i nc h a p t e rt w ow ei n t r o d u c eo u rm a i nc h a l l e n g ei nt h i st h e s i s t h a t i s h o wt oi n c e n t i v a t ep e e r st op r o v i d em o r es e r v i c ew i t hh i g h e rq u a l i t y w ei n t r o d u c e e x i s t i n gr e s e a r c h e s w eb r i n gi ng a m et h e o r ya n da p p l i e dc r y p t o g r a mw h i c ha c ta s m a t h e m a t i c a ib a s i si nt h i st h e s i s i nc h a p t e rt h r e ew eb r i n gf o r w a r dan o v e lp r i c i n ga l g o r i t h mf o rr e c e i v e r d r i v e n p 2 ps t r e a m i n gs y s t e m i nt h ev i e wo fg a m et h e o r y i nr e c e i v e r d r i v e np 2 ps t r e a m i n g a r c h i t e c t u r e s ac l i e n tp e e rm a yg e tr e s o u r c e sf r o mo n eo rm o r e s e r v e rp e e r s 1 1 1 e o p t i m a lp e e rs e l e c t i o np r o b l e mi st om i n i m i z et h et o t a ls t r e a m i n gc o s ts u b j e c tt ot h e b 觚d w i d t hr e q u i r e m e n t h o w e v e r p 2 pp e e r sa r eu s u a l l ys e l f i s hi d e n t i t i e sw h os e e kt o m a x i m i z et h e i ro w nb e n e f i t s t h u sw ea n a l y z et h eo p t i m a lp e e rs e l e c t i o np r o b l e mi na g a m et h e o r e t i ca p p r o a c ha n du s et h ew e l l k n o w nv c gp r o c e d u r et os c h e d u l et h e p r i c i n gp o l i c y w ei n s p i r i tt h et r u er e v e l a t i o no fs e r v e rp e e r s c o s tv a l u ei no r d e rt o m i n i m i z et h et o t a ls t r e a m i n gc o s t 1 1 1 ec h a p t e ri n d e e dd i s c u s s e sh o wt od i f f e r e n t i a t e t h es e r v i c e h o wt oc h o o s es e r v e rp e e r sa n dh o wt oc h a r g et h es e r v i c e i 中田科学技术大学硕士学位论文 a b s t m 髓 i nc h a p t e rf o u rw ed i s c u s sw h i t e w a s h i n ga t t a c k i nw h i c hp e e r sa r ea l l o w e dt o g a i nn e w i d e n t i t i e st oj o i ni nt h es y s t e m w i t hl i n l eo rn oc o s t t h i sa t t a c kp r o v i d e s m a l i c i o u sp e e r st h eo p p o r t u n i t yt oj o i ni nt h es y s t e mw i t hn e wi d e n t i t y t h u st h e yc a l l m o r ee a s i l yc o m p r o m i s es y s t e mf a i r n e s sa n ds a f e t y w ea n a l y z et h i sp h e n o m e n a b a s e do no t h e r s r e s e a r c hr e s u l t sa n du s ead o u b l et r u s tm e c h a n i s mt ob o t hp e n a l i z e a n de n c o u r a g en e wg o n s u m e r s t 硒sm e c h a n i s ma s s i g ne a c hl l e w p e e r t w o r e p u t a t i o n s o n ed e n o t e si t sa b i l i t yt op r o v i d es e r v i c ew h i l ea n o t h e rd e n o t e si t sa b i l i t y t oo b t a i ns e r v i c e i nt h i sw a yw ec a nf i l t e rm a l i c i o u sp e e r sf r o mn e wj o i n i n gp e e r s n i s c h a p t e ri n d e e dd i s c u s s e sh o w t oc o m p u t er e p u t a t i o nf o rt h en e w p e e r s i nc h a p t e rf i v ew ei n t r o d u c ean o v e ih a s h c h a i nb a s e dr e p u t a t i o nm a i n t a i n e e a r c h i t e c t u r e i nd i s t r i b u t e de n v i r o n m e n tap e e r sr e p u t a t i o ni sm a i n t a i n e di no t h e r p e e r s w h e nm a i n t a i n i n go t h e rp e e r s r e p u t a t i o n nm a l i c i o u sp e e rc a l lc h a n g et h e r e p u t a t i o ni fi ti sn o tw e l jp r o t e c t e d t h eh a s h c h a i nm a i n t a i n c ea r c h i t e c t u r ei su s e d t oc o r r e l a t et h ep r e v i o u sr e p u t a t i o ni n f o r m a t i o nw i t hc u r r e n tr e p u t a t i o ni n f o r m a t i o n t h u sap e e re a r ln o ti n t e m i o n a l l yd i s c a r di t ss p e c i f i cm a i n t a i n e dr e p u t a t i o n s 1 r h i s a r c h i t e c t u r ei st h e r e f o r ei b o r ei n v u l n e r a b l et oc o l l u s i o i l sa n dd e n i g r a t i o t i s m s c h a p t e ri n d e e dd i s c u s s e sh o w t os a f e l ym a i n t a i nr e p u t a t i o n si np 2 p c h a p t e rs i xc o n c l u d e st h i st h e s i sa n dd e s c f i b e sf u t u r er e s e a r c hd i r e c t i o n s k e y w o r d s p 2 p r e p u t a t i o n g a m et h e o r y w h i t e w a s h i n g h a s ha l g o r i t h m r v 中国科学技术大学学位论文相关声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工作 所取得的成果 除已特别加以标注和致谢的地方外 论文中不包含任 何他人已经发表或撰写过的研究成果 与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明 本人授权中国科学技术大学拥有学位论文的部分使用权 即 学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版 允许论文被查阅和借阅 可以将学位论文编入有关数据库进行检 索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后也遵守此规定 作者签名 耋墅丞 加7 年歹月2 6 日 中国科学技术大学硕士学位论文第1 章对等同络综述 第1 章对等网络综述 1 1 对等网络基本原理 在传统c l i e n t s e r v e r 网络模型中 高性能服务器占据至关重要的位置 服务器不但提供 数据 同时扮演着转发内部报文 提供安全保护等一系列角色 随着网络规模的扩大 这种 集中式管理越来越不适合网络的发展 一方面 服务器负担太重 形成系统瓶颈 另一方面 随着硬件设施的改进 客户端能力大幅度提高 我们需要某种机制充分利用闲置在客户端的 资源 随着一种免费提供m p 3 的软件n 印s t e r 1 出现 出现了一种不同于c l i e n t s e r v e r 的新 的网络架构 称之为p 2 p p e e r t o p e e r 模式 也就是对等模式 对等模式的定义是 节点 用 户 同时扮演客户端和服务器的角色 既获取服务又提供服务 p e e r t o p e e r 网络称为对等网 络 是指网络中的各个节点是逻辑对等的 不再区别服务器以及客户端 网络中各个节点之 间可以直接进行数据通信而不需要通过中间的服务器 这样利用了闲置在客户端的资源 解 决了单一瓶颈问题 使网络技术向更大规模发展 如图1 1 所示 p 2 p 构建了一种完全分散式的网络结构 不同于c s 的集中模式 c n t 图1 1 a c s 模式网络 圄 圉璺 p e e r 图1 2 a 混和型p 2 p 架构 图画 c 啊 图i i b p 2 p 模式网络 国旦 阿 图1 2 b 纯p 2 p 架构 p 2 p 大体又可分为两种类型 一种是配置了管理服务器的混和型p 2 p 如图1 2 a 所示 这里的服务器并不提供传统的数据服务 它主要是对节点间的通信进行控制和管理 节点在 服务器的帮助下相互之闻进行数据通信 目前流行的p 2 p 软件如n a p s t e r i 和b i t t o r r e n t 2 j 等基本上都属于混和型p 2 p 混合型p 2 p 易于引入用户认证 安全 和计费功能 但是由于 l 髑阻 可 旧 围口 旧 圉曰 l 中国科学技术大学硕士学位论文 第l 章对等同络综述 管理服务器的存在 仍然面临着单点故障和扩展性问题 另一种则是不引入任何服务器的完 全对等的纯p 2 p 结构 如图1 2 b 所示 纯p 2 p 完全是自组织的 节点之间直接进行数据交 换 完全分布式的网络更加强调节点之间的合作 强调服务的有效性和安全性 是目前研究 的热点 我们归纳出p 2 p 的几大技术特点 1 非中心化 d e c e n t r a l i z a t i o n 网络中每一个对等点具有相同的地位 既可以请求 服务也可以提供服务 同时扮演着c s 模式中的服务器和客户端两个角色 还可 以具有路由器和高速缓冲存储器的功能 从而弱化了服务器的功能 甚至取消了服 务器 网络中的资源和服务分散在所有节点上 信息的传输和服务的实现都直接在 节点之间进行 避免了可能的瓶颈 p 2 p 非中心化的基本特点 带来了其在可扩展 性 健壮性等方面的优势 2 可扩展性 在p 2 p 网络中 随着用户的加入 不仅服务的需求增加了 系统整体 的资源和服务能力也在同步地扩充 始终能较容易地满足用户的需要 整个体系不 存在瓶颈 理论上其可扩展性几乎可以认为是无限的 3 网络结构健壮性 由于服务是分散在各个节点之间进行的 部分节点或网络遭到破 坏对其它部分的影响很小 p 2 p 网络一般在部分节点失效时能够自动调整整体拓 扑 保持其它节点的连通性 大多数p 2 p 系统还能够根据网络带宽 节点数 负 载等变化不断地做自适应式的调整 4 高性能 价格比 采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点 将 计算任务或存储资料分布到所有节点上 利用其中闲置的计算能力 高速缓存和存 储空间 达到高性能计算和海量存储的目的 通过利用网络中的大量空闲资源 可 以用更低的成本提供更高的计算和存储能力 5 负载均衡 p 2 p 网络环境下由于每个节点既是服务器又是客户机 减少了对传统 c s 结构服务器计算能力 存储能力的要求 同时因为资源分布在多个节点 更好 地实现了整个网络的负载均衡 6 管理困难 信息的存储及发布具有随意性 缺乏集中管理 比如 传统的基于c a 的用户身份验证系统需要重新设计 服务节点的身份难以被验证 服务好坏未知 由于p 2 p 的分布式特点 热门文件常常得到足够的重视 但是冷门文件却更加难 以被获取 7 服务的可靠性较差 由于单个节点未必会积极的加入p 2 p 系统提供服务 p 2 p 网络 实际无法完全利用分散在客户端的资源 并且由于节点的不稳定性 在一些设计较 差的系统中 存在服务突然被中断的可能 再者 由于用户之间直接交互 大量虚 假的服务可能充斥整个网络 p 2 p 系统的公平性问题和安全问题因此更加突出 需 要有特别的机制激励节点提供高质可靠的服务 1 2p 2 p 文件共享系统与流媒体系统 基于点对点模型的应用主要包括信息共享 实时通信 两络游戏 金融服务 信息检索 协同工作 普及计算和网络存储等 基本原理都是在没有服务器或者没有传统意义上的服务 2 中国科学技术大学硕士学位论文 第1 章对等同络综述 器情况下各个节点协同合作传输服务 目前i n t e r a c t 中最为广泛的p 2 p 应用是基于p 2 p 的文 件共享系统和流媒体系统 前者包括m a z e 3 e m u l e 4 a i t t o r r e n t 2 后者包括p p l i v e 5 p v s t r e a m i n g 6 等 1 2 1 基于p 2 p 的文件共享系统 p 2 p 文件共享系统中节点之间互相提供文件传输服务 尽管p 2 p 系统理论上具有比c s 架构更好的扩展性 可以利用分散在网络中的客户节点资源 但是网络本身的分布式特性决 定了文件位置不确定 因此需要首先在分布式网络中采用某种算法找到特定文件 然后直接 建立连接进行传输 根据文件定位算法的不同可以将p 2 p 文件共享系统大致分为三类 集 中查询机制 非结构化p 2 p 结构化p 2 p 1 集中查询算法 这也就是前面介绍的混合式p 2 p 结构 如软件n a p s t e r 2 非结构化p 2 p 这方面的代表g n u t t e l l a 7 q a 用户通过一种类似广播的泛洪查询方 法定位文件 客户向邻居节点发出查询报文 此查询报文经过的任何一个节点将对 报文进行处理 检查本节点是否拥有此文件 若否 报文将继续以泛洪的形式向其 它节点转发 直至定位到文件 3 结构化l y 2 p 由于泛洪查询产生过多的查询报文 极大浪费网络带宽 因此后人不 断的寻找某种精确文件定位的机制 结构化p 2 p 是指在物理网络之上建立一个具 有极强结构性的o v e r l a y 虚拟l q 络 o v e r l a y 的结构性使得文件查询可以按照某种 规律进行 基于d h t d i s t f i b m e dh a s ht a b l e 的p 2 p 网络是结构化p 2 p 的典型代表 它构建了一种完全自主的点对点网络 通过哈希算法实现文件定位 目前这种模式 的典型代表有c h o r d 1 8 c a n 1 9 p a s t r y 2 0 t a p e s t r y 2 1 在这种模式中 每 一节点由其n o d e l d 唯一地标志 各个节点根据n o d e l d 之间的邻近关系构成了一 个虚拟空间o v e r l a y c h o r d 环形 c a n 多维空间 p a s t r y 为树形环形混合 每一个 节点维护一定数量文件索引 文件名 关键字和实际存储位置 维护一个虚拟空间 上的邻居表 邻居节点的n o d e l d 以及i p 地址 对每个文件通过哈希算法算出其关 键字哈希值k 将其存储在某一节点上 此节点的n o d e l d 是所有节点中离k 最接 近的一个 客户端进行查询时首先将根据文件关键字算出此文件的哈希值k 以次 作为查询依据通过结构化的邻居表按照一定规律在相邻节点中逐跳转发 向着离k 值更近的方向前进 直到到达维护该文件索引的节点 找到了文件索引后就可以进 行实际的文件传输 在第5 章中我们将详细介绍c a n 结构 在上面的文件共享系统中 一个文件通常由一个服务节点传输到客户节点 除了这种传 输模式外 另外一类基于f i l e s w a r m i n g 的p 2 p 系统以b i t t o r r e n t 2 为代表 b i t t o r r e n t 将完整 的文件分为多个小块 多个节点之间可以协同合作完成文件的传输 此时不再是单个节点传 输完整的文件 这类系统从一个集中服务器 t r a c k e r 找到可能拥有文件块的邻居节点 然后 邻居节点之间彼此传输小块文件 最后客户端再整合为完整的文件 我们也可以把这类系统 归纳为集中式定位文件 但是因为其文件传输的特殊性人们一般将其独立出来 这类系统的 最大问题是文件分散传输引起较大的网络开销 带来的网络流量比单纯的两点传输更加不易 控制 此外还有一些系统综合应用了b i t t o r r e n t 的f i l e s w a r m i n g 思想和结构化网络思想 2 3 中田科学技术大学硕士学位论文 第l 章对等网络综述 通过结构化网络定位到拥有文件的若干邻居 然后邻居之间按照f i l e s w a r m i n g 的思想彼此 间进行文件互传 1 2 2 基于p 2 p 的流媒体系统 顾名思义 p 2 p 流媒体系统就是通过p 2 p 结构在节点问传输流媒体服务的系统 在p 2 p 流媒体系统中 若干对某个服务感兴趣的节点协同合作传输流媒体 一些中间节点扮演转发 流媒体的功能 不再是服务器直接向客户提供服务 单播 i p 组播或者广播 流媒体系统和 文件共享系统不同 流媒体系统更加强调实时性 强调降低传输延时 不强调内容的可靠性 在流媒体系统中节点同样需要快速加入对某一服务感兴趣的组 但是因为流媒体研究更为复 杂 课题更加广泛 人们一般并不按照定位服务 加入服务组 的算法区分流媒体系统 我们 一般按照节点之间传输流媒体的拓扑图将系统分为三种 基于应用层组播的流媒体系统 基 于m e s h 的多点接收流媒体系统 混合模式的流媒体系统 1 应用层组播系统 这种系统借鉴了传统的i p 组播拓扑结构 所有的节点构成一个 树型的o v e r l a y 由用户节点在应用层完成报文的复制和传输 在树中从根节点传 输到下面的叶子节点 这种结构可以借鉴i p 组播的很多经验 利于维护和管理 主要缺点在于 树型结构导致节点动态性对网络的影响太大 任何一个上游节点失 效会对所有下游节点造成影响 同时该系统无法利用所有节点的上传带宽 只有上 传带宽大于视频播放速率的节点能参与到服务中 因此很多上传带宽较小的节点根 本不提供任何转发服务 这种结构的代表包括 2 2 2 3 2 基于m e s h 的多点接收系统 这种系统也叫基于接收端 r e c e i v e r d r i v e n 的流媒体系 统 和b i t t o r r e n t 类似 在这类系统中节点可以向多个节点发出请求下载某个流媒 体块 网络不再遵守一定的拓扑结构 不再按照树型结构组织 这种结构降低了单 个节点动态性对网络的影响 同时更好的利用所有节点的上传带宽 但是这种系统 存在和b i t t o n e n t 相同的问题 带来较重的网络传输开销 因此需要专门设计针对 流媒体块的调度算法 此类结构的代表包括 2 4 2 5 1 3 混合型流媒体系统 我们实际可以把除了上面两种结构以外的所有结构统称为混合 结构 但是这些系统还可以按照其它方式进行划分 有的系统建立多棵树型 o v e r l a y 每棵树传输一定的流媒体块 比如f 2 6 2 7 这类系统管理复杂 但是可 以克服单树的一些缺点 有的系统结合了组播和单播 将节点按照某种规律组成组 引入s u p e r n o d e 节点 s u p e r n o d e 在一个组中负责流媒体块传输 如n i c e 2 8 还 有的系统虽然仍然是r e c e i v e r c l r i v e n 但是具有一定的结构性 比如d a g 2 9 等等 这些系统都对单纯的应用层组播和r e c e i v e r d r i v e n 结构提出了改进 1 3 对等网络的其它应用 除了上述两种最为广泛的应用之外 p 2 p 的其它应用还包括 4 中国科学技术大学硬士学位论文第l 章对等罔络综述 i 3 1 实时通信 实时通信技术是网络中重要的通信技术 目前的实时通信技术一般采用一个中心服务器 控制用户的认证等基本信息 节点之间直接进行数据通信 i c q o l c q a i m m s n 等是 典型的实时通信系统 这些系统也包含好友列表等基本功能 目前流行的s k y p e 8 是完全采 用p 2 p 技术的即时通信工具 j a b b e r 9 是一个开放源码的实时通信平台 1 3 2 网络游戏 宽带网络游戏对于带宽的消耗较大 通过p 2 p 技术 一方面是可以下载游戏场景 另 一方面可以节省一些昂贵的游戏服务器 游戏用户之间 可以直接通信 而不需要通过游戏 服务器进行转发 1 3 3 金融服务 由于p 2 p 的沟通只单纯涉及沟通的双方 不会有第三者知道双方沟通的信息 所以p 2 p 非常适合发展在线金融服务 美国的b i l l p o i n t 公司已将p 2 p 技术应用于电子商务的付费机 制 通过e b a y 1 0 一个有名的在线拍卖网站 向全球3 5 个国家的使用者提供了这种技术 他们可直接用彼此的信用卡进行交易 1 3 4 信息检索 搜索引擎是目前人们在网络中检索信息资源的主要工具 目前的搜索引擎如 g o o g l e 1 l 天网 1 2 1 等都是集中式的搜索引擎 人们在需要搜索信息的时候要向服务器发 出指令 由服务器把检索出来的相关目录通过一定的排序法则呈现在用户面前 这就会不可 避免的带来一些问题 比如 如果服务器信息更新周期长 将有大量过时的信息产生 受设 备条件影响 服务器收集的信息有限 受服务器制约 存在单点失效问题等 而p 2 p 将以用户为中心 所有的用户都是平等的伙伴 所有人都共享了他们认为最有 价值的东谣 这将使互联网上信息的价值得到极大的提升 j x l as e t h 0 3 采用p 2 p 的搜 索技术来有效的跟踪数据的更新速度 提高访问的有效性以及检索的效率 p a n d a n g o 1 4 搜 索引擎也利用了p 2 p 的技术 文件共享系统也可以看作是一种信息检索系统 1 3 5 协同合作 协同工作是指多个用户之间利用网络中的计算平台互相协同完成计算任务 通过采用 p 2 p 计算技术个人和组织可以艟时采用各种方式建立在线 非在线的协同应用环境 这使得 中圊科学技术大学硕士学位论文 第1 章对等网络综述 在不同地点的参与者可以在一起工作 采用文件直接共享的方式可以保证系统中的每个人所 获得的信息总是最新的 同时节省了采用单独服务器时对该服务器存储以及性能的要求 g r o o v e 1 5 是基于i n t e m e t 的p 2 p 协同应用软件的典型代表a 1 3 6 普及计算 普及计算技术研究的是如何充分利用网络中各种计算单元来共同完成大规模的计算任 务 由于单一计算单元的计算能力总是有限的 因此人们一般采用并行技术 分布式技术将 多个计算单元节点联合起来共同完成大规模的计算任务 目前网络中的计算机的计算能力一 直没有得到充分利用 人们期望能够充分利用网络中的闲散计算能力来完成大规模的计算任 务 p 2 p 计算技术则为普及计算技术的发展提供了新的机遇 s e t l h o m e 1 6 是u cb e r k e l e y 大学启动的普及计算的研究项目 目前大约吸引了一百万台计算机参与研究 g r i d 1 7 是 研究普及计算的典型代表 本章小结 本章概括性地介绍了p 2 p 出现的背景 特点和应用 互联网的主机数和用户增加使得 网络边缘分布了大量的潜在计算和存储资源 p 2 p 网络架构的出现的正是为了开发利用这些 资源 缓解人们对集中式服务的需求 我们总结了p 2 p 的高扩展性和健壮性等优点 同时 指出在可管理性和服务的可靠性方面p 2 p 系统存在的不足 我们分别针对文件共享系统和 流媒体系统概括地介绍p 2 p 应用 同时还介绍了p 2 p 的其它一些应用环境 论文结构 本文的第2 章将引出p 2 p 系统中需要制定激励策略的原因 即 分布式的系统结构决 定了需要激励措施激励节点提供高质量的服务 第2 章中同时介绍了研究激励措施的几大理 论基础 博弈论和应用密码学 从第3 章开始到第5 章 本文从博弈论角度提出一种针对 p 2 p 系统的激励算法 从数学建模角度提出一种针对新加入节点的双重信誉度算法 从应用 密码学角度对信誉度的分布式维护进行改进 本文一共有如下三个贡献 1 第3 章利用博弈论的思想 提出一种针对流媒体的计费算法 该算法主要目的是为 了降低流媒体系统的服务开销 通过更好的选择服务节点来降低开销 通过博弈论 设计的计费算法来保证服务节点正确汇报自己的开销 防止服务节点的错误报价 以此真正降低服务开销 激励节点提供服务 2 第4 章提出一种利用双重信誉度抵制w h i t e w a s h i n g 现象的算法 该算法可以用于 文件共享或者流媒体系统中 其基本思想是通过对新加入节点维护双重信誉度 一 方面激励它提供服务 一方面对它采取不完全信任的策略 以此过滤掉新加入节点 中的不良节点 6 中嗣科学技术大学硕士学位论文第l 章对等网络综述 3 第5 章提出一种基于h a s h c h a i n 的链式信誉度存储方案 利用这种方案分布式存放 的信誉度 可以更好的保证信誉度维护节点不能破坏自己维护的信誉度 防止节点 之间的勾结或恶意诋毁 但是本论文没有讨论信誉度维护中存在的其它一些实际问题 比如信誉度指数究竟应当 由哪些量构成 比如 信誉度和服务的大小相关还是和服务速率相关 是否和服务内容相关 等等 系统开销究竟应当如何计算 比如 如何包括网络传输的开销 节点接收服务的开销 是否可以忽略 等等 本文没有讨论其它一些针对节点信誉度的攻击 s y b i l a t t a c k 3 0 等 本文通过使用信誉度来保证服务更加可靠 考虑的安全问题实际上仅仅是针对服务的攻击 但是没有考虑其它类型的攻击 如针对路由的攻击 3 i 等等 7 中国科学技术大学硕士学位论文 第2 章对等网络中的激励策略和公平性问题 第2 章对等网络中的激励策略和公平性问题 2 1 研究背景 f 2 p 系统尽管具有系统容错性高 容量大 可扩展性好等优点 但是缺点同样明显 由 于p 2 p 网络的分布式特性 单个节点具有更大的自由度 服务质量因此无法得到保证 节点 动态性使得服务不稳定 节点的自私性导致只有少部分节点愿意提供服务 同时少部分恶意 节点更容易对其它节点发起攻击 这些攻击包括针对文件的攻击和针对路由的攻击d q 系 统测量表明 3 2 p 2 p 网络中大量用户 约7 0 只获取服务 不提供服务 这导致了p 2 p 网络 较为严重的不公平性问题 有的节点只获取服务不提供服务 f r e e t i d i n g 3 2 还有一部分节 点通过欺诈手段增大自身利益 针对文件进行攻击 例如随意伪造文件 随意中止服务等 3 3 甚至有的节点之间互相勾结联合进行攻击 s y b i la t t a c k j 0 在传统网络中 由于服务 总是由中心服务节点提供 公平性问题和服务的安全性可靠性问题并不突出 但是在p 2 p 中 我们需要激励节点提供安全可靠的服务 为了激励节点提供服务 人们一般通过在系统中维护一定的公平性指数来解决p 2 p 网络 中的公平性问题 一个节点拥有一定的公平指数 节点能够获得的服务质量由指数大小决定 多劳多得 以此激励节点提供服务 但是公平性维护一般用于判断用户是否真正提供服务 而并不考虑服务的性质和服务质量 如 3 4 仅仅以传输文件次数表征系统公平性 d 5 1 使用 博弈论观点讨论了如何根据公平性指数对用户提供区分服务 但是仅仅根据传输的文件大小 计算公平性指数 其它一些激励节点提供服务的方案包括 基于互惠的公平性策略 3 6 1 d 7 1 任何一次文件传输 客户节点必需向服务节点证明自己曾经向其它节点提供服务 这种证明 牵涉到很多节点 容易受到恶意节点联合攻击 实际p 2 p 系统不能仅仅根据自私与否区分用户是否提供服务 还需要区分用户提供什么 样的服务 恶意用户可能提供伪造文件 或者根据系统结构的缺陷随意中止服务 或者抵赖 已有的服务 因此更多研究者讨论p 2 p 系统中信誉度维护 信誉度维护的基本思想是 每个用户拥有一定的信誉度值 t r u s t 根据节点的t r u s t 为 客户节点提供不同的服务质量 客户节点也选择t r u s t 较高的服务节点获取服务 以此降低 被欺骗的可能性 每次交易之后 客户节点对本次服务进行评价 系统收集这种评价 更新 服务节点的t r u s t 服务节点同时也针对本次服务对客户进行评价 由系统更新客户节点的 t r u s t 因此信誉度是一个历史数值 表征节点在整个网络中长期的表现 由多次服务的服 务质量来决定 包含了更为全面的信息 在已有的研究中 r a r m a 3 8 给出一种结构化p 2 p 中信誉度维护方案 e i g e n t r u s t 3 9 同时讨论了t r u s t 的维护和计算 此外 大量研究讨论分 布式系统中t r u s t 的更新算法 即 如何抽取单次服务的信息 对整体的信誉度进行更新 3 3 4 0 1 1 4 1 都在某些方面获得了改进 信誉度维护实际是公平性维护的扩展 因为它不仅仅 考虑节点是否提供服务 还考虑了提供怎样的服务 在后面的描述中 我们将公平性指数统一到信誉度中 用信誉度 t r u s t 概括一个节点 9 中田科学技术大学硕士学位论文第2 章对等同络中的激励策略和公平性问息 在系统中的表现 这种表现既包括节点提供服务的多