摘  要： 針對視頻節(jié)目受歡迎程度不同的特性，提出一種P2P流媒體系統(tǒng)中的緩存替換算法，通過將系統(tǒng)中的全部視頻片段分類，為其賦予不同的優(yōu)先級，并周期性地更新該值，同時考慮視頻片段被訪問次數(shù)和最近被訪問的情況，使得被替換出存儲空間的片段更加合理。實(shí)驗(yàn)表明，該算法能提高緩存命中率及系統(tǒng)的啟動延時，性能較優(yōu)。
關(guān)鍵詞： 流媒體；P2P；緩存替換算法；流行度

　隨著互聯(lián)網(wǎng)的飛速發(fā)展，以它為載體的應(yīng)用越來越多樣化，傳統(tǒng)應(yīng)用已經(jīng)不能充分滿足人們的需要，對通過Internet提供更多寬帶增值業(yè)務(wù)的需求已顯得越來越迫切。數(shù)字多媒體技術(shù)的日趨成熟以及網(wǎng)絡(luò)傳輸帶寬的增加使得在互聯(lián)網(wǎng)上開展如視頻會議、IPTV(Internet Protocol Television)、VoD(Video on Demand)等各種多媒體應(yīng)用逐步成為現(xiàn)實(shí)。傳統(tǒng)多媒體的播放方式是用戶事先將視頻文件下載至本地再進(jìn)行觀看，而采用流媒體技術(shù)只需在播放時將部分內(nèi)容緩存，邊傳送邊播放，節(jié)省了下載等待時間和存儲空間。但流媒體文件的體積一般都十分龐大，且對延遲、抖動、包丟失率等較敏感，會造成用戶可感知的服務(wù)質(zhì)量降低。采用高效的流媒體緩存替換策略可以改善這種狀況。首先，從流媒體技術(shù)邊下載邊播放的特點(diǎn)可以看出，使用緩存技術(shù)可彌補(bǔ)網(wǎng)絡(luò)中的延遲和抖動對視頻播放帶來的不良影響；其次從全局看，緩存可緩解對骨干網(wǎng)絡(luò)帶寬以及中心服務(wù)器的壓力；另外，不管是代理服務(wù)器還是客戶端的存儲空間都是有限的，為了充分地利用存儲空間，保障視頻文件的流暢播放，必須依賴于高效的緩存替換策略。

1 基于P2P的流媒體系統(tǒng)
　近年來，P2P(Peer to Peer)技術(shù)在文件共享和網(wǎng)絡(luò)電話業(yè)務(wù)中被成功運(yùn)用，采用P2P技術(shù)構(gòu)建流媒體分發(fā)系統(tǒng)成為了比較理想的候選方案。其主要原因在于，通過這種方式不僅可以獲得較好的系統(tǒng)性能和可擴(kuò)展性，而且不必改變現(xiàn)有網(wǎng)絡(luò)結(jié)構(gòu)。最開始P2P與流媒體技術(shù)結(jié)合的成果是P2P實(shí)時節(jié)目直播系統(tǒng)，從傳統(tǒng)的樹型分發(fā)(如ZIGZAG)到基于Gossip的純Mesh分發(fā)(如Coolstreaming和Anysee[1])。在P2P方式下，網(wǎng)絡(luò)中的每個對等節(jié)點(diǎn)(Peer)同時是服務(wù)提供者和服務(wù)享用者，它們互相協(xié)作，各自貢獻(xiàn)自己的一部分資源。然而在P2P網(wǎng)絡(luò)中，節(jié)點(diǎn)存儲能力、節(jié)點(diǎn)間網(wǎng)絡(luò)鏈接帶寬的有限性決定了數(shù)據(jù)無法以穩(wěn)定的速率連續(xù)地在節(jié)點(diǎn)間傳輸，而在流媒體應(yīng)用中，連續(xù)且穩(wěn)定地傳輸流數(shù)據(jù)是保證視頻播放質(zhì)量必不可少的條件，網(wǎng)絡(luò)的異構(gòu)性、不可預(yù)測的網(wǎng)絡(luò)抖動使得這一條件更難以實(shí)現(xiàn)。因此，必須采取有效的措施確保一定程度的數(shù)據(jù)冗余，以利于為節(jié)點(diǎn)播放器提供連續(xù)的流數(shù)據(jù)。流媒體緩存技術(shù)通過緩存熱門視頻節(jié)目的部分或全部數(shù)據(jù)，為后來的用戶請求提供服務(wù)，減少了啟動延遲，降低了骨干網(wǎng)絡(luò)和流媒體服務(wù)器負(fù)載，而成為了近年來網(wǎng)絡(luò)應(yīng)用的研究熱點(diǎn)。
2 現(xiàn)有流媒體緩存策略
　目前存在的緩存策略主要有兩類：一類是考慮不同的分段方法來提高資源緩存的效率；另一類是基于資源被訪問時的不同特征來設(shè)計。
　分段方法的討論集中在如何將大容量的流媒體對象劃分成合適的片段，提高網(wǎng)絡(luò)傳輸?shù)男剩熬Y緩存算法[2]有效減小了客戶端啟動延時；批處理補(bǔ)丁結(jié)合前綴緩存思想重點(diǎn)在于提高命中率，減少用戶的等待時間；在此基礎(chǔ)上提出的最優(yōu)批處理補(bǔ)丁預(yù)先緩存算法[3](BPP)通過補(bǔ)丁的預(yù)先緩存，減少了用戶的等待時間，節(jié)省了主干網(wǎng)絡(luò)的帶寬；指數(shù)增長的分段(Exponential Segmentation)策略[4]能夠快速替換片段來適應(yīng)緩存對象的訪問模式的變化；基于自適應(yīng)和滯后[5](Adaptive and Lazy)的分段方法根據(jù)用戶對于不同的流媒體對象的訪問頻率和訪問長度來自適應(yīng)地改變分段長度和選取刪除段。SCU算法[6]旨在提高緩存的前綴字節(jié)命中率，減少訪問延遲，降低流媒體播放時的網(wǎng)絡(luò)傳輸成本。
　在資源被訪問的各種特征中，最有影響的當(dāng)數(shù)資源訪問的局部性和資源的被訪問次數(shù)。LRU(Least Recently Used)和LFU(Least Frequency Used)算法就是分別考慮訪問近期性和訪問頻率的實(shí)現(xiàn)方式[7]，但LFU存在緩存污染問題，LRU存在長環(huán)模式問題。同時，這兩種算法還容易出現(xiàn)同一媒體對象的連續(xù)替換問題，導(dǎo)致緩存內(nèi)容被完全釋放的概率增大，請求命中率下降和響應(yīng)延遲增加。LRU-K[8]和LCB-K[9]考慮了對象最近K次被引用的信息，將訪問頻率和訪問的最近性綜合到價值函數(shù)的設(shè)計之中，具有較好的性能。EELRU[10]通過偵測循環(huán)訪問模式的長度，以自適應(yīng)選擇替換出的對象。還有的是采用將前綴和后綴分開緩存并采用不同替換策略的方式，但這樣增加了替換算法開銷及存儲空間管理的復(fù)雜程度。
衡量一個緩存替換策略的主要指標(biāo)一般有以下幾項(xiàng)：
　(1)延時時間(Latency Time)：從用戶發(fā)出一個訪問請求開始，到用戶在接收到該請求后響應(yīng)為止，所經(jīng)歷的時間為延時時間，包括啟動時和播放過程中的延時。延時時間越短，網(wǎng)絡(luò)的服務(wù)質(zhì)量越好，同時這也是衡量骨干網(wǎng)能力的一項(xiàng)重要依據(jù)。
　(2)服務(wù)器負(fù)載(Server Load)：由于用戶向服務(wù)器發(fā)出視頻節(jié)目請求以及服務(wù)器向Peer節(jié)點(diǎn)傳送數(shù)據(jù)產(chǎn)生的負(fù)載。在Peer處部署緩存并應(yīng)用緩存替換策略，通過節(jié)點(diǎn)之間的協(xié)作可有效降低服務(wù)器的負(fù)載。
　(3)緩存命中率(Cache Hit Rate)：緩存命中的次數(shù)與用戶總的請求數(shù)之比，若用Sr表示Peer接收到的用戶總請求次數(shù)，Sh表示緩存命中次數(shù)，則緩存命中率CHR=Sh/Sr，命中率越高，系統(tǒng)緩存的效果越好。
　(4)空間利用率(Space Use Rate)：已經(jīng)使用的緩存空間大小與緩存總空間的比值，用Da表示已經(jīng)使用的空間大小，Dw表示緩存總空間的大小，則空間的利用率SUR=Da/Dw，該值越高，緩存的效率越高。
3 緩存替換算法設(shè)計
　經(jīng)過對已有緩存算法的研究發(fā)現(xiàn)，這些算法都是將所有的視頻文件片段一視同仁地處理，即根據(jù)視頻片段的某些參數(shù)來進(jìn)行替換操作。例如，基于流行度的緩存替換算法[11]，流行度參數(shù)主要由片段的被訪問次數(shù)決定，假如一個具有高熱度的片段在剛進(jìn)入系統(tǒng)的一段時間內(nèi)被訪問次數(shù)不多，就很有可能被替換出去，這樣就造成對熱門視頻片段的錯誤操作，從而降低了系統(tǒng)的工作效率，也降低了用戶的服務(wù)體驗(yàn)。為此，本文提出一種稱為PPR(Priority Popularity Recency)的緩存替換算法。該算法同時考慮屬于不同類型視頻的片段的優(yōu)先級、片段的流行度、片段的最近一次命中時間這三個因素，尤其是片段的優(yōu)先級的引入。首先，從視頻的受歡迎程度這個角度對它們進(jìn)行分類，即在中心服務(wù)器向下分發(fā)視頻時，預(yù)先給三種不同的視頻賦予不同的優(yōu)先級，使得最受歡迎的視頻節(jié)目在總的系統(tǒng)中保留的數(shù)目最多。然后對存儲空間里已有視頻片段的流行度進(jìn)行統(tǒng)計后比較，使得“過期”的片段盡可能地被替換出去。而對于剛剛進(jìn)入網(wǎng)絡(luò)并且具有高流行度潛力的新視頻片段，為了避免由于其被請求的次數(shù)還未來得及累積到一定數(shù)值就被替換出存儲空間，所以將片段的最近一次命中時間這個因素考慮進(jìn)來。
3.1 PPR緩存替換算法參數(shù)描述
3.1.1 視頻的片段的優(yōu)先級
　假設(shè)系統(tǒng)中共有M個不同的視頻節(jié)目Progi(M≥i≥1)，每個節(jié)目又被分為Ni個片段ProgSegi，j(Ni≥j≥1)，該算法以視頻的某一個片段為處理對象，視頻的播放速率為540 kb/s，每次處理60 s大約4 MB的數(shù)據(jù)。
在本文的探討中將視頻分為以下三種：
　(1)熱門視頻：網(wǎng)絡(luò)中剛剛更新的視頻資源，一般是在電視臺或電影院發(fā)布資源之后的一段時間里面，在網(wǎng)上同時需要觀看該類資源的用戶很多，如最新電影或最新一期熱門節(jié)目等。
　(2)經(jīng)典視頻：網(wǎng)絡(luò)中那些一直都會有用戶點(diǎn)播觀看的經(jīng)久不衰的視頻節(jié)目，這類資源的特點(diǎn)是用戶對它的請求保持在一個相對比較穩(wěn)定的水平上，即一直會被訪問，但是并發(fā)訪問量不像訪問熱門資源那么高，如一些經(jīng)典影片或網(wǎng)絡(luò)課程等。
　(3)冷僻視頻：除去以上兩類視頻，還有一類被訪問的總次數(shù)較低，并且并發(fā)人數(shù)也很少的視頻，如很久以前的節(jié)目或是受眾比較少的資源等。
給此三類視頻節(jié)目賦予不同的優(yōu)先級Priorityi，對應(yīng)某類視頻的片段優(yōu)先級表示為Priorityi，j。熱門視頻的優(yōu)先級最高，其次是經(jīng)典視頻，冷僻視頻的優(yōu)先級最低。需要強(qiáng)調(diào)的一點(diǎn)是，上述三種視頻之間沒有絕對的界限，根據(jù)對節(jié)點(diǎn)儲存空間內(nèi)的視頻進(jìn)行記錄統(tǒng)計，它們之間存在著互相轉(zhuǎn)化的可能。例如，熱門視頻會逐漸變成經(jīng)典視頻或冷僻視頻，冷僻視頻也有轉(zhuǎn)化成熱門視頻的可能性。因此，本算法不僅僅是簡單利用優(yōu)先級Priorityi，j，而是每隔時間T對存儲空間里所有片段的優(yōu)先級進(jìn)行更新(T值通過試驗(yàn)來確定)。

3.2 PPR緩存替換算法結(jié)構(gòu)描述
　PPR緩存替換算法由視頻優(yōu)先級更新算法和片段替換算法兩個算法構(gòu)成，整個算法流程如圖1所示。視頻優(yōu)先級更新算法是為了確定片段所屬視頻的優(yōu)先級。由于視頻的受歡迎程度是一個相對較大的時間粒度，而片段的權(quán)值是在一個更小的時間粒度上計算，如果將視頻受歡迎程度放到刪除每一個片段上計算，則會增加不必要的開銷。片段替換算法則是當(dāng)存儲空間不足以存放下一個新片段時，在片段優(yōu)先級確定的基礎(chǔ)上再對其進(jìn)行評估從而選出淘汰的片段，完成替換。兩個算法的偽代碼如下。

　(1)視頻優(yōu)先級更新算法
for everytime
  for each in Cache
Record(i)=Segments arrival sequence of Programme(i) in certain time
Priorityi，j=f(Record(i))
　return
return
(2)視頻片段替換算法
 if NewSegi，j not in Cache
 {
  if R1>Segi，j
 {
 cache the NewSegi，j
 return
 }
  calculate the value(φi，j(t))of all old segments
　select the minimum value(φi，j(t))and delete it
}
if R2<SegSizei，j
continue
else cache the  NewSegi，j
 return
4 實(shí)驗(yàn)結(jié)果與討論
　為證實(shí)前文提出的PPR算法要優(yōu)于常用的緩存替換算法，本文進(jìn)行了仿真實(shí)驗(yàn)，實(shí)驗(yàn)環(huán)境為VC++6.0。假設(shè)客戶對300個視頻片段隨機(jī)發(fā)起請求，其中160個屬于熱門視頻，100個屬于經(jīng)典視頻，其余為冷僻視頻?，F(xiàn)服務(wù)器共收到3 000個針對不同視頻片段的隨機(jī)請求，考察替換算法的不同對延遲時間和緩存命中率的影響。本文選擇了普通的LRU、LFU兩個算法作為比較，進(jìn)行仿真對比，實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

　圖2顯示了平均啟動延遲相對于不同緩存大小的變化情況?？梢钥闯觯S著緩存空間的增大，三種算法的啟動延遲都呈下降趨勢，LFU和LRU算法性能都不如PPR，這主要是由于連續(xù)替換使文件最終被全部替換出緩存。而PPR算法預(yù)先在內(nèi)容服務(wù)器的存儲空間內(nèi)按受歡迎程度調(diào)整三種不同視頻片段的比例，使最容易被請求的數(shù)據(jù)具有較高的權(quán)值來解決這個問題，因此在降低系統(tǒng)平均啟動延遲方面比較有優(yōu)勢。圖3是緩存命中率相對不同緩存大小的變化情況，三種算法的命中率都呈上升趨勢，LRU的命中率最低，PPR算法因綜合考慮了視頻片段的受歡迎程度、被請求的強(qiáng)度以及最近被訪問的特征，而且根據(jù)實(shí)際情況定期更新受歡迎程度這個參數(shù)，因此在緩存命中率方面的性能最好。
　本文首先研究分析了基于P2P的流媒體系統(tǒng)，然后對現(xiàn)有的流媒體緩存算法進(jìn)行了對比分析，提出了一種高效的流媒體緩存替換策略。實(shí)驗(yàn)證明，本算法在延遲時間和緩存命中率兩方面性能更好。另外，將文件大小、傳輸成本等其他因素引入本算法，并且做進(jìn)一步的實(shí)驗(yàn)對比是下一步的工作。
參考文獻(xiàn)
[1] 鄭常熠，王新.P2P視頻點(diǎn)播內(nèi)容分發(fā)策略[J].軟件學(xué)報，2007，18(11)：2942-2954.
[2] SEN S， REXFORD J， TOWS L. Proxy prefix caching for multimedia streams[C]. Proceedings of IEEE Infocom， New York， 1999： 1310-1319.
[3] RIZZO L， VICISANO L. Replacement policies for a proxy cache [J]. IEEE/ACM Transactions on Networking， 2000，8(2)：158-170.
[4] WU K L， YU P S， WOLF J L. Segment-based proxy caching of multimedia streams[C]. Proceedings of the 10th International Conference on World Wide Web， WWW′01， Hongkong， China， 2001：56-60.
[5] CHEN S， SHEN B， WEE S， et al. Adaptive and lazy segmentation based proxy caching for streaming media delivery[C]. Proceedings of ACN NOSSDAV. Monterey， CA， 2003：694-703.
[6] LIM E， PARK S H， HONG H O， et al. A proxy caching scheme for continuous media streams on the Internet[C]. The 15th International Conference on Information Networking. Beppu City， Oita， Japan， 2001：720-725.
[7] KRISHNAMURTY B， REXFORD J. Web protocol sand practice： HTTP/1.1， networking protocols， caching and traffic measurement[M]. Addison Wesley Longrnan Publishing Co.， 2001.
[8] O′Neil E J， O′Neil P E， WEIKUM G. An optimality proof of the LRU-K page replacement algorithm[J]. Journal of the ACM， 1999， 46 (1)：92-112.
[9] OTOO E， OLKEN F， SHOSHANI A. Disk cache replacement algorithm for storage resource managers in data grids[C]. Proceedings of IEEE / ACM Conference on Supercomputing， Baltimore， Maryland， USA， 2002：1-15.
[10] SMARAGDAKIS Y， KAPLAN S， WILSON P. The EELRU adaptive replacement algorithm[J]. Elsevier Science Performance Evaluation， 2003，53(2)：93-123.
[11] 楊傳棟，余鎮(zhèn)危.基于流行度預(yù)測的流媒體代理緩存替換算法[J].計算機(jī)工程，2007，33(7)：99-100.