流媒体服务系统中一种基于数据预取的缓存策略

巫旭敏 殷保群 黄 静 郭 东

(中国科学技术大学网络传播系统与控制联合实验室网络传播系统与控制安徽省重点实验室 合肥 230027)

1 引言

随着计算机网络发展，流媒体服务系统在应用上逐渐成熟。流媒体服务系统具有视频点播(Video On Demand, VOD)特性和实时性，一般使用缓存进行服务[1,2]由于存储容量有限，此类系统通常采用部分缓存[3−12]。这就需要适当的策略管理缓存。在内存管理中 LRU (Least Recently Used) 算法置换最近最少使用的数据，但流媒体服务系统受各节点间网络带宽限制以及存在大量不同内容同时被访问的现象，所以 LRU 对 QoS 的提高有限。基于热度的策略[5−10]通过缓存热度高的数据减小请求延迟和系统负载。热度是指各影片或影片片段被访问次数在总数据请求次数中所占的比率。文献[5]根据优化目标把多媒体文件分割成 3 部分分别存储在缓存、客户端以及中心服务器。文献[6]探讨了两种典型的分段策略：定长分段和指数分段。定长分段由于各段大小相同易于管理[7−12]。文献[5,7]将缓存管理归纳为动态规划，并利用贪心算法求解以降低计算复杂度。文献[8]针对流媒体系统的命中率、点播延迟以及网络抖动等性能进行研究，并给出基于多目标规划的解决方案。文献[9]进一步考虑了影片码率对存储策略的影响。

基于热度的缓存策略通过缓存访问频繁的数据减少本地节点向其它节点请求的数据量以及点播延迟。由于热度是通过统计给出的而未考虑用户的VCR(Video Cassette Recording)行为[11,12]，当用户随机请求影片内容时，若请求数据段未被缓存，用户会获得较大的延迟。在 VOD 系统中 VCR 表示客户端对节目的快进、快退、暂停以及随机访问等交互操作。文献[11]采取折衷的策略，若请求数据未存储到本地就选择缓存中在播放时间上和该数据较接近的内容进行服务，在减小延迟的同时用户的请求会得到偏移。文献[12]针对客户端的 VCR 行为，研究 P2P 系统中的数据预取以及客户端的缓存管理。

在流媒体服务系统中，为了减小服务延迟以及系统负载，主要研究思路是利用有限的存储空间结合影片热度提高缓存效率，而实际上系统是通过缓存以及数据预取两种机制获得数据提供服务的，而当前大部分研究并没有考虑到数据预取对缓存效率的影响。本文的创新之处在于结合数据预取综合考虑流媒体服务系统中数据的起始延迟以及在服务过程中抖动所引起的延迟，计算出该延迟的期望，利用贪心算法给出缓存管理的次优解，并通过在线优化的方法提高缓存效率。

2 预取机制

本文采用 P2P-CDN (Content Distribution Network)的混合结构(图1)，各缓存节点和中心服务器形成 P2P 网络。影片采用定长分段，中心服务器存储所有数据，缓存节点部分存储。当请求到达时，若本地缓存有客户请求的数据，本地缓存直接进行服务，否则，本地缓存向其它缓存或中心服务器请求数据，再对客户端提供服务。通常本地缓存和用户之间的传输延迟小，其数据传输速率大于影片码率，而缓存节点之间以及缓存到中心服务器之间的传输延迟较大，其数据传输速率小于影片码率。

图1 P2P-CDN结构的流媒服务系统

假设有N部影片，其中第v部影片有Sv个数据段，其码率恒定为rv，数据段播放时间为Tv，大小为Seg，Seg=rv⋅Tv。若用户当前观看影片v的第i段，为了减小延迟，本地缓存应向其它节点请求未缓存到本地的数据，并决定需要预取的数据段以及进行带宽分配。假设点播段i时刻为ti，结束播放时刻为ti+Tv，当开始播放段i时，由于上一个预取周期的数据下载可能未完成，需要时间θi下载剩余数据，即开始预取时刻为ti+θi，θi称为预取时间间隔。用户结束段i播放后请求数据段用j表示，用ti+Tv表示用户请求段j的时刻。tj表示段j开始播放的时刻，则段j的请求时延τj=tj−(ti+Tv),τj≥0。预取过程如图 2 所示，播放段i时的预取从时间ti+θi开始，在tj+θj结束。

3 预取和缓存策略

图2 播放数据段i时的预取过程

记fv(x, y), x, y∈{1,2,…,Sv}，表示用户观看影片v从段x跳转到段y的统计次数，当x=y时表示重播当前数据段，可以估计出用户观看影片v时从段x跳转到段y的概率

若已知用户当前点播段α，用户下一段点播段y的条件概率为

记影片v的所有数据段集合为Cv，时刻t影片v存储在本地的数据段集合为，未存储在本地的数据段集合为，Cv=+。若影片v段i未缓存到本地，记为系统中所有节点对该数据段的总上传带宽。bd为本地缓存的下载带宽，满足bd≥，即本地缓存下载带宽不小于任一数据段的上传带宽。为预取影片v段k的带宽，≤≤。用户点播影片v段i后点播段j，若段j未缓存到本地，当满足≥Seg/(T−)时，客户端没有延迟。v记=Seg/(Tv−)，若＞会降低下载带宽利用率，所以≤。当用户结束影片v段i播放后，此时已知下一个请求的数据段为j，若段j未下载完，为了尽快获得需要的数据段本地缓存以系统上传带宽进行下载。用τ表示客户端请求数据段的延迟，当t时刻客户正在观看影片v的段i时，下一个数据段延迟的期望为[12]

式(3)被分为 3 部分，其中第 1 部分表示没有缓存和预取机制的延迟期望，第 2 部分表示缓存机制所减小的延迟期望，第 3 部分表示预取机制所减小的延迟期望。定义表示已知用户访问影片v时请求数据段为i的概率，fv(x, y)中约定x=0表示用户从第y段开始请求影片v，y=0表示用户点播完段x后结束影片v的访问，即x, y∈{0,1,2,…,Sv}，有

通过式(3)可得

记vP表示影片v的热度，它服从 Zipf 分布[7]，有系统延迟期望为

其中可以利用fv(x, y)计算出

要使用户请求数据段的延迟期望最小，则应满足式(8)

Stor表示本地缓存的大小，即式(11)表示缓存到本地的数据段受存储容量限制。表示影片v(v∈{1,2,…,N})需要缓存的数据段以及(k∈)表示影片未缓存的数据段的预取带宽。fv(x, y)为一段时间内统计的结果，,也可以以通过一段时间的统计给出其均值，系统通过周期性地更改这些参数的信息进行缓存调整。定义β因子为

γ因子为

式(8)可以等价为

式(14)第 1 项表示缓存减小的延迟期望，第 2 项表示预取减小的延迟期望。考虑已知Rtv的情况求第2 项，此时式(14)为有约束的线性规划，表示已知存储的情况下进行数据预取，有

记iv表示影片v的段i，Dt表示按照式(15)的贪心算法求解出的预取带宽不为 0 的数据段组成的集合，有Dt⊆Ut,,考虑∈R, iv2t 2∉Rt的情况，若用置换缓存中的，记置换后缓存数据段，未缓存数据段以及预取数据段分别为Rt′,Ut′,Dt′，其中满足∉Rt′,∈Rt′, Rt∪Rt′=∪{iv2}=R∪{}，置换缓存前后的请求数2t′据段延迟的期望分别为E{τ}和E{τ′}，记ΔE{τ}=E{τ}−E{τ′}，有以下 3 种情况：

(1)选择β值较大的数据段缓存，确定Rt，然后在Ut中选择γ值较大的数据段，确定Dt；

(2)将Rt中的数据段按照β值从小到大排列索引，记η=2为一个索引序号的初始值；

(3)当预取一个数据段时，分别按照情况 1，情况 2，情况 3 和Rt中索引为 1 的数据段进行比较，若索引为 1 的数据段不被替换，依次和索引为η, η+1,…的数据段进行比较，直到有数据段被预取数据段替换，记该数据段索引为k，有η=k+1，原索引为1,…,k−1的数据段索引号依次加 1，缓存的预取的数据段索引记为 1，在线继续进行步骤(3)。

由于替换的过程是按照索引号从小到大查找第1 个满足替换条件的数据段，所以可以确定不能替换索引为 1 的数据段则一定不能替换索引为2,…,η−1的数据段。情况 2 中由于＞γ′，而γ′又必定大于等于Dt中最小的γ因子，故当γ′取Dt中最小的γ值时，令ΔE{τ}=0，此时求的为比较的上限，即当的β因子高于此值时就可以终止比较，段不被存储在缓存中，类似可以求出情况 3中的比较上限。

在Rt确定的情况下，可以按照式(15)利用贪心算法进行求解。式(15)是对一段时间进行统计的结果，而实际预取需要根据客户端实时请求的状况进行预取带宽分配，所以实际的预取策略需要将式(15)中的基于统计的参数用实时值替换进行求解。

4 仿真

考虑 3 部影片，热度服从 Zipf 分布，影片按热度从高到低排序，影片v的热度

仿真取μ=0.271[7], N=3。影片分别有 12， 13和 11 个数据段，码率取为 500 kbps，数据段播放时间为 30 s，数据段为 15000 kb，缓存容量取为总数据量的 1/3 即缓存 12 个数据段，下载带宽bd=6000 kbps ，各影片的上传带宽需高于影片的码率分别取为 500～1500 kbps 之间的随机数。客户端请求服从 Poisson 分布，请求的时间间隔服从参数为 60 s 的指数分布，请求数取 50000 次。客户首次请求首段的概率取 0.7～0.9 之间的随机数，首次请求其他数据段的概率服从均匀分布，连续请求即客户观看完影片段i接着观看影片段i+1的概率取0.4～0.6 之间的随机数，观看段i后请求其他数据段的概率服从均匀分布。对于式(8)中的其初始值取0，再通过仿真系统运行一段时间统计给出其均值。算法 1 采用基于热度的缓存算法，即缓存热度大的数据段，当用户点播当前段时开始顺序预取其下一数据段。算法 2 采取本文中所描述的基于数据预取的策略。仿真后分别统计用户点播一段时间发生延迟的数据段总数以及发生延迟数据段的平均延迟。

图 3 为下载带宽分别取 4000 kbps, 6000 kbps以及 8000 kbps 的延迟数据段段数和平均延迟。从图 3(a)可得，在相同时间点，基于预取算法的延迟数据段要少于基于热度算法的延迟数据段，在 4000 kbps 的时候两者发生延迟的数据段段数的差较小，这是因为带宽较小的时候，由于仿真中用户连续点播的概率相对访问其他数据段的概率大，所以采用顺序预取的方式能满足用户连续点播的请求，当带宽较大，预取算法能够更好地利用网络带宽进行数据预取，减小数据发生延迟的概率。带宽增大，顺序预取发生延迟的数据段段数变化不大，而预取算法随着带宽增大其发生延迟的数据段段数明显下降，这说明预取算法更能充分利用网络带宽提高流媒体系统的 QoS。图 3(b)表示预取算法的平均延迟要小于基于热度的算法。

当连续请求概率较大时，用户倾向于顺序播放的点播行为，此时基于热度的算法要好于基于预取的算法，图 4(a)中当连续请求概率取到 0.6～0.8 之间时，基于热度算法发生延迟的数据块要小于预取算法，但图 4(b)显示预取算法数据块的平均延迟较热度算法小。当连续请求概率取到 0.4～0.6 和 0.2～0.4 之间时，预取算法具有更大的优势。随着连续请求概率的减小，基于热度的算法其发生延迟的数据块数增加，延迟的平均值也在增加，这说明基于热度的预取算法不适合于用户随机点播行为明显的视频服务系统。

从仿真结果看，基于数据预取的缓存机制能够减小数据段的延迟，并且更能充分地利用网络带宽提高 QoS，当用户进行 VCR 操作时能够保障用户的点播体验。而基于热度的算法更适用于网络带宽较小以及用户顺序点播行为较明显的系统。记Z=表示系统中的数据段总数。在基于热度的缓存策略中，系统需要记录Z个数据段的访问次数，并计算其热度进行排序。而基于数据预取的缓存策略中，由于涉及 VCR 操作的统计，需要记录2Z个数据，然后计算Z个数据段的β值并排序。可见，基于数据预取的缓存策略需要记录的数据为基于热度的缓存策略的平方，而它们都只需对Z个数值进行排序。

图3 不同下载带宽的延迟数据段段数和平均延迟

图4 连续请求概率对数据段延迟的影响

5 结束语

本文基于预取带宽分配的方法，对流媒体服务系统中的缓存管理问题进行了研究，提出了减小用户点播延迟的优化公式，在给出次优解的基础上给出在线逼近最优解的方法，能够更好地用于具有VCR 功能的流媒体系统。仿真结果说明在 VCR操作特征明显的流媒体系统中，基于预取的缓存策略充分利用系统的带宽以及缓存空间能够有效地降低请求数据段发生延迟的概率，数据段的平均延迟也得到了降低，从而提高用户的点播体验。

[1] Shim J, Scheuermann P, and Vingralek R. Proxy cache algorithms: design, implementation, and performance[J].IEEE Transactions on Knowledge and Data Engineering,1999, 11(4): 549-562.

[2] Liu Jiang-chuan and Xu Jian-liang. Proxy caching for media streaming over the Internet[J]. IEEE Communications Magazine, 2004, 42(8): 88-94.

[3] Liang Wei-fang, Huang Ji-hai, and Huang Jian-hua. A distributed cache management model for P2P VoD system[C].International Conference on Computer Science and Software Engineering, Wuhan, China, Dec. 12-14, 2008: 5-8.

[4] Jiang Wen-bin, Huang Chong, Jin Hai, and Liao Xiao-fei. A new proxy scheme for large-scale P2P VoD system[C].IEEE/IFIP International Conference on Embedded and Ubiquitous Computing, Shanghai, China, Dec. 17-20, 2008:512-518.

[5] Alan TS Ip, Liu Jiang-chuan, and John Chi-shing Lui.COPACC: an architecture of cooperative proxy-client caching system for on-demand media streaming[J]. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(1):70-83.

[6] Wu Kun-lung, Yu P S, and Wolf J L. Segmentation of multimedia streams for proxy caching[J]. IEEE Transactions on Multimedia, 2004, 6(5): 770-780.

[7] Hyung Rai Oh and Hwangjun Song. Metafile-based scalable caching and dynamic replacing algorithms for multiple videos over quality-of-service networks[J]. IEEE Transactions on Multimedia, 2007, 9(7): 1535-1542.

[8] Chen Song-qing, Shen Bo, Susie Wee, and Zhang Xiao-dong.Segment-based streaming media proxy: modeling and optimization[J]. IEEE Transactions on Multimedia, 2006,8(2): 243-256.

[9] Wang J Z and Yu P S. Fragmental proxy caching for streaming multimedia objects[J]. IEEE Transactions on Multimedia, 2007, 9(1): 147-156.

[10] Liu Jie, Liu Yi-na, Cheng Ling-ling, and Tao Jun-cai. Peer caching algorithm based on global segment popularity for P2P VoD system[C]. World Congress on Computer Science and Information Engineering, Los Angeles, USA, Mar.31-Apr. 2, 2009: 140-144.

[11] Tu Wei. Eckehard Steinbach, Muhammad Muhammad, and Li Xiao-ling. Proxy caching for video-on-demand using flexible starting point selection[J]. IEEE Transactions on Multimedia, 2009, 11(4): 716-729.

[12] He Yi-feng, Shen Guo-bin, Xiong Yong-qiang, and Guan Ling.Optimal prefetching scheme in P2P VoD applications with guided seeks[J]. IEEE Transactions on Multimedia, 2009,11(1): 138-151.