（计算机软件与理论专业论文）基于多chord环的p2p+vod系统研究.pdf

大连理t 大学硕十学位论文 摘要 在互联网上提供大规模的v o d ( 视频点播) 服务是一项具有挑战性的工作。传统的视 频点播放方式是基于c s ( 客户端服务器) 模式，面临网络带宽受限的问题，服务器很容 易成为瓶颈。p 2 p ( 对等网络) 技术打破了传统的c s 模式，在网络中的每个结点的地位都 是对等的。每个结点既充当服务器，为其他结点提供服务，同时也享用其他结点提供的 服务，很好地解决了网络带宽瓶颈问题。p 2 p 技术以其可扩展性、高容错性、健壮性等 特点已得到迅猛的发展，并逐步应用到v o d 领域。 本文在深入研究p 2 pv o d 关键技术的基础上，给出了基于多c h o r d 环的p 2 pv o d 系统( m c h o r d v o d ) 。m c h o r d v o d 针对现有网状结构p 2 pv o d 资源定位效率低、时延大 等问题，采用基于多c h o r d 环的d h t 覆盖网络( m c h o r d ) 对资源进行定位。m c h o r d 将播 放同一节目的节点组织到一个c h o r d 环中，由于节点在使用v o d 服务来点播节目时， 其资源检索具有非常强的关联性，这样，通过记录节点在前一次检索时的路由信息，能 进一步缩短资源检索时的路由长度。 在考虑到现有网状结构p 2 pv o d 在数据分发时所采用的接收者驱动模式所存在的 问题，给出了基于定制与合作的数据分发策略，该策略通过定制的方式从发送节点定制 数据，在存在播放位置相近的节点时，播放位置相近的节点采用合作的方式共同完成视 频数据的获取。 由于p 2 pv o d 系统视频节目众多，观看同一视频节目并且播放位置相近的节点很 少，这导致只能有少量的节点进行p 2 p 通信，不能充分体现p 2 p 网络的优势。本文采用 内存缓存与磁盘缓存相结合的方式把播放过的视频数据存储起来，以增加提供服务的节 点的数量。同时，本文给出了基于视频热度的缓存策略，以实现系统的负载均衡。 在p 2 p s i m 上的仿真实验表明，在同等条件下，与同类体系的p r o m i s e 比较， m c h o r d v o d 在播放启动时延、v c r 操作时延、节目提供节点压力等性能指标上，均优 于同类系统p r o m i s e 。 关键词：p 2 p ；c h o r d ；视频点播；数据分发；缓存策略 大连理上人学硕士学位论文 r e s e a r c ho np 2 pv o d s y s t e mb a s e do nm u t i l c h o r d a b s t r a c t i ti sac h a l l e n g i n gj o bt oo f f e ral a r g es c a l es e r v i c eo fv o d ( v i d e oo nd e m a n d ) o nt h e i n t e r n e t t h et r a d i t i o n a lm e t h o do fv o di sb a s e do nt h ec s ( c l i e n t s e r v e r ) m o d e l ，w h i c hi s f a c i n gt h eb a n d w i d t hp r o b l e ma n dt h es e r v e ri se a s yt ob e c o m eab o t t l e n e c k p 2 p ( p e e rt o p e e r ) t e c h n o l o g yb r e a k st h et r a d i t i o n a lc sm o d e lb e c a u s ei tm a k e se a c hn o d ei nt h en e te q u a l t oe a c ho t h e r n o to n l yan o d ew o r k sa sas e r v e rt os e r v eo t h e r sb u ta l s og e t ss e r v e db yo t h e r s t os e t t l et h eb a n d w i d t hp r o b l e mv e r yw e l l p 2 pt e c h n o l o g yg e t sar a p i dd e v e l o p m e n tb e c a u s e o fi t se x p a n s i b i l i t y , f a u l tt o l e r a n c ea n dr o b u s t n e s se t ca n di sa p p l i e di nv o df i e l dg r a d u a l l y t h i sp a p e rh a sc o n d u c t e di n d e p t hs t u d i e so nk e yp r o b l e m so fp 2 pv o d ，o nt h eb a s eo f w h i c h ，t h i sp a p e rp r o p o s e sap 2 pv o ds y s t e m ( m c h o r d v o d ) b a s e do nm u l t i c h o r d p 2 p v o dl o c a t e sr e s o u r c e si n e f f i c i e n t l yw i t hal o n gt i m es p a no nt h ep r e s e n tn e ts t r u c t u r e a i m i n g a tt h i sp r o b l e m ，m c h o r d v o du s e sad h to v e r l a yn e t w o r k ( m c h o r d ) b a s e do nt h e m u l t i c h o r dt ol o c a t er e s o u r c e s m c h o r dp u t sn o d e sp l a y i n gt h es a m ec o n t e n t si no n ec h o r d b e c a u s ew h e nn o d e sa r ep l a y i n gp r o g r a m su s i n gv o d ，t h es e a r c h e dr e s o u r c e su s u a l l yh a sa s t r o n gr e l e v a n c y ，t h es y s t e mc a nf u r t h e rr e d u c et h er o u t el e n g t ht h r o u g hr e c o r d i n gt h er o u t e i n f o r m a t i o no fl a s tr e t r i e v i n g c o n s i d e r i n gp r o b l e m so fp 2 pv o di nt h er e c e i v e rd r i v i n gm o d e lu s e dw h i l ed a t ai s d i s t r i b u t e do nt h ep r e s e n tm e s ho v e r l a y , t h ep a p e r p r o p o s e sac u s t o m i z a t i o na n dc o o p e r a t i o n b a s e dd a t ad i s t i l b u t i o ns t r a t e g yi nw h i c hd a t ai sc u s t o m i z e df r o mt h es e n d e ra n dw h e nt h e r e a r en o d e sa tn e a rp l a y i n gp o s i t i o n st h en o d e sc o o p e r a t ew i t he a c ho t h e rt of i n i s ht h ev i d e o d a t ar e c e i v i n g o w i n gt ot h en u m e r o u sv i d e o sb u tt h es m a l ln u m b e ro fp e e r sw h ow a t c h i n gt h es a m e v i d e oa tn e a rp l a y i n gp o s i t i o n si nv o d s y s t e m i tl e a dt oo n l yaf e wp e e r sc o m m u n i c a t i o n w i t he a c ho t h e rb yp 2 pn e t w o r k s ot h ep 2 pn e t w o r kl o s ti t sa d v a n t a g e s i nt h i sp a p e r ， m e m o r yc a c h ec o m b i n ew i t hd i s kc a c h ei su s e dt oc a c h et h ed a t aw h i c hh a sb e e np l a y e ds oa s t oi n c r e a s et h en u m b e ro fp e e rw h oc o u l dp r o v i d es e r v i c e a n dav i d e op o p u l a r i t yb a s e d c a c h i n gs t r a t e g yw a sp r o p o s e dt of u l f i l lt h el o a db a l a n c i n go ft h es y s t e m s i m u l a t e de x p e r i m e n t so np 2 p s i mp r o v et h a tu n d e rt h es a m ec o n d i t i o nc o m p a r e dw i t h t h ep r o m i s eo ft h es a m ek i n d ，m c h o r d v o do u t p e r f o r m so t h e rs y s t e m so nt h ef u n c t i o n a l i n d i c e so fs t a r t i n gd e l a y , v c ro p e r a t i n gd e l a ya n dn o d ep r e s s u r eo fs u p p l y i n gp r o g r a m se t c k e yw o r d s ：p 2 p ；c h o r d ；v i d e o - - n o d e m a n d ；d a t ad i s t r i b u t i o n ；c a c h i n gs t r a t e g y i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：基王垒g 垒q ! 壁巫鲍里2 y q 旦丕统盟窥 作者签名： 鲑塑缘 日期：2 竺量年二月卫日 人连理j ：人学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 作者签名： 导师签名： 日期： 2 量年眨月j 上日 日期：碰年止月驵日 人连理_ 人学硕士学位论文 1绪论 1 1 课题研究的目的和意义 2 0 0 8 年7 月，中国互联网络信息中，心( c n n i c ) 发布了第2 2 次中国互联网报告，报 告显示截至2 0 0 8 年6 月，网民数已达到2 5 3 亿人，其中网络视频的使用率为7 l ，用 户已达1 8 亿人，是中国的第四大网络应用。 互联网数据中- c , , ( d c c i ) 发布的2 0 0 8 中国互联网调查报告显示，2 0 0 7 年中国点播与 直播市场规模达到9 亿元，较2 0 0 6 年增长3 8 5 ，由于视频分享以及p 2 p 视频播放平 台等视频内容的挤压，未来点播、直播市场规模增长率将放缓，预计2 0 0 8 年中国点播 与直播市场规模将达1 2 亿元，预计增长率达3 3 3 。 目前国外网络流量的5 0 由p 2 p 流量占据，学者预测在未来几年p 2 p 的流量将会 占到网络流量的7 0 以上。 这一系列数字向人们展示着，随着上网人数的不断增加，网络、编解码等技术的不 断发展，流媒体应用将渗透到人们生活娱乐的各个方面，网络视频已经成为人们不可缺 少的主要网络应用之一。然而，随着宽带网络技术的发展，用户对视频点播服务质量有 了更高的要求，对网络视频服务器的性能带来了巨大的挑战。如一部码率为 4 7 8 k b p s ( 4 7 8 x 1 0 2 4 比特每秒) 的视频。在传统的c s ( 客户服务器) 模式下，当有1 0 0 0 个 用户同时播放时，服务器需要的带宽达到约4 7 6 m b ，服务器的网络带宽及其i o 带宽将 成为整个系统性能的瓶颈，无法容纳大规模的视频服务。为了解决这一问题，在不降低 服务质量的情况下，使用p 2 p 技术，通过充分利用边缘计算机的网络带宽和储存能力以 降低服务器提供服务时承受的压力，就成为了解决问题的关键。视频直播和点播( v o d ) 是网络视频应用的两种表现形式，本文主要集中在基于p 2 p 的视频点播( p 2 pv o d ) 。 在现有网络架构中，优化和改进p 2 pv o d 传输技术，突破传统的视频点播服务瓶 颈，使用户主观体验到高品质的v o d 服务具有巨大的现实意义。本课题研究的目的就 是要建立相关的p 2 pv o d 系统模型，改进、优化现有的用于p 2 pv o d 的资源定位技术、 数据分发策略、缓存管理策略，从而为提供优质的v o d 服务作贡献。 1 2p 2 p 与p 2 pv o d 概述 1 2 1p 2 p 概述 ( 1 ) p 2 p 的由来 p 2 p 是英文p e e r - t o p e e r 的缩写，p e e r 在英语里有“同等者 、“同事 和“伙伴” 基丁多c h o r d 环的p 2 p v o d 系统研究 等意义。这样一来，p 2 p 也就可以理解为“伙伴对伙伴”的意思，或者称为对等网。p 2 p 技术并不是一种新兴的技术，2 0 世纪7 0 年代中期，源于局域网的文件共享p 2 p 技术就 开始流行起来了。目前大家所关注的p 2 p 技术，是旧有技术的新的模式。首开p 2 p 之风 最有名的计划是美国柏克利大学开展的寻找外星生命的s e t i h o m e 研究计划。1 9 9 9 年， s e t i i h o m e 开始使用p 2 p 计算方法来分析星际间无线电信号，寻找宇宙中可能存在的 其他外星文明证据。p 2 p 技术串联所有参与研究计划者闲置的电脑来执行庞大复杂的运 算，然后把结果传到s e t i h o m e 总部。也正是s e t i h o m e 计划推动了最近的p 2 p 技 术热潮。2 0 0 0 年用于共享m p 3 音乐的n a p s t e r 1 】软件与美国唱片界的一场官司将p 2 p 技 术重新带回人们的视线。之后，各种基于p 2 p 的应用风起云涌，p 2 p 技术也成了计算机 研究的热点技术，各个领域的计算机专家都开始了对p 2 p 技术及其应用的研究。 ( 2 ) p 2 p 的定义 p 2 p 目前还没有被人们广泛接受的定义，i b m 为p 2 p 下了如下定义。 p 2 p 系统由若干互联协作的计算机构成，且至少具有如下特性之一：系统依存于边 缘化( t i e 中央式服务器) 设备的主动协作，每个成员直接从其他成员而不是从服务器的参 与中受益；系统中的成员同时扮演服务器与客户端的角色，相互之间可以共享资源，并 且可以任意地加入和离开网络；系统应用的用户能够意识到彼此的存在，构成一个虚拟 的或实际的群体【2 j 。 。简单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互信息，p 2 p 使得 网络上的沟通变得更容易，更直接地共享和交互，真正地消除中间商。p 2 p 技术就是用 户可以直接连接到其他用户的计算机进行交换文件，而不是像过去那样连接到服务器去 浏览与下载。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态，重返“非 中心化”，并把权力交还给用户。p 2 p 看起来似乎很新，但是正如b 2 c 、b 2 b 是将现实 世界中很平常的东西移植到互联网上一样，p 2 p 并不是什么新东西，在现实生活中我们 每天都按照p 2 p 模式面对面地或者通过电话交流和沟通。 ( 3 ) p 2 p 网络与传统网络的对比 在p 2 p 网络中，弱化了服务器的功能，甚至取消服务器，任意两台p c 机互为服务 器客户机，即使只有一个对等点存在，网络也是处于活动状态的，节点( p e e r ) 可以随意 地将自己的信息发布到网络上。p 2 p 技术将导致信息数据成本资源向所有用户的计算机 均匀分布，即“边缘化”趋势。 首先，c s ( c l i e n v s e v e r ，客户端服务器) 模式下的因特网是完全依赖于中心服务器 的，没有服务器的p 2 p 不足之处在于不易管理，而对c s 网络，只需要在中心点进行管 人连理上人学硕士学位论文 理，从而带来的不足就是p 2 p 网络中数据的安全性难于保证。p 2 p 技术与c s 技术性能 比较如表1 1 所示。 表1 1p 2 p 网络和传统网络的性能比较 t a b 1 1p e r f o r m a n c ec o m p a r i s o nb e t w e e np 2 pn e t w o r ka n dt r a d i t i o n a ln e t w o r k 在传统的c s 模式中，客户端之问要进行文件交换必须经过服务器，随着节点的增 加，服务器的负担越来越重，并逐渐形成系统瓶颈，一旦服务器崩溃，整个网络也随之 瘫痪。而在p 2 p 网络中每个节点的地位都是对等的，每个节点既可以充当服务器，为其 他节点提供服务，同时也充当客户端，享用其他节点提供的服务。同时，由于每个节点 在工作时都在向网络贡献资源( 存储空间、c p u 周期等) ，因此对等点越多，网络的性能 就越好。 其次，c s 模式下的因特网完全依赖于中心点服务器，没有服务器就根本无法 工作，网络也就毫无意义可言。而在p 2 p 网络中，每个节点都可以被看作是服务器，可 以随意地将自己的信息发布到网络上，以供其他节点交换共享。 最后，在c s 模式下即使客户端有大量的闲置资源，如果没有得到服务器的响应资 源也无法被利用，资源利用率比较低下。而在p 2 p 网络中，一切闲散资源都有机会得到 利用，具有很高的资源利用率。 1 2 2p 2 pv o d 概述 v o d ( v i d e o o n d e m a n d ) 艮 j 视频点播，是集动态图像、静态图片、声音、文字等信息 为一体的，为用户提供实时、高质量的按需点播服务的系统，也称交互式点播系统。它 基于多c h o r d 环的p 2 p v o d 系统研究 是一种以图像压缩技术、宽带通信技术、计算机技术等现代通信手段为基础发展起来的 多媒体通信业务。p 2 pv o d 是在传统的v o d 系统基础上发展而来，当传统的v o d 系统 无法满足现代流媒体的需求时，产生了p 2 p 方式的v o d 系统。 传统的v o d 采用c s 单播模式，服务器的负载能力基本上就是整个系统的服务能 力，因此不具有较高的扩展能力。在简单c s 单播模式的基础上，为了保证用户的服务 质量，还可以采用流媒体内容分发网络( c o n t e n td i s t r i b u t i o nn e t w o r k ，简称c d n ) | 3 1 技术， 把视频源推向网络边缘。但要实现大规模的应用需要部署大量的边缘服务器，代价较为 昂贵。 研究表明，由于人类行为的固有特征，绝大多数的用户请求都集中在少数的热门影 片，而且由于用户数量巨大，同一时间点播相同视频节目的可能性很高，故此，可以利 用一些基于p 组播技术的策略来设计v o d 系统，以节省网络带宽，提高系统容量。采 用口组播技术的v o d 系统一般使用静态或动态服务器通道调度方案，大致分为以下几 类：周期广播方式( p e r i o db r o a d c a s t i n g ) 吲、批处理方案( b a t c h i n g ) 【5 】、补丁方案q a t c h i n g ) 】、 p i g g y b a c k 方案【7 】和流合并方案【8 】等。 尽管用口组播可用于建立可扩展的v o d 服务，但由于缺乏广泛部署的具有组播能 力的网络和专用代理服务器【9 1 0 】，提供这样的服务仍然是具有挑战性的。 ： c s 构架的服务器瓶颈效应和口组播的难以实现，使得更多的人开始研究p 2 p 在 v o d 中的应用。在p 2 p 网络中，每个节点要承担双重任务，首先要从其他节点获得服 务，其次还要网络中的其他节点提供服务，一般还需要具有一定的路由和查询功能。p 2 p 最大的优势在于不必改变传统的网络结构，在现有i n t e r n e t 层次模型上，只需要改动应 用层的分发和路由策略，就可以相对c s 模式大幅提高扩展性，且易于实现。 1 3p 2 pv o d 面临的挑战 p 2 pv o d 是为解决传统v o d 所面临的问题而提出的在p 2 p 环境下实现高质量的 v o d 服务。其所面临的挑战是由v o d 的特点和p 2 p 覆盖网络的特点所产生的。下面通 过对v o d 的特点以及对v o d 实现带来挑战的一些p 2 p 网络的特点进行分析，进而得到 当i j i p 2 pv o d 所面临的挑战。 ( 1 ) v o d 的特点 v o d 的资源数目：预保存节目v o d 有较多数量的影片供点播。 内容：预保存节目v o d 已知要播放的全部内容，可以安排调度播放的内容。 用户观看要求：用户可以从一部视频的任何部分开始观看。 v c r 交互操作：v o d 存在各种v c r 交互式操作，例如快进、快退、拖拽播放、 大连理1 i 大学硕十学位论文 暂停等。 ( 2 ) p 2 p 覆盖网络的特点 网络异构性：现在的i n t e m e t 是一张很大的混合网络，a d s l 、i s d n 、t 1 等不 同的接入技术让不同的节点间具有不一致的特性，包括不同的上下行带宽、不同的拓扑 结构、不同的通信协议和不同的服务质量等等。 非中心化管理：p 2 p 的最大特征就是不存在制约整个网络性能的中心节点，但 作为服务提供商会面临着许多难以控制的后果。如非法用户的恶意攻击、各个节点想尽 办法逃避义务而同时还可以获得其他节点的服务等等。 节点的不可靠性：在p 2 p 系统中，每个节点都是独立的个体。视频点播在播放 时实时性要求较高。不论节点的加入或退出都会对其他的节点产生影响。因此，如何把 节点的不合作行为对其他节点造成的影响降到最低，对于保证服务的质量是十分重要 的。 由于v o d 资源数目较多，且用户可以从视频的任何部分开始观看，使得视频片段 的可以缓存数目很少，而p 2 p 网络的非中心化管理，使得这些为数不多的缓存资源的定 位变得更加困难。p 2 p 网络中节点的不可靠性、网络的异构性，使得p 2 pv o d 的服务质 量( q o s ) 无法保证，q o s 实现困难。v c r 交互操作的实现，要求用户在视频观看过程中 可以快速定位到任意位置的视频片段，但这一点对于非中心化管理的p 2 p 网络来说并不 容易，使得p 2 pv o d 的v c r 交互操作实现困难。 1 4 研究目标 本文重点关注视频点播中的三个关键问题：支持v c r 操作、降低节目提供节点的 带宽压力、减小视频播放节点的播放启动时延及v c r 操作时延。 本文的研究目标是设计实现一个不依赖于任何中心节点的p 2 pv o d 系统，该系统 能够支持v c r 操作，能利用p 2 p 技术降低对服务器的压力，同时又能保证视频播放节 点的播放质量。它需要满足下面特征。 ( 1 ) 支持v c r 操作：可以支持v c r 操作，如快进、后退、拖拽播放等。 ( 2 ) 降低节点压力：不仅仅是降低系统内无效数据的流动，如避免重复包的传输等； 另一方面增加系统中视频节目数据块的拷贝数，使得节点播放时可以从更多的节点得到 数据块，降低节目提供节点的压力。 ( 3 ) 降低时延：降低节点播放时的启动时延以及v c r 操作时延，给用户带来良好的 用户体验。 ( 4 ) 避免单点失效：某些节点的离开，系统应能够自动调整，尽量不影响节点的播 基丁二多c h o r d 环的p 2 pv o d 系统研究 放质量。 ( 5 ) 扩展性：可以支持海量的视频点播服务。 ( 6 ) 鲁棒性：降低节点的离线、网络的抖动对服务质量的影响。 ( 7 ) 安全性：虽然安全不是本系统关注的重点，但安全对一个p 2 p 系统也是至关重 要的，特别是防止数据篡改，因为在采用p 2 p 技术的系统中，这种经过篡改的数据很可 能会扩散，波及很多节点。 1 5 本文工作及各章节安排 基于p 2 p 的v o d 技术得到广泛的研究，并取得了较大的进展，但是仍然存在一些 技术问题，需要进一步的研究。因此本文作了以下研究。 ( 1 ) 针对网状结构p 2 pv o d 资源定位效率不高、实现v c r 操作困难等问题，采用 基于多c h o r d 环的d h t 网络作为p 2 pv o d 的定位技术，以降低了资源定位所带来的时 延。 ( 2 ) 考虑到现有网状结构数据分发策略采用接收者驱动模式所带来的传输时延较大 的问题，本文采用基于定制及合作的策略以降低数据传输时延。 ( 3 ) 节目提供节点压力过大的主要原因之一是p 2 p 网络中可以提供视频下载服务的 节点过少，本文采用内存缓存与磁盘缓存相结合的方式把播放过的视频数据存储起来， 以增加提供服务的节点的数量。同时，本文给出了基于视频热度的缓存策略，以实现系 统的负载均衡。 本文共分四章： 第一章首先介绍了互联网发展现状，指出视频点播是互联网未来发展的一个重要应 用，然后对p 2 p 技术以及p 2 pv o d 技术进行了概述，指出p 2 pv o d 所面临的挑战，接 着提出了本文的研究目标，最后介绍了本文的工作及各章节的安排。 第二章分析了现有的p 2 pv o d 的关键技术。包括p 2 p 资源定位技术、内容分发策 略、节点选择策略。 第三章详细介绍了m c h o r d v o d 系统的设计思想、系统结构、p 2 p 覆盖网络的设计、 内容分发策略及缓存策略。 第四章通过仿真实验，对m c h o r d v o d 以及p r o m i s e 进行了模拟，对m c h o r d v o d 所采用的基于多c h o r d 环的d h t 定位技术性能进行了分析，并对m c h o r d v o d 与 p r o m i s e 的播放启动时延、v c r 操作时延以及节目提供节点的压力等进行了对比分析。 最后是本文的研究总结和展望。本章主要是针对前面章节的研究工作给出一个总 结，同时给出了需要进一步研究的方向。 人连理i ：大学硕士学位论文 2p 2 pv o d 的关键技术 p 2 p 中需要普通节点提供服务器的功能，而这些节点与传统的服务器相比存在一定 差异，如提供服务的节点位置不固定、服务能力有强有弱、节点频繁加入退出等。v o d 本身又有其独特性质，如数据存储量大、带宽占用高、持续服务时间长、高q o s 要求等。 因此，在p 2 pv o d 中，在如何充分利用众多节点资源、保证服务质量等方面面临着许 多挑战，需要考虑更多的一般v o d 中无须考虑的技术问题。例如，在p 2 p 网络中如何 定位可以提供服务的节点，当有多个服务节点时如何选择最佳服务节点，采用何种数据 分发策略能有效地节约系统和网络资源等。下面首先介绍了p 2 pv o d 系统的分类，然 后对p 2 pv o d 中使用到的资源定位技术、节点选择策略、数据分发策略等关键技术分 别进行介绍和分析。 2 1p 2 pv o d 系统的分类 在对p 2 pv o d 系统进行研究的过程中，可以根据数据分发方式的不同、服务器的 体系结构差异以及数据源的多少对p 2 pv o d 系统进行分类，一般来说可以采取下面几 种分类方式。 ( 1 ) 按照数据分发过程中各节点组成的数据分发网络进行化分，将主流的p 2 pv o d 系统分为两类：树状结构和网络结构【】。 ( 2 ) 根据服务器的体系结构进行化分，将p 2 pv o d 系统分为四类：可以分为单索引 多服务器( s i m s ) 、多索引节点多服务器( m i m s ) 、多独立索引服务器( m i l s ) 、完全分布式 多服务器r ( f a m s ) 1 1 2 j 。 ( 3 ) 按网络中资源的存放方式的不同以及分发过程中数据的传输途径的不同，将 p 2 pv o d 系统分为四类：单源单路径、单源多路径、单源分代、多源多路径【l 3 1 。 本文采用第一种分类方式对p 2 pv o d 的关键技术进行介绍与分析。将p 2 pv o d 分 成树状结构与网状结构，有利于对各类p 2 pv o d 系统的优缺点进行分析与比较。 2 2p 2 p 资源定位技术 根据文献 1 4 】，p 2 p 资源定位技术按其拓扑结构可分为四类：集中式p 2 p 网络、非 结构化p 2 p 网络、结构化p 2 p 网络和混合式p 2 p 网络。这几种网络拓扑结构分别采用 了不同的资源定位和路由模型。本节将对这四种p 2 p 资源定位技术进行介绍，并分析各 自的特点以及各自的优缺点。 基于多c h o r d 环的p 2 p v o d 系统研究 2 2 1集中式p 2 p 网络 集中式p 2 p 网络基于一台或多台中央索引服务器，中央索引服务器负责协调或调度 单独的注册节点上的资源。一般地，中央服务器维持着p 2 p 网络中节点的资源的中央目 录，并协调节点间的交互，系统的关键功能( 如文件下载或分布式计算) 则由分布的单独 的节点完成。因此，这类系统不是纯p 2 p 系统，而是混合的p 2 p 系统。n a p s t e r ，s e t i h o m e 和b i t t o r r e n t t ”j 都是典型的集中式p 2 p 网络。 集中式p 2 p 网络实现了资源查询定位与资源传输的分离，使中心服务器的压力和带 宽消耗大为降低，文件传输更加快捷。n a p s t e r 是最早出现的采用集中式p 2 p 网络结构 的系统。n a p s t e r 通过一个中央服务器保存所有n a p s t e r 用户上传的音乐文件索引和存放 位置的信息。当某个用户需要某个音乐文件时，首先连接到n a p s t e r 服务器，在服务器 进行检索，并由服务器返回存有该文件的用户信息或主机信息，再由请求者直接连接到 文件的所有者进行文件传输。 集中式拓扑的一个重要的优点是简单。因为资源发现可以由中央目录来实现，所以 它非常灵活和高效。但集中式p 2 p 网络可能会发生单点失效、网络热点、诉讼等其他问 题。其拓扑结构如图2 1 所示。 这种架构的问题是当数据量( 索引数据) 非常大时，服务器的存储能力和运算能力会 难以满足需求，查询响应时间会比较长。这一问题当然可以通过提升服务器的性能来解 决，但是代价在所难免。同时，随着用户的迅速增长，系统也面临着扩展性方面的问题。 卜 一一 图2 1 集中式p 2 p 网络模型 f i g 2 1 c e n t r a l i z e dp 2 pn e t w o r km o d e l 大连理t 大学硕+ 学位论文 2 2 2 结构化p 2 p 网络 结构化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 ) 的结构。和非结构化p 2 p 网络相比，结构化p 2 p 网络对文档 在系统中的存放位置有严格的控制并且节点之间的关系比较紧凑。结构化p 2 p 网络的最 大优点在于它可以在o ( 1 0 9 n ) ( 其中i v l 是系统中节点的数目) 的跳数之内完成文档的路由 和定位。结构化p 2 p 网络的主要特点是自组织、可扩展、负载均衡以及较好的容错性。 和非结构化p 2 p 网络主要用于文件共享领域不同，结构化p 2 p 网络的这些优良特性使得它 可以应用在对可靠性和扩展性要求比较高的场合。 简单的理解，结构化p 2 p 网络中每个文档对应一个m 比特长的唯一标识符，可以 将文档的这个唯一标识符理解为一个虚拟空间中的地址。整个虚拟空间被划分为很多个 区域，每个区域包含了若干连续的虚拟地址，系统中的每个节点负责这些区域中的一个 或多个。文档被存储在负责它的虚拟地址所在区域的节点中，对文档的插入和查找操作 的路由通过文档的虚拟地址进行。虚拟空间中区域的划分和负责每个区域节点的选择都 是动态的，每次节点加入或者离开系统都会导致动态的调整。文档的唯一标识符是通过 对文档内容或u r l 进行哈希变换得到的，一致性哈希变换( c o n s i s t e n th a s h i n g ) 1 6 l 是最常 用的算法。致性哈希变换的特性是可以将变换后得到的m 比特长的文档标识符均匀分 布在一个值空间中，不同文档产生相同哈希值的概率几乎为零。通过对节点的p 地址 进行相同的哈希变换得到唯一的节点标识符，并将节点标识符也映射在同一个值空间 中，可以将文档存储在有着和文档标识符最接近的节点标识符的节点那里。 结构化p 2 p 网络中主要提供两种操作：文档的插入和文档的查找。这两个操作都是 通过文档的唯一标识符进行的。系统中每个节点在路由表中保存和其相邻的节点的信 息，并比较收到的文档标识符和路由表中的节点标识符，通过选择数值上和文档标识符 最接近的节点标识符对应的节点完成文档的路由。 结构化p 2 p 网络中基于文档标识符的路由方式如图2 2 所示。图中节点a 发出对文 档标识符为0 0 0 0 8 0 的文档的查找请求，通过和它两个相邻节点曰和c 的标识符进行比 较，节点a 发现节点c 的节点标识符和其所请求文档的文档标识符更接近，于是节点彳 将查找请求转发给节点c ；通过类似步骤，这个查找请求经过了节点c 和d ，最终到达 节点e ；节点e 的标识符最接近所请求的文档标识符，因此该文档保存在节点e 中，当 针对该文档的查找请求到达节点e 时，节点e 向查找发起节点么返回所请求的文档。 采用了分布式哈希表结构的结构化p 2 p 网络很好的解决了系统的扩展性问题，比非 结构化p 2 p 网络更适合大规模的应用。但结构化p 2 p 网络中文档的插入和查找都是通过 基丁多c h o r d 环的p 2 pv o d 系统研究 文档的唯一标识符进行的，不能直接提供非结构化p 2 p 网络中常用的多关键字搜索功 能。结构化p 2 p 网络的代表有p a s t 1 7 l 、c a n t l 8 l 、c h o r d l l 9 1 等。 相联路径 一路由路径 节点i d ：0 0 0 5 0 0 文档i d ：0 0 0 0 8 0 节点i d ：0 0 0 8 0 0 点i d ：0 0 0 0 6 0 节点i d ：0 0 0 2 0 0节点i d ：0 0 0 1 2 0 图2 2 结构化p 2 p 网络文档路由示例 f i g 2 2 f i l er o u t i n ge x a m p l eo fs t r u c t u r e dp 2 pn e t w o r k s 2 2 3 非结构化p 2 p 网络 在非结构化p 2 p 网络中，没有中央目录。当一个新的节点加入到网络中时，它自由 地连接其他节点( 如随机选择某些节点作为邻居) 。如果节点要发布某些资源，通常是它 局部地存储这些资源。分散的非结构化拓扑非常适合由高度自治的节点组成的环境，来 自许多不同组织的用户互相之间共享资源，陌生人也不愿意为其他人提供更多附加的服 务。g n u t e l l a l 2 们、f r e e n e t 【2 1 1 、m o j on a t i o n 和n u r e o g r i d 是典型的分布式的非结构化p 2 p 网络。 非结构化p 2 p 网络因其简单和可用性，在互联网上广泛配置，并占据主导地位。如 果发生节点或者网络失效，这类系统容错性好。当随机失效经常发生时，幂律属性能解 释g n u t e l l a 网络的稳定的和可恢复的结构。非结构化p 2 p 网络适合节点的动态性，也支 持r i c h 搜索，如规则表达的关键字搜索和范围搜索( r a n g es e a r c h ) 等。 但是非结构化p 2 p 网络只能提供资源发现的不可靠的保证。某些搜索会失败，即使 请求的资源事实上是存在的，搜索效率也不能保证。在这样的网络中缺乏有效的搜索机 制，只能采用泛洪或类似泛洪的盲目搜索方式，导致在网络中产生过度的流量，同样影 响了系统的可扩展性，因此目前这些搜索技术通常是效率低的。 人连理一i ：人学硕士学位论文 2 2 4 混合式p 2 p 网络 集中式p 2 p 形式有利于网络资源的快速检索，并且只要服务器能力足够强大就可以 无限扩展，但是其中心化的模式容易遭到直接的攻击，分布式p 2 p 形式解决了抗攻击问 题，但是又缺乏快速搜索和可扩展性。混合p 2 p 形式结合了集中式和分布式p 2 p 形式的 优点，在设计思想和处理能力上都得到进一步优化。混合式p 2 p 在分布式的基础上，将 用户节点按能力进行分类，使某些节点担任特殊的任务。s k y p e 即时通信软件就使用了 混合式p 2 p 网络模式。通常的混合式p 2 p 系统结构图和数据流图如图2 3 所示，混合式 p 2 p 网络一般包含3 种节点。 ( 1 ) 用户节点：普通的节点就是用户节点，它不具有任何特殊的功能。 ( 2 ) 搜索节点：搜索节点处理搜索请求，从他们的孩子节点中搜索文件列表，这些 节点必须有较高的网络连接速度以及较高的处理器性能。 ( 3 ) 索引节点：连接速度快、内存充足的节点可以作为索引节点，索引节点保存可 以利用的搜索节点信息、搜集状态信息以及尽力维护网络的结构。 一个节点既可以是搜索节点又可以是索引节点。用户节点可以选择3 个搜索节点作 为它的父节点，如果父节点接受该用户节点作为它的孩子的话，那么该用户节点就可以 提交它要共享的列表给它的父节点。 图2 3 混合式p 2 p 网络查询流程 f i g 2 3s e a r c h i n gi nm i x e dp 2 pn e t w o r k ，查询流 一下载流 在第三代p 2 p 的软件体系结构中，采用了混合p 2 p 形式。这种形式的关键之一就是 引入了索引节点，索引节点不会直接连接到有版权的资料，它就像y a h o o ! 一样，只是 搜索与所需资料相关的地址，至于用户到底连接下载了什么内容和它无关。这种形式的 关键之二是引入搜索节点，搜索节点管理着所属用户的文件列表。用户节点通过索引节 基于多c h o r d 环的p 2 pv o d 系统研究 点获得搜索节点信息，之后用户节点就与获得的搜索节点相连，每一次查询都通过该搜 索节点进行。当用户发出搜索请求后，如果和用户节点直接相连的搜索节点查询结果为 2 0 0 个( 这里的2 0 0 个搜索结果，可以由用户自己来决定) 就停止，如果不足2 0 0 个，就 向相邻的搜索节点发出请求，如果查询结果还不够，就继续向外快速发散，直到所有的 搜索节点都被搜索到。而如果所有的搜索节点都被访问过，就意味着整个网路上的节点 都被搜索到了，其速度要比纯p 2 p 模式快得多。然而，由于索引节点与搜索节点自身的 脆弱性也可能致使其连接的孩子节点处于孤立状态，因此，这种局部索引的方法仍然存 在一定的局限性。 2 3 节点选择策略 国内外科研和商业领域对节点选择策略的研究，分为两个阶段。早期是将节点选择 机制仅作为整个系统设计的一个部分进行研究，在系统设计中描述其采用的节点选择机 制，并努力通过设计一套有效的节点选择机制改进系统性能。随着研究的深入，研究领 域意识到节点选择机制的设计在整个p 2 pv o d 系统中的重要性，因此一些科研人员专 门把这个部分作为一个专题进行研列2 2 j 。 在一个典型的p 2 p 覆盖网络中，网络中的节点来自各个不同自治域，因此节点可以 在任一时间自由的加入或离开覆盖网络，导致覆盖网络具有很大的