（模式识别与智能系统专业论文）宽带流媒体内容分发算法研究.pdf

摘要 摘要 随着网络技术的迅猛发展和宽带的普及，越来越多的用户开始通过网络收看 电视、电影等视频内容，而具有启动时延小、不占用客户端本地存储空间等优势 的流媒体成为首选。但相对于局域网内l a s tm i l e 传输的带宽大、传输有保证而言， 在互联网上开展流媒体业务仍然无法大规模实现。在技术上，主要是受无法为大 量用户长时间获得传输流媒体所需稳定的大带宽制约。 c d n 内容分发网络将信息推到网络边缘，使之更加接近用户，它也成为解决 这一问题的良好解决方案。但传统的c d n 传输和缓存算法，大多是基于b e s t e f f o r t 模式的，它们不能适应流媒体文件通常体积巨大的特点，以及传输中需要有足够 带宽及时获取数据才能保证服务q o s 的特点。 为了使得传输和缓存调度算法适应流媒体文件的特性，在有效利用系统资源 的情况下保证流媒体服务的q o s ，已经有若干研究并提出了相关的传输和缓存调 度的算法；但是在可实用性上，仍然需要改进。在他们工作的基础上，本文主要 进行了以下研究工作： 提出了基于多传播路径的流媒体传输算法。旨在降低网络带宽波动对流媒体 视频点播服务的影响，克服传统方式下，当某一传输数据的路由因请求过多或其 它原因发生拥塞时，服务质量( q o s ) 难以保证的问题。 提出了分级混合缓存调度算法。根据用户对电影的点播行为，提出来内存和 硬盘分级混合缓存的方法，即有效提高系统的效率，分担内容服务器负荷，又有 效保证流媒体点播服务的o o s 。 完成了流媒体内容分发平台的代码。建立在宽带信息网基础上的流媒体伪容 分发平台，实现了对流媒体i p t v 的直播和流媒体视频节目的点播。在这一平台， 实验了提出算法的性能，并且也是我们今后进一步工作的基础。 关键词：流媒体，内容分发，服务质量。传播算法，缓存调度 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dt h ee x p l o s i o no fb r o a d n e t w o r k ， m o r ea n dm o r ep e o p l eb e g i nw a t c h i n gt va n dm o v i eo nt h e i rw e bt h e s t r e a m i n gm e d i a ，w i t hm o r el i t t l es t a r t l a t e n c ya n da l m o s tn o to c c u p y i n gt h el o c a l d i s ks p a c e ，b e c o m e st h ef i r s tc h o i c e b u tc o m p a r ew i t ht h ea b u n d a n c c b a n d w i d t h a n dh i g hq u a l i t yo fl a s t - m i l et r a n s p o r t ，t h ea l t e r a t i o na n di n s t a b i l i t yb a n d w i d t h m a k e i ta l m o s ti m p o s s i b l et oc o s m i c a l l yp r o v i d es t r e a m i n gm e d i ao ni n t e r n e t t h ec d nt e c h n o l o g yp u t st h ec o n t e n tu s e r sw a n t e do nt h em a r g i no fi n t e r n e t ， m a k e st h e mc l o s e rt ou s e r s a n da l s oc a np r o v i d es e r v i c ef o rs t r e a m i n gm e d i a ，b u t t r a d i t i o n a lc d n t r a n s p o r ta n dc a c h i n ga l g o r i t h m sa r eb a s e do nb e s t e f f o r tw a y ， a n d c a n tf i tt h es t r e a m i n gm e d i a ：t h e ya r et y p i c a l l yv e r yl a r g eo ns i z ea n dn e e dal o n g t i m es t e a d yb a n d w i d t hf o rt r a n s p o r tt op r o v i d eh i g hq u a l i t yo fs e r v i c e i no r d e rt om a k et r a n s p o r ta n dc a c h i n ga l g o r i t h mf i tf o rs t r e a m i n gm e d i a s e r v i c ea n du s et h er e s o u r c eo fs y s t e mt og u a r a n t e et h eq o so fs t r e a m i n gm e d i a s e r v i c e ，s o m ew o r k sh a v ea l r e a d yb e e nd o n e ，b u ti ts t i l ln e e d si m p r o v e m e n tf o r c o m m e r c eu s a g e b a s e do nt h e s ew o r k s ，w ed ow o r ko n ： w eg i v eam u l t i - s p r e a dp a t ha l g o r i t h mo na p p l i c a t i o nl a y e rt ot r a n s p o r tm u l t im e d i a ， t h en e wa r c h i t e c t u r ecano v e r c o m et h ed e f e c to ft r a d i t i o n a la r c h i t e c t u r et h a tw h e na s i n g l er o u t i n gc o n g e s t i o nu n d e rt o om a n yv o d d a t ar e q u e s to ro t h e rr e a s o n s ，t h e q o so fs e r v i c ec a i 3 tg e tg u a r a n t e e w eg i v ear a n k e dh y b r i dc a c h i n ga l g o r i t h m a c c o r d i n gt ot h eu s e r sb e h a v i o r s t a t i s t i c s ，w eg i v er a n k e dc a c h i n ga l g o r i t h mo nm e m o r ya n dd i s k ，t h a tcane n h a n c e t h ee f f i c i e n c yo fs y s t e m ，l e s s e nt h ec o n t e n ts e r v e r l sl o a d ，a n dg u a r a n t e et h eq o so f t h ev o ds e r v i c e w eh a v ef i n i s h e dac o n t e n td e l i v e r yp l a t f o r m t h ec o n t e n td e l i v e r yp l a t f o r m ， w h i c hi sb u i l to nb r o a d b a n dn e t w o r k ， c a np r o v i d ei p t va n dv o ds e r v i c eu s i n g s t r e a m i n gm e d i a ，o nt h i sp l a t f o r m ，w ed oo u re x p e r i m e n t sa n da l s ow ec a nd om o r e r e s e a r c ha b o u ts t r e a m i n gm e d i a k e y w o r d s ：s t r e a m i n gm e d i a ，c o n t e n td i s t r i b u t i o n , q o s ，t r a n s p o r t a l g o r i t h m ，c a c h i n gm a n a g e m e n ta l g o r i t h m 第一章流媒体 1 1 基本概念 第一章流媒体 1 1 1 流媒体 随着w e b 应用的迅速普及，互联网继报纸、广播、电视之后已成为第四媒体， 人们对互联网提出了更高的要求，即除了能提供文字、图像信息之外，还希望能 通过互联网提供交互的视音频广播，如视音频的直播和点播；特别是随着近年来 网络技术迅猛发展，因特网、小区宽带和局域网的带宽大幅提高，多媒体应用逐 步深入到娱乐、教育和科学研究等各个方面。 目前通过互联网观看视音频资料主要有下载和流式传输两种方案。 所谓的下载方式是指先将网络远程服务器上的多媒体文件下载到用户本地 计算机硬盘中，然后再由本地计算机对下载后的多媒体文件进行播放。下载方式 存在以下问题：多媒体文件一般较大，例如1m i n 的多媒体资料如以v c d 质量 存放，大约需要i o m 的硬盘空间，这就要求用户计算机具备较大的空余硬盘空间； 同时，由于网络带宽的限制，文件下载常常要花很长时间。 当我们使用的是一个很慢的网络时，下载一个体积巨大的多媒体文件可能要 白自等待数小时。这是用户难以忍受的。此外，这种方式不可能提供网上直播， 只能是点播。 流媒体技术的开发创意是从传统的t c p i p 协议对通过网络传送信息的控制 方法中得到的，当我们通过t c p i p 协议下载文件时，服务器就会按照一定的次序 将文件分成若干个独立的数据包，然后依次发送出去。而客户端的程序会将这些 数据包重新组装起来，最终形成和原来完全一样的完整的文件。这时候，我们就 可以对这个文件进行任何可能的操作了。 流式传输技术则不然，流式传输技术能够按照特定的顺序将文件发送出去， 而播放程序则可以边接收数据边播放他们。为了使播放更加稳定连贯。通常客户 端会通过为接收数据开辟缓存区的方法来解决网路拥堵的问题。只需要在缓存区 充满前等待几秒钟，就可以开始欣赏了。 所谓流媒体( s t r e a m i n gm e d i a ) 就是以流式传输技术通过网路传输，在时间 上具有连续性的媒体文件。 流媒体在播放前不是完全下载整个文件，而是把开始部分内容存入内存，数 据流是随时传送随时播放。采用流媒体播放方式，用户不必等到整个文件全部下 载完毕再观看，而只需经过几秒或十几秒的启动延时即可观看网上的多媒体节 目。使用流媒体播放方式不仅大大缩短了启动延时，而且用户端计算机也不需要 大的缓存容量。 流媒体同时包含下列特征：( 1 ) 流媒体的内容主要是在时间上连续的媒体 数据，像视频、音频、多媒体和计算机动画等都是在时间上连续的媒体文件：，( 1 ) 该媒体可以不经转化便能采用流式传输技术传送，这是流媒体技术的最重要特 第一章流媒体 征：( 3 ) 应用于网路，特别适用于互联网上。客户端需要播放软件或者在浏览 器上加i 二插件才能收听或收看流媒体。总之，流媒体也可以理解为是一种适合流 式传输的媒体文件格式。人们通常把携带流媒体的数据包称作流，典型的流是视 频流和音频流。 在流式传输时，流媒体数据具有实时性，等时性等基本特点，流服务期和客 户终端要保证各种媒体间的同步关系，因此，流媒体传输对“最大延时”，“延 时抖动”等q o s 参数都有严格要求。 1 1 2 流媒体系统 如上所述，流媒体系统大致有以下几个组件：压缩编码( e n c o d e r ) 设备，用 于多媒体文件的压缩和编码；流媒体服务器( s e r v e r ) ，传送多媒体文件；流文件 存档服务器，或称内容服务器，它负责向流媒体服务器提供文件；w w w 艮务器， 它向用户提供页面供用户操作。播放器( p l a y e r ) ，在用户端播放多媒体视音频信 号。如图1 1 所示。 东税霎霉芝篡黔藉： 图1 1 流媒体系统组成 播放服务器主要包括三部分：存储子系统、操作子系统和通信子系统。存储 子系统主要解决如何存放视频文件的问题，即磁盘以及磁带库或光盘库的配置参 数，如媒体文件的存放策略等问题。 按照视频文件发送的顺序，习惯上将内存视为第一级库，磁盘( 阵列) 为第 二级库，而磁带库和光盘库为第三级库。显然，内存的存取速度是最快的，妲价 格也最高，在内存中存放视频文件是不现实的。于是，内存通常用作磁盘与网络 之间的缓存器。由于磁盘具有吞吐率高、存取时延小的特点，因而通常作为那些 需要常用影片数据的缓存。磁带库和光盘库具有海量而廉价的特点，但其存取速 度慢，通常作为所有视频文件的总内容库。 1 1 。3 流媒体分类 按服务器提供流媒体数据的方式，可分为单播、广播和组播。所谓单播是指 函一 专 气祷 第一章流媒体 从1 台服务器送出的每个数据包只能传送给l 台客户机。如图l - 2 所示。 图1 2 单播方式框图 采用单播方式，媒体服务器必须向每个用户发送所申请的数据包拷贝，对于 网上直播，由于流媒体服务器向每个用户传送的信息包都相同，会造成数据大量 冗余，所以网上直播采用单播方式将增大服务器和网络的负担，使服务器响应时 间延长，甚至停止播放。 而采用i p 广播虽然允许主机把一个i p 报文发送给同一个网络的所有主机，但 由于不是所有的主机都需要这些报文，因而浪费网络资源。 解决上述问题的办法是构建一个具有组播能力的网络，允许路由器一次将数 据包复制到多个通道上。如果采用组播( m u l t i c a s t ) 方式，那么流媒体在源端只需 传输一份，组内所有具有流媒体业务的客户端均可以接收到，减少不必要的重复 发送，从而大大减少网络上传输的信息包的总量( 如图1 3 所示) 。 ，回 图1 3 组播方式框图 当然，组播不适于点播方式，因为此时服务器提供给每个用户的数据流都不 同。 1 2 流媒体传输的特点 流媒体传输强调高速、稳定和连续，强调对同步的支持，从而确保媒体数据 的按时到达，这是由于音频和视频数据流比传统数据对网络的延时更敏感，一般 情况下，人们宁愿看一个偶尔缺少若干帧的视频，而无法忍受不断地停停走走的 第一章流媒体 视频。 要在网络中传输高质量的音频、视频信息，除带宽要求之外，网络协议的选 择也直接影响视频数据广播的质量。通常互联网上的w w w n 务器使用h t t p 协 议进行传输，每次连接只处理一个请求，服务器处理完客户的请求，收到应答后 即断开连接，这种方式不适用于数据广播。而且，h t t p 是无状态协议，即协议 对于事件处理无记忆能力，这就意味着如果后续处理需要前面的信息时必须重 传，导致传输数据量增大，浪费带宽。所以流媒体传输过程中引进了实时流协议 r t s p ( r e a l t i f i l es t r e a m i n gp r o t o c 0 1 ) 。r t s p 是由r e a ln e t w o r k s 和n e l s c a p e 共同 提出的，该协议定义了多媒体数据在网络中的有效传输。r t s p 在体系结构上位 - 于r t p ( r e a lt i m et r a n s p o r tp r o t o c 0 1 ) 和r t c p ( r e a l t i m et r a n s p o r tc o n t r o l p r o t o c 0 1 ) 之上。r t p 采用固定数据率传输单向的数据流，尤其适甩于多媒体数 据流的传输。r t c p 可提供流量控制和拥塞控制服务，在r t p 会话期间，收发双 方周期性地传送含有已发送的数据包的数量、丢失的数据包的数量等统计资料的 r t c p 包，服务器可利用这些信息动态地改变传输速率。r t s p 正是利用r t p 和 r t c p 的配合使用，因而特别适用于网上的实时流媒体数据传输，同时还可以允 许双向通信，这样用户在客户端就可以进行视音频数据的前进、后退等操作。 h t t p 与r t s p 相比，h t t p 传输的数据量大、效率低，占用网络带宽较大。h t t p 请求由客户机发出，服务器做出响应，而r t s p 是双向的，客户机和服务器都可 以发出请求，这样客户端可以控制媒体当前播放位置。从上述两点看r t s p 比 h t t p 更适合作为流媒体的传输协议。 但另一方面，许多局域网城域网的防火墙不允许r t s p 通过，这就造成内网 用户无法通过r t s p 协议收看流媒体，而h t t p 却是几乎所有防火墙必须开放的， 因为w w w 服务器就是通过h t t p 进行访问的。 更重要的是，若在互联网上开展流媒体服务，即使用户的网络支持r t s p ， 这种直接的从c s ( 客户端一服务器) 模式，互联网络的带宽也远远不够支持众多 用户，而且也由于互联网上用户数目众多，流媒体服务器传输数据所需的稳定性 也难以得到保证。因而，针对，流媒体传输的特点，在互联网中开展流媒体服务， 必须将内容分发网络( c d n ) 引入其中，以满足流媒体服务的要求。 1 3 流媒体服务质量o o s 的评价标准 1 3 1q o s 的定义 服务质量( q o s ) 是指用户要求网络传输系统所必须保证的关于信息传输的 质和量的特征集，它反映服务提供者( 系统) 和服务使用者( 用户) 之间的能力 和需求关系，是用来描述网络性能的。网络系统通过o o s 体系来支持多媒体应 用，提供服务质量保证。通过q o s ，网络能够对数据包进行合理的排队，对其中 特定的数据包赋以较高的优先级，从而加速传输的进程，并实现实时交互。火d s 所追求的传输质量在于：数据包不仅要到达其欲传输的e t 的地址，而且要保证数 据包的顺序性、完整性和实时性。 4 第一章流媒体 q o s ( q u a l i t y o f s e r v i c e ) 的最初定义由c c i t t ( 现称i t u t ) 给出：“q o s 是 一个综合指标，用于衡量使用一个服务的满意程度”。q o s 的进一步定义可在 r a c e ( r e s e a r c hi n t oa d v a n c e dc o m m u n i c a t i o nf o re u r o p e ) 中找到：“q o s 描述 了关于一个服务的某些性能特点这些性能特点是用户可见的，它以用户可理解 的语言表示为一组参数。这些参数具有客观值或者主观值”。客观值刻画了系统 的行为性能( 如失败概率、吞吐量) ，主观值刻画了系统的其它服务性能( 如安 全性、优先级) 。 1 3 2q o s 与流媒体 提出q o s 机制和定义q o s 参数与多媒体实时应用都存在着紧密的关系。q o s 参数定义的目标就是要能够充分并有效地描述各种应用所想要得到的网络服务 质量要求。但是不同的媒体，如声音、图象、图形、视频、正文和动画等，存在 着不同的服务质量要求。 声音流中声音样本的大小和播放速度取决于相关的设备。假定生成的声音流 报文间隔为2 0 m s ，则电话的带宽要求为6 4 k b p s ，而c d 贝r ! 为1 4 m b p s 。声音流可 以是一个等间隔但报文不等长的数据流。声音流对延迟和延迟抖动变化非常敏 感，但是对出错率要求比较低。因为人们对声音是否连贯非常灵敏，而根据不清 楚甚至模糊的声音辨别含义的能力却非常强。 视频流中视频帧的大小和播放速度由视频设备决定。未经压缩的n t s c t v 视 频流每帧为9 0 0 k 字节( 6 0 0 4 8 0 2 4 ) ，每秒要生成3 0 帧。此时是一个报文等间隔 等长的数据流。但经过压缩后，就成为一个报文等间隔但不等长的数据流。帧大 小与压缩算法和帧所含信息相关。视频流要求高质量的数据传输和传输速率，但 对帧本身的质量可以有所降低。而且一般一个视频流应用的持续时间较长，它不 同于在正文数据传输中突发短暂的高峰流。一般实时流中的实时数据大小可变， 且一般较小，报文间隔不固定。 基于以上的分析可以看出，不同的应用有不同的q o s 要求，需要用不同的q o s 参数进行刻画。 1 3 3i s o 和i t u 中定义的q o s 参数 i s o o s i8 0 7 2 标准第一版中明确定义y q o s 参数。 ( 1 ) 建立连接延迟：用户发出连接请求到接收连接确认之间的时间间隔。 ( 2 ) 建立连接失败率：在最大建立连接延迟内不能建立连接的可能性。 ( 3 ) 吞吐量：每秒接收的用户数据字节数。 ( 4 ) 传输延迟：数据从传输发送方发出到传输接收方接收之间的时间间 隔。 ( 5 )固有出错率：在取样时间段中丢失或出错的信息占总信息数的比率。 ( 6 ) 传输失败率：由于没有符合建立连接时协商的吞吐量、传输延迟或 固有失败率而造成失败的信息占总信息的比率。 ( 7 ) 释放连接延迟：一方产生释放请求到对方执行释放的时间间隔。 第一章流媒体 ( 8 ) 释放连接失败率：没有成功释放的比率。 ( 9 ) 保护：用于说明建立安全连接需求的参数( 没有窃听或修改) 。 ( 1 0 ) 优先级：指明在该连接上传输的优先级。 ( 1 1 ) 弹性：用于说明传输层自动终结的可能性。 从i s o o s i 的q o s 参数定义标准可以看出它具有如下特点： 第一，q o s 参数定义从系统角度出发定义，主要针对运输层上数据传输过程， 大部分q o s 参数用于数据传输阶段，而没有考虑如何反映最终用户各个方面的 q o s 要求以及严格程度，女 t q o s 参数值是否可降低等； 第二，q o s 参数的表达能力有限而且不够。由于在制订该标准时，实时多媒 体应用还不广泛，资源使用的矛盾还不突出，因此在该定义中没有考虑延迟抖动 等实时等对应用所特有的指标。 在i t u 制订的a t m 网络q o s 参数定义中，用户可以指定下列参数： f1 ) 峰值信元速率( p c r ) ： 用户发送信元的最大瞬间速率。 ( 2 ) 长期承受信元速率( s c r ) ： 经过一个长时期测量到的平均速率。 ( 3 ) 信元丢失比率( c l r ) ： 因为错误和拥塞信元不能到达目的地而导致 在网络中丢失的信元所占的百分比。 ( 4 ) 信元传输延迟( c t d ) ：一个信元从进入网络到离去所经历的延迟。 ( 5 ) 信元延迟变化范围( c d v ) ：这是一个测量c t d 变化范围的参数。 ( 6 ) 突发容许( b t ) ：它决定可以按照峰值速率发出的最大突发长度。 ( 7 ) 最小信元速率( m c r ) ：用户希望至少要达到的最小速率。 a t m 标准所定义的q o s 参数，主要针对数据链路层和物理层上数据传输的特 点，反映物理网络上交换的特征，但没有考虑安全性和可靠性等方面。 1 4 互联网中流媒体业务开展的现状和引入c d n 技术的必 要性 流媒体业务现在已经取得了很大的发展。在许多大学中，都建立有基于校园 网的远程教学系统，并且得到实际应用；很多城市的i s p 目前也提供网内的流媒 体业务。 与数年之前的几乎没有资源可供使用相比，目前影响流媒体业务继续深入发 展主要存在以下问题： ( 1 )由于中心资源及传输方式的局限，目前尚没有内容提供商能承担得起 对大量用户同时传输影视流的能力： ( 2 ) 网际的流媒体服务q o s 难以得到保证； ( 3 )目前网上的流媒体文件码率有待提高。 大规模的流媒体应用要突破这些局限，就需要将流媒体与c d n 技术结合， 使得内容更加靠近用户；将内容提供商相对独立出来，以便为更大的范围提供更 好的服务；也使得服务的q o s 有更好的保证。 第一章流媒体 1 5 本文的工作 本文主要进行了以下几项工作： ( 1 ) 建立了基于3 t n e t 宽带信息网环境的流媒体分发集成平台。宽带信息 网是国家下一代主干网的实验模型，相对现有网络，具有更高的速度 和更大的带宽，以及良好的q o s 保证。本文的流媒体分发集成平台， 具有在这种高速主干网上远程分发码率更高、更加清晰的流媒体视频 内容的能力，不并对流媒体的质量提供较好的保证。更重要的是，平 台也为提供了在主干网上研究流媒体分发和缓存算法的实验基弛 ( 2 ) 提出了流媒体传输的多传播路径算法。针对流媒体传输实时性稂强， 视频点播( v o d ) 数据存在的网络带宽与数据动态变化不致的矛盾， 提出多路径传输的算法，为流媒体视频点播提供更高的q o s 保证。 ( 3 ) 提出了基于用户行为的流媒体缓存调度算法。在多传播路径算法将流 媒体文件分块的基础上，针对块与块之间内在联系，提出内容分发平 台中的分级混合的缓存调度算法，达到有效保证视频点播服务q 9 s f f 9 目的。 1 6 本文的组织 本文的章节组织是：第一章为引言，概述流媒体应用的背景和本文所做的：f 作：第二章首先介绍了c d n 网络及其采用的技术，然后研究了当前c d n i 网络 在传播上采用的几种算法；第三章介绍了几种缓冲存储的调度算法；第四章 介绍了作者提出的针对流媒体内容的多传播路径的分发传输算法；第五睾介 绍了建立的流媒体内容集成分发平台，这一平台是我们今后工作的重要基 础：第六章介绍了作者提出的分级混合缓存调度算法；最后，总结了本文的 工作和提出对未来工作的设想。 第一章内容分发嘲络 第二章内容分发网络 2 1 引言：c d n 的作用和发展方向 网络技术的飞速发展使i n t e r n e t 成为信息社会的基础载体，而由此导致的网 络用户急剧增长，超过了现有网络的负担能力。同时，i n t e r n e t 的访问速度和服 务质量还有待于提高，主要表现在长时间的传输延迟和这种延迟的不可预知性。 解决问题最基本的方法是，将放置终端客户所请求的内容的服务器推到7 i n t e m e t 的“边缘”，这样，从本地服务器访问内容会取得好的性能( 低延时、 高传输率、高质量) ，并付出较少的的网络代价。这就是c d n ( c o n t e n td i s t r i b u t i o n n e t w o r k ) 的初衷。c d n 技术是新兴的网络加速技术，它采用分布式缓存：复制、 负载均衡、流量工程和客户端重定向等技术基于i n t e m e t 构筑一个地理上分布的 内容分发网络。c d n 将信息资源向网络边缘推近，用户可以在“最近”的位置 快速访问到所需的内容。 内容分发网络一c o n t e n td i s t r i b u t i o nn e t h v r k ( c d n ) 是构筑在现有的i n t e m e t 上 的一种先进的流量分配网络。它提供了一种智能化的解决方案，通过复制源服务 器内容( 动态或者静态的内容) 到地理位置不同的代理服务器上，同时根据用户请 求的特定内容，自动把该请求转发到含有请求内容副本且距离用户最近的代理服 务器上去，从而可以避免连接到提供该内容的源服务器。重要的是该过程对用户 是透明的，而网络镜像服务需要用户自己选择，无法自动判断最佳站点。 相对于传统的路由和网络交换技术，c d n 是一个全新的领域。尽管最初c d n 结构和算法大多为h t t p 协议和静态的网页内容而设计和提供服务，但是随着多 媒体内容在互联网上越来越多，以及用户对网际间流媒体服务q o s 保证的要求 不断增加，c d n 也逐渐向提供流媒体等海量、动态、实时数据的方向发展。 改进现有c d n 结构和算法，使c d n 在流媒体传输中更好的发挥作用，正 是本文研究的内容。 2 2c d n 结构分析 c d n 是通过将源服务器中的内容分发到离终端客户近的服务器中来完成传 送的。c d n 对于内容提供商和i s p 也有益处。因为c d n 可以同时为多个内容提 供商服务，这种对资源的共享是经济的，c d n 还可以根据网络条件的i 改变和需 求来动态地调整内容的放置、请求路径以及供应能力。 2 2 1c d n 基本系统框架 在参考文献【2 7 】中，提供了c d n 的基本系统框架图。它由7 部分组成： 客户端、复本服务器、源服务器、调度组织系统、路由请求系统、分发系统和统 计系统。如图2 一l 所示。 第二章内容分发网络 图2 1c d n 基本系统框架图 2 2 2c d n 的优势 作为一种基于w e b 的网络体系结构，c d n 能快速地传送w e b 内容。更重要 的是，c d n 技术可以更好地支持i n t e m e t 上日益增长的对动态内容( d y n a m t i c c o n t e n t ) 和音频、视频等流媒体( s t r e a m i n gm e d i a ) 内容的访问。这是因为。，基 于第4 层第7 层交换的c d n 技术可以更智能地分析用户需求和网络运行状况、 更合理地分配网络带宽、调度网络资源、均衡网络负载。 2 3c d n 主要实现技术 2 3 1 负载均衡技术 在整个c d n 系统中最关键的技术就是全局负载均衡技术，它通过对服务器 的性能和运行状况的实时监测，根据不同服务器的健康状况，将来访的数据流量 以最经济，最高效的方式分配到合适的服务器上，达到最佳的服务器负载均衡效 果。 目前，全局负载均衡技术主要有： ( 1 ) d n s 轮循 ( 2 ) h t t p 重定向 ( 3 ) i p 欺骗，又称三角传输 2 3 1 1d n s 轮循 d n s 轮询是一种传统的方法，即多台w w w 镜像主机在d n s 中对应同一城 名，当用户访问w w w ，要求d n s 服务器解析域名时，d n s 服务器按d n s 请 求的前后顺序把城名依次解析成其中的一台主机的i p 地址，从而把任务毛均地 分担到数台w w w 主机上来提高w w w 服务的整体性能。 在这种方案下，用户访问的基本流程如图2 2 所示： 第二章内容分发网络 ，b 图2 2 d n s 重定向方式 算法描述如下： ( 1 ) 用户在自己的浏览器中输入要访问的网站域名，浏览器向本地d n s 请求对该域名的解析： ( 2 ) 本地d n s 将请求发到网站的主d n s ，主d n s 再将域名解析请求转 发到全局负载均衡设备： ( 3 ) 全局负载均衡设备向c d n 各节点的交换机通信，获取各节点服务器 的资源状况，然后根据一组预先定义好的策略，选出最合适的服务 器： ( 4 ) 将当前最适当的c d n 节点的i p 地址发给用户； ( 5 ) 用户向给定的c d n 节点请求相应网站的内容； ( 6 ) c d n 节点中的服务器负责响应用户的请求，提供所需的内容。 这种方案的优点是：实现简单、实时容易、成本低。缺点是选择最优服务 器策略时，会存在判断不准的现象。 2 3 1 2h t t p 重定向( h t t pr d i r e c t i o n ) h t t p 重定向方案，是通过全局负载均衡交换机的h t t p 重定向技术，将用 户的访问请求重定向到最优的服务器上。 用户访问的基本流程如图2 3 所示： 1 0 第一= 章内容分发网络 图2 3 h t t p 重定向方式 算法描述如下： ( 1 ) 当有用户访问加人c d n 服务的网站的内容时，所有访问请求都首先 被发送到全局负载均衡交换机上； ( 2 ) 该全局负载均衡交换机与分布在c d n 各节点的本地负载均衡设备 通信，根据一定策略选出一个最佳节点； ( 3 ) 然后，全局负载均衡交换机向客户机发回一个h t t p 重定向指令 ( h t t p 3 0 2 ) ，同时将重定向主机的l p 地址发送给用户： ( 4 ) 客户机收到重定向指令后，会主动去和选定的最佳站点建立连接请 求相应网站的内容； ( 5 ) 该c d n 节点中的服务器响应用户的请求，为其提供所需的内容： 这种方案解决了传统d n s 轮循方案存在的缺陷，但其缺点是只能为h t t p 访问进行重定向。 2 3 1 3 i p 欺骗 由于h t t p 重定向存在只能为h t t p 访问提供服务的缺陷，i p 欺骗可以作 为一种补充的解决方案，它同样需要在d n s 服务器中将网站对应的域名解析记 录指向到全局负载均衡之换机的i p 地址。 用户访问的基本流程如图2 - 4 所示： 第二章内容分发网络 图2 - 4 i p 欺骗方式 算法描述如下： ( 1 )当有用户访问加人c d n 服务的网站的内容时，所有访问请求都首先 被发送到全局负载均衡交换机上 ( 2 ) 该全局负载均衡交换机与分布在c d n 各节点的本地负载均衡设备通 信，根据定策略选出一个最佳节点。 ( 3 ) 然后，全局负载均衡交换机将用户的请求句发送选定的最佳节点的本 地负载均衡交换机上。 ( 4 ) 该本地负载均衡交换机将本地服务器对用户请求包的响应数据包截 获，将其源地址字段改为全局负载均衡设备的 p 地址，然后发送给用 户。 这样，整个过程对用户来说，感到觉的只是全局负载均衡交换机在为其服务， 并不知道经历了这样个三角传输的过程。 这种方案，主要作为h t t p 重定向方案的补充方案，在同设备上运行。o 2 3 2c a c h e 技术 c a c h e 设备是可以单独应用的网络设备，并非一定使用在内容分发网络中。 高速缓存技术是基于这样一个事实：用户访问i n t e m e t 的数据中，有很大一 部分是重复的，包括访问同样的页面、下载相同的软件。通过使用c a c h e 技术， 可以缓存用户访问过的对象，这样对相同对象的访问就无需再占用服务器处理能 第二章内容分发网络 力或者主干的出口带宽。同时，由于用户对服务器的请求可以由c a c h e 立即响应， 因此可以极大地提高用户访问的响应速度。 从c a c h e 实现的功能可以看出，c a c h e 实际是一个巨大的内容转发系统， i n t e m e t 的内容存储在大容量的磁盘系统中，由c a c h e 提供对存储内容快速查找 的方法。一个具有良好性能的c a c h e 应当具有快速的磁盘读写速度、内容查找速 度及响应速度。 c a c h e 的应用模式分为正向模式和反向代理模式。位于c d n 中的c a c h e 主 要是存取申请该项服务的网络企业用户的网站内容，因此应该配置为反向代理模 式。 反向代理类型高速缓存r e v e r s e - p r o x y ，又称s e r v e r a c c e l e r a t i o n ，与客户端 无关，提供的是对w e b 服务器端的加速访问。它的应用方式是缓存服务器放置 在w w w 服务器或流媒体服务器静端，代理w w w 和流媒体服务器接受所有客 户的请求，此时缓存服务器类似于一台w e b 或流媒体服务器。它在t c p8 0 端口 接受h t t p 请求访问，在t c p5 5 4 端口接受r t s p 协议请求访问，在t c p a j d p1 7 5 5 接受m m s 协议请求。根据i n t e m e t 上的统计表明，超过8 0 的客户经常访问的 是2 0 的网站内容，而流媒体的访问则更加集中。在这个规律下，缓存服务器可 以处理大部分的客户静态请求，而原始的服务器只需处理很少部分的非缓存请求 和动态请求，于是大大加快了客户请求的响应时间，并降低了原始w w w 或流 媒体服务器的负载，极大地提高了高峰时间网络所能承受的访问容量。 2 4c d n 相关算法 2 4 1 概述 上文介绍了目前c d n 传输的主要负载均衡技术：即把请求通过某种方法转 发到指定的内容分发服务器上，然后再由这个被指定路径上的内容服务器来向提 出请求的客户端发送数据，从而实现互联网上数据传输的多、快、好、省。下面 介绍几种基础的和基于它们改进的缓存分发点选择算法。 目前这些基础的c d n 传输算法，大多目标在于合理的安排在何处缓存某个 内容，使得全局代价( 时延、费用) 等最小，并没有考虑到我们要叙述的问题： 保证流媒体顺利播放。因为对用户而言，一个时断时续的影片即使是免费提供也 是用户难以收看的。但是，这些c d n 的基本算法，却是我们做出改进工作的基 础。 2 4 2 图论基础 ( 1 ) 设备位置问题( f a c i l i t yl o c a t i o np r o b l e m ) 给定一系列点i ，在这些点可以放置设备，并且有在点i 放置设备的代价是。 每个客户j 必须被安排到归属某一个设备，它引起的代价是d i c i i ；d i 表示节点i 缓存 引起的代价，c i i 表示i 莉之间的距离。 问题是要找出总代价最小的解决方案。这是个度量空间上的n p 复杂问题。 第一章内容分发网络 解决这一问题通常使用p 接近算法。目前公认的最好的结果是取p 值为! 7 2 8 。 ( 2 ) 最小k 中心问题( m i n i m u mk - m e d i a np r o b l e m ) 给定n 个点，首先选择其中的k 个作为中心点，然后为剩下的每个节点i 选择 距离它最近的中心点。假如位置j 被指定属于中心点i ，我们记引起的代价是也c 。 问题是，要找出能使得指定中心点所花代价的总和最小的k 个中心点。 最d , k 中心问题和设备位置问题的主要区别是最d , k 中心问题在指定中心点 时没有代价，取而代之的是数字k 作为输入参数，它说明能够指定的中心点的上 限。 比如c h a r i k a r 和g u h a 提出的4 相似算法r 4 - a p p r o x i m a t i o na l g o r i t h m ) 是度量 空间上的一个解决算法。 2 4 3 选择缓存点的树算法( t r e e b a s e da l g o r i t h m ) 选择缓存点，就是选择c d n 分发的请求被重定向到网络中的哪个节点上， 或者说内容将由哪个位置上的缓存服务器来提供服务。 树算法假定网络的拓扑结构是树型，并且把它作为一个动态规划问题表解 决。 设t 是有n 个节点的有根树。把树t 的根节点称为r 。一个节点能有任意多个 子节点，并且假设这些节点是从左到右排序的。 对每个节点v t ，其权重w ( v ) 是表示正通过该节点流量的非负值；对每条边 ( u ，v ) ，距离d ( u ，v ) 可以是连接代价，跳数( 经过的节点数) 等数值。树中从u 到v 的路径记为兀。易见：d ( u ，v ) = i 1 。兀u 。d ( x ，y ) 就是树中两点间距离。 假设我们给定了一个顶点集合p t 且r p 。定义点c ( v ，p ) 是从v 向上回溯 到根结点r 的过程中，属于集合p 的第一个结点( 最低祖先结点) 。需要注意的是 结点能够是v 本身。 c o s t ( t ，p ) = w ( v ) d ( v ，c ( v ，尸) ) ( 1 ) 、，e 7 这一代价计算公式包括了选择在位置点集合p 中选择缓存点的代价。因此它 计算的是把集合p 中的点作为缓存点时，服务用户请求的总代价。算法就是要找 出在给定m 时，lpl = m 且r p 的p 集合使上式取最小值。如果取d ( u ，v ) 是时延， 那上式最小值的意义就是在给定m 个缓存点后在网上搜索目标的总花费时间最 小。 若v e t ，记t v 是t 以v 为根节点的子树。给定x ，y t ，若x 在y 左表示，表示 存在u ，v t ，x e t 。，y t ，且u ，v 是u 在v 左的兄弟节点。例如在图2 5 中，集 合l 。中的每个节点都在树t 。中任意节点的左侧。 若u t v ，1 - i 。+ 。是t 中连接u 和v 的路径( 如图2 6 中黑色实线) ，定义： l 。= f x t ，：x 在u 的左侧 t u v = x t v ：x 诺t uul u v 墨三蔓宣窒坌垄堕塑： 图2 5 t 。是t 以v 为根结点的子树 一f t u 图2 6 非兄弟节点的左侧定义 对x t u 。，设： l u 。= y t 。、：y 在x 的左侧 定义： c ( v ，t ) 。，r a ，i n ，c o s t ( i , ，p ) f ( 、i i ；，v e j c ( u ，”，) 。忙l 唑。c o s t ( 瓦，p ) 这里，c ( v ，t ) 就是在集合t ，中选择t 个点作为缓存点的最小代价，c ( u ，v ， t ) 是在集合t 。中选择t 个点作为缓存点的最小代价。这样，原问题就变成了求c “ m ) 和取该最小值时缓存点的集合p