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

【WORD可复制可编辑】基于缓存窗口和段补丁预取的流媒

体动态调度算法

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

杨戈1  2朱晓民1 廖建新1 黄海1

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

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

E-mail:

摘要:该文提出了一种新的基于缓存窗口和段补丁预取的移动流媒体动态调度算法采用代理缓存窗口自适应伸缩和分段缓存补丁块方案实现了移动流媒体对象在代理服务器中缓存的数据量和其流行度成正比的原则。仿真结果表明对于客户请求到达速率的变化该算法比传统算法具有更好的适应性在最大缓存空间相同的情况下能显著减少通过补丁通道传输的补丁数据从而降低了服务器和骨干网络带宽的使用能快速缓存媒体对象到缓存窗口同时减少了代理服务器的缓存平均占有量。

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

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

1.引言

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

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

“热门”对象的访问请求强度很高时候这个算法仍然需要消耗较高的骨干网络

带宽。文献[3]提出的P3S2A(Proxy-assisted Patch Prefetching and Service SchedulingAlgorithm)调度算法根据当前客户请求到达的分布状况代理服务器为后续到达的客户请求进行补丁预取和缓存但它对每个流媒体对象都进行缓存对那些很少被访问的媒体对象进行全部或者部分缓存都将造成代理服务器缓存效率的下降 P3S2A算法将客户对媒体对象的访问等同起来只是考虑客户对媒体对象的访问频率当客户对媒体对象的访问时间是不同时没有区别对待另外对于较流行的流媒体对象缓存速度不够快为了避免这些情况增加较流行媒体对象的缓存空间 更好地区分不同流行度的流媒体对象本文提出基于缓存窗口和段补丁预取的移动流媒体动态调度算法DS3AM2CWP2(Dynamic Scheduling Algorithm forMobile Streaming Media basedon the Cache Window and Segment Patch Pre-fetching) 。

2.基于缓存窗口和段补丁预取的调度算法(D S3 AM2 CWP2)

2. 1自适应窗口和段补丁预取

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

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

Tlas t:媒体对象最近一次被访问的时间当媒体对象第1次被访问时

Tfirst=Tlast;

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

-

1-

-1-

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

N:媒体对象被访问的次数;

Ls:每段段长(时间长度表示)  T:媒体对象总长度(时间长度表示);

B:每个数据块表示传输的最小数据单位(时间长度表示);b:批处理间隔(时间长度表示)b=mB(m=1,2,……);

P:媒体对象前缀部分(时间长度表示)。

在某时刻t Lavg,Tsum/N表示该时刻统计的每次平均访问媒体对象的长度(时间长度)  Lavg可以隔一段时间进行统计一次比如每隔n?T时间(n=1,2,….)统计1次。

设T=k?b缓存窗口大小为WW=m?b(m=1,2,….,k) m的初始值为,k, 在代理中每

,,2,,次缓存补丁预取是以相应的数据段大小为单位每个数据段包含Ns个b Ls=Ns?b设

, ,

, , , ,

,; ,;

D S 3 AM2 CWP2图2算法示意图图1代理服务器中补丁预取的数据段

2.2调度算法(DS 3AM2 CWP2)

D S 3 AM2 CWP2算法的基本思想是利用代理服务器在客户请求转交常规流数据时进行补丁预取并缓存在缓存窗口W内是否进行补丁预取取决于当前批处理区间内是否有客户请求到达以及代理是否已经缓存到W当客户播放完在代理缓存的媒体对象而且代理没有缓存到W这时要从源服务器中提取相应补丁块每

次代理服务器预取的补丁块的数量根据预先定义的数据段大小来定当客户请求到达速率较高时补丁预存能够很快达到缓存窗口最大化地利用缓存可以明显降低通过补丁通道从源服务器提取的补丁数量从而降低骨干网络负担及源服务器并发流的个数。

调度算法具体过程:

(1)假设第1个客户请求在t0时刻到达如图2这时代理中只有缓存客户请求对象的前缀部分对于第1个客户和到达时刻t [t0 t1]的客户请求如A代理服务器立即通过单播向每个客户传送媒体对象前缀部分b代理服务器将在t1时刻请求源服务器通过单播信道开始传输常规流T-b 同时代理开始预先分配一个长度为L0的缓存空间用于缓存即将到达的

-

2-

-2-

, , 1 , ,2, 1 , (i 1)i,n 1, ,2, s ,2

常规流的第一个数据段[b 2b]作为区间[t1  t2]到达客户请求的补丁块实现补丁预取常规流数据到达代理后代理通过组播通道向客户转交。

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

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

,,

时刻通过补丁通道向客户传输补丁数据代理服务器在

1+N0+N1+N2+N3+……+2

,,

2)b 开始预分配一个长度为Ls的缓存空间用于缓存

[(1+N0+N1+N2+N3+……+2

,,

 2, ,)b] 作为以后区间到达的客户请求的补丁 (1+N0+N1+N2+N3+……+2

, s 1, , )时刻加入常规通道。

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

节算法分析。具体见第3

(5)若客户到达的区间前面有多个连续空区间则代理有可能缺失一定的补丁数据如在[t6 t7]区间到达的客户前面连续有两个空区间则代理在t7时刻需要分配3个数据块缓存[5b 7b]  [7b 9b]  [9b 13b] 其中[5b 7b]的数据块需要代理通过一个单播通道从源服务器中重新获取称为补丁服务 [t6 t7]到达的客户请求将在t7时间加入常规流中。

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

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

,,

3.D S 3AM2 CWP 2算法分析

为了分析简单假设到达的客户其w1==2这时通过补丁通道传输的补丁数量要比标准3

假设在每个时间间隔中都有客户媒体对象播放的持续时间长度T=90min前缀长度P=1 min批处理间隔b=1 min常规通道启动周期为W+P,媒体播放速率为r=1.5Mbps (MPEG-1)  u是需要启动补丁通道重传的部分如图3 R表示源服务器输出链路的平均传

-

3-

-3-

,,

,, ,,

,

, 1客户需要在ts 1时刻加入补丁通道在t(1+N0+N1+N2+N3+……+2,2,

( ,Lavg,  1 )b。 , ,

DS AM2 CWP2算法多设这种情况是伪DS 3AM2 CWP2算法。为了便于比较在本试验中

输带宽(即骨干链路的平均传输速率) 骨干链路的归一化带宽(服务器平均并发流个数)为R/r,[u+(T-P)]/(W+P+1/  )如图4代理服务器的缓存平均占用量为

S即S=P?r+(u+u1)?r 如图5其中u1表示从常规通道中预取的补丁 u1=b+(W-b)?(1-p)。

9090算法OBP+prefix&patch cachingOBP+prefix&patch caching算法P3S2A算法80 P3S2A算法80 pseudo-DS3AM2CWP2算法(w1==2)pseudo-DS3AM2CWP2算法(w1==2) 707060605050客户请求到达速率=84040客户请求到达速率=1 3030

2020

1010

0001020304050607080900102030405060708090缓存窗口大小(min)缓存窗口大小(min)

(a)  =1 (b)  =8

图3补丁传输量和窗口W的关系

图3中(a)  b)分别显示OBP+prefix&patch caching算法 3S2A算法和伪DS 3AM2 CWP2算法在不同客户请求强度下通过补丁通道传输补丁数量的比较前两种算法都随W变大而增加 OBP+prefix&patch caching算法增加更快。变化最慢的是伪DS 3AM2 CWP2算法。当W,3 b时DS 3AM2 CWP2算法等同于P3 S2A算法这时无论 如何变化这两个算法要传输的补丁数据量都相同。当W>3b时伪DS 3AM2 CWP2算法都是3种算法中传输最少的补丁数据当 ,8时

P3 S2A算法和伪DS3AM2 CWP2算法都趋于稳定需要传输非常少的补丁数据OBP+prefix&patch caching算法变化不大。同理标准DS 3AM2 CWP2算法也满足这个趋势。

2025 P3S2A算法P3S2A算法算法(w1==2)算法(w1==2)pseudo-

DS3AM2CWP2pseudo-DS3AM2CWP218 OBP+prefix&patch caching算法

OBP+prefix&patch caching算法1620141215 10810645

2

0001020304050607080900102030405060708090缓存窗口大小(min)缓存窗口大小(min)

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

图4中(a)  b)分别显示OBP+prefix&patch caching算法 3S2A算法和伪DS 3AM2 CWP2算法在不同客户请求强度下消耗的骨干链路带宽 3种算法的骨干链路消耗的带宽随缓存窗口增大而减少显然伪D S 3 AM2 CWP2算法减少的更快OBP+prefix&patch caching算法减少的最慢。同理标准DS 3AM2 CWP2算法也满足这个趋势。

-4-

R/r

-4-

(min)R/r

补丁传输量补丁传输量(min)

(P

(P

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

OBP+prefix&patch caching算法800800

700700

600600

500500

400400

300300

200200

100100

0001020304050607080900102030405060708090缓存窗口大小(min)缓存窗口大小(min)

(a)  =1 (b)  =8

图5代理服务器的缓存平均占有量的对比

图5(a)  (b)分别是3种算法在不同客户请求强度下所需要的代理平均缓存空间的对比平均缓存空间随W线性增长伪DS 3AM2 CWP2算法增长的最慢OBP+prefix&patch caching算法和P3S2A算法比较接近当 ,8时 3者已经基本