流媒體服務系統中一種基于數據預取的緩存策略

巫旭敏 殷保群 黃 靜 郭 東

(中國科學技術大學網絡傳播系統與控制聯合實驗室網絡傳播系統與控制安徽省重點實驗室 合肥 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.