（计算机科学与技术专业论文）p2p流媒体服务中索引技术的研究与实现.pdf

固防科学技术人学刖f 宄生院学位论文 摘要 近年来，以b i f r o 玎e m 和e m u l e 为代表的p 2 p 文件共享技术在应用领域获得了很大的 成功；另一方面，传统流媒体系统的服务能力越来越不能满足需求。于是应用p 2 p 模式 解决流媒体服务系统的瓶颈问题成为当前研究的热点。 资源定位是任何p 2 p 模式首要解决的问题。 体系的基础上，深入研究了各种资源定位方法， 播系统的资源定位技术。 本文在分析p 2 p 系统、流媒体系统背景 详细阐明了索引服务是适合p 2 p 视频点 本文主要研究p 2 p 视频点播系统的索引服务技术，其中创新性的研究工作丰耍包括 两大部分：( 1 ) 面向高质量索引源的快速检索算法和( 2 ) 基于软件流水线的索0 f 服务技 术。这些工作针p 2 p 视频点播系统，但这些技术本身可以适用于任何p 2 p 环境，甚仝其 他更广泛的领域。 对于检索算法，本文首先分析了面向高质量索引源检索的重要性；然后提出了面向高 质量索引源的快速检索算法；最后通过实验模拟验证了本算法能将p 2 p 网络中节点问平 均延迟降低8 0 左右，也通过基准性能测试验证了本算法的时空开销可以被服务系统接 受。 对于索引服务技术，本文首先分析了已有服务器结构模型的不足：然后提出了索引服 务器的非对称处理流水线、旋转式o 同步操作数据流水线等两种软件流水线技术；最后通 过试验验证了这种软件流水线技术的有效性，试验中我们在不同的环境下观测到了 53 1 0 4 9 的性能提升。 本文还对基于p 2 p 方式的视频点播系统进行了总体设计，并应用本文提出的技术实 现了其中的索引服务器。 关键词p 2 p ，流媒体，资源定位，索引，软件流水线 国防科学技术人。研究，上院1 学位沦文 a b s t r a c t w i t hb i t t o r r c ma 1 1 de m u l eb e i n gt h er e p r e s e n t a t i v e s ，p 2 p6 l e - s h 耐n gt e c h n o l o g yh a sa c h i e v e d ab i gs u c c e s si nr e c e n ty e a r s o nt 1 1 eo t h e rh a n d ，i ci sb e c o m i n gm o r ea n dm o r ed i 伍c u l tf o r t r a d m o n a ls t r e 锄i n gm e d i as y s t e mt om e e t 血en e e di nc a p a c i t y t h u s ，印p l y i n gt h ep 2 pm o d e l i ns t r e a m i n gm e d i as y s t e mt oa d d r e s st h eb o n i e n e c kp r o b l e mb e c o m e sac u r r e n tr e s e a r c h h o t s p o t r e s o u r c el o c a t i n gi st h e 矗r s tp r o b l e mi na n yp 2 pm o d e l b a s e do nt h eb a c k g r o u n dk n o w l e d g c o fb o t hp 2 ps y s t e ma 1 1 ds t r e a m i n gm e d i as y s t e m ，w ea n a l y z et h er e s o u r c el o c a t i n ga 埯or j t h m sj n d e p t h ，a n dc o m p r e h e n s i v e l yc l a r i f yt h ef a c tt h a tt h ei n d e xs e r v e ri sm em o s ts u i t a b l ew a yf o ra p 2 pv j ds y s t e m o u rr e s e a r c hw o r ki sc o n c e n t r a t e do nt h ei n d e x i n gt e c h n o i o g yf o rap 2 pv o ds y s t e m o fw h i c h t h ei n n o v a t i v e 、r ki n c l u d e s ：( 1 ) af a s ti n d e x i n ga l g o r i t t l i no r i e n t i i l gh i g hq u a i i t ys o u r c ep e e r s ， a n d ( 2 ) a ni n d e x i n gt e c h n o i o g yu s i n gs o r w a r ep i p e i i n i n g t h e s ew o r k sa i ma tt h ep 2 pv b d s y s t e m ，b u tt h et e c h n o l o g yt h e m s e l v e sc a nb eu s e di na n yp 2 ps y s t e m s ，o re v e nm o r eo t h e r n e l d s f o rt h ei n d e x i n ga l g o r i t ，w en r s t l ya n a l y z et h ei m p o r t a n c eo fh i g hq u a l i t ys o u f c ep e e r o r i e n t e di n d e x i n g a n dt h e nw ep r o p o s eaf a s ta l g o r i t h mo r i e n t i n gh i g hq u a l i t ys o u r c ep e e r s ， f i n a l l yw ep r o v eb ye x p e r i m e n t sm a tt | l i sa l g o r i t h r ni sa b l et oo p t i m i z et h ea v e r a g ed e l a y b e t w e e np e e r si nap 2 ps y s t e mb ya b o u t8 0 ，a n dw ep m v eb yb e n c h m a r kt e s t st h a tt h et i m e a n ds p a c ec o s ti sa f f b r d a b l eb yt h es e r v i c es y s t e m f o rt h ei n d e x i n gs e n ，i c et e c l r l o l o g y ，w ef i r s t l ya n a l y z et h en a wo fc u 玎e n ts e r v e ra r c h i t e c t u r e a n dt h e nw ep r o p o s e2t y p eo fs o n w a r ep i p e l i n i n gt e c h n o i o g mo n ei st h en o n s y m m e 【r i c p r o c e s s i n gp i p e l i n i n g ，a n dt h eo t h e ri sz e r o s y n c h r o n i z a t i o nd a t ap i p e l i n i n g f j n a l l y ，w ev a l i d a l e t h ee f f 色c t i v e n e s sb ye x p e r i m e n t s ，a n dw ec a ns e et h ep e r f o r m a n c ei m p r o v e m e n t sr a l l g ef r o m 5 3 t ol0 4 9 i nd i 腩r e n tc o n n g u r a t i o n s ， i nt h ee n d ，w ea i s op r e s e n tm ec o l l e c t i v ed e s 嘻n 。fap 2 pv b ds y s t e m ，a 1 1 di m p l e m e n 【m e i n d e x i n gs e r v e ra p p l y i n gt h et e c h n o l o g i e sw eh a v ep r o p o s e d 1 ( e yw o r d s ：p 2p ，s t r e a m i n gm e d i a ，r e s o u r c el o c a “n g ，i n d e x ，s o r w a r ep i p e l i n i n g 幽防科学技术人学研究生院学似论文 图目录 图l 2 2 】流式传输示意图 图2 【2 2 】分组融合示意图 图3 支持流媒体的c d n 服务 图4 1 5 1c o l l e c t c a s t 的不同组件和它们之削的相互作用 图5 3 i j 不同的准入控制导致不同的流容量增长 图6 1 1 8 1 传统文件下载方式与p 2 p 文件下载方式 图7 2 i 】 c o o l s t r e a m i n g 中o v e r i a y 网络邻节点的数掘传递 图8 超级节点模式一 图9 例拓扑结构相关检索与端到端检索 图1 0 根据坐标对节点进行聚类划分 图1 1源节点检索过程 图1 2 检索算法性能与效果的测试结果 图1 3 【3 3 j 典型的服务器软件流水线体系结构 图1 4 索引服务器软件流水线结构图一 图1 5 “双缓冲”数据流水线同步操作 图1 6 “三缓冲”数据流水线0 同步操作平滑过渡 图1 7 检索请求负载均衡方案一 图1 8 全相连超级节点 图1 9 【2 】c a n 虚拟空问 图2 0p e e r s t r e 蜘系统结构图 图2 lp e e r s t r e a m 组件及功能模块划分图 图2 2以块为单位的媒体数据并行传输 图2 3 段与块 图2 4 索引服务器结构及模块 图2 5 动态位向量 图2 6 流管理类图 图2 7 块类图 卫 _ o - 一 m m h 埔 旧 列 挖 弘 巧 拍 打 船 凹 如 引 ” 驺 弘 弘 国防科子技术人芊研究生院学位论文 图2 8 缓冲区管理模块类图 图2 9 服务协议类图 图3 0 数据传输的c a l l _ b a c k 机制 图3 1 请求协议类图 图3 2 a c e 库结构图 图3 3 数据下载模块类图 图3 4 数据发送模块类图 图3 5 数据、消息传递流向图 图3 6 数据下载功能时序图 图3 7 数据发送功能时序图 图3 8 播放器转发功能时序图 4 l 4 3 4 4 4 4 4 5 4 7 4 7 4 8 4 9 5 0 5 1 国防科学技术大学研究生院学位论文 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题日：星翌碰壁l 丝壁堑生重型堡生：i 垒经蕉塑 学位论文作者签名：鏖麴日期：砸年，三月z 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：雠幽膨垒蘧型遂兹鳋丕僦照 学位论文作者签名：缴 日期：年z 月三日 作者指导教师签名：荔璧至日期：掰年2 月c 日 国防科学技术人学研究生院学位论文 第一章序论 1 1 课题背景及意义 从流媒体服务系统展历程来看，传统流媒体服务器体系结构经历了三个阶段：第一阶 段是1 9 9 5 1 9 9 9 年左右的单服务器体系结构，由单一的媒体服务器向客户提供服务，服 务器是瓶颈；第二阶段是1 9 9 9 2 0 0 2 年左右的并行或集群多服务器体系结构，由相对紧 耦合的服务器群向客户提供服务，服务器群的接入网络以及主干网络的带宽是瓶颈：第一i 阶段是2 0 0 1 2 0 0 3 年左右的多服务器加代理缓冲服务器体系结构，由相对客户较近的代 理缓冲服务器通过缓冲预取策略从多服务器获取数据再向客户提供服务，能满足的并发用 户数与代理缓冲服务器的数量和位置相关。 三个阶段的推进就是为了提高流媒体服务系统的并发用户量。然而，随着流媒体成刖 范围不断拓宽，用户数量的不断增长，传统的c s 流媒体服务模式固有缺陷使得服务器负 载重、价格高，主干网传输压力大，系统越来越难以满足需求。 p 2 p 是一种利用广泛分布的自治资源来完成特定功能的技术，它能较好地适应面向海 量伸缩性的应用系统的需求。其资源包括计算、存储、网络带宽等，所完成的特定功能可 以是分布计算、数据内容共享、通信协作以及流媒体服务等。与传统的c s 模式不同， 在p 2 p 中分布的各个对等节点地位平等，直接交换共享计算、存储、信息等资源和服务， 每个节点在享受服务的同时，还为其它节点提供服务。这样，通过廉价节点的协作就能产 生巨大系统增益。 将p 2 p 的思想应用于流媒体服务，请求节点不仅可以向媒体服务器请求服务，而且 可以向先前已被服务或直接拥有该媒体文件的对等节点请求服务，就可以依靠大量对等节 点自身的能力来减轻服务器和主干网络的压力。我们的研究内容就是利用p 2 p 技术构建 新型的流媒体服务系统，使得在较低的成本水平就可使系统具有良好的扩展性、健壮性和 适应性。 目前流媒体服务已成为i n t e m e t 上的重要业务，并且所占比例有越来越高的趋势，本 课题的研究不仅能够推动流媒体技术的发展，也将对流媒体服务应用起到促进作用。 第1 页 国防科学技术人学研究生院学位论文 1 2 已有技术研究现状 1 2 1 传统媒体流传输方式 多媒体数据包括文字、图形、语音、图像等等，计算机对多媒体数据进行处理，要解 决信息采集、编码、压缩、存储、传输、解压缩、解码、信息重现等等一系列的问题。出 于视频文件所包含的信息量大，需要占用很大的存储空间，使得视频文件在i n t e r n e t 上 进行流式传输有许多的技术困难。 在早期，人们要观看i n t e r n e t 上的视频节目需下载整个视频文件，而流媒体技术例 的产生、发展使得人们只需等待很短的时间就能以边接收边播放的方式欣赏视频节f 1 ，消 除了以往下载方式带来的长时间等待。 流式传输中，服务器将原视频文件分解成个个小的数据包，按照特定的顺序，以比 较平稳的速度发送到网络上；客户端的播放程序可边接收数据边播放，不必等到文件整个 内容全部到达，如图1 所示。流式传输还带来另外两大好处：一是，只占用很少的用户端 空间；二是，对媒体内容的版权进行了保护。 一1 1 卜一i i 卜鳓一l 源文件发送 接收 缓冲区播放 图1 流式传输示意图 流媒体传输有许多不同的实现方式，本小节将对此作逐一介绍。 1 2 1 1 广播和组播技术 在广播1 2 5 】方式中，数据包的单独一个拷贝将发送给网络上的所有用户( 无论用户需 要否) 。无疑它减小了网络的负载和发送者的负担。但广播方式只有在支持广播的网络上 才能实现，使得广播方式通常只能在小范围内使用。 而在组播方式中，数据包将发送到一个组地址，所有加入改组的用户都可以收到。 目前，组播已经得到了广泛的应用，很多实时的多媒体会议及教育系统都是基于组播j f ：发 的。 1 2 1 2 广播式点播技术 广播式点播是以。播的方式满足点播需求。其基本思想是将一个节目划分为若 = 段 第2 页 国防科学技术人学明究生院学位论文 每一段单独占用一个广播频道并在该，。播频道上轮循，“播。用户在点播时，先等待令第 段的开始；在播放某一段时，可以同时接收下段的视频内容，以达到段段之洲的不剐断 播放。由于视频输出采用广播模式，且分段轮循，因此用户在任意时刻恕删石该仃uuj ， 只要稍作等待便可，达到点播观看的目的。该模式一般应用于热门节目的播放中。 1 2 1 3 分组技术 在v o d 应用中，由于大多数请求集中在少数的热门节目上，而且经常集中在一个黄 金时段，在此黄金时段中每一个短的间隔时间内都可能有对同一节目的大量请求。分组技 术【27 j 的做法是，将黄金时间段平均分成许多小的时间间隔，针对每一个时问州隔，收集 所有的用户请求并加以分组，相同请求的用户在同一组中。然后服务器为不同的请求备分 配一个信道，同一组的用户共享一个信道匕的相同的视频流。这种策略虽然使。些川户的 时延增大，但却可能大大提高服务器的服务能力。 1 2 1 4 融合技术 融合技术在于将针对于同节目请求的时f 比较接近的多个视频流合并为一个流以 减少丌销。融合技术【27 j 同分组技术的基本出发点是相同的，都是为了使得多个用户共享 同一视频流。与分组技术不同的是，融合技术首先保证即时响应用户请求，然后根据情况， 对相同节目且时间接近的多个视频流，在时间相对较快视频流中插入一些本不必要的帧 ( 如重复帧) 以减慢其步伐，相反，在时间相对较慢视频流中丢弃一些帧( 如不重要的帧) 以加快其步伐，一旦出现视频流同步时，就让它们共享一个信道，从而达到节约带宽资源 目的，以让更多的用户能得到服务。 1 2 1 5 分组融合技术 分组融合技术1 2 是分组技术和融合技术的结合物。一方面，使用分组技术，对用户 进行分组，同组用户共享信道；另一方面，使用融合技术，将节目相同且时间接近的不同 信道进行融合，使小组成为大组。这样，将更加提高网络带宽的利用率，也减少系统丌销。 如图2 ，在 o ，1 时段请求q 、q l 。，共享流从时刻，i 发出的蜀，在h f 2 】时段请求q 一、 q 2 。，共享流从时刻屯发出的$ ，在时刻包丌始对s l 和岛进行融合，直至它们速度相同， 这州恢复s 至正常速度，去掉，让两组请求起共享s l 。 第3 页 国防科学技术人学研究生院学位论文 1 2 2 内容传送技术 图2 1 2 5 1 分组融合示意图 随着i n t e r n e t 的迅速发展，媒体网站和企业网站的业务都急剧增加，因此，网站必 须拿出应付的策略。并行服务器结构，从局部来看它是一种很好的策略，但从整体上看， 还是存在很大的问题：i n t e r n e t 难堪重负。因为，传统的媒体发如系统采用标准的集f 式的客户机服务器技术实现内容的传送，每个客户端都需要创建一个直接连接服务器的 信道呻1 。 1 2 2 1 镜像服务器技术 镜像服务器技术是一种“送货上门”的技术。一些门户网站在需求量很大的地方建立 镜像服务器，它既分担服务器的网络流量，同时也给i n t e r n e t 减轻了很大的压力。 1 2 2 2 边缘服务器技术 在这种架构中，发布服务器由多台位于核心的广播服务器和位于网络边缘的服务器组 成，形成一种可伸缩的应用级内容传送解决方案。任何一台广播服务器都可以向边缘服务 器发布内容，而由边缘服务器向客户提供服务。这种新的架构具有很好的扩展性。随着企 业的发展，网络的流量不断增加，可以在网络的边缘增加这类服务器。 1 2 2 3 c d n 技术 c d n 汹( c o n t e n td e l i v e r yn e t w o r k ) 技术也是提供边缘服务。与边缘服务器不刷的足， c d n 服务由独立的运营商提供。c d n 可简单理解为网络缓存、网络代理。它的- j ：作力式是 将网站的内容发布到最接近用户的网络边缘，使用户可以就近取得所需的内容。c d n 主要 用来减少骨干带宽的负担，提高骨干网的利用率。 如图3 所示，流媒体的c d n 服务主要有两方面的用途：一是用于处理访问量比较大的 网站的闩常流量，例如c c t v 刚站：二是_ 【= f j 来应付重大事件所产生的爆发流蛩，例如个、 第4 页 国防科学技术人学研究生院学位论文 所做的重大活动的网上直播。 图3 支持流媒体的c o n 服务 1 2 3 p 2 p 网络环境下媒体流传输 从2 0 0 1 年丌始，针对p 2 p 模式媒体服务技术的研究逐步引起众多研究者的天；j ，2 0 0 2 年至今发表了许多该领域内的论文，其研究技术主要可分为两类： 1 2 3 1 p 2 p 应用层组播树 在早期的1 1 1 t e m e t 体系结构中，i p 层实现最小的功能尽力传输的单播数掘服务， 而终端系统实现诸如错误处理、捐j 塞控制、流量控制等功能。这个最小最大原则是i n t e m e t 能从研究性网络走向全球的、商业性基础设旖的一个重要的技术原因。 随着i n t e m e t 的飞速发展，应用也不断在深入发展。应用需要更加丰富的网络功能。 特别对于媒体服务而言，由于媒体数据具有数据量大、持续时间长、要求带宽高等特点， 如果能够把组播功能和流调度策略结合起来，就能使得服务能力迅速增长，满足海量用_ r l f 需求。那么，组播功能应该放在哪一层呢? 根据端到端原则，任何功能应该尽量放在上层， 除非放在下层能获得巨大的性能受益。 如果放在i p 层，i p 层组播有以下缺点：( 1 ) 需要路由器保持每个组播组的状态信息， 这违反了原有设计的“无状态”结构原则，增加复杂性并有严重的扩展约束，尤其是在各 网段带宽、节点处理能力、节点存储能力等方面存在较大差异的情况下：( 2 ) 需要在基础 架构层有相应改变，这就延缓了广泛实施配置的进程，因为需要在路由器中增加新的协议。 应用层组播基本能解决i p 组播所面临的困境：( i ) 所有数据包都是通过单播传输的， 无需路出器的支持，得到广泛配置的速度加快；( 2 ) 底层物理网络无需保存状态信息，l j 终端节点仅需要保存该组少量与其邻近成员的信息；( 3 ) 利用单播可以有效地采取适合媒 体应用特点的错误恢复、流量控制、捌塞控制等策略。 但应用层组播也有其缺点：( 1 ) 效率不高，一条应用层链路可能会反复经过同一条物 理网络链路；( 2 ) 延迟大，两个终端节点之问的通讯可能要通过其它节点，这使得所有节 国防科学技术人学硼究生院；叫市沦文 点之问很难同步接收数据；( 3 ) 丢包概率大。 基于应用层组播树的流媒体服务模式是当前的研究热点，它适合于架构视频直播服务 系统，或热门节目的点播服务，即适合于节目请求率高、并发请求量大的媒体应用需求。 典型的p 2 p 应用层组播树协议有s p r e a d i t 、n i c e 3 1 】和z 培z a g 【3 2 】等等。 1 ，2 3 2 非树型p 2 p 流媒体 所谓非树型，就是指在服务节点和请求节点之1 训的逻辑拓朴结构不再是树型结构。请 求节点不再通过树的中间节点中转得到数据。新加入节点首先找到能为其提供服务的节点 集合，然后制定相应的多源流调度策略，最后直接向这些服务节点请求服务。 非树型对等模式媒体服务涉及三个层次的研究：( 1 ) 媒体内容查找，即如何找到所需 的媒体数据；( 2 ) 媒体流调度与控制，即采用什么策略以保障服务质量的方式将媒体数据 传输到本地：( 3 ) 使用何种服务策略能使整个系统的容量增长更快：( 4 ) 媒体数据前l 局弓 存储，即如何将媒体数据切分并在网络中冗余布局的策略。由于媒体文件数据量大，且热 点现象显著，分布与存储策略也将对系统整体性能有显著影响。这几个层次并非相互独立， 而是相互依赖的。 目前针对非树型对等模式媒体服务的研究论文及项目较少，已有的成果有 p r o m i se f ”j 和p ba 【”j 等。下面介绍一个典型的p 2 p 流媒体系统及其中的关键技术。 1 2 3 3 p 2 p 实时流媒体服务模型c 0 1 1 e c t c a s t c o i l e c t c a s t 的主要研究结果是提出了一个拓扑感知节点选择技术，这为p 2 p 实时流 媒体的一个主要研究问题之数据源节点选择问题指明了一个研究方向。 c o l l e c t c a s t i 5 】是美国印第安纳州普度( p u r d u e ) 大学的研究者提出的一个新型p 2 p 实时 流媒体服务模型，它解决了这个问题：在一个高度多样化和动态变化的p 2 p 网络中，如 何为每个p 2 p 流会话选择、监视并可能地交换发送节点以维持尽可能好的流质量。这种 动态性和多样性反映在各个节点以及节点间的网络连接这两方面：( 1 ) 一个发送者在任何 时间都可能停止对p 2 p 流会话的贡献；( 2 ) 一个发送者贡献出来的输出带宽可能变化；( 3 ) 一个发送者与一个接收者之间的连接可能显示出不同的端到端的带宽、损失和失效率。因 此，个p 2 p 流会话的质量依赖于对节点的明智选择、对发送者网络状态的持续监视、 当发送者或网络失效或严重性能下降时对发送节点的及时交换。 每个c 0 1 l e c t c a s t 流会话包含多个发送者，及它们组成的两个发送者集合：箭用发送崭 集合和活动发送者集合。在会话期阳j ，两个发送者集合的成员可以交换。 菊6 页 国防科学技术人学研究生院学位论文 c o l l e c t c a s t 的整个操作位于应用层，但它推断底层网络的状况，包括：( 1 ) 为选择发 送者而推断底层网络拓扑结构和性能的信息：( 2 ) 监视节点和连接状态，能对节点连接失 效或性能下降以较低延迟做出反应；( 3 ) 动态交换活动节点和备用节点，使得活动发送：符 点总的网络性能可符合要求。 研究者们实现了c o l l e c t c a s t 的实际网络仿真测量，结果显示基于c o i l e c t c a s c 的p 2 p 流服务模型比仅仅基于端到端网络性能信息的p 2 p 流服务模型具有更好的性能。该测量 是通过实现一个基于c o l l e c t c a s t 的p 2 p 流媒体系统原型p r o m i s e ( ap e e r t 0 _ p e e rs e r v i c e f o rm e d i as t r e a m i n g ) 完成的，以p l a l l e t l a b 【3 3 j 为试验环境。 如图4 所示，c o l l e c t c a s t 是一个基于p 2 p 查找子层的层次网络，出如下四个部分组 成：( 1 ) 拓扑推断与标记；( 2 ) 节点选择；( 3 ) 速度和数据分配：( 4 ) 监视和适应。c o l l e c t c a s t 的组件分成接收方和发送方功能。在c o l l e c t c a s t 中接收者起着主导作用。 ( m f r i “毗一s 岫# 如咄a 咖口r o 螂d 图4 9 1c o | | e c i c a s t 的不同组件和它们之间的相互作用 c 0 1 l e c t c a s t 的关键组件是节点选择。因为p 2 p 环境是高度多样化和动态的，选择最 好的节点来服务流会话对提供想要的高质量的流是至关重要的。些应用使用随机技术或 端到端技术。随机技术随机地选择能够实现总的速率要求的一些节点即使这些节点可能 有低的可用性和共享拥塞路径。端到端技术估计出从每个候选者到接收者路径的良好度， 在这些单个路径的质量和每个节点的可用性基础上，选择活动集。端到端技术不考虑节点 之间的其享路段，如果共享一个拥塞路段的一些节点被选择到活动集中，则这些共享路段 可能成为瓶颈。选择技术应该避免经常失效和共享拥塞路径的节点，c o l l e c t c a s t 使用拓扑 感知技术。它推断底层拓扑及其特性，并且考虑路径每一段的良好度，这样够避免路径扶 享拥塞路段。 一旦选择好活动节点，每个节点就会分配到一个流速率和数据块，流会话也就丌始了。 在一个长的流会话过程中，环境可能发生变化：节点可能失效，或网络路径可能变得拥塞。 为了维持接收方好的流质量，c o l l e c t c a s t 的监视和适应模块的功能就是适应这些改变。住 第7 页 tli引引引lll 国防科学技术人彳训宄生院j 1 ：i 7 = 论文 流会话期矧，接收者收集每个发送节点的丢失率和和贡献的流速，这些统计信息被用来更 新友好拓扑。进而调整活动集。 对于节点失效，可用两种方法检测：( 1 ) 从建立在接收者和每个发送者之f 剐的t c p 控 制信道( 例如，连接重建) ，和( 2 ) 如果来自这个节点的速率下降。一旦检测到失效，就会 用新节点替换失效节点来调整活动集。 对于网络波动，接收过程在接收到媒体文件的每个段后做出是否交换活动集的决定 ( 一个段只有几秒钟的长度) 。交换意味着两种行为：( i ) 为当前活动节点集重新分配速度， 或( 2 ) 通过增加或替换节点来调整活动集。在接收一个段后，接收者计算r = ( 矗：月。) 凡， 其中r 。是在最近一段时间的平均总速率，是媒体播放速率。若r 0 意味着网络状况_ f 降超过了可容忍的水平，需要进行活动节点调整。 1 2 3 4 p 2 p 流媒体系统快速扩容 p 2 p 流媒体系统的容量定义为系统能同时提供的p 2 p 流会话总数。因为一个p 2 p 流 会话包括输出带宽总和为如( 媒体播放速率) 的多个供应节点，所以系统在时刻f 的理论 容量为： 吲归l k 掣 ( b ( f ) 是系统在时刻，的供应n 点集合) 。 文( 3 4 】提出了一个称为区分准入控制( 舢( 1 ) 协议的系统快速扩容技术，它的撼本鬯 想是：当有多个节点同时请求媒体内容而系统不能同时满足这么多个请求时，系统尽- j 丁能 优先服务输出带宽高的节点，以达到系统容量快速增长的目的。 设r 为一个流会话持续时间。设置初始状态：两个输出带宽为月卅的2 类供应节点尸。、 牟，两个输出带宽为月仃2 的1 类供应节点牟、掣，两个2 类请求节点尸1 、尸2 一个1 类请求节点p 。系统初始容量为 1 4 + l “+ 1 2 + 1 2 】= l 图5 显示不同的分配决策导致不同的流容量增长。 第8 页 里堕竺至：丝奎垒耋竺塞尘堕；兰堡篁奎 鲥田虹汕 叫_ 砰_ 辟 嘞埘m l 也g 桦一( 州一桦j 图5 【圳不同的准入控制导致不同的流容量增长 图5 ( a ) 中，对请求节点的服务先后次序依次为：掣、覃、夥，容量增长情况是： l l 2 3 ，总的时间为3 f ，请求节点平均等待时间为( 0 + 开2 n ，3 = l 图5 ( b ) 中，对请求节点的服务先后次序依次为：口、f 和牟，容量增长情况是： 1 2 3 ，总的时间为27 1 ，请求节点平均等待时间为( 丁1 + 0 1 3 = 2 3 。 文 3 5 】提出让请求节点在满足一定的条件下可以在接收流的同时为其它节点提供i l f 服务。这也是p 2 p 流媒体系统容量快速增长的另一个很好的策略。 1 2 4 实际使用中的p 2 p 系统 b i t t 0 r r e n t 与e m u l e 同属p 2 p 文件共享系统，其工作原理大体相当：共享的义件设t u 分成相对较小的块：数据传输以块为单位，同时发生在p e e r 与p e e r 之m 和p e e r 与“服务 器”( 即种子节点) 之间；任何p e e r 在下载数据块的同时也为其他p e e r 提供数据。 p 2 p 系统数据传输路径如图6 所示，传统的文件下载方式( 左) 是各个客户机与服务 器相连，下载所需文件。当采用这种方式提供大型热门文件下载时，需要投入极大的服务 器、网络资源。而p 2 p 文件共享系统( 右) 大大缓解了服务器压力，不会遇到类似问题。 第9 页 里堕坠兰! ! 尘垒；型! l 至尘鳖；型! 兰兰 圄6 口”传统文件下戴方式( 左) 与p 2 p 文件下载方式( 右) 这种p 2 p 的方式大大减轻了服务器的负担，增强了文件发布系统的扩聪+ 陆。将p 2 p 思想应用于流媒体系统，点播用户在接收媒体数据的同时也为其他用户提供媒体数掘，f 好司以解决传统c ，s 结构给流媒体系统带束的瓶颂问题。 目前已投入使用的p 2 p 流媒体系统主要以p p l i v e 和c 0 0 l s t r e a m i n g f 圳为代表。这两 大系统均采用了网状的o v e r l a y 结构，均达到了很高的同时在线人数。c o o i s t r e a m 【n 叠的 o v e r l a v 网络邻节点数据传递图如图7 所示。 图7 】c 。s l r e a m m g 中( ) v e h a y 网络邻节点的数据传递( a 为源节点) l _ 3 本文的主要研究工作 本文主要研究p 2 p 幸见频点播系统索引服务技术其中创新性的研究丁作丰要包括两 大部分：面向高质量索引源的快速检索算法和基于软件流水线的索引服务技术。 对于检索算法，本文首先分析了面向高质量索引源检索的重要性；然后提出了面向高 质量索引源的快速检索算法；最后通过实验模拟验证了本算法能将p 2 p 网络q j 节点问平 均延迟降低8 0 左右，也通过基准性能测试验证了本算法的时空开销可以被戕务系统接 受。 列于索引服务拄术，本文首先分析了已有服务器结构模型的不足：然后提出了索引服 务嚣的非对称处理流水线、旋转式0 同步操作数掘流水线等两种软件流水线技术；最扃通 第1 0 页 国防科学技术大学研究生院学何论文 过试验验证了这种软件流水线技术的有效性，试验中我们在不同的环境下观测剑了 53 一1 0 4 9 的性能提升。 本文研究工作以索引服务器为研究背景，但这些技术可应用于多种资源定位技术( 如 d h t ) 当中，甚至其他更多领域，并不仅仅局限于索引服务器。 l - 4 论文结构 全文共分七章： 第一章介绍课题的研究背景及研究现状。 第二章对现有的p 2 p 索引技术进行了深入的分析，指出了“索引服务器专超级：符点”的 模式是应当在p 2 p 流媒体系统中采用的资源定位方式，同时也指出了其中仍需要 研究的问题。 第三章提出了面向高质量索引源的快速检索算法，解决了资源定位中普遍存在的定位质 量和处理速度之间的矛盾。 第四章提出了基于软件流水线的索引服务技术，在大大提高服务器检索性能的基础上， 本章还分析了“索引服务器专超级节点”模式的具体技术细节。 第五章对p 2 p 视频点播系统进行总体设计。 第六章对p e e r 节点的软件进行分析、设计与实现。 第七章总结全文，并阐述了进一步的研究方向。 第l l 页 国防科学技术人。、研究尘院学似论文 第二章p 2 p 流媒体系统资源定位技术分析 资源定位是p 2 p 系统首要解决的问题，索引技术是资源定位的一种方式。本章在分 析各种p 2 p 资源定位技术和流媒体系统自身特点的基础上，得出适合p 2 p 流媒体系统的 资源定位方式，并指出了这种方式尚需研究的问题。 2 1 已有的p 2 p 资源定位方法 在p 2 p 系统中，请求节点获取资源的过程可以大致分为两步：第1 步是资源定位， 第2 步是资源获取。资源定位是指请求节点通过查询得知所需资源的拥有者，即源节点。 资源定位主要有以下4 种方式： ( 1 ) p 2 p 的鼻祖n a p s t e r 例采用中央服务器进行集中式检索。所有新加入节点都需刮 索引服务器上注册所共享的资源对象的索引信息。资源搜索时，发起搜索的节点直接将搜 索请求提交给索引服务器，由索引服务器返回保存了相关资源对象的节点列表。发起搜索 的节点从节点列表中选择某一节点，从该节点上直接下载需要的文件( 不再通过索引暇务 器) 。 以n a p s t e r 为代表的集中式非结构化拓扑的优点是资源定位快且准确，资源搜索丌销 为o ( 1 ) ，实现和维护较为简单，可以支持灵活的资源搜索条件，能比传统的c s 服务模 式提供更强的服务能力。但集中式非结构化拓扑的缺点也是明显的，集中式索r j l 服务器t 、j 能会带来可扩展性和单点失效等诸多问题。 由于集中式非结构化拓扑p 2 p 系统相对简单，资源定位技术相关研究较少。 ( 2 ) 随后的g n u t e l l a l 6 】、f r e e n e t 【8 j 等松散全分布系统采用消息泛洪机制在整个系统中 广播查询请求。这种方式避免了( 1 ) 中的瓶颈问题和单点失效问题，然而广播式的消息 量在最一般情况下正比于矛是系统中节点数量) ，检索请求会给整个系统带来过重的负 担，是一种扩展性不好的方案，也不适合在大规模p 2 p 系统中采用。 g n u t e l l a 采取了典型的全分布式非结构化拓扑，没有索引服务器，每个节点都是平等 的，称为s e r v a n t 。新节点加入时，通过一些“带外”方法( 如通过一些公用w e b 站点等) 获知已在g n u t e j l a 系统中的几个节点，然后通过这几个节点得到g n u t e l l a 系统中更多节点 的列表，从中选择某几个作为邻居。各个节点上的资源对象( 文件) 只保存在本地，不发 布到其它节点上。g n u t e l l a 采用受限t t l ( t i m et ol i v e ) 的泛洪( n o o d i n g ) 技术来进行 资源搜索，每个节点都将接收到的搜索请求广播给所有的邻居节点，同时搜索清求的t t l 值减1 ，直到t t l 的值为o 。如果某节点发现本地有符合搜索条件的资源埘缘，陔h 点会 沿着搜索路径反向传播q u e r y h n 消息到发起搜索的节点，然后两个节点通过h t f p 协议 第j 2 页 田防科j 技术人 删宄7 t 。阮。刊论文 直接传输文件。 g n u t e l i a 系统的维护简单，全分布式结构，具有良好的容错性，能够支持灵活的搜索 条件，并且资源搜索的命中率通常较高。但g n u t e l l a 的泛洪式资源搜索产生的消息数多， 对网络带宽的消耗很大，并由此限制了其扩展性：一个典型g n u t e l l a 系统中的搜索请求会 产生2 万多个搜索消息，对实际g n u t e l l a 系统的评测表明【7 】一次资源搜索在g n u t e l l a 系统 中会消耗3 5 m b p s 的带宽。g n u t e 】1 a 的受限泛洪技术能够搜索的范围有限，只能搜索节点 几( t t l ) 跳之内的资源对象。 f r e e n e t 是能够提供匿名性的p 2 p 文件共享系统，可以保证文件的发布者、查询者和 存储者的匿名性。f r e e n e t 中对数据文件进行加密存储，每个文件在系统中大量复制。 在f r e e n e t 中，文件发布时，首先计算文件的二进制关键字k e y ( 根据文件名通过s h a 1 算法计算得到) ，并产生个h t l ( h o p st oj i v e ) 值。h t l 值决定该文件在多少个符点i 复制。发布节点首先查看自己“路由表”中与k e y 最相近的关键字，将数据发白到对应的 节点上去，并且被发布的文件会在从初始节点到目的节点的路径上进行沿路复制。 在f r e e n e t 中，资源搜索时首先获取需搜索文件的k e y ，然后发出搜索消息。当任一 节点接收到搜索消息时，首先进行本地匹配，若匹配成功则返回结果；否则将搜索消息转 发到本地“路由表”中与k e y 最相近的关键字对应的节点上。搜索消息会直转发f 出， 直到搜索成功或者 r r l 变为o 。如果搜索成功，则在搜索路径中的各节点上复制陔数据， 并在各节点的路由表中建立数据源和k e y 的映射。如果搜索消息转发后出现了路由环或节 点失效，则根据路由表中次相近的关键字进行转发。f r e e n e t 中同一节点会存储较多的k c 相近的文件，同时其路由表中也是相近k e y 的聚集。每个节点使用l r u 算法来箭换文件， 很久没有被访问过的文件会被自动淘汰。 f r e e n e t 对文件进行了大量复制，资源搜索只需搜索到文件的任一个副朱f r e e n e t 不能 保证资源搜索的效率和准确性。模拟显示【9 】if r e e n e t 系统的拓扑结构会不断演变，在经 过较长时间后，f r e e n e t 会形成类“s m a l lw o r l d ”拓扑，资源搜索性能有所提高。 ( 3 ) 而c h o r d 、c a n 【2 1 、p a s t r y ( 3 】、t a p e s t r y 【4 1 等结构化全分布系统则采用d h t 方式 将检索分布到系统的每个节点上去。这种技术将哈希表的思想应用到了p 2 p 系统中，它 将检索源看作( k e y v a j u e ) 信息