（电路与系统专业论文）基于p2p技术的流媒体直播系统mmtv的设计和实现.pdfVIP

北京邮电大学硕士研究生论文 基于p 2 p 技术的流媒体直播系统m m t v 的设计和实现 摘要 最近几年，i n t e r n e t 上的流媒体传播技术得到了迅猛的发展，然而 由于i n t e r n e t 在满足端到端系统的原始需求设计上的对流媒体传播存 在着固有缺陷和限制，容易引发如流媒体服务器端的性能瓶颈和网络资 源的浪费等问题，导致流媒体的质量不尽如人意。为解决这个问题研究 人员提出了三种技术方案：一是由媒体代理服务器发展起来的c d n 技术， 然而c d n 部署面临高昂的成本问题。二是i p 组播技术，但是由于协议 本身的复杂性、网络异构性、以及缺少支持组播的可靠的、具有扩展性 的拥塞控制机制等自身固有的限制而难以部署。为了能够行之有效的提 高i n t e r n e t 上的流媒体的q o s 。研究人员提出了第三个解决方案，基于 p 2 p 网络的媒体分发技术：p 2 p 分发技术，即把组播的功能从网络层移 到了应用层。 本文首先介绍了p 2 p 最新技术进展和流媒体方面的技术框架，主要 包括适合网络传输的媒体编码技术、应用层的q o s 控制技术和流媒体传 输协议。然后在现有研究的分析总结基础上设计和实现了一个高质量的 p 2 p 实时分发系统m m t v 。该系统可以在网络带宽效率、延时和可靠性三 者之间做出更好的权衡，主要特点是：1 ) 易于实现，网络拓扑分布存储， 却没有复杂的p 2 p 组管理协议；2 ) 健壮性，节点不依赖于任何其它特定 的节点，具有较强的稳定性和可靠性；3 ) 网络具有快速反应能力，对节 点的加入离开反应迅速；4 ) 带宽适应性；5 ) 较低的全网内各节点间的延 迟。 关键词：p 2 p 直播系统系统设计系统实现 i 一 北京邮电大学硕士研究生论文 t h ed e s i g na n dm l e a 伍n t a ：n o no ft h e s t r e a m 姬a d i al i v eb r o a d c a s ts y s t e m n 蹦t vb a s e do np 2 pt e c h n o l o g y r e c e n t l y , m u l t i m e d i as t r e a m i n go v e rt h ei n t e m e ti sb o o m i n g h o w e v e r , t h et r a d i t i o n a ld e s i g ni d e ao fi n t e r n e tm o d em a d eai n h e r e n tg a p sa n d c o n s t r a i n t so ft h ed e v e l o p m e n to fs t r e a mt e c h n o l o g yt h a ti st om e e tt h e n e e d so fe n d - t o e n du n i c a s tc o m m u n i c a t i o n ，a l s oi te a s i l yl e a dt os u c ha s t h ew a s t eo fr e s o u r c e so ft h es t r e a m i n gm e d i as e r v e ra n dn e t w o r k p e r f o r m a n c eb o t t l e n e c k sa n do t h e rp r o b l e m s s ot h es t r e a m i n gq u a l i t yi s g e n e r a l l yu n s a t i s f a c t o r y f o rl a r g e - s c a l a b l eb r o a d c a s t i n g ，t os o l v et h i s p r o b l e mr e s e a r c h e r sp r o p o s e dt h r e es o l u t i o n s ：f i r s t ，t h ec o n t e n td e l i v e r y n e t w o r k ( c d n ) m e d i ap r o x ys e r v e rt e c h n o l o g y , b u tt h i sa p p r o a c hh a st h e l i m i t i n gf a c t o ro fe x p e n s i v ec o s t s e c o n d ，i pm u l t i c a s t ，an e t w o r kl a y e r s e r v i c et h a ta l l o w sas i n g l es o u r c et o d i s t r i b u t ead a t as t r e a mt om a n y s i m u l t a n e o u sr e c e i v e r si na ne f f i c i e n tm a n n e r , b u tb e c a u s eo ft h ec o m p l e x n a t u r eo f t h e p r o t o c o li t s e l f , h e t e r o g e n e o u sn e t w o r k s ，a n dt h el a c ko f r e l i a b l e m u l t i c a s ts u p p o r t ，e x t e n s i a b l ec o n g e s t i o nc o n t r o lm e c h a n i s m ，t h i ss o l u t i o n a l s oh a si t so w ni n h e r e n tl i m i t a t i o n sa n dd i f f i c u l tt od e p l o y i no r d e rt o 1 h 一一! ! 室坚皇丕堂堡主堡窒生堡壅 i m p r o v et h eq o so fs t r e a m i n go v e rt h ei n t e m e te f f e c t i v e l ya n de a s i l y , t h e t h i r ds o l u t i o n , m e d i ad i s t r i b a t i o no v e rp 2 pn e t w o r ki s p r o p o s e d t h i s t e c h n o l o g yc h a n g e dt h em u l t i c a s tf u n c t i o nf r o mn e t w o r kl a y e rt ot h e a p p l i c a t i o nl a y e r i nt h i sp a p e r , w eg a v ea no v e r v i e wo f t h el a t e s tp 2 p t e c h n o l o g ya n dt h e t e c h n i c a l a s p e c t s o f s t r e a m i n g m e d i af r a m e w o r ko np 2 pn e t w o r k s ， i n c l u d i n gm u l t i m e d i ae n c o d i n gt e c h n o l o g yf o rn e t w o r kt r a n s m i s s i o n ，t h e q o sc o n t r o lt e c h n o l o g yo ft h em e d i as t r e a m i n ga p p l i c a t i o nl a y e r ，a n dt h e m u l t i m e d i at r a n s f e rp r o t o c o l ，t h e nt h i sp a p e r p r e s e n t san e wp 2 pr e a l - t i m e s t r e a m i n gm o d e l ：m m t v , t h i ss y s t e ma c h i v e sab e t t e rt r a d e o f fa m o n g b a n d w i d t h e f i c i e n c y , d e l a ya n dr e l i a b i l i t y w ee m p h a s i z ef i v es a l i e n t f e a t i l r e so fm m t v ：1 、e a s eo f i m p l e m e n t a t i o n , d i s t r i b u t i o nn e t w o r k t o p o l o g y , b u tn o tc o m p l i c a t e dp 2 pg r o u pm a n a g e m e n tp r o t o c o l 2 ) r o b u s t n e s s ，n o d ei sn o td e p e n d e n to na n yo t h e rs p e c i f i cn o d e s s oi th a sa s t r o n gs t a b i l i t ya n dr e l i a b i l i t y ；3 ) n e t w o r kw i t har a p i dr e a c t i o nc a p a c i t yt o r e s p o n dq u i c k l yl e f tt oj o i nn o d e4 ) b a n d w i d t ha d a p t a b i l i t y ；5 ) t h el o w e r d e l a yo f t h ee n t i r en e t w o r kn o d e s k e yw o r d s ：p 2 p l i v eb r o a d c a s ts y s t e m s y s t e md e s i g n s y s t e mi m p l e m e n t a t i o n 北京邮电大学硕士研究生论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 2 耍：i 车 日期： 猃z ：i ：j 本人签名： 旦：i 车 日期： 猃z ：i ：j 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学 校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段 保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文 注释：本学位 本人签名 导师签名 本授权书。 日期：鲨21i ：! 日期：弛2 - 主：至； 北京邮电大学硕士研究生论文 第一章绪论 本章作为论文的首章首先概述了本论文的研究主题的技术背景，以及本论文研 究主题技术环境和研究方面的主要的挑战。本章的最后指出了本论文的主要工作和 本论文的各个部分内容的组织结构。 1 1 引言 随着i n t e r n e t 的发展，用户对网络的期望和要求也越来越高，不再满足于单 一的静态媒体。将声音、文字、图像、视频等多媒体有机结合形成的媒体演示是 i n t e r n e t 的发展重点，但在动态多媒体方面一直存在带宽限制和数据同步等问题， 于是出现了流媒体技术。流媒体技术将数据流由音视频服务器向客户机实时传输， 用户可以边下载边观看，不用耗费漫长的等待时间，实现了媒体浏览的实时性。 以前，多媒体文件需要从服务器上下载后才能播放。由于多媒体文件一般都比 较大，下载整个文件往往需要很长的时间，限制了人们在互联网上使用多媒体数据 进行交流。流媒体应用的一个最大的好处是用户不需要花费很长时间将多媒体数据 全部下载到本地后才能播放，而仅需将起始几秒的数据先下载到本地的缓冲区中就 可以开始播放了。 随着网络技术的发展，流媒体己成为目前因特网应用的最快增长点之一。远程 教学管理、视频聊天室、i p t v 、视频会议等都是正在兴起或广泛应用的流媒体应用。 流媒体的特点是数据量大、传输持续时间长，并且对延迟、抖动、丢包率、带宽等 q o s 指标要求非常严格。在当前的因特网上构建大规模的性价比高的流媒体系统是 一个具有挑战性的工作。 总的来说，i n t e r n e t 上传输实时媒体的挑战有多个方面。实时媒体的传输有带 宽，时延和丢包的需求。然而，在当前的i n t e r n e t 上传输媒体并没有任何的服务 质量( q o s ) 的保证。另外，网络和终端的异构性使得带宽效率和服务的适应能力有 所下降。设计在i n t e r n e t 上传输实时媒体的协议和机制时，都必须充分考虑这些问 题。 我们列举了以下遇到的四个主要挑战 1 ： 北京邮电大学硕士研究生论文 1 带宽：为了达到可接受的视频质量，实时媒体的传输通常有一个最小的带宽需 求( 比如，2 8 i ( b s ) 。然而，当前i n t e r n e t 并不提供任何的带宽保证来满足这个需求。 此外，传统的路由器并不提供任何的拥塞控制，流量过大时可能导致网络崩溃，从 而更加降低了实时媒体的吞吐率。 2 时延：一般的数据传输通常没有严格的时延要求，但是实时媒体要求严格的 端到端的时延( 比如，1 s ) 。也就是说，每个媒体包都必须及时到达目的端以用于解 码和显示。因为实时媒体要求连续的播放，如果媒体包没有及时抵达，播放进程被 迫停止，这会降低视频质量。换句话说，超过一定时间才到达的媒体包已经没有使 用价值，可以视为已经丢弃了。尽管实时媒体有传输的时间要求，但当前的i n t e r n e t 也不提供如此的时延保证。i n t e r n e t 上的拥塞会导致大量时延，这不能满足实时媒 体的时延需求。 3 丢包：丢包可能会潜在的降低视频质量，甚至导致不能观看。因此，视频应用 通常有丢包限制的需求。更明确的说就是，为了达到可接受的视觉效果，丢包率必 须低于一个门限值( 比如，1 ) 。当前的i n t e r n e t 也不提供如此一个丢包率的保证。 并且，在网络拥塞时，丢包率会非常高，这将会非常严重的导致观看质量的下降。 4 异构性：在分布上存在两种异构，即网络异构和接收终端异构。网络异构是指 i n t e r n e t 上的子网络各具有不同的分布式资源( l z 如，处理资源，带宽，存储资源， 拥塞控制策略等) 。由于丢包和时延的不同，网络异构会造成不同的用户体验。接收 终端异构是指接收者具有不同的时延需求，视觉质量需求或处理能力。比如，在一 个实时演讲的组播中，那些希望提问并与演讲者交互的接收者要求非常严格的实时 要求，同时那些被动的听众可能希望牺牲一些时延来获取更高质量的视频。 因特网上的传统流媒体系统是基于客户端服务器( c l i e n t s e r v e r ，以下简称 为c s ) 模式的，一般包括一台或多台服务器，若干客户机。我们将系统能同时服 务的客户总数称为系统容量。c s 模式的流媒体系统容量主要是由服务器端的网络 输出带宽决定的，有时服务器的处理能力、缓存大小、i o 速率也影响到系统的容 量。在c s 模式下，由于传输流媒体占用的带宽大，持续时间长，而服务器可利用 的网络带宽有限，所以即使是使用高档服务器，其系统容量也不过几百个客户，根 本就不具有经济规模性。另外，由于因特网不能保证q 0 s ，如果客户机距服务器较远， 则流媒体传输过程中的延迟、抖动、带宽、丢包率等指标也将更加不确定。此外， 服务器为每一个客户都要单独发送一次重复的流媒体内容，从而网络资源的消耗也 十分巨大。 在传统分发架构无法满足现有需求时，p 2 p 技术得到了复兴。p 2 p 网络的基本 思想是充分利用因特网上分布在不同地理位置上的计算机的空闲资源，采用分布式 北京邮电大学硕士研究生论文 计算模式来为因特网上的用户提供各种服务。p 2 p 网络中没有集中的服务器，网络 的每一个节点既可以作为客户接受其它节点的服务，也可以作为服务器向其它节点 提供服务。基于p 2 p 的流媒体系统也是借助了这种思想进行流媒体内容的分发传输 的，其设计目标是充分利用众多客户节点的空闲资源，构建一个成本低、扩展性好、 并有一定q 0 s 保证的流媒体传输系统。 1 2 主要工作及论文组织结构 目前国内外的研究人员都投入了大量的精力对p 2 p 网络进行了研究，但很多研 究都是围绕对等点定位、安全问题等方面，对p 2 p 网络的稳定性和媒体数据的实时 分发等的研究并没取得重大突破，使得p 2 p 的流媒体系统还不成熟。本文的主要工 作就是在现有研究的分析总结基础上设计并实现了一个高质量的基于p 2 p 网络的大 规模流媒体直播系统埘，r v 。 删t v 系统是一个以提供高清晰度、高质量服务为宗旨的网络直播视频系统。该 系统利用p 2 p 网络的优势，减少服务器的负担，具有用户越多播放越稳定、支持数 万人同时在线的大规模访问等特点，有效解决了当前网络视频直播服务的带宽和负 载有限问题，实现用户越多，播放越流畅的特性，整体服务质量得到了大幅提高。 另外姗t v 还是一套完整的基于p 2 p 技术的流媒体超大规模应用解决方案，包 括流媒体编码、发布、广播、播放和超大规模用户直播。能够为用户提供稳定和流 畅的视频直播节目。同时删t v 网络是一个高度安全的独立p 2 p 网络，收费频道使 用r a d i u s 协议对用户进行认证计费，可以进行商业化推广。 m m t v 的基本原理如下，系统把所有观看相同频道的节点通过一个服务器组织成 一个专用p 2 p 网络。这个服务器负责提供一些最近的邻居节点信息给观看节点。在 这个专用p 2 p 网络中，每一个节点既可以作为客户端同时接收其它节点的媒体数据， 也可以作为服务器同时为其它节点提供媒体数据。媒体数据和控制信息都是在一个 虚拟的u d p 连接上传输，因此网络传输比较高效。 我的主要工作是分以下几个阶段来进行的： 1 ) 在可行性分析阶段 2 ，我们首先研究了当前流媒体业务的发展状况和应用 领域。不可否认，流媒体已成为目前因特网应用的最快增长点之一，远程教学管理、 视频聊天室、i p t v 、视频会议等都是正在兴起或广泛应用的流媒体应用。其次研究 了两种传统的分发方案的工作方式和优劣势，传统的c 1 i e n t s e r v e r 架构和i p 组 播方案。c l l e n t s e r v e r 架构下服务器的性能瓶颈直接限制了同时观看用户数，因 北京邮电大学硕士研究生论文 此不具有规模性。i p 组播技术在实际的部署中仍然存在一些很重要的关键问题，主 要包括：网络协议的复杂性、网络和终端系统的异构性、组播的可靠性。因此引入 了基于p 2 p 网络的流媒体直播方案。 2 ) 在需求分析阶段，我们首先提出了当前部署流媒体应用遇到的四个主要挑 战，分别是带宽，时延和丢包的需求以及网络的异构性。部署基于p 2 p 网络的流媒 体直播系统必须最大量的解决这四个挑战。然后研究了国内具有市场规模的几款 p 2 p 直播软件的设计特点，包括q q 直播，p p l i v e ，c o o l s t r e a m i n g 等。 3 ) 在系统设计阶段，我们在对p 2 p 技术和流媒体技术的研究基础上，综合研 究了当前p 2 p 系统的内容分发技术，提出一个基于p 2 p 系统的流媒体内容分发系统 哪v 。首先是对整个m m t v 系统的结构设计，然后设计瑚t v 系统是如何通过p 2 p 系 统来分发内容的，最后进行了m m t v 系统的流媒体方案的设计。 4 ) 在系统实现阶段，划分m m t v 系统为四个主要模块，分别是：p 2 p 网络覆盖 层模型设计，流媒体分发方案设计，视频源编码与终端解码，p 2 p 网络安全设计和 认证计费模块。这四个模块依次实现并进行了单元测试。在实现中，我们使用了开 源的跨平台中间库提供的大量接口，做到了跨平台的移植。目前b t b i t v 系统可以运 行在w i n d o w s 和l i n u x 操作系统上。 5 ) 在测试阶段，我们进行了大规模的直播测试以验证其效果。在测试的半个 月舰间，每天平均在线6 0 0 0 人同时观看，决赛期间用户达到9 0 0 0 人以上。平均视 频质量良好，整体的视频质量达到9 7 以上。频道服务器仅使用了一台普通p c 机， 内存占用不到2 0 m ，c p u 占用不到5 ，出口带宽仅占用3 m b s 。运营试验证明，瑚t v 以软件分布式计算方法节约了服务器的硬件成本，并且大量的节约了网络带宽，提 高了观看用户的整体视频质量。因此非常适合大规模流媒体直播业务，可以进行商 业化运营推广。 本文组织结构如下： 第一部分对本论文进行的工作进行概述。 第二部分按照对等网络的拓扑结构划分为4 种类型，并且分别对这四种类型的 对等网络的模型和所采用的技术进行分析。 第三部分介绍当前常用的流媒体技术，包括流媒体编码技术，关于流媒体的应 用层q o s 和组播技术，流媒体服务器技术，服务器构建技术，流媒体同步技术。 第四部分在前面p 2 p 技术和流媒体技术的研究基础上提出一个基于p 2 p 系统的 流媒体直播系统脚r v ，包括整个m v 系统的模块架构设计，姗t 、，系统的p 2 p 网络 覆盖层设计，流媒体分发方案设计。 第五部分介绍m m t v 的详细实现，包括其各个功能模块的实现以及砌v 系统模 北京邮电大学硕士研究生论文 型的一个具体实现，最后介绍了m m t v 的实现效果。 第六部分介绍i v b f i v 的大规模测试以及效果分析等。 第七部分总结全文，并提出了一些未来在p 2 p 流媒体方面需要进行研究和开发 的工作。 1 3 本章小结 本章首先概述了本论文研究主题的技术环境，和在研究工作中主要遇到的挑 战。然后指出了本论文的所作的工作和本论文的各个部分内容的组织结构。 北京邮电大学硕士研究生论文 第二章对等网络中技术概览 本章首先概述了p 2 p 系统的定义以及其拓扑分类，然后按照p 2 p 系统的网络拓 扑结构分类来简单的介绍当前一些典型的p 2 p 系统模型，并且分析了这些模型所采 用对资源定位和搜索的关键算法和技术。最后总结了p 2 p 系统技术的研究现状，以 及p 2 p 系统存在的各种问题。 2 1 p 2 p 系统概述及其分类 最近几年，对等计算( p e e r t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的热门 话题之一，财富杂志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一。 对等网络中的计算机( 称为对等机) 通过直接交换共享计算机资源和服务的网 络，网络中所有的结点是对等的，具有相同的责任与能力并协同完成任务，对等机 兼有客户机和服务器的功能。对等点之间通过直接互连实现信息、处理器、存储甚 至高速缓存等资源的全面共享，无需依赖集中式服务器支持，消除了信息资源孤岛 和c s 模型中的服务瓶颈问题。随着像n a p s t e r 、g n u t e l l a 、f r e e n e t ，i ( a z a a 3 等 对等计算信息共享应用系统的流行，代表了对等计算系统的体系结构也发生了由 n a p s t e r 的集中查询到早期6 n u t e l l a 的自由连接，再到当前6 n u t e l l a 等的偏向于 超级结点的自由连接的逐步演变。 按照p 2 p 技术发展阶段以及p 2 p 系统网络的拓扑结构和资源搜索与定位对等网 络可以大致可以分为以下四种类型： 1 集中化p 2 p 系统： 这种集中化p 2 p 系统是第一代p 2 p 网络所采用的结构模式，这种系统包含有中 心索引服务器，存储着整个p 2 p 系统的资源定位信息，资源搜索与定位比较方便和 快捷，但是正是因为这个原因，这种系统存在扩展性和单点失败问题，因此也通常 被攻击为不是p 2 p 系统。 2 非结构化p 2 p 系统： 这种系统的特点是文件的发布和网络拓扑松散相关。这类系统比较典型的成功 模型包括m o r p h e u s ，g n u t e l l a 。g n u t e l l a 、m o r p h e u s 是纯p 2 p 文件共享系统，后者 如今并入前者中；m o r p h e u s 、g n u t e l l a 等系统采用广播或者受限广播来进行资源定 北京邮电大学硕士研究生论文 位，具有较好的自组织性和扩展性，适用于互联网个人信息共享。缺点是稀疏资源 的召回率低。 3 结构化p 2 p 系统： 这类系统特点是文件的发布和网络拓扑紧密相关。文件按照p 2 p 拓扑中的逻辑 地址精确的分布在网络中。这类系统包括c a n 、t a p e s t r y 、c h o r d 、p a s t r y 4 ，以及 基于这些系统的一些其它文件共享和检索方面的研究实验系统在这类系统中每个 节点都具有虚拟的逻辑地址，并根据地址使所有节点构成一个相对稳定而紧致的拓 扑结构。在此拓扑上构造一个存储文件的分布式哈希表d h t ，文件根据自身的索引存 储到哈希表中。每次检索也是根据文件的索引在d h t 中搜索相应的文件。生成文件 的索引的方法有三种：根据文件的信息生成的哈希值( h a s h ) ，如c f s ，o c e a n s t o r e ， p a s t ，m n e m o s y n e 等；根据文件包含的关键字生成关键字索引；还有根据文件的内容 向量索引，如p s e a r c h 。 4 松散结构化p 2 p 系统： 此类系统介乎结构化和非结构化之间，取两者之长处。系统中的每个节点都有 分配有虚拟的逻辑地址，但整个系统仍然是松散的网络结构。文件的分布根据文件 的索引分配到相近地址的节点上。随着系统的使用，文件被多个检索路径上的节点 加以缓存。类似的系统包括p r e e n e t ，f r e e h a v e n ，k a z a a 等。相关系统非常强调共 享服务的健壮性( 安全性) 。 2 2 集中化p 2 p 系统及其技术分析 在集中化p 2 p 系统中，中心化拓扑最大的优点是维护简单发现效率高。由于资 源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最大的 问题与传统客户机服务器结构类似，容易造成单点故障，访问的“热点”现象和法 律等相关问题，这是第代p 2 p 网络采用的结构模式，经典案例就是著名的m p 3 共 享软件n a p s t e r ，n a p s t e r 是包含有中心索引服务器的最早的p 2 p 文件共享系统，存 在扩展性和单点失败问题。 n a p s t e r 是最早出现的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 首先实现了文件查询与文件传输的分离，有效地节省了中央服务器的带 宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在中央服务器上，如果 该服务器失效，整个系统都会瘫痪。当用户数量增加到1 0 5 或者更高时，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 的典型网络拓扑结构 如图2 - 1 所示。 这种对等网络模型存在很多问题，主要表现为： ( 1 ) 中央服务器的瘫痪容易导致整个网络的崩馈，可靠性和安全性较低。 ( 2 ) 随着网络规模的扩大，对中央索引服务器进行维护和更新的费用将急剧增 加，所需成本过高。 ( 3 ) 中央服务器的存在引起共享资源在版权问题上的纠纷，并因此被攻击为非纯 粹意义上的p 2 p 网络模型。对小型网络而言，集中目录式模型在管理和控制方面占 一定优势。但鉴于其存在的种种缺陷，该模型并不适合大型网络应用。 图2 - 1n a p s t e r 系统的网络拓扑结构示意图 2 3 非结构化p 2 p 系统及其技术分析 非结构化p 2 p 系统被称作是纯p 2 p 系统，这种p 2 p 系统所有的节点都是一个 p e e r ，从而没有了服务器的概念。 北京邮电大学硕士研究生论文 2 3 1 非结构化p 2 p 系统概述 在非结构化的系统中，每个节点存储自身的信息或信息的索引( 如指针和i p 地 址) 。当用户需要在p 2 p 系统中获取信息时，他们预先并不知道这些信息( 如某个文 件) 会在那个节点上存储。因此，在非结构化p 2 p 系统中，信息搜索的算法难免带 有一定的盲目性，例如最简单的泛洪式查找( 类似于广播) 和扩展环查找( 从最近的n 个节点开始，层层转发直到找到目标或超出了跳数的上限为止) 。 一些典型的应用采用了一些优化的办法。如在g n u t e l l a 中，采用了等级制的组 成结构：节点被分成超级节点( s u p e rn o d e ) 和普通节点。普通节点必须依附于超级 节点，每个超级节点作为一个独立的域管理者，负责处理域内的查询操作。在查找 的过程中，查询首先在域内进行，失败后才会扩展到超级节点之间。 非结构化系统的优点在于实现结构简单：无须中央服务器，节点之间完全平等， 网络的层次是单一的，而且节点之间无需维护拓扑信息。 2 3 2 非结构化p 2 p 系统模型分析 非结构化网络在重叠网络( o v e r l a y ) 采用了随机图的组织方式，结点度数服从 ”p o w e r l a w ”规律，从而能够较快发现目的结点，面对网络的动态变化体现了较好的 容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带有规则表达式的 多关键词查询，模糊查询等，最典型的案例是g n u t e l l a 。 g n u t e l l a 是一个p 2 p 文件共享系统，它和n a p s t e r 最大的区别在于g n u t e l l a 是 纯粹的p 2 p 系统，没有索引服务器，它采用了基于完全随机图的洪泛( f l o o d i n g ) 发现和随机转发( r a n d o mw a l k e r ) 机制，其工作方式如图2 - 2 所示。为了控制搜索 消息的传输，通过t t l ( t i m et ol i v e ) 的减值来实现。 在g n u t e l l a 分布式对等网络模型n 中，每一个联网计算机在功能上都是对等的， 既是客户机同时又是服务器，所以被称为对等机( s e r v e n t ，s e r v e r + e 1 l e n t 的组合) 。 随着联网节点的不断增多，网络规模不断扩大，通过这种洪泛方式定位对等点 的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载 而失效。所以在初期的g n u t e l l a 网络中，存在比较严重的分区，断链现象。也就是 说，一个查询访问只能在网络的很小一部分进行，因此网络的可扩展性不好。所以， 解决g n u t e l l a 网络的可扩展性对该网络的进一步发展至关重要。 由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。即使 需要查找的目的结点存在发现也有可能失败。由于采用t t l ( t i m e t o l i v e ) 、洪泛 ( f l o o d i n g ) 、随机漫步或有选择转发算法，因此直径不可控，可扩展性较差。 北京邮电大学硕士研究生论文 因此发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对此 类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性能。 图2 - 2 最初的g n u t e l l a 采用的f l o o d i n g 搜索算法示意图 非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有遵循某 些预先定义的拓扑来构建。这些系统一般不提供性能保证，但容错性好，支持复杂 的查询，并受结点频繁加入和退出系统的影响小。但是查询的结果可能不完全，查 询速度较慢，采用广播查询的系统对网络带宽的消耗非常大，并由此带来可扩展性 差等问题。 为了解决非结构化系统中的随机搜索造成的不可扩展性差的问题，大量的研究 集中在如何构造一个高度结构化的系统。目前研究的重点放在了如何有效地查找信 息上，最新的成果都是基于d h t 的分布式发现和路由算法。这些算法都避免了类似 n a p s t e r 的中央服务器，也不是像g n u t e l l a 那样基于广播进行查找，而是通过分布 式散列函数，将输入的关键字惟一映射到某个结点上，然后通过某些路由算法同该 结点建立连接。 2 3 3 非结构化p 2 p 系统资源搜索与定位 按照搜索策略，非结构化p 2 p 系统资源搜索与定位可以分为两大类：盲目搜索 和信息搜索 5 。盲目搜索通过在网络中传播查询信息并且把这些信息不断扩散给每 个节点。通过这种洪泛方式来搜索想要的资源。而信息搜索在搜索的过程中利用一 些已有的信息来辅助查找过程。由于信息搜索对资源的存储有一些知识，所以信息 搜索能够比较快的找到资源。 北京邮电大学硕士研究生论文 2 3 3 1 盲目搜索佃i 心ds e a r o 珊议介绍l 1 ) 洪泛搜索( f l o o d i n 9 3 鲫蚀) ：在最初的g n u t e l l a 协议中，使用的f l o o d i n g 方 法，就是一种典型的盲目搜索。在网络中，每个节点都不知道其他节点的资源。当 它要寻找某个文件，把这个查询信息传递给它的相邻节点，如果相邻节点含有这个 资源，就返回一个o u e r y h i t 的信息给r e q u e s t e r 。如果它相邻的节点都没有命中这 个被查询文件，就把这条消息转发给自己的相邻节点。这种方式像洪水在网络中各 个节点流动一样，所以叫做f l o o d i n g 搜索。由于这种搜索策略是首先遍历自己的邻 接点，然后再向下传播，所以又称为宽度优先搜索方法( b f s ) 。 2 ) 宽度优先搜索方法( b o a r df i r s ts e a r c h ) ：b f s 搜索把消息传播给所有的邻接点， 它消耗了大量的网络带宽，使消息堵塞严重，效率比较低，扩展性不好。研究人员 在b f s 的基础上进行改进，它的方法是随机抽取一定比例的相邻节点传递消息，而 不是像f l o o d i n g 一样把查询信息传播给所有邻接点。这种修正的极大地减少了网络 中的查询信息，但是在命中率上不如b f s 。 3 ) 迭代加深搜索( i t e r a t i v ed e e p e n i n g ) ：这种搜索策略是在初始阶段，给t t l 一个 很小的值，如果在t t l 减为0 ，还没有搜索到资源，则给1 u r l 重新赋更高的值。这种 策略可以减少搜索的半径，但是在最坏的情况下，延迟很大。 4 ) 随机漫步搜索( r a n d o mw a l k ) ：在随机漫步中，请求者发出k 个查询请求给 随机挑选的k 个相邻节点。然后每个查询信息在以后的漫步过程中直接与请求者保 持联系，询问是否还要继续下一步。如果请求者同意继续漫步，则又开始随机选择 下一步漫步的节点，否则中止搜索。 5 ) 集中搜索( g n u t e l l a 2 ) ：在g n u t e l l a 2 中，系统将建立一个或多个s u p e r n o d e ， 它存储着离它最近的叶子节点的文件信息，这些s u p e r n o d e ，再连通起来形成一个 o v e r l a yn e t w o r k 当叶子节点需要查询文件，它首先从它连接的s u p e r n o d e 的索引 中寻找，如果找到了文件，则直接根据文件所存储的机器的i p 地址建立连接，如果 没有找到，则s u p e r n o d e 把这个查询请求发给它连接的其他超级节点，直到得到想 要的资源。 2 3 3 2 信息搜索( i n f o r m e ds e a r c hm e t h o d s ) 1 ) 缓存搜索( c a c h em e t h o d ) 这种方法不同于盲目搜索很大的地方在与它在每个节点上，不管是中央节点还 是简单节点都存有路径信息。这就是c a c h e 的思路。新的搜索并不需要直接达到资 北京邮电大学硕士研究生论文 源的存储地，只要在搜索的路径中找到以前搜索的记录也就是在它以前的搜索的基 础上找到源i p 地址，就可以把请求消息返回。这样可以极大的减少搜索的消息，提 高效率。 2 ) 移动代理搜索( m o b il ea g e n tb a s e dm e t h o d ) 移动a g e n t 是一个能在异构网络中自主地从一台主机迁移到另一台主机，并可 与其他a g e n t 或资源进行交互的程序。a g e n t 非常适合在网络环境中来帮助用户完成 信息检索的任务。现在意大利的一些研究人员在m o b i l ea g e n t 结合p 2 p 方面做了一 些前沿的研究，其中的一些想法，就是通过在p 2 p 软件中嵌入a g e n t 的运行时环境。 当有节点需要搜索的时候，它发送一个移动a g e n t 给它相邻的节点，移动a g e n t 记 录着它的一些搜索的信息。当这个a g e n t 到达一台新的机器上，然后在这个机器上 进行资源搜索任务，如果这台机器上没有它想要的资源，则它把这些搜索的信息传 给它的邻节点，如果找到资源，则返回给请求的机器。 2 4 结构化p 2 p 系统及其技术分析 结构化p 2 p 系统是优化非结构化p 2 p 系统而提出来的，主要是为了解决非结构 化系统可扩展性差而提出来的，但是它本身也带来的新的问题。 2 4 1 结构化p 2 p 系统概述 结构化p 2 p 系统是为了解决非结构化系统可扩展性差性而提出来的。在结构化 p 2 p 系统中，每个节点只存储特定的信息或特定信息的索引。当用户需要在p 2 p 系统 中获取信息时，他们必须知道这些信息( 或索引) 可能存在于那些节点中。由于用户 预先知道应该搜索哪些节点，避免了非结构化p 2 p 系统中使用的泛洪式查找，因此 提高了信息搜索的效率。 但是，结构化p 2 p 也引入了新的问题： 首先，既然信息是分布存储的，那么如何将信息分布存储在重叠网中的节点上? 其次，由于节点动态的加入和离开重叠网，如何将拓扑的变更信息通知其它节 点? d h t 6 的引入基本解决了上述问题，因此自从d h t 协议出现以后，结构化p 2 p 的应用得到了快速的发展。目前已经有很多较为成熟的n i t 协议被提出并且得到了 应用。其中比较有代表性的有：缓冲阵列路由协议( c a r p ) ；一致性哈希；c h o r d ；内 容寻址网络；p a s t r y 。 北京邮电大学硕士研究生论文 d h t 使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核 心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得到键值( h a s hk e y ) ，对 象的分布存储依据键值来进行。具体来讲，大致有以下步骤： 对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了 一个具体的数值范围中。 重叠网中的每个节点负责数值范围中的特定段落。例如，节点a 负责存储键值 从8 0 0 0 到8 9 9 9 的对象；而节点b 负责7 0 0 0 7 9 9 9 的对象。这样就将对象集合分布 地存储在所有的节点中。 节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引， 如该对象所在节点的i p 地址。 结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目 标信息的节点。在有着大量节点( 如1 0 0 万个) 的p 2 p 系统中，任何节点都不可能拥 有全部的节点，键值，内容的对应关系；因此用户获得了键值之后，如何找到该键 值对应的节点就被称为d h t 的路由问题。d h t 协议必须定义优化的查找( 路由) 算法来 完成这一搜寻的工作。不同的d h t 协议之间区别很大程度上就在于定义了不同的路 由算法。 d h t 的应用非常简洁- a p i 简单到只有一项输入和一项输出： 图2 3 显示了这种应用结构，图中的应用层将数据对象( 文件、数据块或索引)