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

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

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

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

　(1)視頻優(yōu)先級(jí)更新算法
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è)客戶對(duì)300個(gè)視頻片段隨機(jī)發(fā)起請(qǐng)求，其中160個(gè)屬于熱門(mén)視頻，100個(gè)屬于經(jīng)典視頻，其余為冷僻視頻?，F(xiàn)服務(wù)器共收到3 000個(gè)針對(duì)不同視頻片段的隨機(jī)請(qǐng)求，考察替換算法的不同對(duì)延遲時(shí)間和緩存命中率的影響。本文選擇了普通的LRU、LFU兩個(gè)算法作為比較，進(jìn)行仿真對(duì)比，實(shí)驗(yàn)結(jié)果如圖2、圖3所示。

　圖2顯示了平均啟動(dòng)延遲相對(duì)于不同緩存大小的變化情況?？梢钥闯觯S著緩存空間的增大，三種算法的啟動(dòng)延遲都呈下降趨勢(shì)，LFU和LRU算法性能都不如PPR，這主要是由于連續(xù)替換使文件最終被全部替換出緩存。而PPR算法預(yù)先在內(nèi)容服務(wù)器的存儲(chǔ)空間內(nèi)按受歡迎程度調(diào)整三種不同視頻片段的比例，使最容易被請(qǐng)求的數(shù)據(jù)具有較高的權(quán)值來(lái)解決這個(gè)問(wèn)題，因此在降低系統(tǒng)平均啟動(dòng)延遲方面比較有優(yōu)勢(shì)。圖3是緩存命中率相對(duì)不同緩存大小的變化情況，三種算法的命中率都呈上升趨勢(shì)，LRU的命中率最低，PPR算法因綜合考慮了視頻片段的受歡迎程度、被請(qǐng)求的強(qiáng)度以及最近被訪問(wèn)的特征，而且根據(jù)實(shí)際情況定期更新受歡迎程度這個(gè)參數(shù)，因此在緩存命中率方面的性能最好。
　本文首先研究分析了基于P2P的流媒體系統(tǒng)，然后對(duì)現(xiàn)有的流媒體緩存算法進(jìn)行了對(duì)比分析，提出了一種高效的流媒體緩存替換策略。實(shí)驗(yàn)證明，本算法在延遲時(shí)間和緩存命中率兩方面性能更好。另外，將文件大小、傳輸成本等其他因素引入本算法，并且做進(jìn)一步的實(shí)驗(yàn)對(duì)比是下一步的工作。
參考文獻(xiàn)
[1] 鄭常熠，王新.P2P視頻點(diǎn)播內(nèi)容分發(fā)策略[J].軟件學(xué)報(bào)，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ù)測(cè)的流媒體代理緩存替換算法[J].計(jì)算機(jī)工程，2007，33(7)：99-100.