在基于P2P的流媒體系統中CDN服務器負載優化算法

張 驚

同濟大學軟件學院，上海 201804

1 背景介紹

隨著高清視頻的普及，VOD系統的運行成本越來越高。降低VOD的成本成為一個重要的問題。如Lu[1]所述，VOD系統往往是采用P2P與CDN相結合的方式來減緩系統的成本。

圖1

其中P2P技術可以利用用戶的上傳帶寬，有效地降低了傳輸壓力。但是P2P網絡本身穩定性較差，且Free rider的問題存在使得P2P帶寬的不足，單純的P2P網絡無法滿足VOD系統的帶寬要求。因此，我們需要CDN來進行補充。

CDN則可以解決最后一公里問題，有效降低訪問延遲，并且其帶寬充足。在CS架構下，使用CDN進行輔助傳輸可以在提升用戶體驗的同時，有效地降低傳輸的成本。但是CDN相對于P2P網絡來說價格依然較為昂貴，如何降低CDN的使用成本也成為了一個重要的問題。

在傳統的CDN技術中，CDN服務器是緩存全部的數據。但是視頻的體積較大，在每一個節點中都保存視頻的副本會對CDN的造成較大的存儲壓力。因此，CDN節點的服務器會緩存部分數據，通過相鄰節點的協助共同完成請求的處理。除此以外，我們還可以通過控制CDN服務器內的緩存數據量，動態平衡CDN的運營成本與請求處理的效率。

在這個情況下，如何設計CDN節點服務器所緩存的數據以提升CDN服務器所能處理的請求數量，也即提升CDN節點服務器的緩存命中率成為了一個重要的問題。我們在這里提出了一個基于馬爾科夫鏈的緩存預測算法，以提升緩存命中率的算法。

本文下面將闡述并驗證我們的算法。在第三部分中，我們將闡述我們算法的思想與原理。之后，在第四部分，我們根據原理設計一個優化CDN性能的算法。在第五部分我們將使用仿真實驗驗證的算法。

2 相關工作

在基于P2P的VOD系統中，P2P的傳輸策略是一個重要的課題。P2P的傳輸策略直接決定了P2P網絡的性能，以及與P2P網絡協同工作的CDN所面對的數據請求。

在P2P網絡中，Peer之間的傳輸數據分為三個步驟。首先，是Peer在尚未緩沖的數據中，選擇一部分尚未完成緩沖的數據向其它Peer請求。在Bittorrent等P2P網絡中，傳輸的數據被分成了多個等大的piece。在這里，我們稱呼這個步驟的算法為piece選擇算法。其次，是Peer選好了piece之后，在鄰居Peer當中選擇一個處理該piece請求的Peer。這里，我們稱這一步的算法為Peer選擇算法。最后，接到請求的Peer會決定是否處理這個請求。若Peer不打算處理該請求，則稱之為阻塞算法。有不少文獻在這三個算法上有所研究。

在piece選擇算法方面，傳統的P2P網絡采用的是rarest first算法來選擇piece。Rarest first算法能夠很好地提高P2P網絡的魯棒性，但是卻無法適應流媒體傳輸中邊下邊播的需求。因此，Abdelhalim 等[2]采用了滑動緩沖窗口的設計。Peer會在緩沖播放進度前方一定區域內的劃定一個要緩沖的piece的窗口，并提前進行緩沖。這個窗口會隨著視頻的播放進度前進而前進。

在優化Peer選擇策略的方向中，以往的作者主要從Peer之間的數據量的差異與Peer之間傳輸延遲、物理位置等方面進行考慮。Liang[2]引入了BPB算法。這個算法根據Peer的緩沖進度，為Peer選擇緩沖進度相似的鄰居Peer進行傳輸。Wen[3]則進一步地考慮了Peer的緩沖窗口，將BPB算法與緩沖窗口相結合。這樣就避免了緩沖大量數據的Peer的上傳帶寬無法滿足其他Peer的請求，而緩沖數據量較少的Peer有剩余帶寬無法利用的問題。

Mushtaq[4]，Ahmed[5]，Abdelhalim[6]等 人 在 處 理P2P傳輸視頻的時候，不僅僅考慮Peer緩沖進度的相似性，還綜合了Peer之間的帶寬、距離、RTT等特性進行考慮。Xie[7]等人則設計了P4P的概念，Peer優先選擇處于同一個ISP內部的Peer傳輸數據，這樣一方面可以降低Peer之間的傳輸延遲，另一方面可以降低跨ISP的數據傳輸，降低Peer之間的傳輸對ISP造成的壓力，構成了對ISP友好的P2P網絡。

而在與CDN結合的算法中，Lu[1]則考慮到CDN服務器與Peer的可靠性的區別，給予緩沖窗口中不同的piece不同的優先級。

由于傳輸過程中，Peer會根據其鄰居Peer的特性進行選擇。因此，結構化的網絡由于容易控制受到了在線流媒體系統的歡迎。Ahmed[5]，Zhang[8]采用了多層的結構，根據Peer所能夠提供的數據特性，將Peer劃分至不同的層中，層內的Peer優先互相傳輸。

除此以外，在使用CDN的網絡中，Zhan[2]設計了一套使用CDN+P2P的網絡，并在其中設計了分層的CDN。不同層的CDN之間互相協作，實現了良好的擴展性與性能。

3 P2P網絡

1）概述。

我們的算法要在有限的CDN服務器存儲空間的情況下，盡量保證CDN服務器的對Peer的請求的處理能力，因此我們需要盡可能地提高CDN服務器的緩存的數據的命中率。而CDN服務器的緩存命中率則可以使用下式計算：

其中，IC(inCache)、SRM與I都是長度為T的向量，每一個元素與視頻數據中的一個piece相對應。其中，IC每一個元素均為布爾值，只取0或者1，元素為1表示相應的piece被CDN服務器緩沖了，元素為0表示相應的piece沒有被CDN服務器緩沖。而SRM的元素則是代表CDN服務器接收到的對應piece請求數量。向量I所有的元素都為1。

CDN服務器的存儲空間有限，則IC向量中只有有限個元素為1。因此我們要提高Cache的命中率，應該緩存請求最多的那些piece。而如何構造IC向量，也即在CDN服務器選擇哪些piece進行緩存就是我們算法研究的核心問題。

在以Bittorrent為代表的P2P軟件當中，為了方便將數據交由不同的Peer進行傳輸。原始的數據被劃分為了多個等大或近似等大的piece。在我們的傳輸視頻的算法中，我們假設每個Piece所包含的幀數量是一致的。我們按照Peer當前視頻所播放的幀所屬的piece，將Peer分為T+1個狀態，其中最后一個狀態是指Peer完成播放的狀態。我們使用一個狀態空間為[1，T+1]的離散隨機過程來表示Peer在播放過程中的狀態轉移。使用隨機變量X表示Peer當前播放的幀所在的Piece。

2）P2P的數據傳輸算法。

在Peer播放視頻過程中，Peer的請求分別由CDN與P2P網絡處理。由前邊所述，Peer在請求數據過程中進行了Piece選擇算法，Peer選擇算法與阻塞算法三個步驟。

由于流媒體系統要求做到邊下邊播，因此下載需要做到順序下載，因此Piece選擇算法會依賴于Peer當前的播放進度。如Sheu[9]等所做的，在基于P2P的傳輸視頻的流媒體系統中，Peer在piece選擇過程中，不僅僅緩沖即將解碼的piece，而是會在當前播放進度前建立一個滑動緩沖窗口，選擇這個窗口內部的piece進行預緩沖，滑動緩沖窗口的情況如下圖所示。

圖2

在上圖中，黑色部分代表了已經完成解碼的piece，藍色的是當前正在解碼的piece，而綠色的則是在緩沖窗口內的piece。

緩沖窗口的使用是為了避免帶寬波動帶來的播放卡頓。我們設這個窗口的長度為w。piece選擇算法要為piece選擇一個鄰居Peer或者CDN服務器處理請求。在Lu[1]和張勇[12]等人設計的算法當中，Peer選擇算法要根據piece在播放前所剩余的緩沖時間為其選擇不同質量的Peer進行處理。Piece的剩余緩沖時間可以使用變量ΔT，如下圖所示。

實踐教學是高校教學環節的重要組成部分，它的獨特功能和作用，是其它教育環節無法替代的，高等學校實踐教學是在教師指導下，學生在特定的環境中,通過自身努力完成教育目標的教學過程。通過實踐環節教學，可以加深對課程理論教學內容的理解；給學生提供實踐與理論相結合的空間，提高學生對知識學習興趣，增強學生自主學習的積極性；提高學生的實踐動手能力；啟發學生高昂的創新意識。安徽理工大學電氣工程及其自動化專業實踐教學內容主要包含有課程實驗、認識實習、生產實習、課程設計、實訓、畢業設計與畢業實習、創新能力拓展項目等。

圖3

由上圖可以得知，ΔT只取決于Piece在滑動緩沖窗口當中的次序，與Piece在整個視頻數據中的次序無關。而由此，我們可以使用一個T*(T+1)的矩陣PS來表示Peer的選擇結果。矩陣的第i行表示X=i的情況下，Peer向CDN服務器請求每一個數據段的概率。而我們可以得知PS矩陣如下所示。

圖4

在Lu[1]和張勇[12]等人設計的算法當中，Peer根據ΔT的值，會將數據交由不同的Peer處理或者CDN處理。ΔT越小，則在該piece的數據的緩沖時間越少，為了保證視頻播放不發生卡頓，其對傳輸的質量要求越高。因此ΔT越小，向CDN請求該piece的概率越高。因此，在圖4當中下式成立。

3）視頻播放中的隨機過程。

正常情況下，用戶在觀看視頻的過程中，視頻的播放進度是按照時間順序連續變化的。而網絡等原因導致的播放卡頓，其概率取決于終端與服務器之間網絡鏈路的丟包率、帶寬擁塞等網絡環境。而這些網絡問題在視頻播放的時間內變化的可能性相對較低，我們可以將該概率視為定值。而用戶的VCR操作則是基于視頻內容的，也就是指取決于當前進度所播放的視頻內容。因此，客戶端的視頻進度的變化只取決于當前的播放進度，其無后效性滿足馬爾科夫鏈的成立條件。由此我們可以將客戶端視頻播放的隨機過程看作是馬爾可夫過程。

該馬爾科夫過程的狀態空間為[1，T+1]，其中最后一個狀態表示視頻播放完成。而播放完成的節點不會向其它狀態跳轉，該狀態是一個吸收壁。我們可以用一個長度為T+1的向量p表示Peer的狀態分布。而該馬爾科夫鏈的初始狀態是Peer初次進入在線視頻網絡是所處的狀態。在線視頻網絡中，終端加入網絡時，其視頻的播放進度必然是處于視頻的第一個piece中。因此，Peer的初始情況下的狀態概率分布p必然是{1，0，0...0}。

我們可以使用向量p計算一個Peer向CDN請求數據段的概率分布，如下式：

在上式中，向量pr是一個長度為T的向量，其第i個元素表示Peer向CDN服務器請求第i個piece的概率。而CDN服務器所接受到的數據段請求可以用下式計算：

我們設一個Peer的播放進度狀態轉移矩陣為ST(State Transmit)。該矩陣ST為的矩陣。則我們可以得到如下的狀態轉移矩陣。在下面的矩陣當中，元素pi，j代表該Peer從第i個狀態轉移到第j個狀態的概率。

圖5

在這里，我們設一個Peer在k時刻的狀態X的概率分布為p(k)，則有下式：

在播放過程中，Peer可能正常播放視頻，也可能進行VCR操作，亦或者因為網絡的原因而發生卡頓。其中，視頻正常播放是高概率性事件，而VCR以及網絡原因的視頻卡頓是低概率事件。在這里，我們不考慮屬于低概率事件的VCR操作與網絡狀況所引起的Peer狀態變化。則可以得到的Peer的ST矩陣如下式所示：

圖6

由于Peer的狀態分布p的初始狀態的概率分布是{1， 0， 0...0}，以及圖（5）的矩陣的特性，Peer的狀態X在發生狀態變化時遵循下式：

則一個Peer在時刻t請求第i個數據段的概率bi滿足如下式：

上式中，bi不為0的條件是確保第i個數據段在Peer的緩沖窗口內。在整個P2P系統中，CDN服務器所收到的第i個數據段的請求數量可以用下式計算：

其中，nj(t)是t時刻X為j的Peer的數量。我們可以知道nj(t)的特性如下式所示：

則bi的計算公式可以做如下的變換：

由上式，我們可以根據t時刻的第i個數據段請求量，預測t+1時刻的第i+1個數據段請求量。我們可以繼續簡化上式。

而由ps的性質，我們可以知道：

因此，bi(t)遠遠大于psT。我們可以在上式中忽略psT，其式子可以改為下式：

由這個式子，我們可以使用當前時刻的數據請求量來估算下一個時刻除第一個數據段以外的數據段的請求量。

而對于第一個數據段的請求量預測取決于對新加入的Peer數量的預測。在傳統的Bittorrent以及Chang[11]所設計的視頻傳輸系統中，Peer加入網絡開始播放之前，首先都需要進行包括向Tracker服務器注冊在內的初始化過程。我們可以通過統計處在初始化過程中的Peer數量來預測下一個時刻X為1的Piece的數量。

4 緩存替換算法

我們的替換算法的目的是盡可能提高緩存命中率，因此，我們需要預測未來的請求數量最多的piece。由前面的式子所述，我們可以通過當前時間段內每一個piece的請求數量，估算下一個時刻的piece請求分布。我們設CDN服務器能夠給我們的算法的存儲空間可以存儲N個piece。我們對第1到第T-1個piece的請求量進行排序，然后選擇請求量最多的N個Piece。我們設這些Piece的序號組成一個集合C(t)。則我們可以得到集合S(t+1)滿足下式。

則S(t+1)就是我們預測得到的下一個時刻CDN所接受的請求最多的數據段的集合。而CDN在下個時刻緩存這些數據段就可以有效地提升緩存的命中率。

我們的算法只需要記錄當前階段的piece請求分布就可以。而Peer的特性與我們的算法無關。我們算法不必了解整個P2P網絡的全局信息，因此不需要額外的控制信息，不會對傳輸性能造成額外的負擔。而且我們的算法也不需要Peer端有額外的適配邏輯，可以與Peer的各種傳輸策相適應，有良好的可擴展性。

我們算法的計算過程分為統計piece數量與piece請求排序兩部分。其中統計piece數量這一部分的計算量是與請求數量NR有關的，其時間復雜度是O(NR)的，而空間復雜度則是O(T)的。而排序算法則是與視頻的piece數量有關。同一個視頻副本，其piece分割是不變的，因此排序的運算復雜度是恒定的O(Tlog(T))。因此，算法對CDN服務器的運算壓力并不大。

5 實驗設計

在使用CDN服務器輔助傳輸數據的P2P網絡中，系統會有一個中心服務器，保存完整的數據請求，并將視頻數據分發給各個CDN服務器。而各個CDN服務器則緩存視頻數據，并將數據分發給各個終端。CDN服務器是分布于不同的ISP不同的物理地區中，以降低數據在ISP之間進行長途傳輸所產生的延遲以及對ISP網絡所產生的壓力。

我們在仿真實驗中，將Peer分成了多個組，每一個組作為一個獨立的ISP。每個組內的Peer互相傳輸的延遲較低，而組之間的傳輸延遲較高。每個組內有一個CDN服務器。除此以外，我們還設計一個在線媒體的中央服務器。中央服務器存儲了完整的視頻副本。整個P2P網絡中的Peer在向服務器發出請求的時候，首先向自己所在的ISP的CDN服務器發出請求。若CDN服務器沒有緩存請求所要求的piece，則Peer轉向中央服務器發出請求。

作為對比，我們將我們的緩存替換算法與經典的LRU等算法做比較，統計不同的算法下緩存的命中率。

在實驗過程中，Peer加入P2P網絡采用了泊松分布，該泊松分布的。而Peer在播放完成后到離開P2P網絡的時間則采用了指數分布來模擬。而Peer所能緩沖的增強層數量則是平均分布。實驗中傳輸的SVC視頻分為4層。每一種Peer的上行帶寬則設定為下行帶寬的一半。

我們的模擬環境是在NS3模擬器的基礎上運行。Peer之間的傳輸協議則是由流行的Bittorrent協議修改而來。

在這里，請求成功地在CDN服務器緩存中找到所需要的數據的概率被稱為緩存命中率。緩存命中率體現了我們的算法對緩存的預測的準確率。

我們在CDN服務器上存儲了整個視頻副本的一定比例的數據。我們分別試驗了存儲30%、50%、70%的情況的結果。實驗結果如圖所示。在圖中，棕色的線是我們的算法的結果。而藍色的線則是LRU算法的運算結果。圖中綠色的線則是代表了存儲率的標準線。

圖7

圖8

圖9

從圖中可以看到，隨著存儲率的降低，由于覆蓋的數據段的減少，LRU算法越來越無法體現其預測的效果，命中率越來越差，逐漸低于標準線。而我們的算法則依然能夠保持較好的命中率，多數情況下都能夠比標準線要好。

這是因為LRU算法在替換的時候，根據其所存儲的數據的請求記錄來決定移除的數據。而隨著存儲空間的減少，LRU所存儲的數據令越來越少，其所能夠依據的請求記錄也越來越少。因此，其性能會隨著存儲空間的減少而下降。

而我們的算法則是從全局出發，根據CDN接收到的整體的請求分布情況來決定數據的交換。因此，存儲空間的大小并不會對性能造成影響。

因此，我們的算法相對于傳統的緩存替換算法LRU有更好的預測性能。

[1]Lu Z， Gao X， Huang S， etal. Scalable and reliable live streaming service through coordinating CDN and P2P[C]. Proceedings of the International Conference on Parallel and Distributed Systems -ICPADS， 2011.

[2]Zi’ao Zhan， Xu Q. A Stochastic Push Scheme of Streaming Media Partial Content Based on P2P[J].Journal of Networks， 2012， 7(10).

[3]Liang C， Fu Z， Liu Y， etal. Incentivized Peer-Assisted Streaming for On-Demand Services[J].IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS， 2010， 21(9):1354-1367.

[4]Wen Z， Liu N， Yeung K L， etal. Closest Playback-Point First: A New Peer Selection Algorithm for P2P VoD Systems [C]. Global Telecommunications Conference (GLOBECOM 2011)，2011.

[5]Mushtaq M， Ahmed T. Smooth Video Delivery for SVC based Media Streaming over P2P Networks[C].2008 5th IEEE Consumer Communications and Networking Conference，2008.

[6] Ahmed T， Mushtaq， M. P2P Object-based adaptivE Multimedia Streaming[J]. Journal of Network and Systems Management， 2007， 15(3):289-310.

[7]Abdelhalim A，Ahmed T，WalidKhaled H，etal.Using Bittorrent and SVC for efficient video sharing and streaming[C]. Computers and Communications(ISCC)，2012.

[8]Xie H，Yang Y R，Krishnamurthy A，etal.P4p:provider portal for applications[C].Proceedings of the ACM SIGCOMM 2008 conference on Data communication，2008.

[9]Zhang G， Yuan C. Self-Adaptive Peer-to-Peer Streaming for Heterogeneous Networks Using Scalable Video Coding[C]. International Conference on Communication Technology Proceedings， 2010.

[10]Sheu T， Wang Y. Dynamic Layer Adjustments for SVC Segments in P2P Streaming Networks [C]. Computer Symposium (ICS)， 2010 International， 2010.

[11]李斐.基于網絡編碼的P2P分層流媒體傳輸架構研究[D].電子科技大學， 2012.

[12]Chang H，Shih Y，Ya-Yueh Shih，Yuan-Wei Lin.CloudPP:A Novel Cloud-based P2P Live Video Streaming Platform with SVC technology[C].2012 8th International Conference on Computing Technology and Information Management，2012.

[13]張勇，何娜娜，夏海輪.移動P2P流媒體中的數據調度算法[J].吉林大學學報（信息科學版），2010，28（6）.