巫旭敏 殷保群 黃 靜 郭 東

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

1 引言

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

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

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

2 預取機制

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

圖1 P2P-CDN結構的流媒服務系統(tǒng)

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

3 預取和緩存策略

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

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

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

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

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

通過式(3)可得

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

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

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

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

γ因子為

式(8)可以等價為

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

記iv表示影片v的段i，Dt表示按照式(15)的貪心算法求解出的預取帶寬不為 0 的數(shù)據(jù)段組成的集合，有Dt?Ut,,考慮∈R, iv2t 2?Rt的情況，若用置換緩存中的，記置換后緩存數(shù)據(jù)段，未緩存數(shù)據(jù)段以及預取數(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)當預取一個數(shù)據(jù)段時，分別按照情況 1，情況 2，情況 3 和Rt中索引為 1 的數(shù)據(jù)段進行比較，若索引為 1 的數(shù)據(jù)段不被替換，依次和索引為η, η+1,…的數(shù)據(jù)段進行比較，直到有數(shù)據(jù)段被預取數(shù)據(jù)段替換，記該數(shù)據(jù)段索引為k，有η=k+1，原索引為1,…,k?1的數(shù)據(jù)段索引號依次加 1，緩存的預取的數(shù)據(jù)段索引記為 1，在線繼續(xù)進行步驟(3)。

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

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

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 之間的隨機數(shù)?？蛻舳苏埱蠓?Poisson 分布，請求的時間間隔服從參數(shù)為 60 s 的指數(shù)分布，請求數(shù)取 50000 次?？蛻羰状握埱笫锥蔚母怕嗜?0.7～0.9 之間的隨機數(shù)，首次請求其他數(shù)據(jù)段的概率服從均勻分布，連續(xù)請求即客戶觀看完影片段i接著觀看影片段i+1的概率取0.4～0.6 之間的隨機數(shù)，觀看段i后請求其他數(shù)據(jù)段的概率服從均勻分布。對于式(8)中的其初始值取0，再通過仿真系統(tǒng)運行一段時間統(tǒng)計給出其均值。算法 1 采用基于熱度的緩存算法，即緩存熱度大的數(shù)據(jù)段，當用戶點播當前段時開始順序預取其下一數(shù)據(jù)段。算法 2 采取本文中所描述的基于數(shù)據(jù)預取的策略。仿真后分別統(tǒng)計用戶點播一段時間發(fā)生延遲的數(shù)據(jù)段總數(shù)以及發(fā)生延遲數(shù)據(jù)段的平均延遲。

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

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

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

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

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

5 結束語

本文基于預取帶寬分配的方法，對流媒體服務系統(tǒng)中的緩存管理問題進行了研究，提出了減小用戶點播延遲的優(yōu)化公式，在給出次優(yōu)解的基礎上給出在線逼近最優(yōu)解的方法，能夠更好地用于具有VCR 功能的流媒體系統(tǒng)。仿真結果說明在 VCR操作特征明顯的流媒體系統(tǒng)中，基于預取的緩存策略充分利用系統(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.