基于鄰近原則的應用層組播實驗研究

摘要：提出了一個基于鄰近原則的應用層組播系統，其覆蓋網絡由參與節點求得自身網絡坐標之后，根據網絡坐標基于鄰近原則聚類形成。通過基于網絡測量數據的仿真和PlanetLab真實網絡環境中的實際測試，證明了基于該覆蓋網絡結構的應用層組播系統在性能指標上優于當前普遍應用的基于其他結構的覆蓋網絡的系統。在構建覆蓋網絡過程中考慮節點在網絡中的位置分布等因素將能夠提高基于該覆蓋網絡的應用層組播性能。

關鍵詞：應用層組播； 覆蓋網絡； 鄰近原則； 節點聚類； 網絡坐標

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)04－1211－03

應用層組播是近年來互聯網研究的熱點，具有便于實現和推廣的突出優點。在應用層組播中，參與主機間通過邏輯連接建立起覆蓋網絡（overlay network），數據包通過覆蓋網絡進行傳輸。

覆蓋網絡的結構是影響應用層組播系統性能的重要因素。如果在構建覆蓋網絡的過程中不考慮各個節點的位置分布，那么覆蓋網絡的構建中節點很可能大量選取在實際網絡中距離很遠的節點作為鄰居。在Internet中，節點在網絡中呈聚類分布，聚類內部的距離小于聚類之間的距離，聚類之間鏈路可獲得帶寬遠比聚類內部稀缺，因此這種隨機策略會造成網絡帶寬資源的浪費，并且大大影響了組播數據傳輸的性能。因此在構建覆蓋網絡的過程中考慮節點的位置分布是十分重要的[1]。

本文提出了一種基于鄰近原則的覆蓋網絡結構，通過基于網絡拓撲數據的仿真和真實網絡環境中應用于流媒體組播的實驗，對其進行了性能測試，并與基于其他覆蓋網絡結構的系統性能進行了比較分析。

1相關研究

1．1Chainsaw

Chainsaw是一個基于覆蓋網絡的應用層組播系統，它基于一個完全隨機連接的覆蓋網絡[2]。Chainsaw的覆蓋網絡完全消除了樹結構，系統中參與組播的每個節點根據事先確定的鄰居個數，從參與主機中隨機選取一組節點建立邏輯連接作為自己的鄰居。Chainsaw系統的覆蓋網絡結構靈活，易于實現，但其不足之處是沒有充分考慮節點的位置因素。隨機連接的覆蓋網絡結構在異構性很強的實際Internet上會影響數據包的傳輸效率。

1．2Binning

Binning是一種基于節點間的相對距離進行節點聚類的方法[3]，將其應用于覆蓋網絡的構建可以提高數據在覆蓋網絡中的傳輸效率。在Binning的策略中，覆蓋網絡的每個節點分別測得自身到選定的一組網絡坐標節點的傳輸延遲作為自身的網絡坐標，節點根據網絡坐標的大小進行排序，具有相同順序坐標的節點被認為位于同一個箱子中。在同一個箱子中的節點是相對接近的，即它們屬于同一個聚類。構建覆蓋網絡時，假設一個節點需要在整個系統中選取k個節點作為鄰居，它將從自己所在箱子內選擇k/2個節點，再隨機選擇k/2個節點。

Binning采用的聚類方法較為簡單，能夠優化覆蓋網絡的結構，但本質上是利用節點間的相對距離進行聚類，其精確性有待提高。

1．3HONet

HONet是一個基于網絡坐標進行聚類的覆蓋網絡結構[4]，它將結構化的網絡與非結構化網絡進行結合，既具有結構化網絡的可擴展性，又具有非結構化網絡的靈活性。節點根據網絡坐標加入不同的聚類，每個聚類都是一個結構化的覆蓋網絡，同時建立一些聚類間的隨機連接以在充分利用帶寬的基礎上保證整個網絡的連通性。

HONet的聚類方法準確性較高，但維護結構化覆蓋網絡需要較大的帶寬開銷，將會影響組播數據的傳輸效率。

2系統描述

針對Chainsaw、Binning和HONet三個系統存在的不足，本文將從以下三個方面進行改進：a)充分考慮參與節點的位置因素，提高數據包傳輸效率；b)采用準確性更高的網絡坐標系統來提高聚類效果；c)采用非結構化的覆蓋網絡結構，降低帶寬開銷，提高靈活性。

本文提出的系統Canicula是一個基于鄰近原則構建覆蓋網絡的應用層組播系統，它的覆蓋網絡是利用基于網絡坐標的節點聚類形成的。體系結構如圖1所示。

2．1節點間距離預測

在Canicula的覆蓋網絡構建中，為了實現節點聚類，首先需要對節點在網絡中的距離進行預測，這需要知道節點在網絡中的位置信息。筆者采用一個簡單的網絡坐標系統來標志節點在網絡中的位置。

選定Internet上一組確定的主機作為網絡坐標參考節點，任何能夠響應ping操作的節點均可以作為參考節點。每個節點加入系統后，測量自身到這一組參考節點的傳輸延遲，所得到的一組值就是這個節點自己的網絡坐標。

任意兩個節點得到各自的網絡坐標后，就可以預測它們之間的距離。近年來提出了很多基于網絡坐標的距離預測方法，如IDMaps[5]、triangulated heuristic[6]、GNP[6]、Vivaldi[7]等。通過這些方法可以無須經過任何直接的端到端測量估算出任意兩個節點之間的距離。

文獻[8]中對GNP、IDES和triangulated heuristic三種基于網絡坐標的距離預測方法進行了仿真和實驗。結果發現triangulated heuristic方法實現簡單，與另外兩種計算和測量開銷均比較大的距離預測方法在距離預測的準確性上是接近的。因此，結合節省測量開銷和保持結果精確性兩方面考慮，筆者在Canicula的設計中采用了triangulated heuristic方法。

Triangulated heuristic方法基于三角不等式[6]。兩個節點的距離上界是它們到同一個網絡坐標參考節點的距離之和的最小值，設為U，下界是它們到同一個網絡坐標參考節點的距離之差的絕對值的最大值，設為L。節點距離可以由L和U以各種方式組合進行預測。在Canicula的設計中，筆者采用(L+U)/2作為兩個節點的預測距離。

2．2節點聚類

得到節點間的預測距離后，根據預先設定的聚類半徑的大小對節點進行聚類，相互間距離小于聚類半徑的兩個節點被認為位于同一個聚類，否則被認為位于不同的聚類。

每個節點在系統中選取一定數量的節點作為鄰居節點。節點選取鄰居時，從同一聚類選取的鄰居數量和從其他聚類選取的鄰居數量具有不同的上界。在同一聚類選取的鄰居數量較大，在不同聚類選取的鄰居數量較小。這樣，所構建的覆蓋網絡既能充分利用帶寬的分布，提高數據包傳輸的效率，又保證了整個網絡的連通性。

2．3數據包傳輸

Canicula的數據包傳輸采用拉送的方法[2]，每個節點均維護一個固定長度的數據包緩存，在接收到新的數據包后均會通知其鄰居節點。節點從它們的鄰居處得到有新數據包的通知后，向相應的鄰居發出請求并獲取數據包，若多個鄰居處有同一個新數據包，則隨機選擇其中一個鄰居獲取該數據包。

2．4系統工作流程

每個新加入的節點首先從反射節點（rendezvous point）中獲取一組網絡中的節點信息。之后通過triangulated heuristic計算出該節點的網絡坐標，確定該節點所屬的聚類，然后采用Gossip的方式加入聚類[9]。Gossip的方式帶給反射節點的負載是非常輕的，保證了系統的可擴展性。加入聚類根據設置在同一個聚類和不同聚類中分別選取相應數目的鄰居，從而完成一個Canicula節點加入的過程。

3基于網絡拓撲數據的仿真

為了對Canicula的覆蓋網絡結構進行性能測試，筆者編寫了仿真程序。仿真采用的數據集是在實際Internet中測量得到的數據集king[7]，它包含了1 740臺主機兩兩之間的路徑延時。通過仿真觀察了Canicula的各個設計參數，如節點鄰居數量上下界、聚類半徑、網絡坐標參考節點數量等變化時，覆蓋網絡性能的變化，以及取定參數的情況下，Canicula和Chainsaw、Binning覆蓋網絡的性能差異。

仿真采用RDP（relative delay penalty，相對延時代價）作為評價覆蓋網絡性能的指標。RDP定義為兩個節點在覆蓋網絡中的路徑延時和它們直接進行端到端測量延時的比值。RDP的值越小說明構造出的覆蓋網絡結構和參與節點在Internet中的實際分布得越好，則當其應用于流媒體組播時，數據傳輸性能也越好。

3．1參數變化對覆蓋網絡性能的影響

在本文設計的基于網絡坐標進行節點聚類的覆蓋網絡中，影響節點間距離預測和節點聚類的各個參數對覆蓋網絡的性能均有重要影響。筆者選取了節點鄰居數上下界、聚類半徑和網絡坐標參考節點數量三個參數進行仿真，觀察它們的變化對覆蓋網絡性能的影響。

圖2是聚類半徑取40，網絡坐標參考節點取12個，節點鄰居數取不同的上下界時，覆蓋網絡的RDP概率累計分布函數曲線。其中節點的鄰居數包括聚類內的鄰居數（NB）和其他聚類的鄰居數（FARNB）。從圖中可以看到，節點的鄰居數越多，覆蓋網絡的RDP就越小，即性能越好。



當節點聚類內鄰居數取3~5個，其他聚類鄰居數取1~2個，網絡坐標參考節點取12個，聚類半徑（radius）取不同大小的值時，覆蓋網絡的RDP概率累積分布函數曲線如圖3所示。從圖中可以看到，當聚類半徑的大小在一定范圍內時（保證節點在聚類內能找到足夠數量的鄰居節點），聚類半徑越小，RDP也越小，即覆蓋網絡的性能越好。



圖4是節點聚類內鄰居數取3~5個，其他聚類鄰居數取1~2個，聚類半徑取40，網絡坐標參考節點數量（landmark）取不同的值時，RDP的概率累計分布函數曲線。從圖中發現，取10個網絡坐標參考節點比取5個坐標節點的覆蓋網絡性能好，但取15個坐標節點時，其覆蓋網絡的性能相比于取10個已沒有明顯提高。說明坐標節點數量達到一定量值后繼續增加其數量并不能繼續提高系統性能。



3．2三種覆蓋網絡性能比較

為了保證對三種覆蓋網絡的比較是公平的，需要配置各個參數以保證三種覆蓋網絡的節點有相同的平均鄰居個數，這樣才能體現出不同的覆蓋網絡結構在性能上的區別。在仿真中，經過參數的調整，最終使三種覆蓋網絡的平均鄰居個數為4.65，聚類半徑設為40，網絡坐標參考節點個數為12。



圖5是在上述取定的參數條件下，三種覆蓋網絡的RDP概率累積分布函數曲線。從圖中看到，Canicula和Binning的RDP較為接近，Chainsaw的則要大一些。本文對所有節點對的平均RDP進行了計算。Canicula的平均RDP是3.17；Binning的平均RDP是3.40；Chainsaw的平均RDP是6.01。因此，根據RDP指標，在這三種覆蓋網絡中，基于鄰近原則的覆蓋網絡Canicula的性能是最優的。



4基于實際互聯網的實驗

通過在真實的Internet中的實驗對仿真得到的結論進行更可靠的驗證，實驗的真實網絡環境是PlanetLab實驗床[10]。PlanetLab是一個全球性的計算機網絡分布式實驗床，目前擁有340個參與機構，704臺參與主機，遍布在全世界五大洲。利用PlanetLab可進行全球范圍的互聯網大規模實際測試。

筆者于2006年8月在PlanetLab的所有可用節點上對基于Chainsaw、Binning和Canicula三種覆蓋網絡的應用層組播系統性能進行了實際測試。由于遠程主機不穩定等因素，最終實際參與實驗的節點為300個左右。

在實驗中，設置三種覆蓋網絡平均每個節點的鄰居數量均為6，覆蓋網絡的聚類半徑設置為40 ms，以保證對三種覆蓋網絡的比較是公平的。

實驗中主要采用RDP（relative delay penalty）和丟包率（packet loss rate)等關鍵指標作為評價覆蓋網絡在應用層組播中性能的參數。

4．1RDP

三種覆蓋網絡的RDP概率累積分布函數實驗結果如圖6所示。

圖6的結果表明，基于鄰近原則的Canicula的RDP最小，基于節點間相對距離聚類的Binning的RDP比Canicula大，而完全隨機的Chainsaw的覆蓋網絡的RDP更大。

4．2丟包率

丟包率是反映組播性能最直觀的指標之一。實驗中數據源節點以恒定速率（530 kbps）產生新的數據包，以P2P方式在整個覆蓋網絡中進行分發。對基于三種覆蓋網絡的系統所有參與節點的丟包率進行了測量，分別統計了所有節點的平均丟包率和丟包率小于1%的節點比例，結果如圖7和8所示。

從圖7和8看到，Canicula和Binning的平均丟包率比較接近，Canicula略低一些，Chainsaw的平均丟包率相比兩者偏高，丟包率小于1%的節點比例結果相似。筆者對所有節點的丟包率進行了統計，平均丟包率Chainsaw為2.57%，Binning為1.99%，Canicula為1.84%；丟包率小于1%的節點比例Chainsaw、Binning和Canicula三者依次為94.96%、95.97%和96.48%。因此，從丟包率的結果來看，在三個系統中，Canicula的組播性能是最優的。

綜合以上分析，在實際Internet中基于相對延時代價和基于丟包率的標準比較三種覆蓋網絡的性能，Canicula系統仍然是最優的。

5結束語

通過基于網絡拓撲數據的仿真和在PlanetLab上大規模的實際性能測試，得到如下結論：本文提出的基于鄰近原則的覆蓋網絡系統Canicula在組播性能上優于基于完全隨機覆蓋網絡的系統，其基于網絡坐標系統的聚類方法相比基于節點間相對距離的聚類方法更準確，從而使組播性能更優；在構建覆蓋網絡的過程中，基于鄰近原則構建覆蓋網絡能夠提高基于該覆蓋網絡的應用層組播性能。

在當前工作的基礎上，筆者還將考慮進一步優化節點間距離預測的網絡坐標算法，或者引入網絡層的路由信息，使聚類準確度得到提高。另外，數據包的傳送也考慮使用更加智能的策略代替當前的隨機策略，以進一步提高系統性能。

參考文獻：

[1]ZHANG Xin－yan， ZHANG Qian， ZHANG Zhen－sheng， et al. A Construction of locality－aware overlay network: mOverlay and its perfor－mance[J]. IEEE Journal on Selected Areas in Communications， 2004， 22(1): 18-28.

[2]PAI V， KUMAR K，TAMILMANI K， et al. Chainsaw: eliminating trees from overlay multicast[C]//Proc of IPTPS. New York: [s.n.]， 2005.

[3]RATNASAMY S， HANDLEY M， KARP R， et al. Topologically－aware overlay construction and server[C]//Proc of IEEE INFOCOM. New York: [s.n.]， 2002.

[4]TIAN Rui－xiong， XIONG Yong－qiang， ZHANG Qian， et al. Hybrid overlay structure based on random walks[C]//Proc of IPTPS. New York: [s.n.]， 2005.

[5]FRANCIS P，JAMIN S， JIN Cheng， et al. IDMaps: a global Internet host distance estimation service[J]. IEEE/ACM Trans on Networking， 2001， 9(5): 525-540.

[6]NG T S E， ZHANG Hui. Predicting Internet network distance with coordinates－based approaches[C]//Proc of IEEE INFOCOM. New York: [s.n.]， 2002.

[7]DABEK F， COX R， KAASHOEK F， et al. Vivaldi: a decentralized network coordinate system[C]//Proc of ACM SIGCOMM. Portland: [s.n.]， 2004.

[8]ZHANG Rong－mei， TANG Chun－qiang， HU Y C， et al. Impact of the inaccuracy of distance prediction algorithms on Internet applications: an analytical and comparative study[C]//Proc of IEEE INFOCOM. Barcelona:[s.n.]， 2006.

[9]CHU Y H， GANJAM A， NG T S E， et al. Early deployment expe－rience with an overlay based Internet broadcasting system[C]//Proc of USENIX Annual Technical Conference. Boston: [s.n.]， 2004.

[10]PlanetLab[EB/OL]. http://www.planet－lab.org/.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”