ＰＰＮＣａｓｔ：一種基于對等交換的應用層組播方法
2008-12-31 00:00:00秦偉盧顯良周旭彭永祥
計算機應用研究 2008年12期
(1.電子科技大學計算機學院，成都 610054； 2.中國科學院 聲學所高性能網絡實驗室， 北京 100190)
摘 要：
針對高碼率和實時性要求不高的大規(guī)模媒體分發(fā)應用，提出一種新的應用層組播PPNCast。PPNCast基于對等交換的思想對應用層組播系統進行了優(yōu)化，可以支持多種片的分發(fā)模型。通過仿真實驗與Yoid、NICE應用層組播協議對比，結果顯示PPNCast可以明顯改善系統的鏈路壓力均衡度和節(jié)點公平度。
關鍵詞：應用層； 組播； 可靠性； BitTorrent
中圖分類號：TP309 文獻標志碼：A
文章編號：10013695(2008)12380703
PPNCast: application level multicast system based on peertopeer exchange
QIN Wei1， LU Xianliang1， ZHOU Xu2， PENG Yongxiang1
(1. School of Computer Science， University of Electronic Science Technology of China， Chengdu 610054， China； 2. High Performance Network Laboratory， Institute of Acoustics， Chinese Academy of Sciences， Beijing 100190， China)
Abstract:This paper proposed a new application layer multicast protocol named as PPNCast， which was specifically designed for highbandwidth data streaming and low realtime requested applications with large peers set. Optimized by peerto peer exchange，PPNCast supports several distribution models to improve multicast performance. The results of simulations show that PPNCast has better stress equilibrium and fairness property than YoidandNICE.
Key words：application layer; multicast;reliability;BitTorrent
0 引言
組播作為互聯網的一項重要技術具有節(jié)省網絡帶寬、降低服務器負載等優(yōu)點。但網絡層的組播技術由于其對路由器的依賴，涉及到網絡運營商的利益等原因，一直沒有得到廣泛應用[1]。應用層組播技術中，包的復制和轉發(fā)等組播功能是由用戶主機完成的，無須改變現有網絡設備，從而解決了在網絡層組播中存在的難推廣的問題。
應用層組播作為一種P2P技術，現有的組播協議，如ALMI[2]、Yoid[3]、NICE[4]、ESM[5]等，采用不同的方法構造一個覆蓋組播樹，通過組播樹進行數據分發(fā)。每個節(jié)點只能夠從其惟一的父節(jié)點獲得數據。因此，占很大比例的葉子節(jié)點的出口帶寬和服務能力沒有得到有效利用，存在免費搭車的情況，有礙系統的公平性。
一些P2P文件共享系統，如BitTorrent[6]、Guntella[7]等，它們是通過對等網絡實現的。網絡中所有的節(jié)點均是平等的，節(jié)點可以直接交換數據，一個節(jié)點可以同時從多個節(jié)點獲得數據。但這種隨機的連接可能導致覆蓋網的無序狀態(tài)，造成網絡帶寬的浪費。
本文提出一種采用對等交換優(yōu)化應用層組播的方法PPNCast。它采用分層分群的方法提高了單數據源組播系統的容量和擴展性；在群內通過對等網絡文件共享的方式將數據分發(fā)給其他節(jié)點，提高了節(jié)點的出口帶寬的利用率。PPNCast以短暫的初始延時來換取整個系統更高的穩(wěn)定性和公平性。
1 組播樹結構
PPNCast根據節(jié)點間的父子關系，將節(jié)點按照層和群進行劃分和組織。處于同一代的節(jié)點視為一層（layer），發(fā)布源為根節(jié)點，位于layer 0。每個節(jié)點和它的子節(jié)點構成一個群。一個群中存在一個父節(jié)點，負責上下層間的數據通信，它既作為上層中某個群的子節(jié)點，以P2P的方式與上層所在群中的其他節(jié)點進行數據交互，也作為下層所在群的父節(jié)點，將數據通過P2P的方式分發(fā)給群中的其他節(jié)點。此外它還是該群的控制中心維護節(jié)點信息，管理節(jié)點的加入和退出。整個系統的層次結構如圖1所示。
每個節(jié)點維護四個數據結構，即父節(jié)點信息、子節(jié)點表、兄弟節(jié)點表和父兄節(jié)點表。
子節(jié)點表中記錄子節(jié)點地址和到各子節(jié)點的距離。主要用于維護組播樹的拓撲結構。節(jié)點加入時會根據該表判斷加入到該組播樹什么位置。
兄弟節(jié)點表中記錄所有兄弟節(jié)點信息。它的作用類似于P2P網絡中文件分發(fā)協議的鄰居節(jié)點表。數據分發(fā)過程中會與鄰居節(jié)點進行數據交換。
父兄節(jié)點表中記錄父節(jié)點的兄弟節(jié)點信息，當父節(jié)點異常退出后，其子節(jié)點可以從父兄節(jié)點獲得該段中的其他分片，降低父節(jié)點退出對該群的影響。
上述各表會根據節(jié)點加入和退出動態(tài)地對各表進行更新。如圖2所示節(jié)點C要退出組播樹，通知其父節(jié)點A，A更新自己的子節(jié)點表，然后通知它的子節(jié)點。節(jié)點B收到更新報文后，更新其兄弟節(jié)點表，向其子節(jié)點發(fā)送該更新報文。D和E收到消息后，更新自己的父兄節(jié)點表。整個更新過程結束。
2 內容分發(fā)
通常的應用層組播算法中，通過組播樹來分發(fā)數據。該模型有以下缺點：
a)上游任何應用層鏈路的擁塞必定會影響下游鏈路。
b)樹中所有節(jié)點的入度為1，而對于出度大于1的節(jié)點，下載一個復本，要上傳多個復本。從用戶的角度講，有礙公平。
c)通常組播樹中的葉子節(jié)點數量占很大比例，而這些節(jié)點出口帶寬沒有得到有效利用。
針對應用層組播中存在的以上問題，PPNCast將對等網絡中文件共享思想與應用層組播技術相結合。以樹方式管理節(jié)點，以對等交換的方式分發(fā)數據，有效地改善應用層組播的上述缺點。
在一個節(jié)點加入時，已經獲得了父節(jié)點和所有兄弟節(jié)點的地址信息。因此構成了以父節(jié)點為種子節(jié)點的P2P網絡，每個節(jié)點不僅可以從父節(jié)點獲得數據還可以從其兄弟節(jié)點獲得數據。理想的情況下，父節(jié)點只提供一個復本，經過子節(jié)點之間數據交換，使其所有子節(jié)點均能夠獲得完整的復本。
應用層組播主要用于直播等對實時性有一定要求的應用。若對整個文件采用隨機的選片算法，片的到達相對分散，無法達到即時播放的目的。若采用順序選片，子節(jié)點就只能夠從父節(jié)點獲得數據，就會退化為傳統的組播樹模型。PPNCast采用分段再分片的方法，即將數據劃分為若干大小相等的段，每個段由若干片組成。段是順序分發(fā)的，而每個段中的片可以隨機請求。這樣當節(jié)點獲得一個完整的分段就可以播放。
3 片的分發(fā)模型
3. 1 Push模型
每個節(jié)點均通過push的方式將數據分發(fā)給其他節(jié)點。如圖3所示，假設A節(jié)點有兩個子節(jié)點B、C。每個段有三片，第一輪A先將片1推送給B，將片2推送給C。第二輪A將片3推送給B和C，B將片1推送給C，C將片2推送給B。設兩個節(jié)點間傳輸一個分片的時間為t，段的分發(fā)時間為T，則上述情況T=2t。
Push模型的優(yōu)點是每個節(jié)點均知道當前網絡中的其他節(jié)點，從根節(jié)點開始向其他節(jié)點分發(fā)。哪些節(jié)點向哪些節(jié)點分發(fā)哪些片都是確定的。理想的情況下該模型的分發(fā)效率比較高。但網絡中節(jié)點動態(tài)地加入和退出對系統的影響較大。而且每個節(jié)點的性能和節(jié)點之間的鏈路狀況不同，導致兩個節(jié)點之間傳送一個分片的時間t不同。t的差別比較大時，單個節(jié)點的性能會影響系統的性能。
3. 2 Pull模型
Pull模型類似BitTorrent中數據傳輸協議，每個節(jié)點先獲得其他節(jié)點的位圖信息，隨機選擇自己沒有的分片下載。如圖4所示第一輪B和C有1/3的可能獲得相同的分片。如果第一輪B和C第一輪獲得相同的分片，第二輪B與C之間就沒有可交換分片，B與C之間的帶寬被浪費。這種情況T＝3t。
Pull模型節(jié)點由于隨機請求分片，哪些節(jié)點向哪些節(jié)點請求哪些片都是不確定的。這樣可能導致一些節(jié)點間由于擁有相同的分片，而浪費節(jié)點間的帶寬。分發(fā)效率比較低。優(yōu)點是系統有比較好的靈活性和自適應性，節(jié)點的動態(tài)加入和退出對系統的影響不大。單個節(jié)點的性能也不會成為系統的瓶頸。
3. 3 Push與pull結合模型
Push與pull結合模型是結合push模型和pull模型的優(yōu)點，在保證系統靈活性和可靠性的情況下，得到比較好的分發(fā)效率。該模型的具體過程如下：
a）根節(jié)點采用push方式向子節(jié)點推送數據，保證不同子節(jié)點獲得不同的分片。
b）子節(jié)點之間采用pull方式傳送數據，由于根節(jié)點向每個節(jié)點推送的分片不同，可以充分利用節(jié)點之間帶寬，提高了片的分發(fā)效率。
c）當某些節(jié)點由于性能比較差，其他節(jié)點可能無法得到該分片或下載速度比較慢。這時可以向根節(jié)點請求，根節(jié)點會再投放一個該片的復本，以提高該片的擴散速度。
3. 4 網絡編碼模型
以上幾種模型中，節(jié)點只是簡單對分片進行請求和分發(fā)。隨機請求的pull模型中，因為兩個節(jié)點可能擁有相同的分片，使兩者之間帶寬閑置；push模型通過在整個系統對片的分發(fā)進行調度提高系統的分發(fā)效率，但喪失了系統的靈活性。Push與pull結合模型，通過根節(jié)點將分片分散的推送到子節(jié)點在一定程度上提高了系統的片的分發(fā)效率，是push和pull兩種模型的折中，沒有從根本上解決分發(fā)效率和系統靈活性之間的矛盾。
在文獻[8~10]中提出的網絡編碼技術，利用中間節(jié)點對數據塊編碼和重新組包，減少了節(jié)點因為擁有相同信息而無法交換數據的可能性。每個節(jié)點均要對多個分片編碼重新組包，再發(fā)送給其他節(jié)點，節(jié)點收到一定數量的分片后通過解碼獲得數據。網絡編碼模型可以在不降低系統靈活性的同時提高了系統的分發(fā)效率。下面用一個例子來說明網絡編碼在PPNCast中的使用。
如圖5所示，初始時刻父節(jié)點A擁有一個完整段，所有子節(jié)點沒有該段的任何分片。該段有n個分片。節(jié)點B向父節(jié)點A請求分片，父節(jié)點采用下面的方法創(chuàng)建一個分塊D1。
a)生成一組隨機系數(c11 c12 … c1n)；
b)在有限域上得到的源數據為(P1 P2 … Pn)；
c)D1=c11P1+c12P2+…+c1nPn；
d)將D1和隨機數向量(c11c12 … c1n)一起發(fā)送給E節(jié)點。
當E節(jié)點向父節(jié)點請求第二個片，父節(jié)點再重新生成一組隨機數(c11 c12 … c1n)。采用同樣的方法計算得到D2，將D2和隨機數向量(c11 c12 … c1n)發(fā)送給E節(jié)點。
此時，另一個節(jié)點F向節(jié)點E請求數據塊。現在E已經收到兩個編碼塊D1和D2以及對應的系數向量c1和c2。首先，選擇一組隨機數(d1 d2)。采用下面算法計算得到系數向量(E1 E2 … En)和編碼塊F1，發(fā)送給節(jié)點C。
c11 c12 … c1n
c21 c22 … c2n
P1P2Pn=D1D2
(d1 d2)c11 c12 … c1n
c21 c22 … c2n
P1P2Pn=(d1 d2)D1D2
(∑2i=1dici1 ∑2i=1dici2 … ∑2i=1dicin)P1P2Pn=(d1 d2)D1D2
(e1 e2 … en)=(∑2i=1dici1 ∑2i=1dici2 … ∑2i=1dicin)
(e1 e2 … en)P1P2Pn=(d1 d2)D1D2=F1
當節(jié)點收到的編碼塊(D1 D2 … Dn)和對應的n個線性無關的系數向量(c1 c2 … cn)時，該節(jié)點采用上述算法的逆過程就可以得到該段中所有分片(P1 P2 … Pn)。
4 系統可靠性
PPNCast從兩方面保證系統的可靠性。一方面，在群的內部采用非結構化的P2P網絡，節(jié)點的加入和退出對群內的其他節(jié)點的影響很小；另一方面，如果某個群的代表節(jié)點即父節(jié)點異常退出，該群中的節(jié)點會重新推舉出新的節(jié)點作為代表節(jié)點。在此過程中，該群中的節(jié)點可以從父節(jié)點的兄弟節(jié)點獲得源數據分片，從而降低了節(jié)點退出對群內其他節(jié)點的影響。
5 仿真與性能分析
定義1 節(jié)點公平度用來衡量P2P系統的節(jié)點出入流量的平衡程度。設系統中有n個節(jié)點。文件傳輸過程中，節(jié)點i總的入口流量為μi，出口流量為Oi，傳輸文件大小為M bit。節(jié)點公平度為
σ=∑ni=1|Oi-μi|/（nM）
定義2 鏈路壓力均衡度[11]采用均勻性度量的偏差準則來衡量組播中的壓力，它可以有效反映組播模型中鏈路壓力分布的均衡程度。
在NS2上對Yoid[3]、NICE[4]和PPNCast三種應用層組播模型進行了仿真。PPNCast使用push與pull結合的模型作為片的分發(fā)模型。仿真的網絡拓撲使用NEM[12]產生拓撲生成算法采用PLOD[13]生成隨機拓撲時的參數設置為alphaplod 取0.5 betaplod 取500生成的拓撲由1 000個主機700個路由器和2 800條鏈路組成并設定路由器的最大主機接入數量為4。主機按相同的概率連接到網絡中的路由器且一個主機只與一臺路由器相連仿真共進行10組在每一組中設定不同數量的主機通過隨機選擇的方法獲得加入組播。分別對Yoid、NICE和PPNCast在相同的網絡環(huán)境下進行仿真，得到各模型鏈路的壓力均衡度和節(jié)點公平度，如圖6和7所示。
從圖6可以看出在各種規(guī)模的組播中，NICE和PPNCast所建立的組播樹中的壓力分布比Yoid要均勻，而且在這三種協議中PPNCast的鏈路壓力最均衡。主要因為PPNCast采用分布式的P2P方式分發(fā)分片，節(jié)點會自動調節(jié)鏈路壓力。
從圖7可以看出三種組播模型中，PPNCast的節(jié)點公平度明顯優(yōu)于其他兩種組播模型。主要因為PPNCast模型中可以充分利用節(jié)點的出口帶寬，有效減小了節(jié)點出入流量之差，整體上提高了系統的公平性。
6 結束語
本文通過分析現有應用層組播技術缺點和不足，提出一種新的應用層組播方法PPNCast。將對等網絡中的文件共享技術與應用層組播結合，改善了系統的可靠性和公平性。本文詳細介紹了組播樹的結構和數據分發(fā)過程，通過分析各種分發(fā)模型，得出采用push與pull結合的模型和網絡編碼模型可用性比較高，前者的實現相對簡單，對節(jié)點計算能力沒有很高的要求。后者由于其涉及運算量比較大，對節(jié)點性能要求比較高。實現也相對復雜。通過仿真實驗與其他應用層組播模型比較可以看出，PPNCast有效改善了鏈路壓力分布的均衡度和系統的公平度。
參考文獻：
［1］DIOT C， LEVINE B N， LYLES B， et al. Deployment issues for the IP multicast service and architecture[J]. IEEE Network，2000，14(1):7888.
［2］PENDARAKIS D， SHI S， VERMA D， et al. ALMI: an application level multicast infrastructure[C]//Proc of the 3rd USENIX Symposium on Internet Technologies and Systems. Berkeley: USENIX Association，2001:4960.
［3］FRANCIS P. Yoid: your own Internet distribution[EB/OL]. http://www.aciri.org/yoid/.
［4］BANERJEE S， BHATTACHARJEE B， KOMMAREDDY C. Scalable application layer multicast[C]//Proc of ACM SIGCOMM.2002:205217.
［5］CHU Y， RAO S G， SESHAN S， et al. A case for end system multicast[J]. IEEE Journal on Selected Areas in Communications，2002，20(8):14561471.
［6］Bittorrent[EB/OL]. http://www.bittorrent.org.
［7］Gnutella [EB/OL].http://p2pjournal.com/main/gnutella.htm.
［8］AHISWEDE R， CAI ning，LI S Y R， et al.Network information flow[J]. IEEE Transon Information Theory，2000，46(4):12041216.
［9］LI S Y R， YEUNG R W， CAI Ning. Linear network coding[J]. IEEE Trans on Information Theory，2002，49(2):271381.
［10］ZHU Ying， LI Baochun， GUO Jiang. Multicast with network coding in applicationlayer overlay networks[J]. IEEE Journal in Communications，2004，22(1):107120.
［11］沈波，張宏科，劉云.覆蓋網絡組播壓力與伸長度的性能評價模型[J].系統仿真學報，2005，17(5):11071114.
［12］MAGONI D. NEM: a software for network topology analysis and modeling[C]//Proc of the 10th MASCOTS.[S.l.]: IEEE Computer Society， 2002:364371.
［13］PALMER C R， STEFFAN J G. Generating network topologies that obey power laws[C]//Proc of IEEE Global Telecommunication Conference. San Francisco: IEEE Press， 2000:434438.
