流媒體服務(wù)系統(tǒng)中一種基于數(shù)據(jù)預(yù)取的緩存策略

巫旭敏 殷保群 黃 靜 郭 東

(中國科學(xué)技術(shù)大學(xué)網(wǎng)絡(luò)傳播系統(tǒng)與控制聯(lián)合實驗室網(wǎng)絡(luò)傳播系統(tǒng)與控制安徽省重點實驗室 合肥 230027)

1 引言

隨著計算機(jī)網(wǎng)絡(luò)發(fā)展，流媒體服務(wù)系統(tǒng)在應(yīng)用上逐漸成熟。流媒體服務(wù)系統(tǒng)具有視頻點播(Video On Demand, VOD)特性和實時性，一般使用緩存進(jìn)行服務(wù)[1,2]由于存儲容量有限，此類系統(tǒng)通常采用部分緩存[3?12]。這就需要適當(dāng)?shù)牟呗怨芾砭彺?。在?nèi)存管理中 LRU (Least Recently Used) 算法置換最近最少使用的數(shù)據(jù)，但流媒體服務(wù)系統(tǒng)受各節(jié)點間網(wǎng)絡(luò)帶寬限制以及存在大量不同內(nèi)容同時被訪問的現(xiàn)象，所以 LRU 對 QoS 的提高有限?；跓岫鹊牟呗訹5?10]通過緩存熱度高的數(shù)據(jù)減小請求延遲和系統(tǒng)負(fù)載。熱度是指各影片或影片片段被訪問次數(shù)在總數(shù)據(jù)請求次數(shù)中所占的比率。文獻(xiàn)[5]根據(jù)優(yōu)化目標(biāo)把多媒體文件分割成 3 部分分別存儲在緩存、客戶端以及中心服務(wù)器。文獻(xiàn)[6]探討了兩種典型的分段策略：定長分段和指數(shù)分段。定長分段由于各段大小相同易于管理[7?12]。文獻(xiàn)[5,7]將緩存管理歸納為動態(tài)規(guī)劃，并利用貪心算法求解以降低計算復(fù)雜度。文獻(xiàn)[8]針對流媒體系統(tǒng)的命中率、點播延遲以及網(wǎng)絡(luò)抖動等性能進(jìn)行研究，并給出基于多目標(biāo)規(guī)劃的解決方案。文獻(xiàn)[9]進(jìn)一步考慮了影片碼率對存儲策略的影響。

基于熱度的緩存策略通過緩存訪問頻繁的數(shù)據(jù)減少本地節(jié)點向其它節(jié)點請求的數(shù)據(jù)量以及點播延遲。由于熱度是通過統(tǒng)計給出的而未考慮用戶的VCR(Video Cassette Recording)行為[11,12]，當(dāng)用戶隨機(jī)請求影片內(nèi)容時，若請求數(shù)據(jù)段未被緩存，用戶會獲得較大的延遲。在 VOD 系統(tǒng)中 VCR 表示客戶端對節(jié)目的快進(jìn)、快退、暫停以及隨機(jī)訪問等交互操作。文獻(xiàn)[11]采取折衷的策略，若請求數(shù)據(jù)未存儲到本地就選擇緩存中在播放時間上和該數(shù)據(jù)較接近的內(nèi)容進(jìn)行服務(wù)，在減小延遲的同時用戶的請求會得到偏移。文獻(xiàn)[12]針對客戶端的 VCR 行為，研究 P2P 系統(tǒng)中的數(shù)據(jù)預(yù)取以及客戶端的緩存管理。

在流媒體服務(wù)系統(tǒng)中，為了減小服務(wù)延遲以及系統(tǒng)負(fù)載，主要研究思路是利用有限的存儲空間結(jié)合影片熱度提高緩存效率，而實際上系統(tǒng)是通過緩存以及數(shù)據(jù)預(yù)取兩種機(jī)制獲得數(shù)據(jù)提供服務(wù)的，而當(dāng)前大部分研究并沒有考慮到數(shù)據(jù)預(yù)取對緩存效率的影響。本文的創(chuàng)新之處在于結(jié)合數(shù)據(jù)預(yù)取綜合考慮流媒體服務(wù)系統(tǒng)中數(shù)據(jù)的起始延遲以及在服務(wù)過程中抖動所引起的延遲，計算出該延遲的期望，利用貪心算法給出緩存管理的次優(yōu)解，并通過在線優(yōu)化的方法提高緩存效率。

2 預(yù)取機(jī)制

本文采用 P2P-CDN (Content Distribution Network)的混合結(jié)構(gòu)(圖1)，各緩存節(jié)點和中心服務(wù)器形成 P2P 網(wǎng)絡(luò)。影片采用定長分段，中心服務(wù)器存儲所有數(shù)據(jù)，緩存節(jié)點部分存儲。當(dāng)請求到達(dá)時，若本地緩存有客戶請求的數(shù)據(jù)，本地緩存直接進(jìn)行服務(wù)，否則，本地緩存向其它緩存或中心服務(wù)器請求數(shù)據(jù)，再對客戶端提供服務(wù)。通常本地緩存和用戶之間的傳輸延遲小，其數(shù)據(jù)傳輸速率大于影片碼率，而緩存節(jié)點之間以及緩存到中心服務(wù)器之間的傳輸延遲較大，其數(shù)據(jù)傳輸速率小于影片碼率。

圖1 P2P-CDN結(jié)構(gòu)的流媒服務(wù)系統(tǒng)

假設(shè)有N部影片，其中第v部影片有Sv個數(shù)據(jù)段，其碼率恒定為rv，數(shù)據(jù)段播放時間為Tv，大小為Seg，Seg=rv?Tv。若用戶當(dāng)前觀看影片v的第i段，為了減小延遲，本地緩存應(yīng)向其它節(jié)點請求未緩存到本地的數(shù)據(jù)，并決定需要預(yù)取的數(shù)據(jù)段以及進(jìn)行帶寬分配。假設(shè)點播段i時刻為ti，結(jié)束播放時刻為ti+Tv，當(dāng)開始播放段i時，由于上一個預(yù)取周期的數(shù)據(jù)下載可能未完成，需要時間θi下載剩余數(shù)據(jù)，即開始預(yù)取時刻為ti+θi，θi稱為預(yù)取時間間隔。用戶結(jié)束段i播放后請求數(shù)據(jù)段用j表示，用ti+Tv表示用戶請求段j的時刻。tj表示段j開始播放的時刻，則段j的請求時延τj=tj?(ti+Tv),τj≥0。預(yù)取過程如圖 2 所示，播放段i時的預(yù)取從時間ti+θi開始，在tj+θj結(jié)束。

3 預(yù)取和緩存策略

圖2 播放數(shù)據(jù)段i時的預(yù)取過程

記fv(x, y), x, y∈{1,2,…,Sv}，表示用戶觀看影片v從段x跳轉(zhuǎn)到段y的統(tǒng)計次數(shù)，當(dāng)x=y時表示重播當(dāng)前數(shù)據(jù)段，可以估計出用戶觀看影片v時從段x跳轉(zhuǎn)到段y的概率

若已知用戶當(dāng)前點播段α，用戶下一段點播段y的條件概率為

記影片v的所有數(shù)據(jù)段集合為Cv，時刻t影片v存儲在本地的數(shù)據(jù)段集合為，未存儲在本地的數(shù)據(jù)段集合為，Cv=+。若影片v段i未緩存到本地，記為系統(tǒng)中所有節(jié)點對該數(shù)據(jù)段的總上傳帶寬。bd為本地緩存的下載帶寬，滿足bd≥，即本地緩存下載帶寬不小于任一數(shù)據(jù)段的上傳帶寬。為預(yù)取影片v段k的帶寬，≤≤。用戶點播影片v段i后點播段j，若段j未緩存到本地，當(dāng)滿足≥Seg/(T?)時，客戶端沒有延遲。v記=Seg/(Tv?)，若＞會降低下載帶寬利用率，所以≤。當(dāng)用戶結(jié)束影片v段i播放后，此時已知下一個請求的數(shù)據(jù)段為j，若段j未下載完，為了盡快獲得需要的數(shù)據(jù)段本地緩存以系統(tǒng)上傳帶寬進(jìn)行下載。用τ表示客戶端請求數(shù)據(jù)段的延遲，當(dāng)t時刻客戶正在觀看影片v的段i時，下一個數(shù)據(jù)段延遲的期望為[12]

式(3)被分為 3 部分，其中第 1 部分表示沒有緩存和預(yù)取機(jī)制的延遲期望，第 2 部分表示緩存機(jī)制所減小的延遲期望，第 3 部分表示預(yù)取機(jī)制所減小的延遲期望。定義表示已知用戶訪問影片v時請求數(shù)據(jù)段為i的概率，fv(x, y)中約定x=0表示用戶從第y段開始請求影片v，y=0表示用戶點播完段x后結(jié)束影片v的訪問，即x, y∈{0,1,2,…,Sv}，有

通過式(3)可得

記vP表示影片v的熱度，它服從 Zipf 分布[7]，有系統(tǒng)延遲期望為

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

要使用戶請求數(shù)據(jù)段的延遲期望最小，則應(yīng)滿足式(8)

Stor表示本地緩存的大小，即式(11)表示緩存到本地的數(shù)據(jù)段受存儲容量限制。表示影片v(v∈{1,2,…,N})需要緩存的數(shù)據(jù)段以及(k∈)表示影片未緩存的數(shù)據(jù)段的預(yù)取帶寬。fv(x, y)為一段時間內(nèi)統(tǒng)計的結(jié)果，,也可以以通過一段時間的統(tǒng)計給出其均值，系統(tǒng)通過周期性地更改這些參數(shù)的信息進(jìn)行緩存調(diào)整。定義β因子為

γ因子為

式(8)可以等價為

式(14)第 1 項表示緩存減小的延遲期望，第 2 項表示預(yù)取減小的延遲期望?？紤]已知Rtv的情況求第2 項，此時式(14)為有約束的線性規(guī)劃，表示已知存儲的情況下進(jìn)行數(shù)據(jù)預(yù)取，有

記iv表示影片v的段i，Dt表示按照式(15)的貪心算法求解出的預(yù)取帶寬不為 0 的數(shù)據(jù)段組成的集合，有Dt?Ut,,考慮∈R, iv2t 2?Rt的情況，若用置換緩存中的，記置換后緩存數(shù)據(jù)段，未緩存數(shù)據(jù)段以及預(yù)取數(shù)據(jù)段分別為Rt′,Ut′,Dt′，其中滿足?Rt′,∈Rt′, Rt∪Rt′=∪{iv2}=R∪{}，置換緩存前后的請求數(shù)2t′據(jù)段延遲的期望分別為E{τ}和E{τ′}，記ΔE{τ}=E{τ}?E{τ′}，有以下 3 種情況：

(1)選擇β值較大的數(shù)據(jù)段緩存，確定Rt，然后在Ut中選擇γ值較大的數(shù)據(jù)段，確定Dt；

(2)將Rt中的數(shù)據(jù)段按照β值從小到大排列索引，記η=2為一個索引序號的初始值；

(3)當(dāng)預(yù)取一個數(shù)據(jù)段時，分別按照情況 1，情況 2，情況 3 和Rt中索引為 1 的數(shù)據(jù)段進(jìn)行比較，若索引為 1 的數(shù)據(jù)段不被替換，依次和索引為η, η+1,…的數(shù)據(jù)段進(jìn)行比較，直到有數(shù)據(jù)段被預(yù)取數(shù)據(jù)段替換，記該數(shù)據(jù)段索引為k，有η=k+1，原索引為1,…,k?1的數(shù)據(jù)段索引號依次加 1，緩存的預(yù)取的數(shù)據(jù)段索引記為 1，在線繼續(xù)進(jìn)行步驟(3)。

由于替換的過程是按照索引號從小到大查找第1 個滿足替換條件的數(shù)據(jù)段，所以可以確定不能替換索引為 1 的數(shù)據(jù)段則一定不能替換索引為2,…,η?1的數(shù)據(jù)段。情況 2 中由于＞γ′，而γ′又必定大于等于Dt中最小的γ因子，故當(dāng)γ′取Dt中最小的γ值時，令ΔE{τ}=0，此時求的為比較的上限，即當(dāng)?shù)摩乱蜃痈哂诖酥禃r就可以終止比較，段不被存儲在緩存中，類似可以求出情況 3中的比較上限。

在Rt確定的情況下，可以按照式(15)利用貪心算法進(jìn)行求解。式(15)是對一段時間進(jìn)行統(tǒng)計的結(jié)果，而實際預(yù)取需要根據(jù)客戶端實時請求的狀況進(jìn)行預(yù)取帶寬分配，所以實際的預(yù)取策略需要將式(15)中的基于統(tǒng)計的參數(shù)用實時值替換進(jìn)行求解。

4 仿真

考慮 3 部影片，熱度服從 Zipf 分布，影片按熱度從高到低排序，影片v的熱度

仿真取μ=0.271[7], N=3。影片分別有 12， 13和 11 個數(shù)據(jù)段，碼率取為 500 kbps，數(shù)據(jù)段播放時間為 30 s，數(shù)據(jù)段為 15000 kb，緩存容量取為總數(shù)據(jù)量的 1/3 即緩存 12 個數(shù)據(jù)段，下載帶寬bd=6000 kbps ，各影片的上傳帶寬需高于影片的碼率分別取為 500～1500 kbps 之間的隨機(jī)數(shù)?？蛻舳苏埱蠓?Poisson 分布，請求的時間間隔服從參數(shù)為 60 s 的指數(shù)分布，請求數(shù)取 50000 次?？蛻羰状握埱笫锥蔚母怕嗜?0.7～0.9 之間的隨機(jī)數(shù)，首次請求其他數(shù)據(jù)段的概率服從均勻分布，連續(xù)請求即客戶觀看完影片段i接著觀看影片段i+1的概率取0.4～0.6 之間的隨機(jī)數(shù)，觀看段i后請求其他數(shù)據(jù)段的概率服從均勻分布。對于式(8)中的其初始值取0，再通過仿真系統(tǒng)運行一段時間統(tǒng)計給出其均值。算法 1 采用基于熱度的緩存算法，即緩存熱度大的數(shù)據(jù)段，當(dāng)用戶點播當(dāng)前段時開始順序預(yù)取其下一數(shù)據(jù)段。算法 2 采取本文中所描述的基于數(shù)據(jù)預(yù)取的策略。仿真后分別統(tǒng)計用戶點播一段時間發(fā)生延遲的數(shù)據(jù)段總數(shù)以及發(fā)生延遲數(shù)據(jù)段的平均延遲。

圖 3 為下載帶寬分別取 4000 kbps, 6000 kbps以及 8000 kbps 的延遲數(shù)據(jù)段段數(shù)和平均延遲。從圖 3(a)可得，在相同時間點，基于預(yù)取算法的延遲數(shù)據(jù)段要少于基于熱度算法的延遲數(shù)據(jù)段，在 4000 kbps 的時候兩者發(fā)生延遲的數(shù)據(jù)段段數(shù)的差較小，這是因為帶寬較小的時候，由于仿真中用戶連續(xù)點播的概率相對訪問其他數(shù)據(jù)段的概率大，所以采用順序預(yù)取的方式能滿足用戶連續(xù)點播的請求，當(dāng)帶寬較大，預(yù)取算法能夠更好地利用網(wǎng)絡(luò)帶寬進(jìn)行數(shù)據(jù)預(yù)取，減小數(shù)據(jù)發(fā)生延遲的概率。帶寬增大，順序預(yù)取發(fā)生延遲的數(shù)據(jù)段段數(shù)變化不大，而預(yù)取算法隨著帶寬增大其發(fā)生延遲的數(shù)據(jù)段段數(shù)明顯下降，這說明預(yù)取算法更能充分利用網(wǎng)絡(luò)帶寬提高流媒體系統(tǒng)的 QoS。圖 3(b)表示預(yù)取算法的平均延遲要小于基于熱度的算法。

當(dāng)連續(xù)請求概率較大時，用戶傾向于順序播放的點播行為，此時基于熱度的算法要好于基于預(yù)取的算法，圖 4(a)中當(dāng)連續(xù)請求概率取到 0.6～0.8 之間時，基于熱度算法發(fā)生延遲的數(shù)據(jù)塊要小于預(yù)取算法，但圖 4(b)顯示預(yù)取算法數(shù)據(jù)塊的平均延遲較熱度算法小。當(dāng)連續(xù)請求概率取到 0.4～0.6 和 0.2～0.4 之間時，預(yù)取算法具有更大的優(yōu)勢。隨著連續(xù)請求概率的減小，基于熱度的算法其發(fā)生延遲的數(shù)據(jù)塊數(shù)增加，延遲的平均值也在增加，這說明基于熱度的預(yù)取算法不適合于用戶隨機(jī)點播行為明顯的視頻服務(wù)系統(tǒng)。

從仿真結(jié)果看，基于數(shù)據(jù)預(yù)取的緩存機(jī)制能夠減小數(shù)據(jù)段的延遲，并且更能充分地利用網(wǎng)絡(luò)帶寬提高 QoS，當(dāng)用戶進(jìn)行 VCR 操作時能夠保障用戶的點播體驗。而基于熱度的算法更適用于網(wǎng)絡(luò)帶寬較小以及用戶順序點播行為較明顯的系統(tǒng)。記Z=表示系統(tǒng)中的數(shù)據(jù)段總數(shù)。在基于熱度的緩存策略中，系統(tǒng)需要記錄Z個數(shù)據(jù)段的訪問次數(shù)，并計算其熱度進(jìn)行排序。而基于數(shù)據(jù)預(yù)取的緩存策略中，由于涉及 VCR 操作的統(tǒng)計，需要記錄2Z個數(shù)據(jù)，然后計算Z個數(shù)據(jù)段的β值并排序?？梢姡跀?shù)據(jù)預(yù)取的緩存策略需要記錄的數(shù)據(jù)為基于熱度的緩存策略的平方，而它們都只需對Z個數(shù)值進(jìn)行排序。

圖3 不同下載帶寬的延遲數(shù)據(jù)段段數(shù)和平均延遲

圖4 連續(xù)請求概率對數(shù)據(jù)段延遲的影響

5 結(jié)束語

本文基于預(yù)取帶寬分配的方法，對流媒體服務(wù)系統(tǒng)中的緩存管理問題進(jìn)行了研究，提出了減小用戶點播延遲的優(yōu)化公式，在給出次優(yōu)解的基礎(chǔ)上給出在線逼近最優(yōu)解的方法，能夠更好地用于具有VCR 功能的流媒體系統(tǒng)。仿真結(jié)果說明在 VCR操作特征明顯的流媒體系統(tǒng)中，基于預(yù)取的緩存策略充分利用系統(tǒng)的帶寬以及緩存空間能夠有效地降低請求數(shù)據(jù)段發(fā)生延遲的概率，數(shù)據(jù)段的平均延遲也得到了降低，從而提高用戶的點播體驗。

[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.