基于Overlay Network協同選播通信機制的研究

張園園

摘 要：應用層選播因不了解物理網絡拓撲而缺乏高效性，網絡層選播因不了解服務器本身的負載而缺乏靈活性。在充分發揮應用層的靈活性和網絡層的高效性的基礎上，提出了基于Overlay Network的協同選播網絡體系結構，給出了覆蓋層的構造方法，并從域內和域間兩方面對協同選播機制進行了闡述，最后利用Petri網理論對相關機制進行了形式化描述，且對其正確性和完備性進行了驗證。

關鍵詞：Overlay Network；協同選播機制；負載均衡；Petri網

中圖分類號：TP393.09 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2016.05.020

選播Anycast（one-to-one-of-many）是在面向下一代網絡時，為了解決負載均衡和提升服務可用性而提出的。一個選播地址標識不同節點的多個網絡接口，如果一個報文被傳送到一個選播地址上，那么它最終被傳送到具有該地址標識的、根據路由協議距離度量“最近”的一個接口上。

傳統的選播服務是在應用層或網絡層上實現的，在網絡層上實現選播具有低時延和低開銷的優勢。但是，由于網絡層不了解提供選播服務節點的信息和負載狀況，可能會選擇一個負載過重的節點來為用戶提供服務，這樣反而降低了選播通信的效率；應用層則通過外部實體來實現選播，很容易了解到服務節點當前的狀態和負載信息，可以非常便捷地選擇一個相對空閑的服務節點來提供服務。但是，由于應用層不了解底層網絡拓撲信息，所選出的節點很可能距離用戶很遠，這樣反而不利于其靈活性優勢的發揮?，F有的一些研究已經開始考慮在應用層實現選播時加入反映物理網絡的因素或者在網絡層加入反映服務節點信息的因素，繼而出現了許多新型網絡架構。盡管如此，應用層和網絡層的關系仍沒有達到合理的協調。為此，本文提出基于Overlay Network的協同選播網絡體系結構，將應用層和網絡層各自的優勢很好地結合起來，以期提高選播服務的質量，達到大規模部署和應用的目的。

1 基于Overlay Network的協同選播網絡體系結構

為了充分發揮應用層的靈活性和網絡層的高效性優勢，并且實現協同選播，本文提出了基于Overlay Network的協同選播網絡體系結構。這一網絡體系結構的建立，需要在應用層和網絡層之間構造虛擬的協同選播覆蓋層?？紤]到實際可行性等因素，本文提出基于選播服務域層—匯聚層的分層協同選播覆蓋層模型。圖1所示為協同選播Overlay Network拓撲結構模型。

為了更好地實現協同選播，使用戶節點都能與其距離最近、最優的選播服務節點通信，同時解決選播存在的交錯服務問題，對網絡中的節點重新進行了劃分，提出了一種以選播服務器節點為中心的區域劃分方法，并將劃分后的區域稱為“選播服務域（Anycast Service Domain，ASD）”，在每個域內可能存在一種或者多種類型的選播服務。

在每個選播服務域內，通過提取選播服務節點和選播路由器，并部署一定的選播代理節點來共同構成底層的覆蓋層，即選播服務域層。選播代理節點負責管理應用層選播服務器節點的狀態信息，選播路由器負責獲取網絡層的拓撲信息。在選播服務域內，將選播代理節點與能夠獲得網絡層物理拓撲的選播路由器協同起來完成域內協同選播。

在每個選播服務域內選取一個域頭節點（Domain Head，DH）來收集自身選播服務域內的信息，并對其進行管理。為了防止域頭節點發生故障，在每個選播服務域內選取部分性能相對較高、運行穩定的選播服務代理節點，并隨機選取兩個節點分別作為域頭節點和后備節點。將域頭節點和選播服務域層的選播路由器提取出來，通過虛擬鏈路構成域間覆蓋層，也就是匯聚層。在匯聚層，將域間獲得的物理拓撲信息的選播路由器與應用層服務域狀態信息的域頭節點協同起來共同完成域間協同選播。

綜上所述，基于Overlay Network的協同選播覆蓋層的構造過程體現了分層的思想。覆蓋層的底層是由選播服務器、選播路由器和選播代理節點共同構成的選播服務域層，頂層是由各個選播服務域的域頭節點和選播服務器共同構成的匯聚層。

2 協同選播服路由機制

基于Overlay Network的協同選播體系結構從域內和域間兩方面提出了協同選播機制。在對協同選播服路由機制進行闡述之前，需引入以下幾個概念：①選播服務節點。它是指能夠提供選播服務的節點。將提供同一類服務的節點構成一個選播組，其中的節點稱為選播組成員，這些節點共享一個Anycast地址。②服務節點利用率。它是指節點負載與承載能力的比值。節點的承載能力是指其綜合處理能力，可以根據這個指標有效均衡服務器的負載。③協同服務域。它是指提供同一種選播服務的節點所在的選播服務域的集合。④服務域利用率。它是指選播服務域內所有提供同類選播服務的節點的總負載與總承載能力的比值。根據服務域利用率，可以在選播服務域之間進行負載的均衡調整。

對于一個選播服務節點而言，可能提供的服務類型是多種類的，對應多個Anycast地址，且分屬于不同的協同服務域。將基于Overlay Network的協同選播覆蓋網中所有的選播服務域根據服務類型劃分成不同的協同服務域來提供選播服務。這樣，既充分發揮了網絡層的高效性和應用層的靈活性，又節約了在每個選播服務域內的查找時間，提高了選播服務的效率。

圖2所示為基于Overlay Network的協同選播機制模型，其中，圖（a）所示為協同選播機制的模型（從域內角度和域間角度來看），圖2（b）所示為協同選播機制服務過程。假設整個網絡有7個選播服務域，即Domain1～Domain7，共存的三類選播服務分別為A，B和C.其中，能提供同一類服務的構成一個協同服務域，而Domain6可以同時提供A和B兩類服務，因此它分屬于兩個協同服務域。如果Domain1、Domain3、Domain6和Domain7內都存在能提供A類選播服務的節點，當一個用戶發送選播請求要獲得A類服務時，基于Overlay Network的協同選播機制就要在所有能提供此類服務的域內。也就是說，可以在由A類服務構成的協同服務域內找到相對于此用戶最優的選播服務節點和到這個節點的最優路徑來提供選播服務。同理，Domain4、Domain5和Domain6構成B類選播的協同服務域，Domain2和Domain3構成C類選播的協同服務域。

（a）協同選播服務機制的模型圖

（b）協同選播機制服務過程示意圖

3 基于Petri網的協同選播路由機制驗證

Petri網是一種數學和圖形化工具，具有準確的語義定義，并且直觀、易用。Petri網的概念是于1962年德國科學家Carl Adam Petri提出的，主要用于對異步并發機制的描述。從形式上看，Petri網的結構就是一個沒有孤立節點的有向二分圖，它為描述異步并發關系提供了豐富多樣的分析手段。鑒于此，本文采用Petri網的形式化描述語言來描述基于Overlay Netwrok的協同選播機制，并對其正確性和完備性進行驗證。

3.1 描述

根據基于Overlay Network的協同選播服務機制，得到圖3所示的Petri網模型。這里只分析服務請求節點和代理節點、選播路由器和域頭節點的交互情況。由于對于任意一個用戶或者機制中任意一個節點而言，工作過程是完全相同且相互獨立的，因此，對于整個系統而言，只要一個用戶節點在本系統中的運行是正確的，那么該機制就是正確的。在存在多個服務請求節點的情況下，庫所P0的初始標記個數和容量為用戶節點的總量，但整個Petri網的性質無任何變化。另外，域頭節點與其他代理節點的細節行為對本地用戶發送服務請求、協同選播路由和應答請求的整個機制沒有影響，因而，為了簡化Petri網，沒有描述這些實體的細節行為。

務，T6 和T7的觸發取決于該類型的選播協同服務域能否提供此類選播服務，T10、T11 和T12的觸發取決于選播運行過程中是否會出現服務器故障或者鏈路斷開的情況，T13和T14、T15和T16、T17和T18的觸發取決于選播服務節點或者選播服務域是否發生過載。表1所示為Petri網庫所和變遷的定義。

3.2 驗證

雖然庫所變遷圖能夠直觀地顯示基于Overlay Network的協同選播機制中實體間的交互，但是，多個實體間復雜的異步交互過程可能會產生無法預料的后果。因此，本文進一步采用Petri網分析方法對此機制的正確性和完備性進行驗證。

本文對Petri網系統的正確性和完備性的驗證采用可達圖法?；诳蛇_圖的列舉法是通過構建系統可達圖，展現每個網和它們之間的單個變遷的發生過程。如果Petri網系統是有界的，則對應的可達圖就是有限的，并且其各種性質極易被證明。我們采用可達圖法構建圖3所示的Petri網系統的可達圖，得出如圖4所示的基于Overlay Network協同選播過程的Petri網可達圖。借助可達圖，可以從理論上驗證系統的正確性和完備性。該可達圖包含了系統在初始條件下所能達到的所有系統標識和系統變遷序列。

圖4中，帶有下劃線的狀態表示與初始狀態重合形成圈，為了清楚起見，沒有直接用弧連接?；贠verlay Network的協同選播機制的正確運行包括以下幾種情況：①選播請求用戶在本地選播代理節點找到了選播服務成員，然后將選播服務節點的信息返回給用戶，兩者開始通信，在Petri網中的變遷實施序列為（T0，T2，T13，T8，T10）。如果當前選播服務節點發生故障，則可通過域內路徑進行動態調整，將選播服務重新定位到新的服務節點。此時的變遷實施序列為（T0，T2，T14，T8，T10）。②用戶在本地選播代理節點未找到此類選播服務，則本地代理節點將請求發送給其他代理節點，域頭節點在本選播服務域內進行服務查找，在Petri網中的變遷實施序列為（T0，T1，T3，T15，T5）。如果當前服務節點發生故障，則域頭節點在該選播服務域內進行動態調整，為用戶重新選擇節點，在Petri網中的變遷實施序列為（T0，T1，T3，T16，T5）。③域頭節點在本選播服務域內未找到合適的選播服務節點，則它將消息發送到協同選播服務域的其他域頭節點，根據域間最優路徑，選出

一個服務節點返回給用戶。此時的變遷實施序列為（T0，T1，T4，T6，T17，T9，T12）。如果通過協同服務域間所選的服務節點或者鏈路發生故障，則通過路徑動態調整將選播服務請求重新定位到新的服務節點，在Petri網中的變遷實施序列為（T0，T1，T4，T6，T18，T9，T12）。

由此可見，上述變遷序列均在圖4所示的可達圖中出現，且分別位于初始狀態節點下的不同基本圈中，說明這些變遷序列是可反復無限次實施的。同時，從圖4中還可以發現，所有可能狀態從初始狀態開始都是可達的，且都處于不同的基本圈中，因此，不可能出現死鎖，也不會出現死循環，進而得出系統的各種行為邏輯都是正確的。各庫所的Token 數量均不超過1，因此Petri網是有界的，從而保證了系統資源的有限性。在多個用戶請求資源的情況下，由于用戶每次只能提交一個資源請求，即庫所P0 的初始Token 數量及其容量均限定為1.由于各弧的權重均為1，只要用戶數量有限，各庫所Token 的最大數量也不會超過用戶數量，因此，系統是有界的。由以上分析可知，所有變遷序列一定會發生變化，且由Petri 網的有界性保證了資源消耗的有限性，因此，系統模型是正確的。另外，從可達圖還可以看出，系統不論處于何種狀態，都能返回到初始狀態，而其所有變遷均可無限次觸發，因此，系統不會無限制地陷入某種局部循環狀態，也無“饑餓”現象出現，更不會發生死鎖或活鎖。同時，Petri網系統的可達狀態均是合理、有效的，因此系統模型是完備的。

4 結論與展望

本文在充分發揮應用層選播的靈活性和網絡層選播的高效性的前提下，提出了基于Overlay Network的協同選播覆蓋網絡體系結構，在此基礎上，提出了基于Overlay Network的協同選播服務機制，并對協同選播的過程進行了詳細描述，最后利用Petri網理論對協同選播機制進行了形式化描述，通過Petri網可達圖對系統模型的正確性和完備性進行了驗證。

參考文獻

[1]Jun zhi，Jianyong Liu，Kai chen.Coures Optimization on Based on Improved Immune Genetic Algorithm[J].Computational Sciences and Optimization，2009（2）.

[2]尹海衛，王慶生.利用anycast技術實現MANET與IPv6網絡互聯[J].計算機應用與軟件，2013，30（3）.

[3]張燕梅.基于覆蓋網絡的服務組合關鍵技術研究[D].北京：中國礦業大學，2009.

[4]F.Y.Wang，YGao，M.C.Zhou.A modified reachability tree approach to analysis of unbounded Petrinets[J].IEEE transactions on systems，man and cybermetric-Part B：metrics，2004，34（1）.

[5]魯法明.Petri網的可達性分析的代數方法[D].泰安：山東科技大學，2007.

[6]曹陽，張維明，沙基昌，等.Petri網在通信網絡仿真建模中的應用[J].計算機仿真，2001（5）.

[7]Angela Adamyan，David He.Sequential Failure Analysis Using Counters of Petri Net modes[J].IEEE Transaction on Systems，Man and Cybernettics-Part：Systems and Humans，2003，33（1）.

[8]P.Ramachandran.A sufficient condition of reachablitiy in a general Petrinet[J].Discrete event dynamic： theory and applications，2004（14）.

[9]王德志，余鎮危.基于Petri網的PIM-SM協議建模與分析[J].計算機工程與應用，2007，43（3）.

〔編輯：劉曉芳〕