基于CDN－P2P流媒體直播系統(tǒng)方案設計實現

鄧 達，呂智慧

（復旦大學 計算機科學技術學院，上海200433）

0 引 言

多媒體內容在當今互聯網中得到大量發(fā)展，流媒體已成為目前因特網應用的最快增長點。流媒體的特點是數據量大、傳輸持續(xù)時間長，并且由于其直觀性較強，對延遲、抖動、丟包率、帶寬等QoS（quality of service）指標要求也就非常嚴格，在當前的因特網上構建大規(guī)模的性價比高的流媒體系統(tǒng)是一個具有挑戰(zhàn)性的工作，并具有一定的商業(yè)意義。

如何緩解網絡擁塞，提高用戶獲取信息的速度，成為困擾企業(yè)和服務商的一大難題。目前，互聯網上的內容分發(fā)傳遞主流技術有CDN和P2P。這兩種技術各有各的優(yōu)勢，也有著一些不足。CDN技術成本價高，而且實現復雜，擴展能力相應較弱。P2P則由于客戶節(jié)點加入離開的動態(tài)不確定性，導致在網絡友好性、可靠性和管理性上有較大欠缺。

CDN和P2P技術盡管有著各自的不足，但兩者基本上是可以互補的。融合這兩種技術，構建一個統(tǒng)一的內容分發(fā)系統(tǒng)方案，將會對大型流媒體直播、高清電視、巨型文件下載等高帶寬需求業(yè)務的進一步普及提供廣闊的發(fā)展空間。通過P2P擴展CDN的容量，同時CDN可以克服P2P的動態(tài)性、引導P2P內容分發(fā)實現對ISP、主干網的友好性，形成一種更加完善的內容分發(fā)應用模式。

1 相關研究

有研究者早在2006年就提出了融合CDN和P2P的技術方案［1］。其提出在CDN基礎上疊加P2P來擴展分發(fā)能力，并深入分析了CDN和P2P融合的成本，采用了不同的客戶端貢獻策略進行對比，最終通過模擬實驗來證明融合的有效性。其思想更多的是如何在CDN邊緣服務器上利用P2P技術傳輸流媒體文件，以更好的降低CDN中心資源服務器的壓力。

2007年以來，SIGCOMM、ACM MM、INFOCOM等著名國際會議陸續(xù)出現了多篇研究P2P內容分發(fā)的論文。大多數論文重點關注如何更好的提供P2P大規(guī)模分發(fā)的能力的同時，保持較低的延遲和較高的穩(wěn)定性。其中也有少部分論文研究的是P2P內容分發(fā)對網絡友好性影響。文獻［2］首次大規(guī)模的部署了結合P2P和CDN技術的LiveSky，對結合技術的樹形結構進行了理論推導，得出擴展因子的統(tǒng)計理論公式，另外還測得了詳細的實驗數據。

2 系統(tǒng)架構

CDN－P2P混合架構總體來說可以分為3種結構。其一是CDN邊緣服務器之間使用P2P結構。其二是CDN各邊緣服務器與其服務的peer節(jié)點組成一個自治區(qū)域，各自治區(qū)域的peer節(jié)點采用P2P架構。其三是前述兩種結構的綜合［2］。

本文主要采用第二種結構，在CDN各邊緣服務器的P2P網絡結構采用mesh和tree的混合P2P結構。采用一層的tree結構，用于保證網絡的可控性和節(jié)點的異構性；接下來的網絡用純mesh結構組織，如圖1所示。

圖1 系統(tǒng)拓撲結構

放大層就是一層樹結構的節(jié)點，其中每一個節(jié)點稱為偽CDN節(jié)點。它們必須滿足上載帶寬高于媒體碼率，只有這樣才能起到放大CDN帶寬的效果。另外，它們直接向CDN邊緣服務器拉數據，服務鄰居除了CDN服務器之外，沒有更多的；而且他們直接互不成鄰居。其余的Peer組織成mesh結構，維護各自的鄰居列表。注意，CDN不是它們的直接鄰居，它們并不直接向CDN發(fā)起塊請求（除了特殊情況，比如剛啟動或者請求緊急數據塊的情況）。

3 CDN－P2P混合分發(fā)方案詳細設計

本文在此詳細討論了peer節(jié)點加入后，各節(jié)點和CDN服務器所運行的算法。

3.1 節(jié)點加入算法

放大層的基本想法就是對CDN的上載能力進行放大，因此，在放大層中的偽CDN節(jié)點的上傳帶寬必須大于碼流速率，否則就起不到放大作用。不過，在放大層初始建立，如果加入節(jié)點的能力比較弱，沒有任何節(jié)點的上載速率超過碼流播放速率，這樣很有可能導致一開始加入的節(jié)點不能得到任何數據（因為非偽CDN節(jié)點不能向CDN直接請求非緊急的數據塊）。為了避免上述情況的發(fā)生，并且由于在節(jié)點加入CDN網絡之后，我們仍然會運行偽CDN置換算法，因此在節(jié)點加入過程中，我們放棄檢驗其上載帶寬是否會高于碼流速率這一限制。

3.1.1 放大層的初始建立

起初，CDN節(jié)點設置放大層節(jié)點個數為N，這一數據是根據CDN的帶寬和碼流速率而確定的。每當節(jié)點加入，且當前CDN的偽CDN節(jié)點數＜N，那么就將新加入的節(jié)點設為偽CDN節(jié)點，與CDN直接成為鄰居，并且給他分配其余相應的鄰居。由于偽CDN節(jié)點直接向CDN節(jié)點請求數據，因此其作為鄰居的作用更多的是向其鄰居節(jié)點傳送數據，沒有必要與同為放大層的任何偽CDN節(jié)點成為鄰居。

3.1.2 偽CDN節(jié)點更換算法

隨著節(jié)點的陸續(xù)加入，更多更強的節(jié)點會進入CDN的網絡。原先在放大層中的偽CDN節(jié)點會變得不是網絡中最強的節(jié)點，因此，更換算法勢在必行。更換算法的執(zhí)行是以時間驅動的，即各個偽CDN節(jié)點每隔一段時間會運行一次，用來尋找更強的節(jié)點。這里的強并不僅僅是指上載帶寬的強，而是多方面的綜合，可以包括網絡情況，節(jié)點本身性能情況，節(jié)點的地理位置，節(jié)點存在網絡中的時間等眾多因素。

本系統(tǒng)中，我們考慮兩點：節(jié)點的上載帶寬和穩(wěn)定性。假設某節(jié)目時長為L，當前時間為t，節(jié)點在網絡中已經經過時間為s，那么穩(wěn)定性計算公式SI為［3］

假設節(jié)點上載帶寬為U b／s，碼流速率為R b／s，那么計算其強弱的指標P為

式中：K——調整帶寬和穩(wěn)定性之間強弱的參數。可以看出，這一公式是為了使得節(jié)點的上載帶寬和在網絡中存在的時間融合成一個強度的值，用來表示節(jié)點的強弱。

具體的節(jié)點更換算法是：對于每一個偽CDN節(jié)點a，其遍歷自己的鄰居，如果發(fā)現鄰居里面最強的節(jié)點b比自己更強，那么就讓b替換自己偽CDN節(jié)點的地位，主動與CDN斷開連接，而b則與CDN成為鄰居。注意到，如果b不僅與偽CDN節(jié)點a是鄰居，而是與另一些偽CDN節(jié)點也為鄰居，那么將b置換為偽CDN節(jié)點的同時，會破壞放大層所滿足的基本條件：偽CDN節(jié)點之間不能是鄰居！因此，在對換之后，我們必須再次遍歷b，將其與可能的偽CDN鄰居關系解除。

3.1.3 偽CDN狀態(tài)監(jiān)控

此算法也是以時間間隔運行的。其目的是向CDN節(jié)點上傳特定的數據包，以上報自己當前的狀態(tài)。包括已用上傳帶寬，剩余上傳帶寬等。這樣CDN節(jié)點就會對其下的偽CDN節(jié)點的狀態(tài)有相應的估計，對于將來節(jié)點加入時，給與其緩沖的節(jié)點可以更好的計算。當然，為了保證所有的偽CDN節(jié)點之間互不成為鄰居，我們在這里也讓節(jié)點自己查找自己所有的鄰居，如果有鄰居是偽CDN節(jié)點，那么就斷開鄰居關系。

3.1.4 偽CDN節(jié)點的離開

偽CDN節(jié)點的離開，就是從其已有的鄰居里面，選擇最強的鄰居替換自己，即，再次執(zhí)行更換算法。這樣，即使一個強節(jié)點離開了，也會用相應的比較強的節(jié)點來替換自己，就不會對網絡產生非常大的影響了。這種方法也很好的保證了網絡的穩(wěn)定性。

3.2 節(jié)點加入緩沖算法

當某個節(jié)點加入直播網絡，CDN節(jié)點根據自己，放大層偽CDN節(jié)點和當前加入節(jié)點的狀況估算出節(jié)點的最快可能播放時間，然后進行緩沖。

具體地講，如果當前節(jié)點加入后，直接從當前時刻開始進行緩沖，假設進過t之后緩沖完成，那么播放至少要等t之后才開始，也就是說，當前加入節(jié)點至少已經有了t秒的時延。如果可以從加入時刻開始，直接緩沖t后的數據，就可以大幅減少延遲的發(fā)生。在此，問題的難點在于，精確地估算出緩沖完成所需要的時間非常難。但，如果結合CDN的穩(wěn)定性，實際上可以對緩沖時間有粗略估計。

根據當前CDN和偽CDN的帶寬情況，選擇適當的節(jié)點，以速率v，直接推送給加入節(jié)點buffer長度為α的數據。這樣，至少需要t＝α·len（buffer）／v的時間才可以緩沖完。在此同時，我們通過P2P方式，讓當前節(jié)點向其鄰居節(jié)點拉數據來填充其后1－α的buffer（如果是偽CDN節(jié)點的緩沖，直接向CDN所要數據塊）。

我們假定估算緩沖時間為t。顯然，t之后，buffer的前α已經完成了，后1－α是經過P2P方法來獲取的，所以并不能保證。但是，后1－α部分并不一定需要完全填滿。引入另一個系數β，如果后1－α的buffer有β已經填滿，那么就直接開始播放。否則會再等待一段時間進行緩沖，然后再播放。具體流程圖如圖2所示。

3.3 塊調度算法

圖2 節(jié)點加入緩沖算法

塊調度算法就是對于某一個節(jié)點，向其鄰居節(jié)點或者CDN節(jié)點提出哪些數據塊的申請，并且以什么樣的結構進行交換的算法。塊的結構是用BufferMap的思路，把緩沖區(qū)分成多塊，最基本的請求單位就是塊，并且請求的結構是一個隊列，越靠前的請求塊，其優(yōu)先級越高。在帶寬有限的情況下，隊列后部的請求塊可能會延時或者會被放棄傳送。本系統(tǒng)中，塊調度算法分為兩個階段，第一個階段是緩沖階段，使用隨機調度算法結合之前提到的緩沖算法，第二階段是緩沖完成后的塊調度算法。

第一部分緩沖時的塊調度算法直接采用隨機算法，即，對于給定的鄰居列表，從有本節(jié)點所需要的塊的鄰居中隨機選取一個，發(fā)起塊請求。采用隨機算法的原因是節(jié)點剛剛加入網絡，對網絡中其它節(jié)點信息獲知量很少，而且，這一過程僅僅在節(jié)點剛進入網絡進行緩沖中使用，因此不適合，也不必要復雜的算法。

第二部分的塊調度算法，采用鄰居評分和劃分塊優(yōu)先級的方法來調度［4］。

對于緩沖區(qū)，我們劃分為4個部分，分別占有1／8，1／8，1／2，1／4，叫做緊急區(qū)1，緊急區(qū)2，普通區(qū)和稀缺塊區(qū)。各個區(qū)域的塊的優(yōu)先級從高到低依次為緊急區(qū)1，緊急區(qū)2，稀缺塊區(qū)和普通區(qū)。其中只有當緊急區(qū)1的數據塊還未填滿的時候，節(jié)點可以向CDN直接索要緊急數據塊。對于其余部分的塊，只能向鄰居發(fā)起請求。

對于節(jié)點評分機制，是用來評估各個鄰居對于本節(jié)點的傳輸性能，以此區(qū)別各個鄰居的貢獻能力。最終向各個鄰居請求的塊的隊列會基于各個鄰居的評分的基礎之上，分數越高的鄰居，向其請求的數據塊就會越多，而且越有可能是緊急區(qū)2的數據塊。

3.4 CDN服務器的加入控制算法

3.4.1 節(jié)點加入條件

即使是CDN－P2P混合分發(fā)系統(tǒng)，為了保證直播系統(tǒng)的質量等要求，我們也不能任意的加入無數的節(jié)點。弱節(jié)點超過一定的限度，整個網絡資源就會相當貧乏。可以想象，如果加入的節(jié)點的上載帶寬小于碼流帶寬，那么加入越多的節(jié)點，整個網絡的帶寬資源就會越多的消耗，直到無法再提供最低限度的服務。因此，我們必須設置準入條件，以確保直播系統(tǒng)的穩(wěn)定和質量保證。

在本系統(tǒng)中，我們可以得到的保證的上載帶寬有CDN節(jié)點和放大層中的各個位CDN節(jié)點。因此，我們基于這些參數給出節(jié)點加入的限制條件。

先考慮CDN上載帶寬U，CDN的帶寬分為3部分，一部分用于給各個偽CDN提供最原始的視頻數據U1，另一部分提供各個節(jié)點的緊急請求數據包U2，還有一部分是提供新加入節(jié)點的緩沖U3。而偽CDN節(jié)點，帶寬V，基本就是給各個鄰居提供的上載帶寬V1，或者提供一些加入節(jié)點的緩沖數據V2。假設碼流速率為R，那么準入條件為U＋∑V≥U1＋U2×α＋∑V1＋（U3＋∑V2）×β＋R式中：α、β——一定的參數，一般比1稍大，用來估計緊急請求和緩沖帶寬在節(jié)點加后的上界。如果當前CDN網絡滿足上述條件，那么允許新節(jié)點加入，否則，可以將需要加入的節(jié)點引渡到其它CDN邊緣服務器。

3.4.2 節(jié)點加入算法

隨機算法，每當有節(jié)點加入，則直接對其運行節(jié)點加入算法：首先判斷是否滿足準入條件，是否可為偽CDN節(jié)點，分配給其緩沖的節(jié)點，給其分配鄰居，等等。如果在某一時間，有非常多的節(jié)點迅速的加入網絡，形成flash crowd的情況，那么，CDN包括偽CDN節(jié)點很有可能會面臨巨大的壓力，以至于它們無法給每個加入的節(jié)點進行緩沖和數據交換，這樣就會對整個網絡有很大的影響。

為了適當的減少上述問題的危害性，我們在系統(tǒng)中做了適當的改進。我們并不是每次對加入的節(jié)點都進行逐一處理，我們加入一個節(jié)點加入隊列。也就是說，當節(jié)點需要加入網絡時，我們先將其進入加入隊列中，然后每隔特定的時間t（實驗中為0.1s）或者隊列滿了的時候，讓CDN對整個隊列進行處理。

處理的方式是將他們組織成小型樹狀結構［5］，根據他們的上傳帶寬進行從大到小排列。然后從隊列的兩頭進行配對。從隊列頭中取出上傳帶寬最大的節(jié)點a，算出其速率是碼流的K倍，接著相應的從隊列的尾部取出K個節(jié)點，讓a和這K個節(jié)點組成一棵樹，a給其下的K個節(jié)點進行緩沖，而CDN則分配給a進行緩沖。這樣，CDN網絡相當于只用了一道緩沖碼流，就直接服務了K＋1個節(jié)點。繼續(xù)這樣的操作，直到隊列為空為止。

4 實驗設計及結果分析

根據本實驗的參數設置，如果不用P2P，而使用純CDN結構，實驗節(jié)點是不能全部得到服務的。因此，我們僅將基于中心結構的P2P隨機算法系統(tǒng)與本論文的系統(tǒng)進行對比試驗。

Zhang Meng的p2pstrmsim是一個基于消息的C＋＋實現的P2P模擬程序，其中模擬了節(jié)點的地理信息，加入方式，各個節(jié)點的傳輸帶寬等基本信息，也監(jiān)控了包括節(jié)點啟動時延，播放時延，播放質量等關鍵指標。本實驗采用p2pstrmsim程序為基礎，并且在處理節(jié)點消息隊列中，加入我們特定的算法進行模擬。

算法3.1.2、3.1.3以及3.3都是基于時間的算法，每隔一個固定的時間執(zhí)行。其余算法是基于事件的，例如節(jié)點加入，節(jié)點離開或觸發(fā)相應的算法執(zhí)行。實驗的基本參數如下：

Peer節(jié)點分為3種不同的節(jié)點：上傳帶寬：512kb／s，384kb／s，128kb／s，下載帶寬為1000kb／s，512kb／s，384 kb／s比例為0.1，0.5和0.4。每個peer默認最多有15個鄰居。仿真時間為600s，碼流大小為300kb／s，緩沖區(qū)長度為20s。每隔一秒交換一次buffermap。

4.1 驗證加入緩沖算法效果

本實驗重點對比兩種算法在緩沖時間上的區(qū)別，體現出修改后的算法的優(yōu)越性。實驗使用2個CDN服務器，帶寬為40M，放大層節(jié)點個數為90個。500個節(jié)點模擬。節(jié)點采用節(jié)勻速加入退出策略，在前80%的時間勻速加入，后50%的時間有20%的節(jié)點勻速離開。可以計算，放大比例為

圖3是緩沖時間的累積分布圖（cdf圖）。縱坐標是節(jié)點的比例，橫坐標是緩沖的時間。原先的隨機算法，在緩沖時，由于直接采用固定20s的時間進行緩沖，因此，所有的啟動延遲都是20s。而從此圖可以看出，改進算法的節(jié)點緩沖平均時間為16s左右。可見，改進算法確實有一定的效果。

圖3 啟動延遲對比

圖4，顯示了兩種算法的質量參數（質量度用已經播放的數據塊除以應該播放的數據塊來表示）。對比兩種曲線可以看出，兩種算法的質量參數幾乎相等，不過在放大層建立的初期，質量都有部分下降。并且改進算法的下降比隨機算法提前，從這點也可以看出，改進算法減少緩沖時間的效果是在保證播放質量的前提下實現的。

圖4 質量對比圖1

關于在放大層建立的初期會導致質量的下降，這是由于我們的算法導致的。設想，我們節(jié)點的緩沖算法除了CDN會推給節(jié)點一部分數據，另一部分是需要節(jié)點向Peer之間互傳獲取的。而一開始，節(jié)點十分少，互傳幾乎得不到數據，因此會致使節(jié)點再次等待緩沖。一旦緩沖結束，由于節(jié)點稀少，啟動的節(jié)點只能向CDN請求緊急數據包，這會大大加重CDN的負載，因此導致質量下降。

4.2 驗證flash crowd情況下的效果

此實驗重點對比兩種算法在flash crowd情況下的區(qū)別，體現出修改后的算法的優(yōu)越性。本實驗使用3個CDN服務器，帶寬為50M，放大層節(jié)點個數為90個。1000個節(jié)點模擬。節(jié)點一開始速加入100個節(jié)點。在0.4＊MAX＿SIM＿DURATION（大約240s）時刻，在0.05＊MAX＿SIM＿DURATION（大約30s）的持續(xù)時間內將所有的剩余節(jié)點加入。最后勻速有20%節(jié)點退出。

圖5是在線節(jié)點數與時間的關系圖。節(jié)點在240s到280s之間，從103個節(jié)點直接增加至1000個節(jié)點，從而測試在flash crowd情況下，系統(tǒng)的具體反映情況。

圖5 在線節(jié)點數目

圖6，顯示了兩種算法的質量參數。在放大層的建立之初，改進算法和隨機算法的質量差不多。在加入節(jié)點出現flash crowd時，改進算法比之隨機算法有更好的質量度。

除了初始的放大層建立初期質量的下降外，質量曲線顯示，共有兩處下降。第一處在240s過后一點。這里的下降是因為此時正好處于flash crowd的情況，大量節(jié)點加入網絡導致整體質量的下降。注意，改進算法質量的下降要比原始算法小，并且有些許提前。考慮我們的緩沖算法，比完全沒有緩沖會有較好的啟動延時，因此對于flash crowd的反應也會相應較早

圖6 質量對比圖2

第二處的質量下降大約出現在430s多。此時顯示整個網絡已經趨于穩(wěn)定。在大量節(jié)點進入播放階段，會對網絡造成一定的影響，播放的質量會有所下降，此處并沒有過多節(jié)點的加入和離開，質量仍然不斷下降到達最低谷。通過實驗分析，在240s時，大量節(jié)點急促加入的過程中，整個系統(tǒng)會因為所需要的緩沖流量過多而無法支持所有節(jié)點的充分緩沖，某些節(jié)點在等待緩沖時，并沒有真正的緩沖完成而被迫播放。這些節(jié)點往往會在播放了一段時間后，因為緩沖區(qū)不滿而停下繼續(xù)緩沖，產生不穩(wěn)定性，最終導致了質量度的下降。這就是在430s后質量到達最低谷的原因。不過，即使如此，改進算法在flash crowd情況下，也比隨機算法有更好的質量保證。

5 結束語

本文將CDN與P2P技術相結合，應用于流媒體視頻直播系統(tǒng)。采用二層樹形結構與mesh結構相混合的P2P架構，詳細介紹了偽CDN節(jié)點的選取規(guī)則以及維護方式。本文針對直播的特殊性，利用估測緩沖完成時間來提高啟動播放時延，并且針對瞬時擁塞，給出了小樹結構的節(jié)點加入緩沖算法，減小P2P的動態(tài)性帶來的影響，使整個系統(tǒng)更加穩(wěn)定。最后通過仿真模擬實驗，將系統(tǒng)改進算法與不使用本文所提算法進行對比，驗證算法的有效性。

［1］Xu Dongyan，Sunil Suresh Kulkarni，Catherine Rosenberg，et al.Analysis of a CDN－P2Phybrid architecture for cost－effective streaming media distribution［J］.Computer Science Multimedia Systems，2006，11（4）：383－399.DOI：10.1007／s00530－006－0015－3.

［2］Hao Yin.Design and deployment of a hybrid CDN－P2Psystem for live video streaming：experiences with LiveSky［C］／／Beijing，China：Proc of the 17th ACM International Conference on Multimedia，2009：19－24.

［3］Wang Feng，Liu Jiangchuan，Xiong Yongqiang.Stable peers：Existence，importance，and application in peer－to－peer live video streaming［C］／／Phoenix，AZ：Proc of INFOCOM，2008：1364－1372.

［4］HUANG Yi.The dynamic communication architecture design of live streaming system based on CDN－P2P［D］.Shanghai：Fudan University，2011（in Chinese）.［黃翼.面向流媒體直播的CDN和P2P動態(tài)交互傳輸架構的設計［D］.上海：復旦大學，2011.］

［5］HUANG Sijia.The design of a live streaming system based on CDN and tree based P2Phybrid architecture［D］.Shanghai：Fudan University，2011（in Chinese）.［黃思嘉.基于CDN和P2P樹網混合的流媒體直播系統(tǒng)設計［D］.上海：復旦大學，2011.］

［6］LU Zhihui，WU Jie，Fu Weiming.Towards a novel web services standard－supported CDN－P2Ploosely－coupled hybrid and management model［C］／／FL：IEEE International Conference on Services Computing，2010：297－304.

［7］Cho S，Cho J，Shin S－J.Playback latency reduction for internet live video services in CDN－P2Phybrid architecture［C］／／Cape Town，South Africa：IEEE International Conference on Communications，2011：1－5.

［8］Jiang Hai，Li Jun，Li Zhongcheng，et al.Efficient large－scale content distribution with combination of CDN and P2Pnetworks［J］.International Journal of Hybrid Information Technology，2009，2（2）：13－22.

［9］Mansy A.Analysis of adaptive streaming for hybrid CDN／P2P live video systems［C］／／19th IEEE International of Network Protocols，2011：276－285.

［10］Thinh Nguyen Kim，Seil Jeon，Younghan Kim.A CDN－P2P hybrid architecture with content／location awareness for live streaming service networks［C］／／IEEE 15th International Symposium on Consumer Electronics，2011：438－441.