《基于cdn的流媒体动态调度算法》由会员分享，可在线阅读，更多相关《基于cdn的流媒体动态调度算法（5页珍藏版）》请在金锄头文库上搜索。
1、2009 年 2 月Journal on CommunicationsFebruary 2009第 30 卷第 2 期通 信 学 报Vol.30 No.2基于 CDN 的流媒体动态调度算法杨戈1, 2，樊秀梅3(1. 辽宁大学 信息科学与技术学院，辽宁 沈阳 110036；2. 北京大学 深圳研究生院 集成微系统科学工程与应用重点实验室，广东 深圳 518055；3. 北京理工大学 计算机科学技术学院 智能信息技术北京市重点实验室，北京 100081)摘 要：采用指数分段缓存补丁块方案，根据媒体流行度更新缓存窗口大小，实现了流媒体对象在代理服务器中缓存的数据量和其流行度成正比的原则。仿真结果表
2、明，该算法比 MBP(multicast batched patching)算法和OBP(optimized batch patching)+prefix2. Key Laboratory of Integrated Microsystems, Shenzhen Graduate School of Peking University, Shenzhen 518055, China;3. Beijing Key Lab of Intelligent Information, School of Computer Science, Beijing Institute of Technology,
3、 Beijing 100081, China)Abstract: The scheme that the patch bytes were segmented and cached was employed. The cache window size was updated periodically according to the popularity of streaming media object. The principle was obeyed that the data cached for each streaming media object were in proport
4、ion to their popularity at the proxy server. Simulation results show that the strategy is more adaptive than MBP(multicast batched patching) algorithm and OBP(optimized batch patching)+prefix streaming media; scheduling algorithm; transmission cost1 引言在基于 CDN(content distributed network)的流媒体系统中，流媒体服
5、务器和流媒体代理服务器 是提供流服务的关键平台，是流媒体系统的核心 设备。流媒体服务器一般处于 IP 核心网中，用于收稿日期：2006-11-16；修回日期：2008-10-11 基金项目：国家自然科学基金资助项目（90604012） ；新世纪优秀人才支持计划（NCET-07-0074） ；国家高技术研究发展计 划（“863”计划）基金资助项目（2007AA01Z220） ；2007 年度辽宁大学青年科研基金资助项目（2007LDQN08） Foundation Items: The National Natural Science Foundation of China (90604012)
6、; The Program for New Century Excellent Talents in University (NCET-07-0074); The National High Technology Research and Development Program of China (863 Program) (2007AA01Z220); 2007 Years Science Fund for Young Scholars of Liaoning University (2007LDQN08)第 2 期杨戈等：基于 CDN 的流媒体动态调度算法43存放流媒体文件，响应用户请求并
7、向终端发送流 媒体数据。流媒体代理服务器，位于网络的边缘， 靠近用户，流媒体代理服务器的作用显得尤其重 要，其中流媒体调度算法的研究是其中热点之一。典型的流调度算法可分为 2 类：静态调度算 法和动态调度算法。静态调度算法主要包括：金 字塔算法1、摩天大楼算法2等。这些算法不能根 据用户请求到达情况做出动态调整，占有较多缓 存。动态调度算法由用户请求驱动媒体流的调度， 不同的用户尽可能共享同一个数据流。 动态调度算法主要包括 batching 算法3、 patching 算法4,5、piggybacking 算法6、OBP (optimized batch patching)7、OBP+pre
8、fix caching 算法、OBP+prefix&patch caching8,9等。batching 算法用一个多播给在一定时间范围内到达的对同 一个流媒体对象请求的不同用户提供服务，节省 了带宽资源，但用户得到的响应延迟较大； patching 算法用一个多播给不同用户提供服务，同 时每个用户发起一个单播接收多播已播放过的节 目前缀，减少了服务器需要传输的整个流媒体的 个数，进一步节省了传输带宽，但当用户的请求 率增大时，也需要更多的补丁通道个数，导致较 大的服务器负担；OBP 算法结合了 batching 算法 和 patching 算法的优点，降低了服务器网络带宽 消耗，但它要求通信
9、网络是一个具有网络层多播 的网络，而且对用户提出了更高的要求； piggybacking 算法通过调整邻近流的播放速率，允 许不同用户共享同一个视频流，让后面的视频流 赶上前面的视频流来实现两者的合并，网络资源 的利用率得到了提高，但调节用户的播放速率影 响了用户对媒体节目的收看效果；OBP+prefix caching 算法通过在代理服务器中提前缓存流媒体 对象的前缀部分10，可以降低或消除客户端的启 动延迟。以上算法在骨干网络带宽消耗、服务器 负载方面都获得较好性能，但没有考虑占流媒体 对象大部分的后缀的缓存策略，对后缀的有效缓 存可以进一步降低骨干网络带宽消耗和服务器负 载。OBP+pr
10、efix&patch caching 算法分段缓存补丁 数据，客户可以共享一部分补丁块，但当客户对 流媒体对象的访问请求强度很高时，这些算法仍 然需要消耗较高的骨干网络带宽。 文献11提出了 MBP(multicast batched patching)算法，根据当前到达的客户请求分布状况， 代理服务器为以后到达的客户请求进行补丁预取 和缓存，对于较流行的媒体对象，客户请求到达 率很高时，效果更加明显，而在代理服务器缓存 空间的消耗方面和 OBP+prefix&patch caching 算法 基本相同，取得了比 MPatch(multicast patching with prefix ca
11、ching)算法更低的传输成本消耗。但 它们对每个流媒体对象都进行缓存，对那些很少 被访问的媒体对象进行全部或者部分缓存都将造 成代理服务器缓存效率的下降，MBP 算法将客户 访问媒体对象等同起来，只是考虑客户对媒体对 象的访问频率，当客户对媒体对象的访问时间不 同时，没有区别对待，为了避免这些情况，增加 较流行媒体对象的缓存空间，更好地区分不同流 行度的流媒体对象，本文提出了基于 CDN 的流媒 体动态调度算法 DSA（dynamic scheduling algorithm for streaming media based on CDN） 。 本文第 2 节详细介绍一种流媒体动态调度算
12、法 DSA。第 3 节对算法进行仿真分析，得出 DSA 算法比 MBP 算法和 OBP+prefix&patch caching 算 法具有更好的适应性。第 4 节为结束语。2 流媒体动态调度算法（DSA）假定网络处于理想状态，没有抖动和传输延 时，服务器到代理之间的网络只提供单播服务， 而代理到客户之间支持 IP 多播服务，用户总是希 望从头开始播放11,12。 缓存在代理中的每个流媒体对象都要建立和 保存一个叫媒体对象访问日志的数据结构，如下 P：媒体对象前缀部分（时间长度表示） ； Ti：媒体对象 i 的总长度（时间长度表示） ； B：每个数据块，表示传输的最小数据单位 （时间长度表示）
13、 ；b：批处理间隔 b=mB（m=1, 2,） （时间长度 表示） ； Ls：第 s 段补丁数据的段长（时间长度表示） 。设 b=B，Ti=kb，缓存窗口大小为W，W=mb（m=1, 2,k） ，m 的初始值为，2k Ls=2s-1B，如图 1 和图 2 所示。44通 信 学 报第 30 卷图 1 代理服务器中补丁预取的数据段图 2 流媒体对象的分段和分块设被请求对象的前缀已经被缓存到代理中， 客户请求如 A 到达时刻 tt0，t1，如图 3 所示， 媒体对象前缀立即被代理服务器通过单播向每个 客户传送，在 t1时刻代理分配一个长度为 L0的 缓存空间，缓存即将到达的常规流的数据段 b，2b作
14、为区间t1，t2到达的客户请求的补丁 块，源服务器通过单播信道开始向代理传输常规 流 Tib 常规流到达代理后，代理通过多播通道 向客户转交。图 3 流媒体调度策略在某个时间间隔内没有客户请求到达，则该 区间为空区间，代理暂停分配缓存空间，缓存窗 口不变，如果连续出现 M(M1)以上空区间，缓存 窗口减小 Mb。客户到达的区间前面有多个连续空 区间，则代理有可能缺失一定的补丁数据，在本 区间结束时需要代理通过一个单播通道从源服务 器中重新获取缺失的补丁数据，如在t6, t7区间到 达的客户前面连续有 3 个空区间，则代理在 t7时 刻需要分配 4 个数据块缓存7b,12b、12b, 21b、
15、21b, 38b、38b, 71b，这时代理不需要从源服务 器中获取补丁服务，t6, t7到达的客户请求将在 t71 时间加入常规流中。 若没有出现空区间，到达时刻 tts, ts1 的客户请求，代理服务立即通过单播向每个客户传 送媒体对象前缀，代理服务在 ts+1时刻通过补丁通 道向客户传输补丁数据，代理服务器在 ts1时刻 分配一个长度为 Ls的缓存空间，并缓存0, 2(s+1) b， 但前面的客户已经预缓存0, 2sb，所以此时代理只 要分配 2sb 的空间来预缓存，在时刻加入常规2St通道，用于缓存2sb, 2(s+1)b，作为以后区间到达的 客户请求的补丁。客户需要在 ts1时刻加入
16、补丁 通道。经过一段时间，当客户对媒体对象的访问趋平稳时，Wb，其中是用户对avg1LbavgL这个媒体对象的平均访问时间。 设 ui是媒体对象 i 需要启动补丁通道重传的补 丁数据，如式(1)所示，T 是常规通道启动周期， Ci是当媒体对象 i 的前缀已经缓存到代理中时，单 位时间的传输成本，如式(2)和式(3)所示。Cs是每 比特从源服务器到代理之间的路径上的传输成本， Cp是每比特从代理到客户之间的路径上的传输成 本，r 是媒体对象播放的平均带宽，整个流媒体系 统共有 N 个媒体对象，是媒体对象 i 的请求到i达速率，是流媒体系统中总的访问速率，fi是媒 体对象 i 被访问的概率，其中，=1。=fi，pj是补丁数据为 jb 的概率。1Ni ifi=b(1)10mij jubjp11mj jjp当 t0W+PT 时的传输成本13 C1=
