（计算机软件与理论专业论文）p2p流媒体点播技术中缓存算法的研究.pdf

摘要 摘要 随着计算机和网络技术的快速发展，互联网流媒体技术广泛应用于网络 直播、视频点播、远程教学等领域。但传统的基于c s 架构的服务模式很容 易引起服务器的性能瓶颈和带宽瓶颈，难以胜任大规模的并发应用。最近几 年新兴的对等网络( p 2 p ) 技术，通过节点之间的直接交互来实现信息资源 的共享，极大地减轻了系统对中心服务器的依赖程度，但由于视频点播当中 的高度交互性需求，使得实现的复杂程度较高。如何在动态的p 2 p 网络环境 中构建大规模、高可扩展、高可靠、高播放体验的p 2 p 流媒体点播系统，是 近年来研究的热点之一。 本文是在对p 2 p 流媒体点播系统中缓存算法研究的基础上，提出了一个 基于全局分段流行度的节点缓存算法g s p k ( g l o b a ls e g m e n t p o p u l a r i t y b a s e dc a c h i n ga l g o r i t h m 一目。该算法是在对p 2 p 流媒体点播系统 全局考虑的基础之上，通过对流媒体分段流行度的分布式统计，结合文件内 分段采用频率的递减分布特性，综合评定各个流媒体分段的缓存效用值，使 整个系统所缓存的各流媒体分段的副本数量与其缓存效用值成正比。在与其 它缓存算法( 如：l r u ，l f u 算法) 的对比实验中，g s p k 算法在提高流行度统 计精确度、改善缓存空间利用率、提高分段命中率等方面具有更好的性能。 关键词：p 2 p ；流媒体点播；缓存算法 u a b s t r a c t 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 ft h en e t w o r kt e c h n i q u e ，t h em e d i as t r e a m i n g t e c h n o l o g yh a sb e e nu s e di nn e t w o r kl i v i n gb r o a d c a s t ，v o d ，r e m o t ei n s t r u c t i o na n d s oo n b u tt h et r a d i t i o n a lc sm o d e lb r i n g st h es e r v e ro np e r f o r m a n c eb o t t l e n e c ka n d b a n d w i d t hb o t t l e n e c k s ，t h i sm a k e si tc a n n o tb eu s e di n l a r g e s c a l ep r o c e s s e so f o p e r a t i n gc o n c u r r e n t l y t h i sy e a r st h en e wt e c h n o l o g yo fp 2 pu s et h ed i r e c t i n t e r a c t i o nb e t w e e np e e ra n dp e e rt or e a l i z et h es h a r i n go fi n f o r m a t i o nr e s o u r c e s g r e a t l yr e d u c et h es y s t e m sr e l i a n c eo nc e n t r a ls e r v e r s h o w e v e r , a sv o dw h i c h d e m a n dah i g hd e g r e eo fi n t e r a c t i v i t y , m a k e sa c h i e v e m e n tah i g h e rd e g r e e o f c o m p l e x i t y n o wh o wt ob u i l dap 2 pm e d i as t r e a m i n gv o ds y s t e mw i t hl a r g e s c a l e ， h i g hs c a l a b i l i t y , r e l i a b i l i t ya n dp e r f o r m a n c ei nad y n a m i cp e e r - t o p e e rn e t w o r k e n v i r o n m e n ti sah o tr e s e a r c ht o p i ci nr e c e n ty e a r s t h i sd i s s e r t a t i o np r o p o s e san e wa l g o r i t h mn a m e dg s p k ( g l o b a ls e g m e n t p o p u l a r i t y b a s e dc a c h i n ga l g o r i t h m - 髟) w h i c hi sap e e rc a c h i n ga l g o r i t h mb a s e d o ng l o b a ls e g m e n tp o p u l a r i t yf o rp 2 pv o d s y s t e m t h i sa l g o r i t h me v a l u a t et h ec a c h e u t i l i t yo fm e d i as e g m e n tv i ag a t h e r i n gt h es t a t i s t i c so fm e d i as e g m e n tp o p u l a r i t y g l o b a l l y , a n dm a k et h en u m b e r so fam e d i as e g m e n tc o p i e si nt h ew h o l es y s t e m v a r i e sd i r e c t l yw i t hi t sc a c h eu t i l i t y t h es i m u l a t i o ne x p e r i m e n t si n d i c a t et h a tt h i s a l g o r i t h mh a sb e u e rp e r f o r m a n c ei n i n c r e a s i n g s t a t i s t i c s p r e c i s i o no fs e g m e n t p o p u l a r i t y , c a c h es p a c eu t i l i z a t i o nr a t ea n ds e g m e n th i tr a d i ot h a no t h e r sa l g o r i t h m s s u c ha sl r u 。l f ua n ds oo n k e yw o r d s ：p 2 p ；v o d ；c a c h i n ga l g o r i t h m i i i 学位论文独创性声明 学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得南暑大学或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名( 手写) ：程了蟾签字日期：矽召年工月加日 学位论文版权使用授权书 本学位论文作者完全了解南昌大学有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权南昌大学可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名c 手瓢程务於导师签名c 手瓢p 球 签字日期：彤年工月如日 签字日期：励矿年2 - 月为日 第1 章绪论 1 1 课题的意义 第1 章绪论 视频点播( v o d ) 是二十世纪9 0 年代在国外发展起来的，英文称为“v i d e oo n d e m a n d ”，简称“v o d ”。顾名思义，就是根据观众的要求播放节目的视频点播 系统。它泛指一类能在用户需要时随时提供交互式视频服务的业务，即“想看 什么就看什么，想什么时候看就什么时候看”。 v o d 技术早在2 0 世7 0 年代就引起了人们的关注，但由于当时都是基于c s 架构的服务模式，而这种模式由于服务器输入输出( i o ) “瓶颈”的限制，一台 服务器只能支持有限的并发流( 千数量级的并发流) ，难以胜任大规模的并发应 用，要解决十力、百万用户同时收看视频文件的问题，不仅需要大量服务器， 还需要极宽的网络带宽，这不仅导致系统费用昂贵，而且随着用户数量的增加， 其服务器的负载越来越大，当超过一定的阀值，服务器的处理速度将会非常慢， 甚至崩溃，显然这种单纯的c s 模式是不太适用于当前的社会需求，为此，研 究者们提出了相应的解决办法：如i p 组播技术【1 3 j 和c d n l 4 - 6 1 ( c o n t e n td e l i v e r y _ n e t w o r k s ，内容分发网络) 。采用i p 组播技术来进行媒体数据分发能够有效降低 服务器和网络的负载，但组播在可靠传输、拥塞控制、安全性等方面尚存在问 题，提出多年之后仍然难以在i n t e m e t 上大规模部署【| 7 8 】。近年来内容分发网络 c d n 在i n t e m e t 上得到了的广泛部署，它通过将内容推送到距离用户更近的网 络“边缘 节点，从而降低中心内容服务器和骨干网络的负载压力，改善了用 户流媒体使用体验。但由于c d n 的“边缘”分发节点仍然采用c s 的服务模式， 系统能支持的并发用户数与c d n 系统的部署成本投入呈线性增长关系。为了提 供大规模的商用流媒体服务，运营商需投资大量的服务器硬件设备和网络带宽， 从而产生高昂的部署成本，为解决该问题，人们开始积极探寻新的方法，新的 技术。 最近几年新兴的对等网络( p 2 p ) 技术，通过节点之间的直接交互来实现信 息资源的共享【9 】。它借助节点间的交互行为，极大地减轻了系统对中心服务器 的依赖程度，使整个系统具有传统技术无法比拟的扩展性，改变了传统模式下， 第1 章绪论 并发用户数量和运营成本之i 、日j 的线性关系。并且随着该技术相关理论的不断完 善和发展，它在各领域的应用中所表现出的巨大潜力，已引起各界人士的广泛 关注。目前，v o d 技术在企业、军队、宾馆、图书馆、档案馆、博物馆、网络 教学、汽车、火车、轮船、飞机、商场、医院及小区等领域得到了广泛的应用。 根据i n f o r m a 分析公司预测，到2 0 1 0 年，视频点播技术将带来价值高达1 0 7 亿 美元的收入，这个数字充分表现了v o d 技术的巨大价值，被业界普遍认为是信 息产业新的业务增长点和经济增长点。 但由于点播当中的高度交互性需求，使得实现的复杂程度较高，影响了流 媒体的q o s ( q u a l i t yo fs e r v i c e ，服务质量) ，本文通过对p 2 p 流媒体点播技术中 缓存算法的研究，来提高流媒体的q o s 。在p 2 p 流媒体点播系统中，每个p e e r 节点会将收到的媒体数据分片在本地( 内存、磁盘) 缓存，以供其邻居节点获 取。但对于点播系统，针对某一视频文件，初始的播放时序由每个节点加入系 统时确定。在p e e r 节点加入系统时间点离散的情况下，各个节点更趋向于播放 不同时间点上的视频内容，造成节点之间缓存的数据分片重合度低。如果系统 中媒体数据缓存机制性能低下，节点将难以从系统中其他p e e r 节点下载得到相 应数据，转而则会频繁地向服务器发起数据请求，从而加重服务器的负载压力。 因此，可通过研究高效的流媒体缓存算法，来增加p e e r 节点自身的缓存服务能 力，从而降低服务器的负载压力。 综上所述，该课题是计算机应用技术中的重要课题，也是一项具有较高难 度的课题，开展本课题的研究具有重要的实用价值。 1 2 国内外p 2 p 流媒体点播技术中缓存算法研究现状 在传统的缓存算法中，最有影响的当属以资源访问的局部性原理和资源访 问频率为理论指导的l r u l l 0 j ( l e a s tr e c e n t l yu s e d ) 算法和l f u i l lj ( l e a s t f r e q u e n c yu s e d ) 算法。l r u 算法总是替换最久没有被使用的对象，认为最近 被使用者在未来也具有较高的使用价值。而l f u 总是替换出使用频率最小的缓 存对象，认为对象的使用频率越高，未来的使用价值越大。 这两种算法在p 2 p 流媒体系统中都存在缺点：l r u 存在长环模式问题( 由 于缓存大小小于对象的重用模式长度，存在对象刚被替换出缓存又被请求使用 的情况) ；l f u 存在缓存污染( c a c h i n gp o l l u t i o n ) 问题( 即过去曾被多次使用 2 第1 章绪论 的对象，即便不再被使用，仍占据着缓存空问) 。鉴于此，l r u 尉1 2 】算法将访问 频率和访问的最近性综合到效用函数的设计中，这虽然使其性能得到较好的改 善，但仍然同时存在l r u 算法和l f u 算法的缺点。 针对p 2 p 流媒体分发系统的自身特点，文献混合p 2 p 流媒体的缓存替换 算法研究i l3 】提出了基于流媒体流行度的f c n 缓存算法，该算法借助服务器 的介入来计算系统中每个流媒体对象的流行度，从而根据流行度来设计缓存效 用函数。该策略有效地利用了p 2 p 系统中的缓存对象效用值与其流行度成正比 的特性，在理论上使缓存效率得到提升。但该算法太过于依赖于中心服务器， 对流行度的统计工作会造成对服务器过于密集的请求，这不仅会给服务器带来 灾难性的负担，而且也违背了p 2 p 的初衷。 文献基于流媒体文件字节有用性的代理服务器缓存替换策略 1 4 j 提出了 b b l c b k 缓存算法。该算法考虑到用户可能只点播流媒体文件的某一部分而非 全部，提出“字节有用性 的概念，并根据字节有用性来评价缓存对象的缓存 价值。该缓存算法在流媒体代理服务器中能提升缓存效率，但由于其并非专为 p 2 p 系统而设计，未考虑到p 2 p 系统中流媒体对象的流行度等因素对缓存效用 的影响，故不完全适合p 2 p 流媒体系统。 文献基于流行度预测的流媒体代理缓存替换算法b 5 】提出了流行度预测 算法，针对流行度随时间变化的特性，利用回归分析技术预测流媒体对象的流 行度，并将该预测算法应用于流媒体代理缓存服务器的缓存替换算法之中。该 算法的缺点是运算量较大。另外，由于该算法是为流媒体代理服务器而设计， 而没有考虑到p 2 p 系统中流媒体对象在全局范围内的分布规律。 h e f e e d a 等人在文献ah y b r i da r c h i t e c t u r ef o rc o s t e f f e c t i v eo n d e m a n dm e d i a s t r e a m i n g ) ) i s 6 】中提出了基于视频文件片段的缓存机制。在该机制中，p e e r 节点 可缓存不等长的视频内容，然后向所在域的中心节点( n c s p ) i l 报所缓存分片以 及可上传速率。n c s p 计算该网络子网中的服务带宽容量，并向a c s p 和 b o o t s t r i p 节点逐级汇报得到该视频文件的全局缓存信息。n c s p 根据某视频文 件分片的全局缓存信息以r o u n d r o b i n 策略来调度p e e r 节点的缓存操作。但由 于该机制通过由p e e r 节点组成的树型拓扑来控制全局的缓存，存在可靠性低及 维护代价高的缺点。 c u i 等人在文献( ( a s y n c h r o n o u ss t r e a m i n gm u l t i c a s ti na p p l i c a t i o n l a y e ro v e r l a y n e t w o r k s ) ) 1 1 7 】中提出了基于会话的分段缓存模型，每个p e e r 节点在点播会话过 第1 章绪论 程中缓存定长的视频片断，由于缓存只在某视频文件的点播会话期间有效，因 此该缓存机制只提高了较“热”的视频文件的服务容量，对相对较“冷”的视 频文件没有服务品质改善。 在文献( ( i n t e m e tp e e r - t o - p e e rv i d e o o n - d e m a n dw i t hs t o r a g ec a c h i n go n p e e r s ) ) 【1 8 j 中，y i n g 等人提出一种集中式的缓存管理机制。在该机制中，t r a c k e r 根据每个视频文件的当前点播数和缓存副本数，计算对应视频文件的缓存评级 值。每个p e e r 节点在本地缓存空间不足时启动缓存替换操作，缓存评级值低的 视频文件将被替换。从该文献提出的缓存管理机制可知，其集中式的缓存管理 存在可扩展性问题和单点失效风险，此外，由于节点的异构性，缓存副本数并 不能真实反映系统服务容量。 g u o 等人在文献( ( d e s i g na n de v a l u a t i o no fas c a l a b l ea n dr e l i a b l ep 2 p a s s i s t e d p r o x yf o ro nd e m a n ds t r e a m i n gm e d i ad e l i v e r y ) ) 1 9 j 中提出了一种p 2 p 点播缓存机 制p r o p 。该机制包含了基于访问热度的缓存片段替换算法。在本地缓存己满 的情况下，p e e r 节点启动缓存视频片段替换算法淘汰热度较低以及热度较高的 片段。p r o p 相对以前的p 2 p 点播缓存算法可有效地解决单点失效问题，但基 于热度的视频片段替换算法并不能有效地提高系统q o s 。原因为该算法忽略了 访问热度分布在两端的视频片段的服务容量问题。具体表现在，对某时刻具有 较高访问热度的视频片段，其系统缓存副本可能仍不能满足点播的带宽需求， 而较冷的视频片段仍需要保持一定的服务能力。【2 0 j 在参阅大量相关文献资料后，发现现有的基于流行度的流媒体缓存策略大 都无法很好地应用在p 2 p 点播系统中，有些算法( 如p 2 c a s 2 m 21 2 1 】) 仅仅只关 注节点内部的状态，忽略了全局，导致流行度的统计结果过于片面。而有些算 法( 如f c n t l 3 】) 虽然从全局出发，但算法设计太过于依赖中心服务器，对流行 度的统计工作会造成对服务器过于密集的请求，这不仅会给服务器带来灾难性 的负担，而且也违背了p 2 p 的初衷。所以，一个合理的p 2 p 流媒体缓存算法， 应充分利用p 2 p 的特性，对流媒体分段的流行度进行全局性统计。本文提出了 一种新的基于全局分段流行度的节点缓存算法g s p k ，具体见本文第三章。 4 第1 章绪论 1 3 本文主要研究内容 本文在通过对p 2 p 流媒体技术的现状和未来的发展趋势，进行细致分析和 总结的基础之上，深入细致地对p 2 p 流媒体点播技术中缓存算法展开研究，提 出了一个基于全局分段流行度的节点缓存算法g s p k ( g l o b a ls e g m e n t p o p u l a r i t y b a s e dc a c h i n ga l g o r i t h m 一目。该算法是在对p 2 p 流媒体点播系统全 局考虑的基础之上，通过对流媒体分段流行度的分布式统计，结合文件内分段 采用频率的递减分布特性，综合评定各个流媒体分段的缓存效用值，使整个系 统所缓存的各流媒体分段的副本数量与其缓存效用值成正比。在与其它缓存算 法的对比实验中，g s p k 算法在提高流行度统计精确度、改善缓存空间利用率、 提高分段命中率等方面具有更好的性能。 1 4 本文结构 本文共分五章。 第一章：绪论，首先论述了开展该课题的意义，然后介绍了国内外对p 2 p 流媒体点播技术中缓存算法的研究现状及发展趋势，并说明了本文的主要研究 内容，最后介绍了本文的结构。 第二章：分别介绍了p 2 p 技术和流媒体技术，并简要介绍了一个典型的p 2 p 流媒体点播系统工作模型，最后分析、总结了当前p 2 p 流媒体系统面临的挑战。 第三章：本章从流行度的统计策略、超级节点选取策略、流行度的计算和 效用函数的设计四个方面，介绍了g s p k 算法( g l o b a ls e g m e n tp o p u l a r i t y b a s e d c a c h i n ga l g o r i t h m k ) 的设计。 第四章：用仿真软件n s 2 对缓存算法l r u 、l f u 以及g s p k 进行仿真试 验，以验证该g s p k 算法的优越性。 第五章：总结全文，并对今后的研究工作方向进行展望。 第2 章p 2 p 流媒体技术概述 2 1 引言 第2 章p 2 p 流媒体技术概述 p 2 p 流媒体技术是为解决传统流媒体服务可扩展性和可靠性差等问题，结 合了流媒体技术与p 2 p 技术，通过将视频服务器的带宽、传输、存储和计算压 力分散于各个客户端，从而提高系统的整体容量和服务能力的一项技术。然而， 由于p 2 p 流媒体技术是基于p 2 p 技术的基础之上，所以它继承了p 2 p 技术的一 些缺陷，如网络节点的高度不稳定性( 节点随机的登入、登出) 会对系统的运行 效果带来较大的影响。本章将详述p 2 p 技术领域和流媒体技术领域的相关知识， 并提出了当前p 2 p 流媒体技术所面临的挑战。【2 2 】 2 2p 2 p 技术 对等网络( p e e r - t o p e e r ，简称p 2 p ) 是目前非常热门的应用，自1 9 9 9 年以来， p 2 p 的研究一直是国外知名学府( 如美国麻省理工学院，加州大学伯克利分校和 莱斯大学等) 以及知名企业的研发机构( 如微软，诺基亚研究院) 关注的重点。它 甚至被美国财富杂志称为改变互联网发展的四大新技术之一，被认为是代 表宽带互联网未来的关键技术。 ，相对于传统的c s 模式( 通常只有服务器节点的资源得到利用) ，p 2 p 模式一 个非常显著的特点就是能充分利用“网络边缘资源 ，即节点无需依赖集中式服 务器资源，各节点可以直接进行通信。在这种模式下，每个节点具有相同的地 位，既可以请求服务，也可以提供服务，它同时扮演着c s 模式中服务器和客 户机的双重角色，甚至还可以具有路由器和高速缓存的功能，利用这个特点， 该技术可以在现有的计算资源和有限网络带宽基础上，实现大规模网络流媒体 播放，其价值潜力巨大。 现有的p 2 p 技术研究涵盖网络拓扑构造、安全与可靠性、分布式数据存储 和大规模并行计算等范畴。 6 第2 章p 2 p 流媒体技术概述 2 2 1 概念 从技术角度看，p 2 p 概念定义如下：p 2 p 系统由若干互联协作的计算机构 成，且至少具有如下特征之一：系统依存于边缘化( 非中央服务器) 设备的主动 协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中成员同 时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在，构成 一个虚拟或实际的群体。 一般认为p 2 p 系统的特征包括：大规模( 1 a r g e s c a l e ) 、无中心 ( d e c e n t r a l i z a t i o n ) 、自组织( s e l f - o r g a n i z a t i o n ) 、可扩展性( s c a l a b l e ) 以及高度动态 性( d y n a m i c ) 和异构。1 生( h e t e r o g e n e o u s ) 环境。p 2 p 系统由网络中为数众多的节点组 成，其数量一般在十力个以上。每个节点具有一定的服务能力，单个节点的资 源和计算能力可能很弱小，但整个系统可提供服务能力巨大。p 2 p 系统设计的 关键在于让单个能力弱小但总数巨大的节点通过精妙的协同工作方式，提供强 大的整体服务能力。 2 2 2p 2 p 模式与c s 模式的比较 p 2 p 模式与c s 模式的本质区别是整个网络结构中是否存在中心节点( 或中 心服务器) 。c s 模式要求具有强大处理能力和大带宽的高性能计算机，配合高 档服务器软件，把大量数据集中存放在服务器中，在集中处理数据的同时，还 可向互联网其他节点提供服务。p 2 p 模式中，各节点之间的关系是平等的、直 接联系的，具有处理信息和提供信息等功能。在p 2 p 模式中，各个节点都能够 为请求节点服务，充分利用了节点资源，因此能大大缓解c s 模式下服务器的 压力，增强了系统的鲁棒性。但提供服务的节点的不稳定性，给p 2 p 流媒体的 研究带来了许多问题。 表2 1 是p 2 p 模式与c s 模式的特性比较。c s 模式使互联网上的资源向服 务器集中，这种模式安全性好、易于管理，能满足一对多、强对弱的社会关系 形式，符合市场需求。与之相反，p 2 p 模式使资源在互联网各点均匀分布，形 成“边缘化 趋势，这种模式交互性好，即时性好，能满足一对一或彼此相当 的社会关系形式，也符合市场需求，p 2 p 的独特市场空间是现有互联网应用的 补充，两种模式将共存。 7 第2 章p 2 p 流媒体技术概述 表2 1p 2 p 模式与c s 模式的特性比较 特性p 2 p 模式c s 模式 安全性差好 易管理性差好 数据发布好差 数据接收中好 容错性好差 可扩展性好差 数据互动性好差 数据即时性好差 数据质量中好 数据覆盖率和数量差好 抗干扰性好 差 成本控制好差 2 2 3p 2 p 的拓扑结构 流媒体的传输属于耗带宽型应用，如果能有效利用系统边缘资源( 如客户端 的带宽资源) ，系统的容量便会大大增加，p 2 p 技术便是解决该问题的方案之一。 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系。 节点之间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使 用的是集中式和层次式的拓扑结构。集中式拓扑结构系统面临着过量存储、拒 绝服务( d o s ) 攻击等一些难以解决的问题，而p 2 p 技术就是要构造一个非集中式 的系统拓扑结构。 在构造过程中，需要解决的主要问题包括：系统中所包含的大量节点如何 命名、组织，如何确定节点的加入离开，如何进行出错恢复等。目前，p 2 p 的 拓扑结构分为混合式结构网络模型、无结构化网络模型、结构化网络模型。 8 第2 章p 2 p 流媒体技术概述 1 混合式网络模型 混合式p 2 p 结构是最早出现的p 2 p 应用模式，是指c s 与p 2 p 的混合，由 于它仍然具有中心化的特点，也被称为非纯粹的p 2 p 结构，经典案例就是著名 的m p 3 共享软件n a s p t e r l 2 3 】。 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 模型中，一群高性能的中央服务器保存着网络中 所有对等计算机共享资源的目录信息。当需要查询某个文件时，对等计算机会 向某一台中央服务器发出文件查询请求。中央服务器进行相应的检索和查询后， 会返回符合查询要求的对等计算机地址信息列表。发起查询的那台对等计算机 接收到应答后，会根据网络流量和延迟等信息进行选择，挑选出性能强的对等 计算机建立连接，并传输文件。n a p s t e r 的结构模式和工作原理如图2 1 所示。 n u ：8 一 ，、 u p q ：q u e r y r ：r e q u e s t d ：f i l ed o w n l o a d 图2 1n a p s t e r 网络结构和工作原理图 但是，这种对等网络模型存在很多问题，其最大的隐患就在中央服务器上， 由于n a p s t e r 在文件查询服务上采用的是集中式的架构，一旦该服务器失效，将 会使整个系统都发生瘫痪，导致整个网络的崩溃，系统可靠性和安全性较低； 并且，随着用户数量的不断增加，n a p s t e r 系统的性能也会随之下降；随着网络 规模的扩大，对中央索引服务器进行维护和更新的费用也将急剧增加，将会使 9 第2 章p 2 p 流媒体技术概述 得成本过高。 而且中央服务器的存在，容易引起共享资源在版权问题上的纠纷，事实上， n a p s t e r 就是由于版权问题，而最终走向没落。 可见，对小型网络而言，混合式模型在资源管理和控制方面占一定优势， 但该模型并不适合大型网络应用。 2 无结构化网络模型 无结构化网络模型分为纯分布式无结构p 2 p 网络和基于超级节点的无结构 p 2 p 网络。 ( 1 ) 纯分布式无结构p 2 p 网络 在p 2 p 的祖先n a p s t e r 出现后不久，g n u t e l l a l 2 4 1 第一个无结构p 2 p 网络， 在2 0 0 0 年3 月诞生于n u l l s o f t 公司。g n u t e l l a 是一个p 2 p 文件共享系统。它和 n a p s t e r 系统最大的区别就在于其网络拓扑结构，它没有中心索引服务器，被称 为纯粹的p 2 p 系统。每个节点都随机维护自己本地局部的拓扑连接关系，采用 了基于完全随机图的“洪泛”发现和随即转发机制。g n u t e l l a 网络结构模型和 工作原理型如图2 2 所示，当需要进行信息查找时，g n u t e l l a 系统将发送一个广 播消息给周边的节点，询问是否有相关的内容。如果周边节点存在相关的内容， 则向查询节点发回查找结果。为了控制搜索消息的传输范围，g n u t e l l a 系统引 入了生存时间( t t l ) 的概念。 八 u 巾。 q ：q u e r y r ：r e q u e s t d ：f i l ed o w n l o a d 图2 2g n u t e l l a 网络结构和工作原理图 1 0 第2 章p 2 p 流媒体技术概述 在g n u t e l l a 分布式对等网络模型中，每一个联网计算机在功能上都是对等 的，既是客户机，又是服务器，所以被称为对等计算机。由于互联网上的节点 数服从“p o w e r - l a w 规律( 幂率分布) ，即少数的节点拥有很高的连接度，这导 致了小世界现象( 在人类社会中，任意两个不直接相识的人，通过最多6 个中间 人就可进行通信) 。因此，g n u t e l l a 的搜索模式能够较快发现目的节点，面对网 络的动态变化体现了较好的容错能力。 但是，随着联网节点的不断增多，网络规模不断扩大，通过这种“洪泛 方式定位对等点的方法将造成网络流量急剧增加，从而导致网络中部分低带宽 节点因网络过载而失效。所以，在初期的g n u t e l l a 网络中，存在比较严重的分 区、断链现象( f i gg n u t e l l a 的用户群不能实现全体的互通) 。 资源发现的准确性和可扩展性是非结构化网络面临的两个重要问题。由于 非结构化网络一般不提供性能保证，查询可能没有结果。采用广播查询的系统 对网络带宽的消耗非常大，由此，带来了可扩展性的问题。 ( 2 ) 基于超节点的无结构p 2 p 网络 该模型的典型代表是k a z a a 2 引，它通过使用“超节点”阳来构建双层会话 的p 2 p 网络，而作为其核心的超节点层自组织成无结构网络，该模型综合了集 中式p 2 p 快速查找和纯p 2 p 去中心化的优势。k a z a a 模型如图2 3 所示。 图2 3k a z a a 模型结构图 l l o d e 第2 章p 2 p 流媒体技术概述 k a z a a 模型将节点按能力不同( 计算能力、内存大小、连接带宽和网络滞留 时间等) x e 分为普通节点和搜索节点两类。其中搜索节点与其临近的若干普通节 点之间构成一个自治的簇，簇内采用基于集中目录式的p 2 p 模型，而整个p 2 p 网络中，各个不同的簇之间再通过纯p 2 p 的模式将搜索节点相连起来，甚至也 可以在各个搜索节点之问再次选取性能最优的节点，或者另外引入一个新的性 能最优的节点作为索引节点末保存整个网络中可以利用的搜索节点信息，并且 负责维护整个网络的结构。 由于普通节点的文件搜索在本地所属的簇内进行，只有查询结构不充分的 时候，再通过搜索节点之间进行有限的“泛洪”。这样就极为有效地消除了纯 p 2 p 结构中使用“泛洪”算法带来的网络拥塞、搜索迟缓等不利影响。同时， 由于每个簇中的搜索节点监控着所有普通节点的行为，这也能确保一些恶意的 攻击行为能在局部网络得到控制，并且超级节点的存在能在一定程度上提高整 个网络的负载平衡。总的来说，基于超级节点的混合式p 2 p 网络结构比以往有 较大程度的改进。然而，由于超级节点本身的脆弱性也可能致使其簇内的节点 处于孤立状态，因此，这种局部索引的方法仍然存在一定的局限性。 3 结构化网络模型 结构化模型与非结构化模型的根本区别在于：每个节点所维护的邻居是否 能够按照某种全局特定的规则，而不是随机的方式组织起来。结构化模型这种 组织方式决定了节点之i 、日j 可以方便、快捷地查找。 结构化对等网络模型是一种采用纯分布式的消息传递机制和根据关键字进 行查找、定位的服务模型，目前的主流方法是采用分布式哈希表( d h t ) 技术【2 川。 分布式哈希表是一个广域范围内大量节点共同维护的巨大散列表。散列表 被分割成不连续的块，每个节点被分配给一个属于自己的散列块，并成为这个 散列块的管理者。在d h t 技术中，网络节点按照一定的方式分配一个唯一的节 点标识符，资源对象也通过散列运算产生一个唯一的资源标识符。当需要查找 资源时，就可以通过散列运算定位到存储该资源的节点。 经典的d h t 案例包括p l a x t o n t 2 8 1 、t a p e s t r y 2 9 1 、c h o r d s 3 0 , 3 1 】、c a n t 3 2 】等算法。 p l a x t o n 是第一个能够被d h t 系统大规模使用的路由算法，虽然该算法的 初衷是针对静态网络设计，而非p 2 p 系统。该算法采用“前串匹配 的路由模 式，每一步路由都会把信息传送到与前串更加匹配目标的节点去。例如i d 为 1 2 第2 章p 2 p 流媒体技术概述 4 7 5 3 2 的节点收到目标4 7 1 9 0 的查询请求，它与目标i d 前串有两位是匹配的， 那么，它将会把该请求发送到与目标i d 前串有3 位匹配的节点去( 比如4 7 1 1 0 ) 。 这样，重叠网中的所有节点都要根据自己的i d 记录一张路由表。具体记法是如 果i da 具有前串b ，而且b 的下一位是c ，那么，该节点针对前串b 需要根据b 的每一种可能的下一位记录一个邻居节点。例如i d 采用4 进制，i d 为1 2 3 4 的 节点针对前1 2 需要记录1 2 1 7 ，1 2 2 7 和1 2 4 7 各一个作为自己的邻居。这个算法 的优点是，当o ( n 2 ) l 拘节点间距离己知时，节点可以通过选择路由表记录的邻居 做到对路由的优化。 t a p e s t r y 算法的思想来源于p l a x t o n 算法，在p l a x t o n 算法中，结点使用自 己所知道的邻近结点表，按照目的标识符来逐步传递消息。t a p e s t r y 算法在 p l a x t i o n 算法的基础上，加入了容错机制，从而具备了可适应p 2 p 动态变化的 特点。 c h o r d 是一个使用环标识空间的系统，c h o r d 系统中节点通过对自身i p 地 址做s h a 1 运算得到一个m b i t 的标志号，这些节点按照标志号的大d , j 1 0 j i 序组 成一个逻辑环，这个环被称为c h o r d 环，环上的每个节点有唯一的前驱和后继。 环上的资源也根据s h a 1 算法得到一个m b i t 的k e y ，这个k e y 和节点的标志 号在相同的哈希空问内。每个环节点负责那些k e y 小于自身节点但是大于该节 点前趋节点的资源，每个c h o r d 节点上除了有一个前驱和后继( 表) 外，还维持 一张含m 个表项的f i n g e r 表，其中第i 个表项保存的是离n o d ei d 距离至少 2 1 长度的最近节点。对任意一次的资源查找请求，c h o r d 利用f i n g e r 表最多查 找m 次就可以定位环上资源。 c a n 采用的标识是从一个多维m e s h 中选择的。每个节点都与其对应的标 识周围的一个立方区域相关联，它的邻居就是拥有和它相邻的立方区域的节点。 路由时，消息一直是从一个节点传输到它所拥有的，与目标标识最接近的n o d e i d 的邻居。与前几种算法不同，c a n 中每个节点维护大小为d 的路由表，同 时，每一次路由都在o ( d n d ) 步内完成。特别地，当d = o ( 1 0 9n ) 时，c a n 的路 由表和路由长度将与上述其他结构化p 2 p 系统相似。 1 3 第2 章p 2 p 流媒体技术概述 2 3 流媒体技术 2 3 i 概念 流媒体是指在i n t e m e t i n t r a n e t 中使用流式传输技术的连续媒体格式，如音 频、视频或多媒体文件。流媒体技术是网络音、视频技术发展到一定阶段的产 物，是一种解决多媒体播放网络带宽问题的“软技术”。流媒体技术并不是单一 的技术，它是融合了很多网络技术之后产生的技术。它涉及到流媒体数据的采 集、压缩、存储、传输以及网络通讯等多项技术。 一般来说，流有两种含义，广义的流是使音频和视频形成稳定和连续的传 输流和回放流的一系列技术、方法和协议的总称，一般称为流媒体系统；而狭 义的流是相对于传统的下载一回放( d o w n l o a d p l a y b a c k ) 方式而言的一种媒体 格式，它支持从网络上获取音频和视频文件的连续多媒体流，客户可以边接收 边播放，改变了传统的音视频等多媒体信息的网络传输方式( 完全下载后再播 放) ，使时延大大减少。 从技术含量角度来说，流式传输可分两种，一种是简单地顺序流式传输， 一种是复杂地实时流式传输。其中流式传输的延迟受媒体播放速率、网络状况、 缓存大小等因素的影响。 顺序流式传输是仅仅对流媒体格式的文件进行顺序下载，在下载文件的同 时用户可以观看，但是，不支持拖动，即回放或快进，它是通过功能的限制来 减少网络的抖动。由于技术简单，仅需厂商提供服务器即可组建，目前在网络 上应用比较广泛。 实时流式传输中，增加了对拖动功能的支持。在观看过程中，用户可快进 或后退以观看前后的内容。这一普通单机播放功能应用于网络播放，对技术的 要求相当高，如果只是简单地在顺序播放的基础上增加这一功能，频繁的拖动 将使服务不堪重负，势必要通过更多的技术途径来解决。p 2 p 对等技术对这一 点是一个有益的补充，在一定程度上提高了实时流式传输的可行性，改善了媒 体传输的q o s 。 1 4 第2 章p 2 p 流媒体技术概述 2 3 2p 2 p 流媒体的拓扑结构 p 2 p 流媒体传输系统根据其源节点提供数据的方式可分为两种：单源的p 2 p 流媒体传输和多源的p 2 p 流媒体传输，分别如图2 4 、图2 5 所示： s 图2 4 单源的p 2 p 流媒体传输 图2 5 多源的p 2 p 流媒体传输 单源的p 2 p 流媒体系统建立在应用层组播技术3 3 , 3 4 1 的基础之上，由一个发 送者向多个接收者发送数据，接收者有且只有一个数据源，服务器和所有客户 第2 章p 2 p 流媒体技术概述 节点组织成组播树，组播树的中间节点接收来自父节点组播的媒体数据，同时 将数据以组播的方式传送给其子节点。如在图2 4 中，p l ，p 3 ，p 4 ，p 5 请求同 一媒体内容，服务器按某种策略将其组织成一棵组播树，p l 直接由服务器处获 得数据，而p 3 ，p 4 由p 1 处获得数据，p 5 则由p 4 处获取数据。显然，以组播 的方式传输媒体，源节点只需发送一个媒体数据拷贝，数据在传输过程中根据 需要自动复制，避免了单播方式下为每个接收者单独发送信息的缺点，同时减 轻了服务器的负载，节约了网络资源。但是，在这种方式下，由于节点既接收 数据又转发数据，完成应用层的路由功能，因此对节点的性能要求较高，如至 少能发送一个完整的媒体流，即上行带宽要足够大。s p r e a d i t 3 5 j ，s p l i t s t r e a m l 3 6 】 是典型的基于组播的p 2 p 流媒体传输系统。 而多源的p 2 p 流媒体传输系统，则是由多个发送者以单播的方式同时向一 个接收者发送媒体数据。在这种方式下，单个发送者提供的上行带宽不足以支 持一个完整的媒体流正常回放时所需带宽r 。如果将若干发送者的能力聚合在 一起，使得其上行带宽的总和大于r ，就能够提供正常的流媒体服务。这种方 式适于性能较低的节点，如p d a