算法原稿基于缓存窗口和段补丁预取流媒体动态调度算法

【WORD格式原稿】基于缓存窗口和段补丁预取的流

媒体动态调度算法

免费查阅标准与论文地址:

*基于缓存窗口和段补丁预取的流媒体动态调度算法 12111杨戈朱晓民廖建新黄海

1北京邮电大学网络与交换技术国家重点实验室北京(100876)

2辽宁大学信息科学与技术学院沈阳(110036)

E-mai l :

摘要:该文提出了一种新的基于缓存窗口和段补丁预取的移动流媒体动态调度算法采用代理缓存窗口自适应伸缩和分段缓存补丁块方案 实现了移动流媒体对象在代理服务器中缓

存的数据量和其流行度成正比的原则。仿真结果表明对于客户请求到达速率的变化该算法比传统算法具有更好的适应性在最大缓存空间相同的情况下能显著减少通过补丁通道传输的补丁数据从而降低了服务器和骨干网络带宽的使用能快速缓存媒体对象到缓存窗口 同时减少了代理服务器的缓存平均占有量。 关键

字:移动流媒体调度算法代理缓存段补丁预取

中图分类号:TP393文献标识码:A

1引言

在移动通信网上流媒体正受到越来越多的重视在大规模的流媒体系统中用户的点播往往集中于少数热门节目这就使得合并用户服务、共享服务器和网络带宽等资源成为可能于是流调度技术应运而生。

[1,2]OBP(Optimized Batch Patching)+prefix&patch caching算法将补丁数据也进行分段缓存让不同批处理区间到达的客户可以共享一部分补丁块但当客户对“热门”对象的访问请

32求强度很高时候这个算法仍然需要消耗较高的骨干网络带宽。文献[3]提出的PSA(Proxy-assisted Patch Prefetching and Service Schedul ing Algorithm)调度算法根据当前客户请求到达的分布状况代理服务器为后续到达的客户请求进行补丁预取和缓存但它对每个流媒体对象都进行缓存对那些很少被访问的媒体对象进行全部或者部分缓存都将造成代

32理服务器缓存效率的下降 PSA算法将客户对媒体对象的访问等同起来只是考虑客户对媒体对象的访问频率 当客户对媒体对象的访问时间是不同时没有区别对待 另外对于较流行的流媒体对象缓存速度不够快 为了避免这些情况增加较流行媒体对象的缓存空间 更好地区分不同流行度的流媒体对象本文提出基于缓存窗口和段补丁预取的移动流媒体动

322态调度算法DSAMCWP(DynamicSchedul ing Algorithm for Mobi leStreaming Media basedon the CacheWindowand Segment Patch Pre-fetching)。

2基于缓存窗口和段补丁预取的调度算法(DS3AM2CWP2)2 1自适应窗口和段补丁预取

缓存在代理中的每个流媒体对象都要建立和保存一个叫媒体对象访问日志的数据结构 具体内容如下:

T:媒体对象第1次被访问的时间; first

T:媒体对象最近一次被访问的时间 当媒体对象第1次被访问时 T=T;lastfirstlast

*本课题得到国家杰出青年科学基金(60525110);新世纪优秀人才支持计划(NCET-04-0111);高等学校博士学科点专项科研基金资助课题(20030013006);电子信息产业发展基金项目(基于3G的移动业务应用系统);电子信息产业发展基金重点项目(下一代网络核心业务平台)资助。

- 1 - - 1 -

免费查阅标准与论文地址:

T:媒体对象被访问的总长度(时间长度表示); sum

N:媒体对象被访问的次数; L:每段段长(时间长度表示) T:媒体s

对象总长度(时间长度表示); B:每个数据块表示传输的最小数据单位

(时间长度表示);b:批处理间隔(时间长度表示)b=mB

(m=1,2,……); P:媒体对象前缀部分(时间长度表示)。

在某时刻t L,T/N表示该时刻统计的每次平均访问媒体对象的长度(时间长度)avgsum

L可以隔一段时间进行统计一次 比如每隔n?T时间(n=1,2,…)统计1次。 avg

设T=k?b缓存窗口大小为WW=m?b(m=1,2,…,k) m的初始值为在代理中每k????2??个b L=N?b设次缓存补丁预取是以相应的数据段大小为单位每个数据段包含Nsss

?s???s???1?1?????2s>n, s?2, (i?1)i=0,1s???本文中取i=2 n=1如图1则2?s=0,1, , nN?s1 , n+1??=??=N?s1 ,?????

?

??

2 2调度算法(DS3AM2CWP2)322 DSAMCWP算法的基本思想是利用代理服务器在客户请求转交常规流数据时进行补丁预取并缓存在缓存窗口W内是否进行补丁预取取决于当前批处理区间内是否有客户请求到达以及代理是否已经缓存到W 当客户播放完在代理缓存的媒体对象而且代理没有缓存到W这时要从源服务器中提取相应补丁块每次代理服务器预取的补丁块的数量根据预先定义的数据段大小来定 当客户请求到达速率较高时补丁预存能够很快达到缓存窗口最大化地利用缓存可以明显降低通过补丁通道从源服务器提取的补丁数量从而降低骨干网络负担及源服务器并发流的个数。

调度算法具体过程:

(1)假设第1个客户请求在t时刻到达如图2这时代理中只有缓存客户请求对象的前0

缀部分对于第1个客户和到达时刻t?[t t]的客户请求如A代理服务器立即通过单播01向每个客户传送媒体对象前缀部分b代理服务器将在t时刻请求源服务器通过单播信道开1始传输常规流T-b 同时代理开始预先分配一个长度为L的缓存空间 用于缓存即将到达的0

- 2 - - 2 -

免费查阅标准与论文地址:

常规流的第一个数据段[b 2b]作为区间[t t]到达客户请求的补丁块 实现补丁预取 常规12

流数据到达代理后代理通过组播通道向客户转交。

(2)当到达时刻t?[t t]的客户请求如B代理服务同样立即通过单播向每个客户传送12媒体对象前缀部分b代理服务器在t时刻开始预先分配一个长度为L的缓存空间 用于21缓存[2b 3b] 作为下一个区间[t t]内到达的客户请求的补丁 同时代理服务器在t时刻232通过补丁通道向客户传输补丁数据通过组播向客户转交常规流 系统运行到t时刻代理3服务器已经缓存2个长度L L的补丁段。 01

(3)同理若在整个缓存窗口中没有出现空区间 当到达时刻t?[t t]的客户请求如 ss1 D代理服务同样立即通过单播向每个客户传送媒体对象前缀部分b代理服务在t时刻s+1

?1s?=??12通过补丁通道向客户传输补丁数据代理服务器在

1+N+N+N+N+……+时刻20123?1s???1??2??)b 开始预分配一个长度为L的缓存空间 用于缓存[(1+N+N+N+N+……+2s 0123?1s??s???1?1????22????(1+N+N+N+N+……+2  2)b] 作为以后区间到达的客户请求的补丁

0123

?1s???12时刻加入常规通道。 客户需要在t时刻加入补丁通道在t )s1(1+N0+N1+N2+N3+……+2

(4)若在某个时间间隔内没有客户请求到达则该区间为空区间这时代理暂停分配缓存空间 同时缓存窗口减小一个b。此后如果在后续的时间间隔内有客户请求到达则代理根据实际情况决定分配缓存的大小以及是否向服务器要求补丁服务和加入常规通道的时间 具体见第3节算法分析。

(5)若客户到达的区间前面有多个连续空区间则代理有可能缺失一定的补丁数据如在[t t]区间到达的客户前面连续有两个空区间则代理在t时刻需要分配3个数据块缓存[5b 677

7b]  [7b 9b]  [9b 13b] 其中[5b 7b]的数据块需要代理通过一个单播通道从源服务器中重新获取称为补丁服务 [t t]到达的客户请求将在t时间加入常规流中。 677

(6)重复上面(3),(6)步直到缓存窗口边界。经过上面(1),(7)步后如果在代理中已经缓存媒体对象的一部分大小等于前面一个服务周期结束时缓存窗口的最终长度后来的客户请求将开始一个新的服务周期首先由代理向客户提供服务在服务到缓存窗口需要代

过一个单播通道从源服务器中获取媒体对象剩余部分(T-W)。 理通

(7)经过一段时间本文取经过该媒体对象的播放时间可设代理缓存窗口W,

Lavg??( )b。 +1??b??

3 DS3AM2CWP2算法分析

为了分析简单假设到达的客户其w==2这时通过补丁通道传输的补丁数量要比标准1322322 DSAMCWP算法多设这种情况是伪DSAMCWP算法。为了便于比较在本试验中 假设在每个时间间隔中都有客户媒体对象播放的持续时间长度T=90min 前缀长度P=1min 批处理间隔b=1min  常规通道启动周期为W+P,媒体播放速率为r=15Mbps (MPEG-1) u是需要启动补丁通道重传的部分如图3 R表示源服务器输出链路的平均传

-3 - -3 -

免费查阅标准与论文地址:

输带宽(即骨干链路的平均传输速率) 骨干链路的归一化带宽(服务器平均并发流个数)为R/r,[u+(T-P)]/(W+P+1/λ)如图4代理服务器的缓存平均占用量为S即S=P?r+(u+u)?r 1如图5其中u表示从常规通道中预取的补丁 u=b+(W-b)?(1-p)。 1 19090 OBP+prefix&patch caching算法OBP+prefix&patch caching算法P3S2A算法80算法P3S2A pseudo-DS3AM2CWP2算法(w1==2)80 pseudo-

DS3AM2CWP2算法(w1==2)70706060(min)50(min)50客户请求到达速率=8客户请求到达速率=14040补丁传输量3030202010100001020304050607080900102030405060708090(min)缓存窗口大小(min)缓存窗口大小

(a)λ=1(b)λ=8图3补丁传输量和窗口W的关系

32322图3中(a) (b)分别显示OBP+prefix&patch caching算法 PSA算法和伪DSAMCWP算法在不同客户请求强度下通过补丁通道传输补丁数量的比较前两种算法都随W变大而

322增加 OBP+prefix&patch caching算法增加更快。变化最慢的是伪DSAMCWP算法。 当W

32232?3b时 DSAMCWP算法等同于PSA算法这时无论λ如何变化这两个算法要传输322的补丁数据量都相同。 当W>3b时伪DSAMCWP算法都是3种算法中传输最少的补丁

32322数据 当λ?8时 PSA算法和伪DSAMCWP算法都趋于稳定需要传输非常少的补丁322数据 OBP+prefix&patch caching算法变化不大。同理标准DSAMCWP算法也满足这个趋势。

2025 P3S2A算法P3S2A算法pseudo-DS3AM2CWP2算法(w1==2)算法(w1==2)pseudo-DS3AM2CWP218 OBP+prefix&patch caching算法

OBP+prefix&patch caching算法162014121510 R/r R/r810补丁传输量64520001020304050607080900102030405060708090缓存窗口大小(min)缓存窗口大小(min)

(a)λ=1(b)λ=8图4骨干链路归一化带宽和窗口W关系

32322图4中(a) (b)分别显示OBP+prefix&patch caching算法 PSA算法和伪DSAMCWP算法在不同客户请求强度下消耗的骨干链路带宽 3种算法的骨干链路消耗的带宽随缓存窗

322口增大而减少显然伪DSAMCWP算法减少的更快 OBP+prefix&patchcaching算法减少

322的最慢。同理标准DSAMCWP算法也满足这个趋势。

-4- -4-

免费查阅标准与论文地址:

P3S2A P3S2A算法算法10001000 pseudo-DS3AM2CWP2算法(w1==2)pseudo-DS3AM2CWP2算法(w1==2)OBP+prefix&patch caching算法

OBP+prefix&patch caching算法900900800800700700(MB)(MB)600600500500400400300300占用的代理缓存空间占用的代理缓存空间2002001001000001020304050607080900102030405060708090(min)缓存窗口大小(min)缓存窗口大小

(a)λ=1(b)λ=8图5代理服务器的缓存平均占有量的对比

图5(a) (b)分别是3种算法在不同客户请求强度下所需要的代理平均缓存空间的322对比平均缓存空间随W线性增长伪DSAMCWP算法增长的最慢OBP+prefix&patch

32322caching算法和PSA算法比较接近 当λ,8时 3者已经基本重合。 因为标准DSAMCWP 322322算法比伪DSAMCWP算法的u小而在同样条件下u相同所以标准DSAMCWP算1322法必然在伪DSAMCWP算法曲线下面。

4结束语322本文根据用户对流媒体对象的访问行为提出了DSAMCWP调度算法每次分配不同大小的缓存段 实现基于常规流的补丁预取和缓存 同时隔一段时间更新一次缓存窗口大小根据媒体流行度动态决定其最大缓存大小尽量拖延了加入常规流的时间这样不但降低了补丁块传送的数量从而降低了骨干网络带宽的消耗和流媒体服务器的负担而且在

32232少量客户请求时能够节省代理缓存。实验表明 DSAMCWP算法比PSA算法和OBP+prefix&patch caching算法具有更好的性能但是在客户请求相对较少的情况下 32232DSAMCWP算法有可能在某一时刻比PSA算法和OBP+prefix&patch caching算法占有多一些的代理缓存但经过一段时间的缓存窗口自动调整这种情况会有很大改善考虑到目

322前的缓存成本 DSAMCWP算法还是具有非常大的实际用途。另外移动网络用户也非

322常需要流媒体系统提供VCR-l ike功能 下一步是如何在DSAMCWP算法的基础上实现VCR-l ike功能。

参考文献

[1]Verscheure O,Venkatramani C, Frossard P and Amini L Joint serverschedul ing and proxycaching forvideo del ivery[J] Computer Communications,

2002 25(4):413-423

[2] Frossard P,Verscheure O Batch patch caching forstreaming media[J] IEEECommunications Letters,2002,

6(4): 159–161

[3]覃少华李子木蔡青松 胡建平基于代理缓存的流媒体动态调度算法研究[J]计算机学报 2005,

28(2):185-194

QINShao-Hua, LIZi-Mu,CAI Qing-Song,HUJian-Ping Studyondynamicschedul ing algorithmsforstreaming media based on proxy caching[J] ChineseJournal of Computers,2005,28(2):185-194

- 5 - - 5 -