（计算机应用技术专业论文）p2p点播系统模型与模拟器的研究、设计与实现.pdf

厂_ _ _ 1 - i 一1 删 苏州矣学学位论文使用授权声明 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 ， 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文日 论文作者签名：塞垫楚日 导师签名：隧越日 期：竺21 ：垒卑 期：印叩! 乡! 么 i p 2 p 点播系统模型与模拟器的研究、设计与实现 摘要 p 2 p 点播系统模型与模拟器的研究、设计与实现 摘要 目前，对p 2 p 流媒体直播系统的研究已趋于成熟，但点播系统研究中还有不少关 键问题尚待解决。本文对几种典型p 2 p 流媒体模型进行详细分析，针对其不足，结合 网状结构系统的协议简单、鲁棒性强和树状结构控制开销小、数据调度简单等优点， 设计了一种基于跳表的视频点播系统模型s t - p 2 p v o d ( s k i pt a b l eb a s e dp 2 p v o d ) 及 相应的模拟器p d p 2 p s i m ( p a r a l l e ld i s c r e t ee v e n td r i v e np 2 ps i m u l a t o r ，并行离散事件 驱动p 2 p 网络模拟器) ，模拟测试结果表明，新模型对加快v o dv c r 操作时对资源的 查找定位速度、改善系统性能具有良好效果。论文对s t - p 2 p v o d 模型中的拓扑结构、 节点管理、数据调度、控制协议与交互、p d p 2 p s i m 模拟器的设计实现等关键课题进 行了深入的讨论。 在s t - p 2 p v o d 系统模型的拓扑结构中采用了基于跳表的拓扑结构和网状的伙伴 节点组织结构的双层结构。基于跳表的资源定位可以有效支持v c r 操作，减少v c r 时延和服务器负载。在数据调度方面，采用推拉结合的思想，根据缓冲区的动态状态 选择按推或拉的方式进行调度，保证了数据尽量在播放前到达，提高了数据调度的有 效性，减少了控制开销。论文还对控制协议中系统节点间交互的消息类型和格式进行 了定义，并描述了消息节点间的传递过程和节点对消息的处理过程。 论文研究、设计实现了s t - p 2 p v o d 网络模拟器，对该模拟器的设计时，考虑到 了p 2 p 网络模拟的通用性，采用了面向对象思想对整体架构进行设计。为提高p 2 p 网络模拟器的模拟速度，设计“生产者与消费者”双线程并行离散驱动模型，克服了 大规模p 2 p 节点模拟时单线程串行处理离散事件速度过慢的缺陷。在p d p 2 p s i m 网 络模拟器基础上，对s t - p 2 p v o d 模型进行系统仿真，并与传统的p 2 v o d 模型进行了 性能测试对比，测试结果表明了新模型很好的可扩展性、健壮性和高效性。 关键词：p 2 p 网络，视频点播，跳表，数据调度，p 2 p 网络模拟器 作者：袁堂夫 指导老师：陆建德 m o d e l ，t h en o d em a n a g e m e n t ，t h ed a t as c h e d u l i n g ，t h ec o n t r o lp r o t o c o l sa n di n t e r a c t i o n ， a n dt h ed e s i g na n di m p l e m e n t i o no f t h es i m u l a t o rp d p 2 p s i m t h es t - p 2 p v o ds y s t e mm o d e lu s e sd o u b l el a y e rt o p o l o g yt h a ti sb a s e do ns k i pt a b l e s a n dm e s hs t r u c t u r e dp a r t n e rn o d e s r e s o u r c el o c a t i n gb a s e do ns k i pt a b l e sc a ne f f e c t i v e l y s u p p o r tt h ev c ro p e r a t i o n ，r e d u c ev c rl a t e n c y a n ds e r v e rb u r d e n t h ec o m b i n e d p u l l - p u s hi d e a sa r eu s e dt os c h e d u l ed a t a a c c o r d i n gt ot h ed y n a m i cs t a t eo f t h ev o d b u f f e r , t h ep u s ho rp u l lw a yi ss e l e c t e dt os c h e d u l ed a t at h a te n s u r e st h ed a t aa r r i v ea se a r l i e ra s p o s s i b l eb e f o r ep l a y i n g ，s oa st oe n h a n c et h ee f f e c t i v e n e s so ft h ed a t as c h e d u l i n ga n d r e d u c ec o n t r o lo v e r h e a d t h et y p e sa n df o r m a t so fm e s s a g e st h a ta r ei n t e r a c t e db e t w e e n n o d e si nc o n t r o lp r o t o c o la r ed e f i n e d t h em e s s a g et r a n s m i t t i n gp r o c e d u r ea m o n gn o d e s a n dt h em e s s a g e p r o c e s s i n gi nn o d e sa r ea l s od e s c r i b e di nt h et h e s i s t h i st h e s i sh a sm a d er e s e a r c h , d e s i g na n di m p l e m e n t a t i o nt ot h ep 2 pn e t w o r k s i m u l a t o rp d p 2 p s i m w h e nd e s i g n i n gt h i ss i m u l a t o r , t h ec o m m o n a l i t yi st a k e ni n t o a c c o u n t ；t h eo b j e c t o r i e n t e di d e ai su s e dt od e s i g nt h r o u g h o u to v e r a l ls t r u c t u r e s i no r d e rt o r a i s et h es i m u l a t i o ns p e e dw h e n s i m u l a t i n gal a r g e s c a l ep 2 pn o d e s ，c o m p a r e dt os e r i a l l y p r o s s e s s i n gt h a ti st o os l o wb ys i n g l e - t h r e a d e dd i s c r e t ee v e n td r i v e nm o d e l ，t h i st h e s i s d e s i g n s ”p r o d u c e r sa n dc o n s u m e r s ”d o u b l e - t h r e a d e dp a r a l l e ld i s c r e t ee v e n td r i v e nm o d e l o nt h eb a s i so fp d p 2 p s i m t h es t - p 2 p v o ds y s t e ms i m u l a t i o nm o d e li si m p l e m e n t e da n d i i t h er e s e a r c h ，d e s i g na n di m p l e m e n t a t i o no fp 2 pv o dm o d e la n dt h es i m u l a t o r a b s t r a c t t e s t e d ，a n di sc o m p a r e dt ot h et r a d i t i o n a lp 2 v o dm o d e li np e r f o r m a n c e t h et e s tr e s u l t s s h o wt h a tt h en e wm o d e lh a sg o o ds c a l a b i l i t y , r o b u s t n e s sa n d e f f i c i e n c y k e y w o r d s ：p 2 p ；v o d ；s k i pt a b l e ；d a t as c h e d u l e ；p 2 pn e t w o r ks i m u l a t o r ； i i i w r i t t e nb yy u a nt a n g f u s u p e r v i s e db yl uj i a n d e 目录 第一章绪论1 1 1 研究背景1 1 2 国内外研究现状2 1 3 论文的主要工作3 1 4 论文的特色与主要贡献3 1 5 论文的组织结构4 第二章p 2 p 流媒体技术与模拟器5 2 1p 2 p 技术。5 2 1 1p 2 p 网络5 2 1 2p 2 p 网络的分类5 2 2 流媒体系统8 2 3 视频点播系统的发展历程8 2 3 1 传统的c s 结构点播系统9 2 3 2 基于集群的点播系统9 2 3 3 基于c d n 的点播系统1 0 2 3 4 基于p 2 p 技术的点播系统1 0 2 4 典型的p 2 p 流媒体模型分析1 1 2 4 1p e e r c a s t 模型1 1 2 4 2p 2 v o d 模型。1 3 2 4 - 3s p l i t s t r e a m 模型1 4 2 4 4 基于g o s s i p 协议的d o n e t 模型。1 6 2 5p 2 p 网络模拟器1 8 2 6 本章小结2 0 第三章p 2 p 点播系统模型s t - p 2 p v o d 设计2 l 3 1s t - p 2 p v o d 模型概述2 1 3 2s t - p 2 p v o d 模型结构2 2 3 2 1 基于跳表的组织结构2 3 3 2 2 数据调度2 6 3 2 3 服务器的带宽控制2 7 ：1 8 ：1 9 31 p s i m 的设计与实现3 2 ：；：2 3 3 i m 的总体设计3 4 4 4 并行离散驱动事件驱动引擎模块设计3 5 4 4 1 离散事件驱动引擎的一般结构3 5 4 4 2 单线程串行离散事件驱动模型的性能分析3 8 4 4 3 “生产者与消费者”并行离散事件驱模型的设计与实现3 9 4 4 4 模型性能分析4 0 4 5 网络搅动模块设计4 0 4 6 网络管理模块设计4 2 4 7 网络拓扑模块设计4 2 4 8 节点模块设计4 3 4 9 数据统计模块设计4 5 4 1 0p 2 p 网络模拟器p d p 2 p s i m 的测试与结果分析4 5 4 1 0 1 运行时间与模拟时间的关系4 6 4 1 0 2 运行时间与模拟节点数的关系4 7 4 1 1 本章小结4 7 第五章s t - p 2 p v o d 模型仿真程序实现4 8 5 1 视频服务器的仿真实现4 8 5 2 节点中各大模块的仿真实现5 0 5 2 1 视频缓冲区模块的仿真实现5 1 5 2 2 数据通道的定义5 2 5 2 3 邻居节点管理模块的仿真实现5 3 5 2 4 消息模块的定义5 5 5 2 5 两种基本事件的定义5 6 5 2 6 消息处理模块的仿真实现5 6 5 2 7 动作处理模块的仿真实现j 5 8 5 3 网络搅动和数据统计模块的完善6 0 5 4s t - p 2 p v o d 系统模型的测试过程6 1 5 5 仿真试验及结果分析6 3 5 6 本章小结6 5 第六章总结与展望6 6 6 1 论文总结6 6 6 2 未来工作展望6 7 参考文献6 8 攻读硕士学位期间发表的论文7 2 致谢7 3 p 2 p 点播系统模型与模拟器的研究、设计与实现第一章绪论 1 1 研究背景 第一章绪论弟一早珀了匕 随着计算机网络技术的发展与普及，人们不再满足于传统的聊天、下载文件浏览、 网页等呆板的因特网使用方式，而多媒体通信可以集成视频、音频、文本及图像为一 体，为用户提供更为丰富的使用体验，因此受到人们越来越为广泛的欢迎。流媒体技 术是网络和多媒体技术的交叉领域，用户可以一边接受数据，一边观看流媒体，而不 必等待所有数据全部下载完毕，视频点播( v i d e oo nd e m a n d ，v o d ) 技术因此应运而 生，满足了实时交互的需要。 由于流媒体应用具有持续时间长、占用带宽大、及时性要求高等特点，传统的 c s 模式难以支持大量用户的同时在线，易形成系统瓶颈。i p 组播技术以其多路复用 的方式能够减轻服务器和网络的负载，但是需要多播路由器的支持，目前在网络上难 以广泛部署。c d n 分发网络通过在i n t e m e t 上广泛部署服务节点，将要传送的内容传 送到距离用户最近的网络节点，并把客户请求路由到离客户最近的服务节点，从而减 轻对服务器的压力和骨干网络的带宽消耗。这种方法代价比较昂贵，需事先建立庞大 的c d n 网络，使一般流媒体内容提供商无法承担高昂的服务器租赁费用。为此，通 过采用p 2 p 技术有效利用大量普通用户终端设备的计算资源和带宽资源，使得提供大 规模节点的视频点播服务在现阶段成为可能。p 2 p 技术的基本思想是利用广泛分布的 闲散客户端资源，使每个客户端在获取数据享受系统服务的同时也充当临时的服务器 角色，利用自己的数据和带宽资源服务其它客户端，从而提高系统整体的服务能力。 目前，p 2 p 技术在文件共享和视频直播领域已经被广泛应用，基于p 2 p 技术的大 规模视频直播和文件共享系统己被成功部署。然而，利用p 2 p 技术实现视频点播服务 的难度相对比较大，研究过程中所面临的挑战更为严峻。相对于p 2 p 技术的其他应用， 视频点播具有其自身的特点：1 ) 播的用户间播放进度存在差异，如果两个用户问的播 放进度比较大，会对资源共享造成影响，甚至无法共享；2 ) p 2 p 点播系统网络的动 态性更高，除了节点的加入和离开外，点播过程中还需要支持快进、快退等v c r 操 作，这些v c r 操作加剧了网络的动态性；3 ) 同时流媒体本身又有其独特性质，如数 p 2 p 点播系统模型与模拟器的研究、设计与实现 传输持续时间长、带宽占用率高以及高q o s 要求等。 下，基于p 2 p 网络的视频点播系统的研究成为当今研究的热点。如何利 客户端资源来有效降低中心服务器的资源消耗，如何满足用户高实时性 的交互要求，如何在保证服务质量的前提下提供高性价比、高可扩展性的大规模流媒 体点播服务，是本文的主要研究内容。第2 4 次中国互联网络发展状况统计报告【lj 显 示，我国的网民规模和宽带网民规模增长迅猛，互联网规模稳居世界第一位。截至 2 0 0 9 年6 月底，中国网民规模达到3 3 8 亿，较2 0 0 8 年底增长1 3 4 ，半年增长了4 0 0 0 万；而宽带网民规模则达到了3 2 亿，占总网民数的9 4 3 ，较2 0 0 8 年底上升了3 7 个百分点。可见，如何为大量用户提供高质量的p 2 p 点播服务具有相当大的研究价值。 1 2 国内外研究现状 近年来，许多大学、研究机构以及商业机构都已经对基于p 2 p 网络的流媒体服务 体系给予了很大的重视。在国外，马萨诸塞大学、美国斯坦福大学以及微软研究院对 单源的p 2 p 流媒体传输展开了研究，并取得了一定的成果。伯克利大学和普度大学对 多源的p 2 p 流媒体传输进行了深入的研究。此外，也有一些研究机构将传统的流媒体 技术运用于p 2 p 系统，如美国奥利根大学提出的p a l s ，采用了媒体流的分层编码技 术，由各个节点发送不同层的编码流，接收者根据其能力选择接收若干层的编码。在 商业应用上，也出现了一些商用p 2 p 流媒体传输系统，如a l l c a s t l 2 j 、c h a n n e lo n e m e d i a 3 1 ，对p 2 p 流媒体传输系统的运行模式进行了尝试。 目前，该领域大部分的研究内容集中在流媒体转发策略的研究上，这些研究大致 可以分为两类：基于树状多播和基于网状多播。基于树状多播的研究比较广泛，其中 以d i r e c t s t r e a m 4 1 、p e e r c a s t l 5 、p 2 v o d t 6 1 、p 2 c a s t t 7 1 、s p l i t s t r e a m l 8 】等p 2 p 流媒体系统 为代表。基于网状多播的p 2 p 流媒体系统以g n u s t r e a i l l 【9 1 、p r o m i s e l l 0 1 、c o l l e c t c a s t 1 1 1 为代表。 另外媒体编码【1 2 】传送技术也是流媒体领域的一个研究热点，同样有大量的研究工 作致力于此。媒体编码传送技术基本可以分成三类：信息重复( i n f o r m a t i o nr e p l i c a t i o n ) 的单速率方案( s d c ) 、累积的分层( c u m u l a t i v el a y e r i n g ) 传输方案( f g s ) 和非累积的分 层( n o n c u m u l a t i v el a y e r i n g ) 传输方案( m d c ) 。 在国内，p 2 p 流媒体的业务正借着p 2 p 直播系统的宣传攻势进入一个快速发展期， p 2 p 点播系统模型与模拟器的研究、设计与实现第章绪论 许多新兴的p 2 p 厂家不断涌现。由于p 2 p 点播系统技术上高难度性，目前大多数的 p 2 p 流媒体厂家的点播业务刚刚起步，还不够成熟。腾讯旗下的q q l i v e i s j 是目前在 国内市场占有率较高的p 2 p 视频播放软件。来自于华中科技大学并由上海聚力传媒技 术公司开发的p p l i v e t l 4 1 以及上海众源网络有限公司的p p s t r e a m 15 1 ，也比较受用户的 喜欢。迅雷看看【1 6 】是深圳迅雷网络技术有限公司新推出的p 2 p 视频点播软件。 1 - 3 论文的主要工作 本文从p 2 p 视频点播系统的节点组织和数据调度两方面出发，重点解决p 2 p 视频点播系统中如下两个问题：第一、对等点播系统是一个高度动态的分布式环境， 如何有效组织该环境下的p e e r 节点，满足节点间数据的高效共享? 第二、如何让调 度算法适应系统的动态性，满足对等点播服务的实时性要求，提供更好的用户观看体 验? 为此，本文研究、设计了基于跳表的p 2 p 视频点播系统模型s t p 2 p v o d ( s k i p t a b l eb a s e dp 2 pv o d ) 。该模型的拓扑结构中采用基于跳表的拓扑结构和网状的伙伴节 点组织结构的双层结构，基于跳表的资源定位可以有效支持v c r 操作，减少v c r 时延和服务器负载。在数据调度方面根据缓冲区的动态状态选择推或拉的方式进行调 度，保证了数据尽量在播放前到达，提高了数据调度的有效性，减少了控制开销。 为了方便、快速对该模型进行仿真实验，本文还设计、实现了基于c + + 语言的高 效、通用、可扩展的p 2 p 网络模拟器p d p 2 p s i m ( p a r a l l e ld i s c r e t ee v e n td r i v e np 2 p s i m u l a t o r ，并行离散事件驱动p 2 p 网络模拟器) ，提出“生产者与消费者 双线程并 行离散事件驱动模型，克服了单线程串行离散事件处理速度过慢的缺陷。基于该p 2 p 网络模拟器，论文对p 2 p 视频点播系统模型s t p 2 p v o d 进行了仿真程序实现，并进 了测试和评估研究。 1 4 论文的特色与主要贡献 本论文的特色与主要贡献表现在以下几个方面： 夺将基于跳表的拓扑结构引入到p 2 p 流媒体点播系统中，设计了p 2 p 视频点播 系统模型s t p 2 p v o d ，基于跳表的资源定位可以有效支持v c r 操作，减少 v c r 时延和服务器负载。 令节点管理方面，提出了伙伴邻居，跳表邻居以及其他邻居的概念，其中伙伴 一章绪论p 2 p 点播系统模型与模拟器的研究、设计与实现 邻居又划分了前驱和后续两种邻居，分成三个层次、使用四种独立队列管理 邻居节点，方便数据调度时本地节点快速、有效的定位查找。 数据调度方面，采用推拉结合的思想，根据缓冲区的动态状态选择推或拉的 方式进行调度，在缓存区稳定时，在前驱邻居节点注册子流、以推送方式稳 定了后续下载数据；在缓存区不稳定时，以主动请求的拉方式增加对上行带 宽的利用，加快了数据的下载，保证了数据尽可能在播放前到达。 设计实现的p 2 p 网络模拟器p d p 2 p s i m 高效、通用、可扩展，采用“生产者 与消费者”双线程并行离散驱动模型，提高了模拟器处理离散事件的速度， 进而提高了整体模拟速度，为p 2 p 网络研究者提供了一个有用工具。 1 5 论文的组织结构 本文分为四个部分：第一部分为第一章的绪论，概要介绍研究背景、国内外研究 现状，综述论文所做的主要工作、特色与贡献，及论文结构；第二部分为p 2 p 流媒体 背景技术与理论研究部分，由第二章组成；第三部分为s t p 2 p v o d 系统模型的研究 与设计以及p d p 2 p s i m 模拟器的设计实现部分，以及基于p d p 2 p s i m 模拟器的 s t p 2 p v o d 系统模型的仿真实现和测试分析，包括第三章、第四章和第五章；第四 部分为最后的第六章，对全文进行总结并对下一步工作进行展望。论文具体安排如下： 第一章，介绍课题研究背景及意义、国内外研究现状、本课题所要研究的主要内 容以及论文的主要特色与贡献。 第二章，分析了p 2 p 流媒体相关技术，解剖了目前几种典型的p 2 p 流媒体模型， 并研究比较了一些用于p 2 p 网络研究的模拟器。 第三章，阐述了对基于跳表的p 2 p 点播系统模型s t p 2 p v o d 的研究，给出了总 体设计，讨论了跳表的拓扑结构、资源定位方法、数据调度方式以及节点的交互过程。 第四章，叙述了基于c h 的高效、通用、可扩展的p 2 p 模拟器p d p 2 p s i m 的设 计与实现，研究了单线程串行离散事件驱动模型，设计了一个“生产者与消费者”双线 程并行离散驱动模型。 第五章，基于p d p 2 p s i m 模拟器，对s t p 2 p v o d 模型系统进行仿真实现，并进 行了测试，对结果进行分析和评价。 第六章，对所做工作进行了总结，并对未来的工作进行展望。 4 p 2 p 点播系统模型与模拟器的研究、设计与实现 第二章p 2 p 流媒体技术与模拟器 第二章p 2 p 流媒体技术与模拟器 本章重点分析了p 2 p 网络技术和流媒体技术，回顾了视频点播的发展历程，解剖 了几种典型的p 2 p 流媒体模型，并分析了当前常用的几种用于p 2 p 网络研究的模拟 器。 2 1p 2 p 技术 2 1 1p 2 p 网络 p 2 p 即对等网络，对等节点之间直接交换信息，共享计算机资源和服务的网络技 术。在p 2 p 网络是一种分布式网络，每个连接到网络中的计算机都处于对等的地位， 整个网络一般来讲不依赖于专用集中服务器。每个对等节点既是资源和服务的提供者 ( s e r v e r ) ，又是资源的获取者( c l i e n t ) 。通常共享的资源和服务包括信息、计算资源( 如 c p u ) 、存储资源( 如磁盘空间和缓存) 用等。 2 1 2p 2 p 网络的分类 p 2 p 网络结构主要分为三类：集中式p 2 p 网络、无结构p 2 p 网络以及结构化p 2 p 网络。而无结构的p 2 p 网络又可以细分为纯分布式无结构的p 2 p 网络和基于超级节 点的无结构p 2 p 网络。具体说明如下： 1 集中式p 2 p 网络 图2 1 集中式p 2 p 网络 一一1 1 , 矗询漉 - r 数据滚 流媒体技术与模拟器 p 2 p 点播系统模型与模拟器的研究、设计与实现 式p 2 p 网络采用混合式的体系结构，即星形拓扑结构，服务器仍然是整个 心。如图2 1 所示所有的节点都和服务器建立连接，服务器负责索引所有节 容。当节点发出请求时，中心目录服务器会根据节点的请求找出符合该节点 要求的节点，然后文件交换就直接在这两个节点之间进行。集中式p 2 p 网络实现简单 高效，只要服务器能够正常工作，网络和节点就能有效地维护。但另一方面，正是由 于整个网络对于服务器的依赖性，一旦服务器发生故障，整个网络必将面临瘫痪。可 见，这种集中式p 2 p 网络的容错性不搞。另外，由于服务器节点带宽和资源存储方面 的有限性，这种集中式p 2 p 网络的扩展性也不高。这种网络的实际应用中，通常使用 多台服务器组成机群，提供冗余、替代机制使得一台服务器发生故障时它的任务可以 被其他服务器分担，来提高整个网络的稳定性、容错性。n a p s t e r l l 7 1 是集中式p 2 p 网 络的典型代表。 2 无结构p 2 p 网络 如图2 2 所示，在这种无结构p 2 p 网络中不存在服务器，每个节点都是对等的， 既是服务器又是客户。节点之间一般采用洪泛或随机走的方式进行资源搜索定位，所 以这种网络存在可扩展性和资源定位准确性两方面的问题。一方面随着网络规模的扩 大，这种盲目性的资源定位方式会造成网络流量急剧增加，另一方面无结构p 2 网络 无法保证资源定位的效率，即使要查找的节点存在，也可能查找失败。g n u t e l l a 1 8 】是 纯分布式无结构p 2 p 网络的典型代表。 。下载流 图2 2 无结构p 2 p 网络 6 p 2 p 点播系统模型与模拟器的研究、设计与实现 第二章p 2 p 流媒体技术与模拟器 f a s t t r a c k 是与g n u t e l l a 并列的典型的无结构p 2 p 协议【1 9 】，它的改进之处在于引 入了“超级节点”和“普通节点”的概念，考虑到了p 2 p 网络中节点的异构性，如图2 3 所示。超级节点通常处理能力强、带宽高、不受n a t 限制，而普通节点通常处理能 力弱、带宽低、常受n a t 限制。普通节点加入网络时通常选择一个超级节点作为父 节点，通过父节点来索引和共享数据。超级节点间通常采用洪泛或随机走的方式进行 资源搜索定位。 图2 3 基于超级节点的无结构p 2 p 网络 3 结构化p 2 p 网络 由于无结构p 2 p 网络存在可扩展性不高，资源定位不准确等缺陷，结构化p 2 p 网 络被提出。结构化p 2 p 网络的共同特点就是都有一个严格的覆盖网拓扑结构，如带弦 环结构的c h o r d t 2 0 l 、多维空间结构的c a n t 2 1 1 、超立方体结构的t a p e s t r y 2 2 1 和p a s t r y 2 3 】 等。结构化p 2 p 网络通常使用分布式散列表( d h t ) 来将节点、数据对象映射到覆 盖网中，为每个节点和数据对象分配一个唯一的i d 。在路由和资源定位时，基于本 身的拓扑结构和路由表结构，采用分布式、局部性的贪心路由算法，逐步缩小当前节 点与目标节点之间的i d 差异。通常定位效率为o ( 1 0 9 n ) 跳，并且能保证定位成功， 就覆盖网而言此定位效率接近最优。 结构化p 2 p 网络的节点加入算法基本上大同小异，大致可以分成三步： s t e pl ：新节点n 以某种方式找到一个网络中的现存节点g ，通常称为“自举节点”。 s t e p2 ：n 通过g 发送以n 为目的地的消息，该消息最终到达i d 与n 最接近的 节点z ，n 从z 或者从消息路径的每个节点中获取路由表信息以及应由自己负责的数 据，之后再做修正和优化。 7 p 2 p 点播系统模型与模拟器的研究、设计与实现 由表以反映n 的到来。这里的“其他节点”通常 ，节点的失效通常采用周期性的发送消息来确 认。如果检测到节点失效，需要对路由表进行修复。对节点失效的修复通常需要很大 的网络开销。结构化p 2 p 网络严格的拓扑结构维护起来一般比较复杂，容易受到攻击 者的攻击，因此它的容错性、安全性通常不及无结构化p 2 p 网络。 2 2 流媒体系统 流媒体是指采用流式传输技术在因特网上播放的媒体格式，如音频、视频。用户 在播放前并不需要下载整个流媒体文件，可以一边接受数据，一边将接受到的数据包 重组和解码，并进行播放。 从功能上，可将流媒体系统划分成视频直播系统和视频点播统两种。在视频直播 系统中，用户问的播放进度是同步的、实时的，不可以进行快进、快退、暂停等v c r 操作；在视频直播系统中，用户间的播放进度是异步的，用户可以进行快进、快退、 暂停等v c r 操作。 从工作方式上，又可以将流媒体系统分成两类：基于树状多播和基于网状多播。 基于树状多播的流媒体系统将网络中的所有节点组织成多播树，流媒体发布源为树的 根节点，视频流按照从父节点到子节点的方向传播，直到传到叶子节点。它最大的缺 陷就是节点的失效容易引起多播树的分裂，而且维护多播树的开销比较大。基于网状 多播的流媒体系统采用随机选择节点策略，构造连接度较高的无结构网络，节点间通 过周期性地发送b u f f e r m a p ( 数据块的位示图) 来通告自己所拥有的数据块，从而邻 居节点可以根据需要主动获取自己缺少的数据块。它的缺陷就是控制开销大，延迟明 显，且资源定位方面比较复杂。 2 3 视频点播系统的发展历程 视频点播系统的体系结构大致经历了如下四个阶段的发展：首先从c s 结构的集 中式视频点播系统发展到基于集群结构的视频点播系统，完成局域范围内服务器单点 到多点的扩展：然后从基于集群的视频点播系统发展到基于内容分发网络的视频点播 系统，实现点播服务器从局域范围到广域范围的扩展；最后从基于内容分发网络的视 8 p 2 p 点播系统模型与模拟器的研究、设计与实现第二章p 2 p 流媒体技术与模拟器 频点播系统发展到目前基于p 2 p 的视频点播系统，使得百万千万级的大规模流媒体点 播系统成为可能。 2 3 1 传统的c s 结构点播系统 如图2 4 所示，传统的c s ( c l i e n t s e r v e r ) 结构点播系统采用单一服务器提供服务， 所有客户端都直接从服务器获取流媒体数据。客户端在向服务器发送数据请求时，如 果服务器有能力支持新的客户端加入，就会接受请求，否则就拒绝客户端的请求。这 种模式具备管理简单，操作方便，开发成本低廉等优点，但是流媒体分发的负载全部 集中在服务器上，随着客户端数量的增加，容易造成服务器端的带宽瓶颈，从而限制 了c s 结构点播系统的扩展性。而随着全球互联网用户飞速增长，必然加快在线点播 和网络电视等流媒体业务的发展，而这种传统的c s 架构显然无法适应大规模的流媒 体数据发布。这种c s 结构视频点播系统的典型代表有苹果公司的d a r w i n 、r e a l 公 司的h e l i x 、以及微软公司的m e d i as e r v i c e 等。 2 3 2 基于集群的点播系统 图2 4c s 结构网络 基于集群的点播系统依然采用c s 结构，与前一种方式的改进之处在于后台部署 多个真实服务器，通过前端机的服务调度机制，把用户请求按照负载平衡的原则调度 到后台真实服务器上，在定程度上扩展了服务器的服务能力。随着节点规模的增加， 这种方式仍然无法适应大规模视频点播的需要，系统扩展性依然比较差。南加州大学 的y i m a 2 4 1 视频点播就是基于集群的视频点播系统的典型代表。 9 第二章p 2 p 流媒体技术与模拟器p 2 p 点播系统模型与模拟器的研究、设计与实现 2 3 3 基于c d n 的点播系统 如图2 5 所示，内容发布网络c d n ( c o n t e n td e l i v e r y n e t w o r k ) 的基本思路就是在 互联网的各处放置大量的服务节点，构成互联网上面的另一层网络。c d n 可以实现 把服务器的内容高效、稳定地发布到离客户端最近的地方，尽可能避开互联网上有可 能影响数据传输速度和稳定性的瓶颈和环节，使内容传输得更快、更稳。c d n 系统 能够实时地根据网络流量和各节点的连接、负载状况以及到用户的距离和响应时间等 综合信息将用户的请求重新导向离用户最近的服务节点上。通过c d n 系统，用户的 响应时间被大大缩短，改善了i n t e m e t 上流媒体的服务质量，有效地提高了网络资源 的利用率。虽然c d n 是一种有效的流媒体发布技术，但是其扩展性依然有限，而且 部署成本非常高，限制了它的应用和推广。目前，国外的a k a i i l a i 【2 5 】，l i m e l i g h t 2 6 1 公司、以及国内的蓝讯( c h i n a c a c h e ) 2 7 1 等大型的c d n 服务提供商都推出了自己的基 于c d n 的视频点播系统。 由此扩 p 2 p 点播系统模型与模拟器的研究、设计与实现第二章p 2 p 流媒体技术与模拟器 目前，典型的基于p 2 p 技术的点播系统包括p e e r c a s t 5 1 ，p 2 v o d 【6 1 ，s p l i t s t r e a m 8 1 等 2 4 典型的p 2 p 流媒体模型分析 下面将详细介绍并分析几种典型的p 2 p 流媒体模型。 2 4 1p e e r c a s t 模型 p e e r c a s t l 5 1 是一个树状结构的模型，如图2 6 所示。在这棵应用层组播树中，流媒 体发布服务器为树根，数据从父节点向子节点传播，最终传到叶子节点截至。因为子 节点参与分发数据，服务器的负载被分散到整个网络中，具有很强的扩展性。 图2 6p e e r c a s t 单树模型 新节点n 试图加入时，首先向服务器s 请求服务，如果服务器有足够的资源，则 服务器向节点1 1 提供服务，否则服务器s 把n 的请求转发给其某个直接的子节点。 子节点根据自己的资源情况判断是否给n 提供服务，以此类推，直到n 找到一个父节 点。在这个模型中，每个节点仅仅维护自己的父节点和直接的子节点的信息。当新节 点n 的请求发给节点y 时，如果y 有足够的资源则给n 提供服务，n 被插入为y 的子 节点；如果y 没有足够的资源，则需要把新节点n 的请求转发给其他节点，转发有 如下策略： ( 1 ) 随机选择( r a n d o m ) y 从它的子节点中随机选择一个节点t 作为目标节点。 把1 1 的请求发给t 。这种策略最简单，y 不需要维护任何的状态信息，而且在统计的 平均意义上，生成应用层组播树会比较平衡。 p 2 p 点播系统模型与模拟器的研究、设计与实现 r o b i n ) ：y 维护它所有子节点的队列，把新节点的请求 策略y 需要维护一些状态信息，期望取得更平衡的组播 ( 3 ) 根据物理位置选择( s m a r t p l a c e m e n t ) ：y 维护它所有子节点的路由信息，新 节点n 发出加入请求时附带本身的路由信息， y 把n 的请求转发给物理位置离n 最 近的子节点。如果y 离n 比它所有的子节点更近，则y 踢掉距离最远的子节点f 而给 n 提供服务，f 需要重新加入。这种策略考虑了节点的物理位置，使组播树更接近节 点的物理拓扑，可以有效地减少包丢失率和时延，从而改善q o s 。 ( 4 ) 根据节点带宽选择( s m a r t b a n d w i d t h ) ：新节点n 发出加入请求时附带本身的 带宽信息，如果n 的带宽比y 小，则用上述策略加入，否则，y 把自己从父节点p 断开，把n 重定向给p ，然后把自己重定向给n 。 当节点n 离开时，如果n 是叶子节点，则n 只需向其父节点发一个退出的请求， 通知n 的父节点释放所有为n 提供服务的资源，组播树的其它节点维持不变。如果节 点n 不是叶子节点，则节点n 的离开会导致n 的所有后续子节点失去服务，所以在节 点n 离开之前，必须为n 的所有子节点重新分配父节点。重新分配父节点有两种模式， 一种是d 的所有后续节点中每一个节点都被重新加入；另一种就是维持节点d 后面的 子树不动，也就是说节点d 只把它的每个直接子节点作为一个子树重定向给新的服 务节点t 。这种模式由于不需要重新加入所有子节点，树的修复会更快。节点d 至少 知道服务器s 和父节点p 可以给其子节点提供服务。 所以总共有四种策略： 设c 为节点d 的所有直接子节点的集合。 ( 1 ) g r a n d f a