P2P覆蓋網(wǎng)絡中流媒體分布式優(yōu)化方案

1、P2P覆蓋網(wǎng)絡中流媒體分布式優(yōu)化方案譯文原文：Distributed Optimization of Media Flows inPeer-to-Peer Overlay Networks論文原作者：Antonios Argyriou&Jacob ChakareskiP2P打破了傳統(tǒng)Client/Server(C/S)模式，在網(wǎng)絡中，每一個節(jié)點的地位都是對等的。每一個節(jié)點既充當服務器為其他節(jié)點提供服務，同時也享用其他節(jié)點提供的服務。P2P網(wǎng)絡非中心化的特點，即網(wǎng)絡中的資源和服務分散在所有結點上，信息的傳輸和服務的實現(xiàn)都直接在結點之間進行，可以無需中間環(huán)節(jié)和服務器的介入，避免了可能的瓶頸。帶來了

2、其在可擴展性、健壯性等方面的優(yōu)勢。P2P網(wǎng)絡中隨著用戶的增加，其資源和服務能力也在同步的擴充，因此理論上其可擴展性幾乎可以認為是無限的。同時在P2P網(wǎng)絡中將計算任務或存儲資料分布到所有結點上。利用其中閑置的計算能力或存儲空間，達到高性能計算和海量存儲的目的。通過利用網(wǎng)絡中的大量空閑資源，可以用更低的成本提供更高的計算和存儲能力。同時，因為資源分布在多個節(jié)點，更好的實現(xiàn)了整個網(wǎng)絡的負載均衡。與傳統(tǒng)的系統(tǒng)相比起來，P2P技術具有巨大的優(yōu)勢，它已經(jīng)被廣泛的應用到例如文件內容共享（例如，電驢，比特精靈等），協(xié)同處理，即時通訊等等方面。隨著在線視頻產(chǎn)業(yè)在互聯(lián)網(wǎng)上的飛速發(fā)展，基于P2P的流媒體應用，例如P

3、Plive，PPStream，QQlive等應用在互聯(lián)網(wǎng)上迅速流行開來。在大規(guī)模的P2P視頻點播和直播服務中還有很多可以突破的技術，本文提出一個分布式的流媒體優(yōu)化方案。這里考慮的問題是，在非結構化的P2P覆蓋網(wǎng)絡中最優(yōu)的流媒體失真問題。通過公式將這個問題表示為一個分布式的速率分配問題，并且用一個傳統(tǒng)的分解技術來解決這個問題，以便全網(wǎng)設備的媒體失真率達到最小化。通過對等端之間的信息交互來保證本地速率分配代價的時效性。流媒體數(shù)據(jù)包同樣附帶著包含受解碼器影響和自身大小影響的率失真信息。這個做法帶來的好處就是對等端可以不用再計算最優(yōu)速度分配而轉換為簡單的允許轉發(fā)或丟棄行為的輕量級實現(xiàn)。而且，模擬結果也

4、表明，當我們的流媒體算法中加入媒體數(shù)據(jù)包的精確的率失真特性描述時，將會帶來顯著的質量效益。P2P網(wǎng)絡已經(jīng)成為一種替代IP組播實現(xiàn)以點對多的媒體分發(fā)的解決方案。P2P網(wǎng)絡從根本上說是一個由協(xié)作端之間的單一會話組成的覆蓋網(wǎng)絡。對等端的主要任務就是扮演一個代理的角色，緩存一部分接收到數(shù)據(jù)包，這些數(shù)據(jù)包將會被轉發(fā)到網(wǎng)絡中其他的對等端。這種交付模式的一個主要好處就是它提供了一種可擴展的方式來分發(fā)點播或直播的視頻給大量的接受者，而系統(tǒng)的容量將會隨著對等端的增多而增大。大規(guī)模的點播和直播的P2P多媒體流取得了巨大的成功。這個系統(tǒng)的性能曲線主要取決于覆蓋結構和維持算法.或許影響P2P網(wǎng)絡最重要的問題就是P2P

5、覆蓋網(wǎng)絡的結構受到參與端行為的動態(tài)影響。因此，如果覆蓋網(wǎng)絡被組織成一棵樹，那么帶寬的波動和失效的對等端如果靠近根節(jié)點的話將會造成緩沖區(qū)向下溢出，而影響到大規(guī)模的下游節(jié)點。為了減輕這些問題帶來的影響，一個基于網(wǎng)格的P2P網(wǎng)絡覆蓋協(xié)議允許無需來自常規(guī)網(wǎng)絡覆蓋結構里的明確支持的對等端之間的數(shù)據(jù)傳播。通過這個方法，一個對等端可以一邊接受數(shù)據(jù)一邊隨機的選取目標端的一個子集來推送接收到的媒體數(shù)據(jù)包。如圖，我們簡單的假設媒體在網(wǎng)絡中的分發(fā)情況，節(jié)點P4必須最大限度的同時保證轉發(fā)給客戶端C1和C2的數(shù)據(jù)包的質量。這個傳輸過程優(yōu)于現(xiàn)行的數(shù)據(jù)傳輸在于它提供一個高度可靠的數(shù)據(jù)分發(fā)。然而我們不能簡單將這種交付方法用于

6、點播的媒體流，因為它可能無法實時交付。另外一個缺點就是允許相鄰對等端直接的傳輸，對于高帶寬視頻流應用程序來說，大量的數(shù)據(jù)副本將會造成一個很大的開支。盡管有大量對P2P流媒體的研究，但是大部分已有的工程都將焦點放在不同的應用層流交付模型上的性能上。盡管這個很重要，但是通訊模型和覆蓋層維護算法已經(jīng)被獨立的開發(fā)和研究而且已經(jīng)推廣開來。說得更具體一點就是，現(xiàn)在缺少一個考慮到個別媒體數(shù)據(jù)包對整體P2P流媒體影響的通用框架。在本文中，我們在這個方向上邁出一小步，應用一個采用率失真優(yōu)化的數(shù)據(jù)包調度和獨立于覆蓋層結構的媒體流的分布式流媒體優(yōu)化方法。率失真優(yōu)化流算法已經(jīng)被成功的應用到更加高端的應用中，因此他們提

7、供了另一個在像P2P覆蓋網(wǎng)絡這樣更加普遍的通訊模型中研究多媒體分發(fā)的方案。在主流的P2P流媒體項目中，流媒體僅僅考慮到類似最大可接受的延遲，最小帶寬，以及最小的丟包率這樣一個抽象的服務質量需求。然而有明顯影響的單個媒體數(shù)據(jù)包解碼的質量卻沒有被考慮進來。不同的媒體數(shù)據(jù)包對他們的解碼率失真性能有著不同的重要的作用。直到最近，才有一些研究工作關注到這個方向。例如，在參考文獻6里面，作者同樣考慮到了在P2P工程中的率失真優(yōu)化流，但是他們關注先進的以及描述多樣的編碼方案。我們相信考慮到不同媒體數(shù)據(jù)包的率失真的特點是一個很重要的概念，因為它允許在不同的覆蓋拓撲結構上對媒體流的質量進行細粒度的評估。為了避免

8、我們的計劃被限制在特定的拓撲結構中，我們假設一個基于網(wǎng)格的P2P傳輸模型，參與的對等端來自隨機的連接定向的網(wǎng)格（即非結構化的網(wǎng)絡覆蓋）。兩個對等端之間的連接是單向的，這就意味著數(shù)據(jù)是從父節(jié)點交付給子節(jié)點的。每一個端在網(wǎng)絡覆蓋結構中都有多個父節(jié)點和子節(jié)點。我們假設一個對等端可以從一個中央服務器獲取當前活躍節(jié)點的列表。說具體一點就是，這個引導服務器維護一個所有參與的對等端的列表并且為新參與的對等端提供所有參與者的子集。每一個參與的對等端都要為在同一個層中轉發(fā)的媒體流提供一個向前的子集。把這種覆蓋拓撲結構建模為一個有向無環(huán)圖G=N,A，其中N表示所有的覆蓋層節(jié)點，A表示連接對等端的的連接方向。我們定

9、義M為目前正在交付的媒體流數(shù)，同樣，定義Am為對等端之間用來轉發(fā)媒體流m的連接方向。圖1顯示了一個簡單的有兩個正在轉發(fā)的媒體流的拓撲結構。我們在數(shù)據(jù)包的級別來考慮媒體流，因為如果沒被解碼的話不同的媒體數(shù)據(jù)包對視頻的質量有不同的影響。我們定義一個來自媒體流的媒體數(shù)據(jù)包 m 的索引為km。類似相關的工程,率失真信息被包含在它的數(shù)據(jù)包里，包括它的大小R（km）和對重建視頻時造成失真（被定義為D(km)）。在實際中的D(km)，是率失真的MSE（均方差）增長的總和，如果數(shù)據(jù)包沒有在規(guī)定的最后期限內交付的話將會影響到視頻流。如圖，每一個對等端同時為傳入的流媒體維持多個緩存區(qū)域，媒體數(shù)據(jù)包的轉發(fā)取決于速率

10、分配算法。我們提出這個方法的目的是為每個被對等端轉發(fā)的媒體流計算最優(yōu)化的帶寬分配。這是一個分布式的速率分配問題，它可以被公式化為一個約束優(yōu)化的實用功能。在對上述問題正式定義之前，我們先來引進需要的符號：D(i,j) m (r(i,j)m )表示與當流m i以速度 r(i,j)m在對等端ij之間被轉發(fā)時相關聯(lián)的失真率。i 表示在對等端i引入的媒體流組。那么，全部通過鏈接(i,j)轉發(fā)的流的總失真率就可以表示為：（1）其中 m是一個很重要的因素，在執(zhí)行速度分配給向外轉發(fā)的link (i, j)時候，對等端i可以被分配給媒體流m。這個權重因子表示流m在交付需求方面的重要性。它將間接影響到分配給特殊流

11、的速度。（2）這個表達式表示通過link (i, j)發(fā)送的流的整體速度。其中 r(i,j)m表示分配給流m i的速度。使用前面表達式來表示總失真率是在特殊的對等端間鏈接里引進的，我們可以用如下的表達式表示所有對等端和所有媒體流的平均媒體失真率：（3）我們把網(wǎng)絡失真率DN減小到最小的話可用的帶寬R(i,j)在每一個連接路徑link(i,j) A 就不會溢出。因此，我們考慮的優(yōu)化的問題可以寫成：（4）接下來，我們?yōu)榻鉀Q這個問題提供一個分布式的解決方案：現(xiàn)在我們的目標是以最小的協(xié)調和信息傳遞來讓每一個對等端參與解決這個最優(yōu)化問題。由于RD（率失真）曲線是凹的而且是兩次可微的，我們可以直接應用拉格朗

12、日對偶性來解決先前的這個約束優(yōu)化問題。此外，這個實用程序功能是可分的而且兩次分解之后可以推導出來一個分布式的解決方案。我們可以對約束優(yōu)化問題（4）應用拉格朗日對偶性運算，并且得到以下局部的拉格朗日式子：（5）在這個公式中，(i,j) 0表示在端i上，link(i,j)的拉格朗日乘數(shù)。那么對偶函數(shù)被定義為：（6）其中是每一個對等端的拉格朗日乘數(shù)向量。因此，這個對偶問題是：（7）現(xiàn)在，拉格朗日乘數(shù)表示每一個被選擇的速率分配的代價。我們知道，現(xiàn)在，如果*是對偶問題的最優(yōu)解決方案的話， r*(i,j)(*)就是我們定義在（4）里面的最原始的問題的最優(yōu)解決方案。此外，這個拉格朗日乘數(shù)將原來的問題分解成為

13、了對于每一個對等端可以獨立優(yōu)化的獨立的流速率分配問題。尤其是，每一個對等端i必須解決最優(yōu)的速率分配問題：（8）現(xiàn)在，對偶算法的收斂就是分布式流量控制問題的最優(yōu)解已經(jīng)被一個凸面的效用函數(shù)證實了。為了計算每一個對等端節(jié)點i的拉格朗日乘數(shù)(i,j)，我們采用梯度法;（9）來計算(i,j)，在每次速率分配后執(zhí)行。現(xiàn)在看看在一個節(jié)點的多個流的速率分配。在一個新的優(yōu)化水平里，我們將會計算一個端節(jié)點分享給傳出流的最優(yōu)速率分配。這么做是基于轉發(fā)的流的重要性并通過梯度因素 m = Dm(R)/R反映出來。這個因素體現(xiàn)了在媒體流m的數(shù)據(jù)傳輸速率以及信號失真率之間的權衡。特別的，在對我們選擇的流m運行的率失真曲線D

14、m(R)它保持mDm(R)/R (i,j)。與此相關的對應在曲線上的率值就是應該被分配給從對等端i到對等端j以路徑link(i,j)轉發(fā)的最優(yōu)速率。現(xiàn)在，我們把這個最優(yōu)值記為r*(i,j)m。那么，整體轉發(fā)速率就是：（10）由于一個媒體流已經(jīng)分配了它的傳出速率r*m(i, j)，所以一個對等端可以輕易的將這個速率制定給每一個獨立的數(shù)據(jù)包，數(shù)據(jù)包包含的媒體流沒有任何下一步的優(yōu)化步驟。現(xiàn)在，對失真率的描述信息被包含在每一個獨立的數(shù)據(jù)包。由于每一個數(shù)據(jù)包k被D(km)和R(km)標記，一個對等端可以輕易的計算出每一個數(shù)據(jù)包的梯度D(km)/R(km)。此外，由于連接路徑的拉格朗日乘數(shù)(i,j) 已經(jīng)

15、可以從每一個對等端的本地獲取，因此梯度D/R比(i,j)更優(yōu)的數(shù)據(jù)包將會被轉發(fā)，否則將會直接被從本地緩存里丟棄而不會被繼續(xù)在覆蓋層里轉發(fā)了。因此，每個對等端的問題被還原為簡單的通過比較通過比較由他們的失真率描述信息表示的他們的相對重要性，來決定轉發(fā)或是丟棄數(shù)據(jù)包。最后，我們通過比較參與對等端不同的數(shù)據(jù)包調度算法得到的模擬結果。我們執(zhí)行了數(shù)據(jù)包級的ns-2網(wǎng)絡仿真器的一部分算法。對等端之間的數(shù)據(jù)傳送我們使用了TCP的選擇確認協(xié)議。我們通過不同的上傳容量來測試對等端，為了表示不同區(qū)域的用戶的非對稱的最后的訪問路徑，我們假設他們的下載速度高8倍。關于建立覆蓋網(wǎng)絡，主要的原則我們已經(jīng)在第二節(jié)中解釋了。

16、說得更加具體一點就是，每一個對等端向中心服務器請求一個它可以獲取內容的五個對等端的列表。這個列表被用來平均的分配傳入的請求。因此，沒有什么特別的覆蓋網(wǎng)絡維護算法。我們比較了一個最早的截止日期第一的調度算法和一個采用無特別調度技術的貪婪算法。而不是使用實際的視頻數(shù)據(jù)，我們創(chuàng)建了人工的預格式化的視頻內容.這種人造數(shù)據(jù)單位的形式類似于等距離的視頻的幀序列，同時他們也有相互依賴的特性。采用這種模擬的辦法的主要優(yōu)點在于它允許我們將焦點精確的放在潛在流優(yōu)化算法上面，這也是本文的重點?？蚣苡赏ㄟ^它們對接受者的重要性來分層組織的數(shù)據(jù)單元組成，所有的數(shù)據(jù)單元有相同的大小，設置為200bytes。與質量的增長相聯(lián)

17、系的數(shù)據(jù)單元被定義為質量單元。例如，符合相同內部編碼的框架的單位有一個10的失真率。每一個對等端的成功準時收到媒體數(shù)據(jù)單位的質量都被統(tǒng)計下來。最后，預格式化數(shù)據(jù)的幀速率被設置為30幀每秒，同時，初始的向前翻滾延時為4秒。A，結果對于我們的評估，我們實驗了在一個包含50個覆蓋節(jié)點和兩個轉發(fā)流的靜態(tài)網(wǎng)絡中采用推薦的流系統(tǒng)。在圖3a中，我們給出了在試驗中測試的覆蓋層中所有的客戶端的平均質量。我們假設這些對等端中的一部分心甘情愿的向前轉發(fā)一個媒體數(shù)據(jù)流。這意味著更現(xiàn)實的條件是愿意無私奉獻出自己的資源的對等端通常很低。這個數(shù)據(jù)結果主要反映出通信體制通過利用可用信道減少的部分來獲取性能增長的能力。究其原因當然是廣播調度保證了需要成功解碼的數(shù)據(jù)包會在覆蓋結構中自始至終的傳播。當然，如果有充足的初始向前翻滾延遲和在每一個對等端有增長的本地可用內存的話，轉發(fā)交付的質量肯定會得到提高。在圖3b中，我們觀察到相同數(shù)量的節(jié)點中得到了相似的結果，但是在對等端的數(shù)量增多以后，他們的種子獲得到了媒體的說明部分（總體的50%）。如同我們所預料的，在所有測試的調度