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

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

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

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

　(1)視頻優先級更新算法
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 實驗結果與討論
　為證實前文提出的PPR算法要優于常用的緩存替換算法，本文進行了仿真實驗，實驗環境為VC++6.0。假設客戶對300個視頻片段隨機發起請求，其中160個屬于熱門視頻，100個屬于經典視頻，其余為冷僻視頻。現服務器共收到3 000個針對不同視頻片段的隨機請求，考察替換算法的不同對延遲時間和緩存命中率的影響。本文選擇了普通的LRU、LFU兩個算法作為比較，進行仿真對比，實驗結果如圖2、圖3所示。

　圖2顯示了平均啟動延遲相對于不同緩存大小的變化情況。可以看出，隨著緩存空間的增大，三種算法的啟動延遲都呈下降趨勢，LFU和LRU算法性能都不如PPR，這主要是由于連續替換使文件最終被全部替換出緩存。而PPR算法預先在內容服務器的存儲空間內按受歡迎程度調整三種不同視頻片段的比例，使最容易被請求的數據具有較高的權值來解決這個問題，因此在降低系統平均啟動延遲方面比較有優勢。圖3是緩存命中率相對不同緩存大小的變化情況，三種算法的命中率都呈上升趨勢，LRU的命中率最低，PPR算法因綜合考慮了視頻片段的受歡迎程度、被請求的強度以及最近被訪問的特征，而且根據實際情況定期更新受歡迎程度這個參數，因此在緩存命中率方面的性能最好。
　本文首先研究分析了基于P2P的流媒體系統，然后對現有的流媒體緩存算法進行了對比分析，提出了一種高效的流媒體緩存替換策略。實驗證明，本算法在延遲時間和緩存命中率兩方面性能更好。另外，將文件大小、傳輸成本等其他因素引入本算法，并且做進一步的實驗對比是下一步的工作。
參考文獻
[1] 鄭常熠，王新.P2P視頻點播內容分發策略[J].軟件學報，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] 楊傳棟，余鎮危.基于流行度預測的流媒體代理緩存替換算法[J].計算機工程，2007，33(7)：99-100.