基于Overlay Network協(xié)同選播通信機(jī)制的研究

張園園

摘 要：應(yīng)用層選播因不了解物理網(wǎng)絡(luò)拓?fù)涠狈Ω咝裕W(wǎng)絡(luò)層選播因不了解服務(wù)器本身的負(fù)載而缺乏靈活性。在充分發(fā)揮應(yīng)用層的靈活性和網(wǎng)絡(luò)層的高效性的基礎(chǔ)上，提出了基于Overlay Network的協(xié)同選播網(wǎng)絡(luò)體系結(jié)構(gòu)，給出了覆蓋層的構(gòu)造方法，并從域內(nèi)和域間兩方面對(duì)協(xié)同選播機(jī)制進(jìn)行了闡述，最后利用Petri網(wǎng)理論對(duì)相關(guān)機(jī)制進(jìn)行了形式化描述，且對(duì)其正確性和完備性進(jìn)行了驗(yàn)證。

關(guān)鍵詞：Overlay Network；協(xié)同選播機(jī)制；負(fù)載均衡；Petri網(wǎng)

中圖分類號(hào)：TP393.09 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2016.05.020

選播Anycast（one-to-one-of-many）是在面向下一代網(wǎng)絡(luò)時(shí)，為了解決負(fù)載均衡和提升服務(wù)可用性而提出的。一個(gè)選播地址標(biāo)識(shí)不同節(jié)點(diǎn)的多個(gè)網(wǎng)絡(luò)接口，如果一個(gè)報(bào)文被傳送到一個(gè)選播地址上，那么它最終被傳送到具有該地址標(biāo)識(shí)的、根據(jù)路由協(xié)議距離度量“最近”的一個(gè)接口上。

傳統(tǒng)的選播服務(wù)是在應(yīng)用層或網(wǎng)絡(luò)層上實(shí)現(xiàn)的，在網(wǎng)絡(luò)層上實(shí)現(xiàn)選播具有低時(shí)延和低開銷的優(yōu)勢(shì)。但是，由于網(wǎng)絡(luò)層不了解提供選播服務(wù)節(jié)點(diǎn)的信息和負(fù)載狀況，可能會(huì)選擇一個(gè)負(fù)載過(guò)重的節(jié)點(diǎn)來(lái)為用戶提供服務(wù)，這樣反而降低了選播通信的效率；應(yīng)用層則通過(guò)外部實(shí)體來(lái)實(shí)現(xiàn)選播，很容易了解到服務(wù)節(jié)點(diǎn)當(dāng)前的狀態(tài)和負(fù)載信息，可以非常便捷地選擇一個(gè)相對(duì)空閑的服務(wù)節(jié)點(diǎn)來(lái)提供服務(wù)。但是，由于應(yīng)用層不了解底層網(wǎng)絡(luò)拓?fù)湫畔?，所選出的節(jié)點(diǎn)很可能距離用戶很遠(yuǎn)，這樣反而不利于其靈活性優(yōu)勢(shì)的發(fā)揮?，F(xiàn)有的一些研究已經(jīng)開始考慮在應(yīng)用層實(shí)現(xiàn)選播時(shí)加入反映物理網(wǎng)絡(luò)的因素或者在網(wǎng)絡(luò)層加入反映服務(wù)節(jié)點(diǎn)信息的因素，繼而出現(xiàn)了許多新型網(wǎng)絡(luò)架構(gòu)。盡管如此，應(yīng)用層和網(wǎng)絡(luò)層的關(guān)系仍沒(méi)有達(dá)到合理的協(xié)調(diào)。為此，本文提出基于Overlay Network的協(xié)同選播網(wǎng)絡(luò)體系結(jié)構(gòu)，將應(yīng)用層和網(wǎng)絡(luò)層各自的優(yōu)勢(shì)很好地結(jié)合起來(lái)，以期提高選播服務(wù)的質(zhì)量，達(dá)到大規(guī)模部署和應(yīng)用的目的。

1 基于Overlay Network的協(xié)同選播網(wǎng)絡(luò)體系結(jié)構(gòu)

為了充分發(fā)揮應(yīng)用層的靈活性和網(wǎng)絡(luò)層的高效性優(yōu)勢(shì)，并且實(shí)現(xiàn)協(xié)同選播，本文提出了基于Overlay Network的協(xié)同選播網(wǎng)絡(luò)體系結(jié)構(gòu)。這一網(wǎng)絡(luò)體系結(jié)構(gòu)的建立，需要在應(yīng)用層和網(wǎng)絡(luò)層之間構(gòu)造虛擬的協(xié)同選播覆蓋層?？紤]到實(shí)際可行性等因素，本文提出基于選播服務(wù)域?qū)印獏R聚層的分層協(xié)同選播覆蓋層模型。圖1所示為協(xié)同選播Overlay Network拓?fù)浣Y(jié)構(gòu)模型。

為了更好地實(shí)現(xiàn)協(xié)同選播，使用戶節(jié)點(diǎn)都能與其距離最近、最優(yōu)的選播服務(wù)節(jié)點(diǎn)通信，同時(shí)解決選播存在的交錯(cuò)服務(wù)問(wèn)題，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)重新進(jìn)行了劃分，提出了一種以選播服務(wù)器節(jié)點(diǎn)為中心的區(qū)域劃分方法，并將劃分后的區(qū)域稱為“選播服務(wù)域（Anycast Service Domain，ASD）”，在每個(gè)域內(nèi)可能存在一種或者多種類型的選播服務(wù)。

在每個(gè)選播服務(wù)域內(nèi)，通過(guò)提取選播服務(wù)節(jié)點(diǎn)和選播路由器，并部署一定的選播代理節(jié)點(diǎn)來(lái)共同構(gòu)成底層的覆蓋層，即選播服務(wù)域?qū)?。選播代理節(jié)點(diǎn)負(fù)責(zé)管理應(yīng)用層選播服務(wù)器節(jié)點(diǎn)的狀態(tài)信息，選播路由器負(fù)責(zé)獲取網(wǎng)絡(luò)層的拓?fù)湫畔?。在選播服務(wù)域內(nèi)，將選播代理節(jié)點(diǎn)與能夠獲得網(wǎng)絡(luò)層物理拓?fù)涞倪x播路由器協(xié)同起來(lái)完成域內(nèi)協(xié)同選播。

在每個(gè)選播服務(wù)域內(nèi)選取一個(gè)域頭節(jié)點(diǎn)（Domain Head，DH）來(lái)收集自身選播服務(wù)域內(nèi)的信息，并對(duì)其進(jìn)行管理。為了防止域頭節(jié)點(diǎn)發(fā)生故障，在每個(gè)選播服務(wù)域內(nèi)選取部分性能相對(duì)較高、運(yùn)行穩(wěn)定的選播服務(wù)代理節(jié)點(diǎn)，并隨機(jī)選取兩個(gè)節(jié)點(diǎn)分別作為域頭節(jié)點(diǎn)和后備節(jié)點(diǎn)。將域頭節(jié)點(diǎn)和選播服務(wù)域?qū)拥倪x播路由器提取出來(lái)，通過(guò)虛擬鏈路構(gòu)成域間覆蓋層，也就是匯聚層。在匯聚層，將域間獲得的物理拓?fù)湫畔⒌倪x播路由器與應(yīng)用層服務(wù)域狀態(tài)信息的域頭節(jié)點(diǎn)協(xié)同起來(lái)共同完成域間協(xié)同選播。

綜上所述，基于Overlay Network的協(xié)同選播覆蓋層的構(gòu)造過(guò)程體現(xiàn)了分層的思想。覆蓋層的底層是由選播服務(wù)器、選播路由器和選播代理節(jié)點(diǎn)共同構(gòu)成的選播服務(wù)域?qū)?，頂層是由各個(gè)選播服務(wù)域的域頭節(jié)點(diǎn)和選播服務(wù)器共同構(gòu)成的匯聚層。

2 協(xié)同選播服路由機(jī)制

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

對(duì)于一個(gè)選播服務(wù)節(jié)點(diǎn)而言，可能提供的服務(wù)類型是多種類的，對(duì)應(yīng)多個(gè)Anycast地址，且分屬于不同的協(xié)同服務(wù)域。將基于Overlay Network的協(xié)同選播覆蓋網(wǎng)中所有的選播服務(wù)域根據(jù)服務(wù)類型劃分成不同的協(xié)同服務(wù)域來(lái)提供選播服務(wù)。這樣，既充分發(fā)揮了網(wǎng)絡(luò)層的高效性和應(yīng)用層的靈活性，又節(jié)約了在每個(gè)選播服務(wù)域內(nèi)的查找時(shí)間，提高了選播服務(wù)的效率。

圖2所示為基于Overlay Network的協(xié)同選播機(jī)制模型，其中，圖（a）所示為協(xié)同選播機(jī)制的模型（從域內(nèi)角度和域間角度來(lái)看），圖2（b）所示為協(xié)同選播機(jī)制服務(wù)過(guò)程。假設(shè)整個(gè)網(wǎng)絡(luò)有7個(gè)選播服務(wù)域，即Domain1～Domain7，共存的三類選播服務(wù)分別為A，B和C.其中，能提供同一類服務(wù)的構(gòu)成一個(gè)協(xié)同服務(wù)域，而Domain6可以同時(shí)提供A和B兩類服務(wù)，因此它分屬于兩個(gè)協(xié)同服務(wù)域。如果Domain1、Domain3、Domain6和Domain7內(nèi)都存在能提供A類選播服務(wù)的節(jié)點(diǎn)，當(dāng)一個(gè)用戶發(fā)送選播請(qǐng)求要獲得A類服務(wù)時(shí)，基于Overlay Network的協(xié)同選播機(jī)制就要在所有能提供此類服務(wù)的域內(nèi)。也就是說(shuō)，可以在由A類服務(wù)構(gòu)成的協(xié)同服務(wù)域內(nèi)找到相對(duì)于此用戶最優(yōu)的選播服務(wù)節(jié)點(diǎn)和到這個(gè)節(jié)點(diǎn)的最優(yōu)路徑來(lái)提供選播服務(wù)。同理，Domain4、Domain5和Domain6構(gòu)成B類選播的協(xié)同服務(wù)域，Domain2和Domain3構(gòu)成C類選播的協(xié)同服務(wù)域。

（a）協(xié)同選播服務(wù)機(jī)制的模型圖

（b）協(xié)同選播機(jī)制服務(wù)過(guò)程示意圖

3 基于Petri網(wǎng)的協(xié)同選播路由機(jī)制驗(yàn)證

Petri網(wǎng)是一種數(shù)學(xué)和圖形化工具，具有準(zhǔn)確的語(yǔ)義定義，并且直觀、易用。Petri網(wǎng)的概念是于1962年德國(guó)科學(xué)家Carl Adam Petri提出的，主要用于對(duì)異步并發(fā)機(jī)制的描述。從形式上看，Petri網(wǎng)的結(jié)構(gòu)就是一個(gè)沒(méi)有孤立節(jié)點(diǎn)的有向二分圖，它為描述異步并發(fā)關(guān)系提供了豐富多樣的分析手段。鑒于此，本文采用Petri網(wǎng)的形式化描述語(yǔ)言來(lái)描述基于Overlay Netwrok的協(xié)同選播機(jī)制，并對(duì)其正確性和完備性進(jìn)行驗(yàn)證。

3.1 描述

根據(jù)基于Overlay Network的協(xié)同選播服務(wù)機(jī)制，得到圖3所示的Petri網(wǎng)模型。這里只分析服務(wù)請(qǐng)求節(jié)點(diǎn)和代理節(jié)點(diǎn)、選播路由器和域頭節(jié)點(diǎn)的交互情況。由于對(duì)于任意一個(gè)用戶或者機(jī)制中任意一個(gè)節(jié)點(diǎn)而言，工作過(guò)程是完全相同且相互獨(dú)立的，因此，對(duì)于整個(gè)系統(tǒng)而言，只要一個(gè)用戶節(jié)點(diǎn)在本系統(tǒng)中的運(yùn)行是正確的，那么該機(jī)制就是正確的。在存在多個(gè)服務(wù)請(qǐng)求節(jié)點(diǎn)的情況下，庫(kù)所P0的初始標(biāo)記個(gè)數(shù)和容量為用戶節(jié)點(diǎn)的總量，但整個(gè)Petri網(wǎng)的性質(zhì)無(wú)任何變化。另外，域頭節(jié)點(diǎn)與其他代理節(jié)點(diǎn)的細(xì)節(jié)行為對(duì)本地用戶發(fā)送服務(wù)請(qǐng)求、協(xié)同選播路由和應(yīng)答請(qǐng)求的整個(gè)機(jī)制沒(méi)有影響，因而，為了簡(jiǎn)化Petri網(wǎng)，沒(méi)有描述這些實(shí)體的細(xì)節(jié)行為。

務(wù)，T6 和T7的觸發(fā)取決于該類型的選播協(xié)同服務(wù)域能否提供此類選播服務(wù)，T10、T11 和T12的觸發(fā)取決于選播運(yùn)行過(guò)程中是否會(huì)出現(xiàn)服務(wù)器故障或者鏈路斷開的情況，T13和T14、T15和T16、T17和T18的觸發(fā)取決于選播服務(wù)節(jié)點(diǎn)或者選播服務(wù)域是否發(fā)生過(guò)載。表1所示為Petri網(wǎng)庫(kù)所和變遷的定義。

3.2 驗(yàn)證

雖然庫(kù)所變遷圖能夠直觀地顯示基于Overlay Network的協(xié)同選播機(jī)制中實(shí)體間的交互，但是，多個(gè)實(shí)體間復(fù)雜的異步交互過(guò)程可能會(huì)產(chǎn)生無(wú)法預(yù)料的后果。因此，本文進(jìn)一步采用Petri網(wǎng)分析方法對(duì)此機(jī)制的正確性和完備性進(jìn)行驗(yàn)證。

本文對(duì)Petri網(wǎng)系統(tǒng)的正確性和完備性的驗(yàn)證采用可達(dá)圖法?；诳蛇_(dá)圖的列舉法是通過(guò)構(gòu)建系統(tǒng)可達(dá)圖，展現(xiàn)每個(gè)網(wǎng)和它們之間的單個(gè)變遷的發(fā)生過(guò)程。如果Petri網(wǎng)系統(tǒng)是有界的，則對(duì)應(yīng)的可達(dá)圖就是有限的，并且其各種性質(zhì)極易被證明。我們采用可達(dá)圖法構(gòu)建圖3所示的Petri網(wǎng)系統(tǒng)的可達(dá)圖，得出如圖4所示的基于Overlay Network協(xié)同選播過(guò)程的Petri網(wǎng)可達(dá)圖。借助可達(dá)圖，可以從理論上驗(yàn)證系統(tǒng)的正確性和完備性。該可達(dá)圖包含了系統(tǒng)在初始條件下所能達(dá)到的所有系統(tǒng)標(biāo)識(shí)和系統(tǒng)變遷序列。

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

一個(gè)服務(wù)節(jié)點(diǎn)返回給用戶。此時(shí)的變遷實(shí)施序列為（T0，T1，T4，T6，T17，T9，T12）。如果通過(guò)協(xié)同服務(wù)域間所選的服務(wù)節(jié)點(diǎn)或者鏈路發(fā)生故障，則通過(guò)路徑動(dòng)態(tài)調(diào)整將選播服務(wù)請(qǐng)求重新定位到新的服務(wù)節(jié)點(diǎn)，在Petri網(wǎng)中的變遷實(shí)施序列為（T0，T1，T4，T6，T18，T9，T12）。

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

4 結(jié)論與展望

本文在充分發(fā)揮應(yīng)用層選播的靈活性和網(wǎng)絡(luò)層選播的高效性的前提下，提出了基于Overlay Network的協(xié)同選播覆蓋網(wǎng)絡(luò)體系結(jié)構(gòu)，在此基礎(chǔ)上，提出了基于Overlay Network的協(xié)同選播服務(wù)機(jī)制，并對(duì)協(xié)同選播的過(guò)程進(jìn)行了詳細(xì)描述，最后利用Petri網(wǎng)理論對(duì)協(xié)同選播機(jī)制進(jìn)行了形式化描述，通過(guò)Petri網(wǎng)可達(dá)圖對(duì)系統(tǒng)模型的正確性和完備性進(jìn)行了驗(yàn)證。

參考文獻(xiàn)

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

[2]尹海衛(wèi)，王慶生.利用anycast技術(shù)實(shí)現(xiàn)MANET與IPv6網(wǎng)絡(luò)互聯(lián)[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（3）.

[3]張燕梅.基于覆蓋網(wǎng)絡(luò)的服務(wù)組合關(guān)鍵技術(shù)研究[D].北京：中國(guó)礦業(yè)大學(xué)，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網(wǎng)的可達(dá)性分析的代數(shù)方法[D].泰安：山東科技大學(xué)，2007.

[6]曹陽(yáng)，張維明，沙基昌，等.Petri網(wǎng)在通信網(wǎng)絡(luò)仿真建模中的應(yīng)用[J].計(jì)算機(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]王德志，余鎮(zhèn)危.基于Petri網(wǎng)的PIM-SM協(xié)議建模與分析[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（3）.

〔編輯：劉曉芳〕