（计算机系统结构专业论文）视频点播服务的p2p数据分发策略研究.pdf

摘要 摘要 随着通信网络技术的迅速发展和宽带接入的普及化 交互式多媒体业务日益 成为网络业务的发展方向 视频点播服务作为一项重要的网络多媒体业务成为研 究的热点 p 2 p 技术为实现大规模的v o d 系统提供了最为经济且有效的解决方 式 利用p 2 p 技术在增强系统扩展性的同时保证良好的视频服务质量是研究的 热点和难点 其中 视频服务质量包括优质的视频画面 较短的播放延迟 较少 的播放停顿 v c r 功能的提供等 数据分发策略是影响p 2 pv o d 系统性能的最重要的策略 本文分析了现有 的各种树结构与网结构的系统中的分发技术并提出自己的优化策略 以良好的扩 展性 较高的服务质量为目标 进行了h y b r i d v o d 模型的设计 主要研究内容 和贡献如下 本文首先研究了单视频覆盖网络下的数据分发策略 文中基于m e s h 结构的 p 2 p 网络 设计能够充分利用系统内节点上行带宽 满足播放需求的同时进行前 向预取的数据分发策略 针对m e s h 结构系统中的控制流拓扑并非完全分布式 索引服务器易产生单点失效的问题 系统进行了混合式拓扑的设计优化 并在该 拓扑的基础上进行了多服务节点间调度算法的设计 仿真实验表明 系统在源服 务器负载 索引服务器压力 跳转延迟方面均优于现有系统 能较好地满足扩展 性与视频服务质量的需求 其次 本文还对如何解决实际系统中冷门频道与热门频道节点服务器负载不 均的现象进行了研究 通过分析现有多视频缓存与分发 m v c 策略的不足 结合 混合式的网络拓扑设计 文中提出了一种新的以段为单位的主动复制与被动复制 相结合的策略 该方法控制协议简单 能有效地解决由于节点离开造成的块缺失 问题 仿真试验表明 结合m v c 的h y b r i d v o d 系统可有效扩大冷门频道的规 模 利用热门频道的点播节点为冷门频道服务 降低了整个服务器的负载 提高 了系统的扩展性能 关键词 视频点播p 2 p 网络数据分发多视频缓存 a b s t r a c t a b s t r a c t i n t e r a c t i v em u l t i m e d i ab u s i n e s sb e c o m e st h ed i r e c t i o no fn e t w o r kb u s i n e s s i n c r e a s i n g l y a so n eo ft h ei m p o r t a n tn e t w o r km u l t i m e d i ab u s i n e s s v o d v i d e oo n d e m a n d b e c o m e sah o tt o p i ci nr e s e a r c ha r e a t ob u i l dal a r g e s c a l ev o ds y s t e m t h em o s te c o n o m i c a la n de f f i c i e n ts o l u t i o ni sc o n s i d e r e da sp 2 pt e c h n o l o g y t h es t r a t e g yo fd a t ad i s t r ib u t i o ni sm o s ti m p o r t a n ti nt h ed e s i g no fp 2 pv o d s y s t e m t h ea r t i c l ea n a l y z e sc u r r e n td i s t r i b u t i o nt e c h n o l o g yi nd i f f e r e n ts y s t e m so f t r e es t r u c t u r ea n dm e s hs t r u c t u r e a n dp r o v i d e si t so w ni m p r o v e m e n t w h i c h t h r o u g h t h ed e s i g no fh y b r i d v o dm o d e l t oa c h i e v eb e t t e rs c a l a b i l i t ya n dh i g h e rq u a l i t yo f s e r v i c e t h em a i nr e s e a r c hc o n t e n ta n dc o n t r i b u t i o na r el i s t e da sf o l l o w i n g t h i st h e s i sf i r s ti n v e s t i g a t e so nt h es t r a t e g y o fd a t ad i s t r i b u t i o nu n d e r s i n g l e v i d e oo v e r l a yn e t w o r k b a s e do nt h ep 2 pn e t w o r ko fm e s hs t r u c t u r e w ec o m e u pw i t han e ws t r a t e g yw h i c h b yf u l l ym a k i n gu s eo ft h eu p l o a db a n d w i d t hi nt h e s y s t e mn o d e s c a np r e f e t c h e sd a t aa n ds a t i s f i e st h ep l a y i n gd e m a n d t h eh y b r i d v o d m o d e lc h o o s e sam i x e dt o p o l o g yt os o l v et h ep r o b l e mo fs i n g l en o d ef a i l u r ei nt r a c k e r s e r v e r a n dp r o v i d e sad i s t r i b u t e dc o l l a b o r a t e dn o d es e a r c h i n gm e c h a n i s mf o rs e e k i n g w i t hs e g m e n t s e e dt o p o l o g y b e s i d e s t h em o d e ld e s i g n sa l la l g o r i t h mf o rt h ed a t a s c h e d u l i n gf r o mm u l t i p l es e r v i c en o d e s w h i c hp r o p e r l yf i t st h eh e t e r o g e n e o u sa n d d y n a m i cn e t w o r ke n v i r o n m e n t s e c o n d l y t h i st h e s i sc o n c e n t r a t e so nt h el o a d i n gp r o b l e mo fv i d e o sw i t hd i f f e r e n t p o p u l a r i t y c o n s i d e r i n gt h ed e s i g n e dh y b r i dt o p o l o g y w ep r o p o s ean e wm u l t i p l e v i d e oc a c h es t r a t e g y w h i c hc o m b i n e sa c t i v er e p l i c a t i o na n dp a s s i v er e p l i c a t i o n t o g e t h e r t h i s m e t h o dc a nd e c r e a s ed e p a r t u r e m i s s e se f f i c i e n t l y s i m u l a t i o n e x p e r i m e n ti n d i c a t e st h a t w i t hm v c n o d e sp l a y i n gp o p u l a rm o v i ec a nj o i n i n u n p o p u l a rc h a n n e l s t h ew h o l e s e r v e rl o a dc a nb ed e c r e a s e ds i g n i f i c a n t l y k e yw o r d s v i d e o o i l d e m a n d p 2 pt o p o l o g y d a t ad i s t r i b u t i o n m u l t i p l e v i d e o c a c h i n g i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文 是本人在导师指导下进行研究工作所取得的成 果 除已特别加以标注和致谢的地方外 论文中不包含任何他人已经发表或撰写 过的研究成果 与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明 作者签名 圣主壁 签字日期 巡夏 芝j 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一 学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权 即 学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版 允许论文被查阅和借阅 可以将学位论文编入有关数据 库进行检索 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 本人 提交的电子文档的内容和纸质论文的内容相 致 保密的学位论文在解密后也遵守此规定 豸公开口保密 年 作者签名 垒查重 签字日期 2 墨l 导师躲q 堕生 签字日期 第l 章绪论 第1 章绪论 1 1 引言 根据c n n i c 中国互联网络信息中心 的 第2 3 次中国互联网络发展状 况统计报告 1 表明 截至2 0 0 8 年底 中国网民规模达到2 9 8 亿人 较2 0 0 7 年增长4 1 9 互联网普及率达到2 2 6 略高于全球平均水平 2 1 9 继 2 0 0 8 年6 月中国网民规模超过美国 成为全球第一之后 中国的互联网普及再 次实现飞跃 赶上并超过了全球平均水平 随着通信网络技术的迅速发展和宽带 接入的普及化 用户的上网需求也在不断转变 从以前的互联网信息检索浏览 电子邮件 简单及时通讯等带宽要求不高的应用不断向音频 视频 即时通讯 网络电视 网络高品质音乐 网络游戏 网络教育等高带宽要求的应用转变 交 互式多媒体业务日益成为网络业务的发展方向 流媒体视频服务的提供成为研究 的热点 2 流媒体视频服务是将电视机 个人电脑及手持设备作为显示终端 通过机顶 盒或计算机接入宽带网络 在互联网上实时 流动地传播音 视频内容的连续媒 体的服务 音 视频文件采用流式传输方式 通过特殊的压缩方式分成一个个数 据包发出 用户通过解压设备对数据包进行解压后即可播放 2 用户在网络上 享受流媒体视频服务时不必等到整个文件全部下载完毕 只需经过几秒或几十秒 的启动时延即可播放 然后客户端边接收数据边播放 流媒体视频服务按播放方式可分为流媒体视频广播和流媒体视频点播 2 流媒体视频广播系统将节目源组织成频道 通过内部局域网或互联网将视 音频 节目向p c 机 i p 机顶盒广播 它可以现场直播 亦可定时广播 还可将多路视音 频节目同时在局域网或i n t e r n e t 上播放 每个用户可在终端选择收看的频道 客 户端通过媒体播放器即可实时接收数据流并播放 但不能控制流 流媒体视频点播 v i d e o o n d e m a n d 3 简称v o d 则被设计为目标是在 任何时候提供所需要的任何节目 并支持与用户的互动 有效地解决了需求服务 被动性 媒体信息的滞后性等技术问题 给用户使用带来方便 v o d 在现实生 活中有许多应用 主要包括 电影点播 新闻点播 电视会议 电视购物 数字 第1 章绪论 图书馆 远程教学和医疗服务等 流媒体视频广播技术目前比较成熟 应用也比较广泛 在国内比较成熟应用 有p r i v e 4 p p s t r m m 5 u u s e e q s o p c 叙 7 j 等 而v o d 由于数据量大 传 输带宽高 实时性强 对流量带宽的资源需求很大 过多的用户经常会造成视频 服务器磁盘i o 吞吐能力以及网络带宽成为瓶颈 点播服务的q o s q u a l i t yo f s e r v i c e 得不到保障 系统扩展性能受到限制 主要表现为网络拥堵 服务延迟 服务中断 甚至由于服务器负担过重而拒绝服务等 3 为了解决这些问题 各 种各样的技术被应用于v o d 系统中 形成了不同结构 适用于不同网络条件和 用户规模的v o d 系统 p 2 p 技术在v o d 系统中的应用是当前研究热点 p 2 p 技术为实现大规模的 v o d 系统提供了最为经济且有效的解决方式 本文以p 2 p v o d 系统中的数据分 发策略为研究方向 针对系统扩展性 视频服务质量问题 提出 t 中混合式拓扑 结构的p 2 p v o d 系统的设计模型 其中 g o s s i p 层保持网络中高可靠性的连接 段种子拓扑层采用k a d 协议构造结构化的p 2 p 网络 使得d h t 可以用于拖动操作 后的合作节点定位 以有效减轻索引服务器的压力 在该混合式拓扑的基础上 本文首先针对单视频覆盖网络进行多服务节点数据调度算法的设计 接着针对多 视频覆盖网络提出以段为单位的复制与缓存策略 并对该策略下的服务节点数据 调度进行设计 本章首先介绍v o d 系统的发展 p 2 p 网络的体系结构及主要特点 接着分析 p 2 p 应用在v o d 系统中的关键技术并提出本文的研究方向 1 2 网络视频点播系统的发展 根据视频服务器在网络中的物理位置及提供服务方式的不同 现有的v o d 系统大致可分为集中式 分布式以及基于p 2 p 技术的v o d 系统三种 集中式v o d 系统对主机性能 网络带宽要求很高 服务用户数量少 不合 适进行展开大规模网络应用 目前的应用主要集中小范围网络点播需求上 如卡 拉o k 厅 在过去十多年中 对v o d 系统的研究工作大部分关注的是分布式系 统和基于p 2 p 技术的v o d 系统中 分布式v o d 系统把视频节目按某种策略存 储在网络上分布的多台视频服务器上 每台视频服务器为一定量的用户提供服 2 第1 章绪论 务 如果要满足更多的用户点播需求 只需要适当的增加视频服务器的数量 具 有容错性与可扩展性的优点 8 但由于造价高昂和网络带宽的限制 分布式v o d 系统目前还不能普及到主流商业应用 近年来p 2 p 技术的兴起和发展让基于p 2 p 网络的v o d 点播系统成为研究的热点 本节主要分析这些系统的研究现状及目 前比较流行的v o d 系统的体系结构 1 2 1 集中式的v o d 系统 传统的v o d 系统采用客户机一服务l 器 c s n 计算模式 如图1 1 所示 视频 节目集中存储在一台或一组中心视频服务器里 由它向所有请求的用户提供流媒 体服务 这类系统一般均采用高性能的视频服务器 从硬件上来提高服务器的性 能 图1 1 集中式的v o d 系统结构 c i s 结构的优点是实现和管理简单 在用户数目不多的小规模应用上有一定 的优势 随着系统规模的扩大 服务器的负载能力成为系统的瓶颈 不具备较高 的扩展能力 为适用大规模的应用环境 针对存在较多用户在同一时间范围内点播相同视 频节目的现象 人们提出了i p 组播 9 的方式 使得多个请求用户可以共享一个 数据流频道 从而减轻了服务器和网络的负载 为满足视频点播中异步的服务请 求 产生了b a t c h i n g 1 0 p a t c h i n g 1 l 等一系列相关技术 但i p 组播因实现方面 的复杂性在今后的若干年内还难以在i n t e m e t 上得到广泛配置和部署 3 第1 章绪论 1 2 2 基于内容分发网络的v o d 系统 c d n c o n t e n td e l i v e r yn 酌j v o r k 1 2 即内容分发网络 通过在现有的i n t e r n e t 中增加一层新的网络架构 引入智能化策略 将中心的内容发布到最接近用户 服务能力最好的网络 边缘 节点 使用户可以就近取得所需的内容 解决i n t e r n e t 网络拥塞状况 提高用户访问网站的响应速度 基于c d n 的分布式v o d 点播系统是目前商用的v o d 系统的主流 如中国 电信正在推广的i 阿v 系统 其结构示意如图1 2 1 1 3 分布式v o d 系统一般都 采用了核心服务器 边缘服务器的系统结构 核心分发服务器主要负责存储媒 体数据 将边缘服务器请求的数据通过以太网络推送到边缘服务器 边缘点播服 务器负责为宽带用户群提供点播服务 将最终用户的数据请求转换为自身的数据 请求并发送到核心分发服务器 并且将以太网上来自分发服务器的数据流缓冲到 本地 供终端用户访 图1 2 分布式点播系统的典型应用结构图 从系统结构上看 分布式v o d 系统的视频服务器由多节点通过高速的内联 网构成并行系统 并具有良好的可伸缩性和扩展性 多节点并行地提供多条流的 视频服务 提高了视频服务并发能力 可满足大量用户的服务请求 然而 传统 的c d n 技术仍然是一种c s 的计算模式 其服务的扩展能力取决于分布节点的 不断部署 由此造成了c d n 服务能力扩展的成本非常高 需要不断的投资 同 4 第1 章绪论 时 用户访问具有随意性 突发性等特点 而c d n 系统不具备弹性动态扩展的 能力 难以从根本上提升系统效率 一些v o d 系统的设计方案建立在传统的c d n 系统基础上 在骨干网层次 保留了原有的c d n 系统的架构和功能 在边缘节点引入了p 2 p 技术来进行流媒 体的共享 实现了p 2 p 技术与c d n 传输的结合 1 4 1 2 3 基于p 2 p 技术的v o d 系统 集中式v o d 系统的服务器瓶颈效应 i p 组播的难以实现和基于c d n 的分 布式v o d 系统的高昂造价使得更多人开始寻求构建大规模v o d 点播系统的方 式 最近的几年里 p 2 p 1 5 成为最为流行的技术之一 不同于传统的b s 和c s 模式 p 2 p 是一种分散的网络模式 在这种网络模式中每一个实体被称为对等体 既充当客户机享用其他节点提供的服务 又充当服务器为其他节点提供服务 从 而减少甚至是克服了对中心服务器的依赖 能够避免因为过度依赖而产生的不良 影响 p 2 p 提供了一些有意义的机制 它允许信息在不同的用户端交换 在具有 相同兴趣的节点之间 快速 动态的建立起联系 这类系统的典型应用就是p 2 p 文件共享 如e m u l e 1 6 b i t t o r r e n t 1 7 e d o n k e y 1 8 等 随着这些p 2 p 项目取得巨大的成功 利用p 2 p 技术提供视频点播服务的尝 试也倍受人们的关注 在这种网络模式中 每一个点播用户缓存一定数据 利用 本地上载带宽 既充当服务器为其他节点提供服务 又充当客户机享用其他节点 提供的服务 节点还一般具有一定的路由和查询功能 系统不必改变传统的网络 结构 在现有i n t e r n e t 层次模型上 只需改动应用层的分发和路由策略 可以大 大降低中心服务器的负载 具有良好的可扩展性 1 9 1 3p 2 p 网络简介 p 2 p 网络是p 2 p 得以实现的基础 是具有非常高的扩展性的分布式网络结构 p 2 p 网络更确切的说 应该被称为p 2 p 覆盖网络 p e e r t o p e e r o v e r l a yn e t w o r k 2 0 1 如图1 3 中所示 它是在实际物理网络基础之上形成的虚拟网络 其中 底层物理网络可以是i n t e r n e t 网络 无线网络 w i r e l e s sn e t w o r k 等 而p 2 p 网 第1 章绪论 络中相邻节点在实际物理网络中可能相距很远 1 3 1p 2 p 网络的特点 图1 3p 2 p 覆盖网络拓扑 在p 2 p 网络中 各节点具有相同的责任 义务并协同完成工作 对等点之 间通过直接互连共享信息 运算 存储甚至高速缓存等资源 无需依赖集中式服 务器就可以完成各类服务 与传统的c s 模式形成了鲜明对比 其大致具有以下 特点1 2 0 1 节点地位平等 p 2 p 网络中每个节点都同时扮演着服务器和客户端的角色 所有成员在功 能 地位上都是平等的 网络中所有资源和服务都分散在各个节点上 不再由单 独的内容服务器提供 信息的传输s n l 及 务的实现都直接在各个节点之间进行 这 种平等性使得网络中的用户能够平等的享受服务 在享受服务的同时也为别人提 供服务 充分挖掘了网络节点的潜力 增进了节点间的信息交流 充分利用了网 络带宽 2 动态性 底层网络的特性决定了动态性成为p 2 p 网络的重要特点之一 节点加入与 离开频繁 使得结构化的网络组织形式的代价较高 而以自适应 松散耦合方式 来组织p 2 p 网络具有更大优势 6 第1 章绪论 3 可扩展性 网络的可扩展性 s e a l a b i l i t y 2 1 是指当节点增加时 网络能够承载由此带 来的负载 是否需要增加额外的设备来接纳新加入的节点 在p 2 p 网络中 新 加入节点所需的服务以及随之而来的通信开销由网络中其他节点共同分担 同 时 整个系统的资源和服务能力也得到扩充 因此 p 2 p 网络不会随用户的增加 而达到服务容量饱和的情况 整个系统的扩展性非常优异 4 健壮性 由于p 2 p 网络自身的特点 如资源冗余性 服务分散由各节点提供等特性 大大提高了其健壮性 当部分服务节点失效或者局部网络被破坏时 可以由其他 服务节点提供服务 因此对其他部分的服务影响很小 另外p 2 p 网络一般能够 在节点失效时自动调整整体网络结构 保证其他节点的连通 5 负载平衡 系统中的资源和服务分布在对等节点上 服务直接在节点之间进行 不需要 通过中间环节或者服务器进行 大大减少了传统c s 模式对服务器各种i 0 和计 算请求 服务带宽等方面的要求 服务提供的平均化分布实现了整个网络的负载 平衡 6 1高性价比 高性能价格比是p 2 p 技术被广泛关注的一个非常重要的原因 在硬件技术 高速发展的今天 个人计算机的性能 存储能力比几年前的服务器要优异很多 但是价格却非常低廉 利用p 2 p 架构可以有效的利用互联网中散布的大量普通 用户节点 且这些节点会随着技术的进步自行更新软硬件 将各类计算任务 存 储资料分到这些节点上 利用其闲置的计算能力和存储空间 达到更低的成本却 可以提供随时升级的高性能计算和海量存储的目的 1 3 2p 2 p 网络的体系结构 p 2 p 网络的数据传输是直接在请求者和接收者之间进行 但根据p 2 p 的控制 层面的实现 又可以归结为以下几种体系结构 2 2 1 集中控制结构 该结构使用中央服务器进行控制操作 服务器负责管理所有节点的信息 节 7 第1 章绪论 点向服务器发出请求 由服务器指导其向哪些节点连接请求资源 结构示意见图 1 4 这种结构的p 2 p n 络同时具有d s 模式和分布式系统的优点 但中央服务器 需要维护系统中的各节点的资源 状态等信息并提供所有路由服务 其开销巨大 且容易造成系统单点失效 目前的p 2 p 应用大多为这种模式 以n 斛e r 2 3 为其 中显著代表 图1 4 集中控制结构的p 2 p 网络 2 纯分布式结构 如图1 5 所示 纯分布式结构的系统没有中心控制节点 它又可分为有结构 和无结构两种 其中 无结构的分布式网络中 加入的节点并不按照一定的规则 形成一定的拓扑 而是通过例如洪泛的发现机制来确定周围的节点和资源 图1 5 纯分布式结构的p 2 p 网络 8 第1 章绪论 这种方式的网络扩展性良好 能够适应节点加入 离开网络的动态变化 但 节点不易管理 查询定位困难 并且存在安全性方面的问题 典型代表有 g n e t a l l a 2 4 和f r e e n e t 2 5 而有结构的分布式网络是指节点在加入时按照一定的 规则在逻辑上形成有序的拓扑 便于查找和定位 这种结构一般使用分布式哈希 表 d i s t r i b u t e dh a s ht a b l e d h t 来实现寻址和数据存储 2 6 2 8 算法较为复杂 3 混合式结构 如图1 6 中所示 混合式结构引入了超级节点将网络层次化 每个超级节点 管理系统的一个子网 对子网中的节点集中控制 超级节点间形成分布式的体系 结构 混合式结构结合了集中控制结构和纯分布式结构的优点 系统的扩展性良 好且性能良好 但是超级节点的存在使得系统仍然存在单点失效的问题 典型代 表有k a z z a 2 9 m o r p h e u s 3 0 等 n l n 2 且后面的列表是前面列表的真子集 p a t i a l v i e wl i s t 作为n e i g h b o u r l i s t 的候选集合 而n e i g h b o u rl i s t 又作为p a r t n e rl i s t 的候选集合 节点同n e i g h b o u rl i s t 列表中的节点建立邻居关系 周期性的交换段位图信 息 作为k e e p a l i v e 信息和选择合作者的标准 除此之外 每隔一段时间 节点 随机选择一个邻居转发自己的邻居视图信息 设置信息的耵l 值 接受到的节 点根据该信息更新自己的p a t i a l v i e wl i s t 并观察t t l 的值 如果为零则丢弃 否则随机选择一个邻居节点继续转发 邻居视图信息以g o s s i p 的形式在网络中传 播 每个节点维护网络中的部分同段节点视图 合作节点间的数据传输率低于一个门限值时 则淘汰该合作节点并从邻居节 点中重新选择 如果在 定时间内未接受到来自某邻居的k e e p a l i v e 信息 则认 为该邻居已离开该网络或离开该段 从p a r t i a l v i e wl i s t 选择新的候选者 点播节点维护一定数目的s e g m e n t s e e dl i s t 作为合作节点的补充 向段种子发 送的数据块请求若在一定时内没有得到响应 则判定该段种子节点离开网络 节 点从列表中的其它段种子节点的路由表项中直接获取同段种子或发起新的段种 第3 章单频道网络数据分发策略的研究 子查找 2 段种子节点 表3 4r o u t e r 层节点维护列表信息 r o u t e r 2 0 i t e m1 n o d e i di p a d d r e s sc u r s c h e d u a lu p d a t e t i m e l i s t d i s t a n c e i t e mk 2 一1 r e q u e s t i t e m1 n o d e i di p a d d r e s su p d a t e t i m e 1 i s t i t e mn 4 段种子节点除了作为普通点播节点的一员维护上述信息外 还需维护拓扑层 的路由节点信息列表 节点在加入拓扑层及接收到查找信息时 初始化并更新维 护自己的路由表项 根据路由表的设计 节点包含较多的同段 邻近段节点的信 息 且同段节点按照地理位置的远近被存储在相应的k 桶中 可迅速响应查询 节点同时维护近期内向它发出段请求的节点列表 作为跳转节点的初始合作节点 的候选 下面将根据节点进入网络并获取数据服务的过程 对混合式拓扑结构中控制 信息的传播与拓扑的维护进行详细描述 1 节点的加入和离开 用户点播某一视频时 向索引服务器发送点播请求 索引服务器返回一系列 c u rs c h e d u l e 处于该段的节点列表 同时利用索引服务器由目标段i d 和节点自身 的网络坐标构成目标i d 在段种子拓扑层进行段查找并返回a 个同段种子 用户收看完视频后离开网络 不需要向其它节点发送退出消息 其他节点将 根据超时信息自动去除并替换列表中的条目信息 2 顺序播放的过程 节点在顺序播放切入下一段数据下载的时候 通过正在连接的段种子节点进 行下一段查找 并向返回节点请求它们的r e q u e s tl i s t 作为候选邻居节点 可以快 速建立起新的网络拓扑关系 当上述过程不能够获取足够的节点信息时 用户继续向索引服务器发送点播 请求 同加入过程 3 2 第3 章单频道网络数据分发策略的研究 3 随机拖放的实现 进行随机拖放的过程 同顺序播放的段切换过程 仅在查找距离的跳数上略 有增加 3 3 数据调度策略 按照播放顺序进行数据块的请求 则点播视频的节点至少要以视频播放速率 获取数据才可以进行视频的正常播放 根据上文所述 在存有剩余上载带宽能力 的实际网络中 节点按照可以获取的最大下载速度向前预取 则调度窗口偏离播 放位置不断前进 我们以调度窗口的起始位置作为节点的逻辑位置 数据调度策略主要包括以下几个方面的内容 1 服务节点的选择 2 节点如何向服务节点请求数据块 3 对于接受到的同时来自多个节点的请求 服务节点按照什么策略提供服 务 3 3 1 服务节点的选择 节点缓冲所有接受到的数据 则在某一时刻其缓冲情况如下所示 采用按照 块次序的顺序调度 但由于合作节点的中途离开或者网络抖动或用户拖动操作 缓存中会存在数据块的空缺 如图3 5 所示 c u r p la y i n g c u r s c h e d u a l 1 t r 7 i 7 u r g e n tv t n d o w 图3 5 节点缓存及调度区域示意 我们选择与节点所需数据相关度最高的n 个邻居节点作为服务节点 采用 第3 章单频道网络数据分发策略的研究 轮调度策略 并根据以段划分的网络拓扑作相应设计 使得每一轮的调度数据限 制在同一段内 调度至段尾时提前终止 并切换到下一段的首轮调度 节点的缓冲可以用缓冲位图表示 其中已下载的块表示为 1 未完成下载 的块表示为 0 节点周期性的与邻居交换缓冲位图 从而获取邻居节点的缓冲 信息作为数据块请求的依据 b i t t o r r e n t 等基于m e s h 的p 2 p 内容共享应用均进 行整个文件的位图信息交换 而本文采用仅在段内进行数据调度的策略 同时节 点维护逻辑位置处于同段的邻居节点 则节点间只需交换该段缓存位图 一定程 度上减小了不必要的传输及计算开销 节点将收到的段缓冲位图与自身的段位图进行异或运算 取调度位置之后的 1 的位数为节点间的相关度表示 见公式3 5 n 为视频段包含的数据块数 相 关度越大说明该邻居可提供的数据越多 r el a t i v i t v 一t c t n a 跌 m a p d i o 锄砌嘞 f 3 5 节点的数据来源包括三个部分 1 服务器节点 如上图3 5 中所示 距离播放位置一定距离的区域作为紧 急数据区域 为防止与合作节点间的丢包或传输延迟 这部分数据块下载直接向 服务器请求 区域的大小为调度周期 视频播放率 a t x r 2 合作节点 以上一轮调度的位置作为本轮调度的起始位置 首先决定调 度窗口的大小 然后根据调度算法确定向每个合作节点发出的块请求 调度窗口 的大小至少为调度周期 视频播放率 t r 3 段种子节点 段种子节点作为合作节点的补充 负责为紧急数据域之后 调度窗口前的数据块请求服务 避免随着播放过程的推进而需向服务器请求这些 数据 从而有效的分流服务器的负载 3 3 2 服务节点间的数据块调度算法 节点同时从多个服务节点获取数据块 可有效适应网络的动态性变化 为提 供视频的正常播放 数据下载速率首先至少需要满足视频播放率 则存在n 个 合作节点时 每个节点需要提供的带宽能力为r n 为有效利用网络中的富余带 宽能力 我们根据上一阶段的调度反馈适当调节每个节点提供的服务能力 当合 第3 章单频道网络数据分发策略的研究 作节点圆满完成上一节点的调度任务 说明其上行带宽并未被完全利用 可以在 原请求基础上增加一个增量 而如果向其请求的数据块并未能完全下载 则说明 其带宽能力不足 以当前的下载量和r n 中的较大值作为下一阶段的请求量 当下载量小于一个门限值时将该节点进行新合作节点的选择更替 调度算法见图 3 6 这样的块请求策略同时具有负载均衡和自适应性的能力 另外 若当前调度窗口被段划分截为两半 则在本轮调度中只进行本段数据 的请求 并根据截断调度窗口的大小与预计传输速率的比值确定提前结束本轮的 数据调度的时间 随后切换到下一段数据的调度 合作节点是数据信息的主要来源 但在每轮调度结束时 落在调度窗口内的 数据块不一定能全被获取 原因主要有 1 合作节点均不含该数据块 2 接受数据块请求的合作节点离开网络 3 网络抖动造成的数据包延迟或丢失 4 合作节点的带宽能力不足 5 算法中采用贪婪策略依次将块请求分配至剩余带宽能力最大的节点 不 一定满足最优分配 合作节点调度过程中产生的缓存空缺将由段种子节点或服务器提供服务 段 种子节点的调度区域在紧急数据域之后 调度窗口之前 不采用轮调度策略 所 有空缺块按时间顺序排成一个请求队列 靠近紧急数据域的块位于队列首部 节 点同时向连接着的多个段种子节点发送数据请求 当某个段种子节点没有被分配 块请求 或是已完成请求块的下载时 节点查询请求队列并取出队首元素 对该 段种子节点发送新的请求 若某个块请求响应时间超时 将重新被插入到该队列 中 这种调度策略可能会造成冗余的块请求 但确保了靠近紧急数据域的块请求 被优先满足 有效的减少了由服务器进行数据提供的几率 综上我们采用的数据调度方案 紧急数据由服务器提供 服务器的稳定性及 良好的带宽能力为用户的视频播放提供了可靠的服务质量保障 又能有效地缩短 拖放延迟 用户执行拖放到目标位置时 随即从服务器获取前1 0 s 的数据开始播 放 并同时建立起节点的网络连接关系开始服务节点的数据请求 但是紧急数据 块的获取会增大服务器的负载 影响系统的扩展性 我们将其与服务节点间的数 第3 章单频道网络数据分发策略的研究 据块调度算法有效结合 算法充分利用了文中设计的混合式网络拓扑的特点 综 合了多对多数据调度策略的优势和顺序数据获取满足播放实时性的优点 有效地 降低了进入紧急数据区域的缓存空缺 图3 6h y b r i d v o d 系统合作节点间的数据调度算法 第3 章单频道网络数据分发策略的研究 3 3 3 服务节点的块请求响应策略 服务节点需一一满足从不同节点发来的块请求 下面分别讨论普通节点和段 种子节点的响应策略与顺序 1 普通节点 仅接收其它同段节点发送的块请求 节点以最大上行带宽 u p l o a d p i 响应每个请求 服务节点将接收到的块请求按紧急程度顺序插入请求 队列 完成一个数据块的传输后即从队列首部取出下一个块请求并提供服务 紧 急程度定义如下 r e q u e s t u r g e n c y c u rr e q u e s t c u r p l a y i n g 3 6 服务节点优先响应紧急程度高的块请求 从而保证靠近播放点的数据块优先 下载 减小了数据块因请求未被响应而进入数据紧急区域的可能性 减小了服务 器的负载 同时 节点设置超时门限 放弃在指定时间范围内未能响应的请求 从而满足调度的实时性 2 段种子节点 段种子节点需同时为请求存储段内容的节点和逻辑位置同 段的节点提供服务 为有效减少服务器负载 采用优先响应段数据请求的策略 同样依据数据紧急程度排序请求 综上 数据块请求应包含的域有 n o d e i d i p a d d r e s s r e q u e s t u r g e n c y f l a g s e g m e n t c u r t i m e 3 4 仿真实验与结果分析 我们分别对系统的服务器负载 索引服务器压力及跳转延迟进行仿真测试 网络仿真环境是n s 2 利用网络拓扑生成器g t i t m 6 8 产生基于中转 桩模型 t r a n s i t s t u bm o d e l 的网络拓扑作为实验的底层网络 该网络拓扑共包含1 0 0 0 个随 机产生的物理节点 其核心由5 个平均拥有4 个路由节点的相互连通的中转域构 成 平均每个中转域与l o 个桩域相连 每个桩域平均包含5 个物理节点 核心路 由节点间的网络带宽为1 0 0 0 m b p s 中转域路由节点间的网络带宽为1 0 0 m b p s 桩 域路由节点间的网络带宽为1 0 m b p s 物理节点按接入带宽分为4 种类型 a d s l 一5 1 2 a d s l 一1 5 0 0 s d s l 一51 2 d s l 一2 0 0 0 分别占2 5 3 5 2 5 1 5 带宽示意见下表3 5 3 7 第3 章单频道网络数据分发策略的研究 表3 5 节点带宽类型 类型i 带宽 a d s l 5 1 2a d s l l5 0 0s d s l 5 1 2d s l 2 0 0 0 上行 12 8 k b i t l s2 5 6 k b i t l s5 12 k b i t l s2 0 4 8 k b i t l s 下行 5 12 k b i t l s15 3 6 k b i t s5 12 k b i t s2 0 4 8 k b i t s 媒体源服务器和索引服务器分别是一个核心路由节点 节目视频编码率为 3 0 0 k b p s 播放时间为9 0 分钟 每段时间为5 分钟 数据块粒度为1 秒钟的视 频数据 初始缓冲为1 0 s 调度周期为1 0 s 实验首先对h y b r i d v o d 模型的服务器负载进行t 钡 z j 试 节点按照泊松分布加 入网络 九取值为0 5 n u m b e r s e c o n d 测试服务器负载情况并同理想调度模型 及g r i d c a s t 模型进行比较 假定节点加入网络之后不执行跳转操作 节点有5 0 的几率提前结束视频的播放并在视频播放完自动离开系统 测试时间为1 0 0 分钟 结果如图3 7 所示 o o o og 0 01 0 01 0 0 0 i i i i l lb ero t o d 图3 7 媒体源服务器负载对比图 首先可以观察到 随着节点规模的增大 g r i d c a s t 系统和h y b r i d v o d 系统 的服务器负载都维持在一个相对稳定的范围内 系统具有良好的扩展性 在某些 特定时刻该负载值优于理想调度模型 这是因为理想调度模型并没有考虑数据的 预取 节点根据播放速率下载视频并在播放结束时离开网络 靠近结束位置的节 点只能从服务器端获取数据流 而g r i d c a s t 和h y b r i d v o d 系统的调度策略使得 这部分数据已经被分布在网络上 其次 当节点规模增加至3 0 0 时 h y b r i d v o d 的性能开始优于g r i d c a s t 这是因为系统中均匀分布的各段种子节点有效地分流 3 8 第3 章单频道网络数据分发策略的研究 了服务器端的负载 实验二对存在拖动操作时索引服务器的压力进行测试 假定加入系统的节点 有9 0 进行拖放操作 其中5 0 的节点执行1 次跳转 2 0 的节点执行2 次跳转 2 0 的节点执行3 次跳转 跳转位置随机 记录不同强度九下索引服务器的平均 响应数 假定节点加入网络之后不执行跳转操作 节点在播放结束后自动离开系 统 在系统进入稳定阶段之后进行测试 图3 8 索引服务器压力对比图 图3 8 中显示 当节点不执行拖动操作时 索引服务器仅响应节点的加入请 求 其压力大小与节点的加入数呈递增的线性关系 而在h y b r i d v o d 的结构中 拖动操作对索引服务器几乎没有影响 仅当九较小时距离标准曲线有一定偏差 这是由于拖动节点首先依赖段种子拓扑进行新邻居节点的查找 仅当节点保存的 段种子索引信息失效时才会向索引服务器发送请求 当网络规模较小时 该失效 比率较大 实验证明了在用户交互频繁的系统中 h y b r i d v o d 可以有效降低索 引服务器的压力 有利于系统的扩展性和单点失效的避免 接下来考虑拖放操作的延迟时间 各节点跳转后在缓存了1 0 s 的数据后进行 播放 记录这段延迟时间为跳转延迟 图3 9 中显示了实验结果 中央索引结构 的跳转延迟随着节点规模的增大而有所增加 这是由索引服务器压力增大造成的 反应延迟造成 实验通过设定较大响应服务时间来模拟这一情况 节点规模较小 时 h y b r i d v o d 与g r i d c a s t 系统中节点的索引信息稀缺 需要较长的时间返回 第3 章单频道网络数据分发策略的研究 固定数目的邻居集合 其性能与中央索引结构相比较差 可以考虑冷门频道的点 播节点的拖放请求直接由服务器提供服务的改良 而随着节点规模的增大 h y b r i d v o d 与g r i d c a s t 可以通过索引拓扑获得良好的跳转延迟 同时 由于 h y b r i d v o d 模型中节点尽可能地向前预取 使得部分跳转数据请求可以直接被 本地缓存满足 其性能略优于g r i d c a s t 3 5 本章总结 24 681 0 n u m b e r m i n u t e 图3 9 拖放操作跳转延迟对比图 本章对单视频覆盖网络的数据分发策略进行了研究与设计 提出了一种混合 式网络拓扑的原型系统h y b r i d v o d 的设计方案 该方案通过构造有结构的段种 子节点拓扑层提供分布式的拖放目标定位与合作节点查找机制 在这种网络拓扑 结构上 文中进行了合作接节点与段种子节点 服务器相互配合的数据调度策略 的设计 以实现尽快 尽好地完成点播视频的下载 最后通过仿真实验验证了 h y b r i d 原型系统在服务器负载 索引服务器压力 跳转延迟方面均优于现有系统 能较好的满足系统扩展性与视频服务质量的需求 弱 嚣 幅 竹 o o 一 一分cm苗一 第4 章多频道网络数据分发策略的研究 第4 章多视频覆盖网络数据分发策略的研