曹生林，柳立言

(寧夏師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,寧夏 固原 756099)

可信可控網(wǎng)絡(luò)中的一致性視圖構(gòu)建機(jī)制*

曹生林，柳立言

(寧夏師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,寧夏 固原 756099)

在可信可控網(wǎng)絡(luò)中利用多個(gè)控制節(jié)點(diǎn)對(duì)AS進(jìn)行聯(lián)合控制，容易造成多個(gè)控制節(jié)點(diǎn)在網(wǎng)絡(luò)控制過程中持有的AS視圖不一致問題。針對(duì)該問題，在可信可控網(wǎng)絡(luò)模型的基礎(chǔ)上提出了基于選舉算法的AS內(nèi)一致性視圖構(gòu)建機(jī)制，該機(jī)制首先基于選舉算法選舉出主控制節(jié)點(diǎn)，然后主控制節(jié)點(diǎn)根據(jù)AS內(nèi)各個(gè)控制節(jié)點(diǎn)的負(fù)載，將視圖構(gòu)建任務(wù)分配給負(fù)載最低的控制節(jié)點(diǎn)負(fù)責(zé)構(gòu)建視圖，并利用主控制節(jié)點(diǎn)的時(shí)間對(duì)生成的視圖的版本進(jìn)行界定，從而避免了多個(gè)控制節(jié)點(diǎn)獨(dú)自構(gòu)建視圖造成的視圖混亂問題。仿真實(shí)驗(yàn)的結(jié)果表明，所提出的一致性視圖構(gòu)建機(jī)制具有良好的性能。

可信可控網(wǎng)絡(luò)模型;選舉算法;一致性視圖

1 引言

可信可控網(wǎng)絡(luò)將網(wǎng)絡(luò)控制邏輯的計(jì)算集中到控制節(jié)點(diǎn)CN(Control Node)上，以便對(duì)網(wǎng)絡(luò)建立統(tǒng)一的網(wǎng)絡(luò)控制層面。但是，由于單一控制節(jié)點(diǎn)容易導(dǎo)致性能瓶頸和單點(diǎn)故障問題，為了提高可信可控網(wǎng)絡(luò)的可擴(kuò)展性，在自治系統(tǒng)AS(Autonomous System)內(nèi)采用多控制節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行協(xié)同控制已成為相關(guān)研究者的共識(shí)[1,2]。

雖然在可信可控網(wǎng)絡(luò)中多個(gè)控制節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)進(jìn)行協(xié)同控制的方法能夠有效地提高可信可控網(wǎng)絡(luò)的可擴(kuò)展性和魯棒性，但是也給可信可控網(wǎng)絡(luò)帶來了新的視圖一致性問題：在可信可控網(wǎng)絡(luò)中，每個(gè)控制節(jié)點(diǎn)在控制域內(nèi)維護(hù)一個(gè)控制信息數(shù)據(jù)庫來保存本控制域的控制信息，而在每個(gè)控制節(jié)點(diǎn)上又運(yùn)行著多個(gè)網(wǎng)絡(luò)控制機(jī)制，由于網(wǎng)絡(luò)延遲以及網(wǎng)絡(luò)震蕩性等原因，如果多個(gè)控制節(jié)點(diǎn)的多個(gè)控制機(jī)制都需要自己構(gòu)建AS的網(wǎng)絡(luò)視圖，很容易造成視圖信息的不一致，從而導(dǎo)致不同網(wǎng)絡(luò)控制機(jī)制對(duì)網(wǎng)絡(luò)的控制策略產(chǎn)生矛盾，影響網(wǎng)絡(luò)的正常運(yùn)行。

為了便于說明多個(gè)控制節(jié)點(diǎn)網(wǎng)絡(luò)視圖可能不一致的問題，我們給出了一個(gè)示例，如圖1所示，控制節(jié)點(diǎn)CN1和CN3分別在t1和t2時(shí)刻開始構(gòu)建各自的網(wǎng)絡(luò)視圖，分別向除自身以外的所有控制節(jié)點(diǎn)發(fā)送其他控制域的視圖請(qǐng)求。而在CN1和CN3構(gòu)建網(wǎng)絡(luò)視圖的過程中，CN4負(fù)責(zé)的控制域的網(wǎng)絡(luò)狀態(tài)在t3時(shí)刻發(fā)生了變化，由于CN1與CN4的網(wǎng)絡(luò)延遲較長(zhǎng)，使得CN4給CN1返回的網(wǎng)絡(luò)視圖發(fā)生在t3以后，而由于CN3與CN4的網(wǎng)絡(luò)延遲較短，使得CN3在t3時(shí)刻之前就返回了其局部視圖，這就會(huì)造成CN1在t5得到的視圖與CN3在t4時(shí)刻得到的視圖不一致。而由于CN3與CN2間的通信延遲，造成CN3得到視圖的時(shí)刻t4晚于CN1得到視圖的時(shí)刻t5，這就造成生成時(shí)刻較晚的視圖反而不如生成時(shí)刻較早的視圖準(zhǔn)確性高。

Figure 1 Network view constructed by control nodes respectively

從上述示例可以看出，由每個(gè)控制節(jié)點(diǎn)單獨(dú)生成視圖會(huì)造成視圖的一致性問題，主要表現(xiàn)為兩個(gè)方面：

(1)控制節(jié)點(diǎn)的視圖與網(wǎng)絡(luò)真實(shí)狀態(tài)不一致。由于分布式網(wǎng)絡(luò)環(huán)境下傳輸時(shí)延和計(jì)算耗費(fèi)時(shí)間等原因，很難構(gòu)造與網(wǎng)絡(luò)實(shí)際狀態(tài)嚴(yán)格吻合的視圖，網(wǎng)絡(luò)視圖與網(wǎng)絡(luò)實(shí)際狀態(tài)必然會(huì)存在一個(gè)時(shí)間差。為了解決這一問題，一般采用不斷更新視圖版本的方法來反映網(wǎng)絡(luò)的實(shí)際狀態(tài)。因此，這個(gè)問題可以歸結(jié)為，多個(gè)控制節(jié)點(diǎn)組成的分布式網(wǎng)絡(luò)環(huán)境下，缺少全局時(shí)間對(duì)網(wǎng)絡(luò)視圖進(jìn)行版本界定，造成網(wǎng)絡(luò)視圖版本前后不一致的問題。如圖1給出的例子中，CN3在t4時(shí)刻得到的視圖不如CN1在t5(t4>t5)時(shí)刻得到的視圖準(zhǔn)確，就是新老視圖的不一致性問題。

(2)多個(gè)控制節(jié)點(diǎn)的視圖互相矛盾。由于不同控制節(jié)點(diǎn)獨(dú)自構(gòu)建視圖，造成視圖來源混雜，從而導(dǎo)致網(wǎng)絡(luò)視圖混亂，很難判斷它們所構(gòu)建視圖的正確性。如圖1給出的例子中，CN3得到的視圖沒有反映t3時(shí)刻以后CN4對(duì)應(yīng)的控制域內(nèi)的網(wǎng)絡(luò)狀態(tài)變化，與CN3得到的視圖矛盾。

因此，為了解決上述的視圖版本前后不一致問題和不同控制節(jié)點(diǎn)視圖不一致問題，本文給出了可信可控網(wǎng)絡(luò)中的一致性視圖構(gòu)建機(jī)制，該機(jī)制主要由主控制節(jié)點(diǎn)選舉算法和基于選舉的一致性視圖構(gòu)建算法兩部分組成。其主要思想是，當(dāng)網(wǎng)絡(luò)控制機(jī)制提出一致性視圖構(gòu)建需求時(shí)，其所在的控制節(jié)點(diǎn)將任務(wù)提交給選舉算法產(chǎn)生主控制節(jié)點(diǎn)；然后主控制節(jié)點(diǎn)根據(jù)控制節(jié)點(diǎn)的優(yōu)先級(jí)將任務(wù)分配給優(yōu)先級(jí)最高的節(jié)點(diǎn)處理，負(fù)責(zé)處理的控制節(jié)點(diǎn)組織多個(gè)控制節(jié)點(diǎn)基于合作的方式構(gòu)建一致性視圖后，將最終的處理結(jié)果發(fā)送給主控制節(jié)點(diǎn)；主控制節(jié)點(diǎn)再將處理結(jié)果發(fā)送給請(qǐng)求方。這保證了多個(gè)控制節(jié)點(diǎn)的網(wǎng)絡(luò)視圖源一致，解決了多個(gè)控制節(jié)點(diǎn)的視圖不一致問題，并且通過利用主控制節(jié)點(diǎn)的時(shí)間戳作為版本號(hào)的方式，避免了網(wǎng)絡(luò)視圖前后版本的不一致性。

2 AS內(nèi)的主控制節(jié)點(diǎn)選舉算法

基于選舉算法的一致性視圖構(gòu)建機(jī)制主要通過為AS選出主控制節(jié)點(diǎn)的方法為多個(gè)控制節(jié)點(diǎn)的網(wǎng)絡(luò)視圖提供統(tǒng)一的版本界定方法和視圖來源。在本節(jié)中，我們將根據(jù)可信可控網(wǎng)絡(luò)的特點(diǎn)，為多個(gè)控制節(jié)點(diǎn)構(gòu)建一個(gè)主控制節(jié)點(diǎn)選舉算法。

選舉算法是分布式系統(tǒng)中常用的算法，其從進(jìn)程集合中選出一個(gè)特定的進(jìn)程來對(duì)特定任務(wù)進(jìn)行處理，以實(shí)現(xiàn)多個(gè)進(jìn)程之間的協(xié)作。選舉算法應(yīng)用的領(lǐng)域很多，如群服務(wù)器、重復(fù)數(shù)據(jù)更新、負(fù)載均衡、應(yīng)急恢復(fù)以及互斥等方面。根據(jù)不同網(wǎng)絡(luò)的拓?fù)漕愋?，人們提出了不同的分布式選舉算法[3]。一般情況下選舉過程可以分成兩個(gè)階段：(1)選擇具有最高優(yōu)先級(jí)的優(yōu)勝者；(2)通知其他參與者誰是優(yōu)勝者。兩個(gè)階段都需要在系統(tǒng)中發(fā)布進(jìn)程的ID，因此通過進(jìn)程之間的通信方式可以將選舉算法分成兩種：面向廣播網(wǎng)的選舉算法[4]和面向存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)的選舉算法。其中面向存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)的選舉算法，又有面向單向環(huán)的選舉算法[5～7]、面向雙環(huán)的選舉算法[8]、面向完全圖的選舉算法[9]和面向弦環(huán)的選舉算法[10]。

根據(jù)上述在分布式網(wǎng)絡(luò)環(huán)境下的選舉算法，我們針對(duì)可信可控網(wǎng)絡(luò)中視圖構(gòu)建的一致性需求和多個(gè)控制節(jié)點(diǎn)的負(fù)載均衡，基于bully算法[11]設(shè)計(jì)了可信可控網(wǎng)絡(luò)中的主控制節(jié)點(diǎn)選舉算法和基于合作的視圖構(gòu)建算法。

由于在可信可控網(wǎng)絡(luò)中每個(gè)控制節(jié)點(diǎn)只有一個(gè)參與選舉的進(jìn)程，為了便于理解，我們?cè)诤笪闹薪y(tǒng)一將參與選舉的對(duì)象確定為AS內(nèi)的控制節(jié)點(diǎn)。

2.1 優(yōu)先級(jí)定義

為了統(tǒng)一各個(gè)CN負(fù)載的評(píng)價(jià)標(biāo)準(zhǔn)，我們給出了一個(gè)以請(qǐng)求需要等待的時(shí)間作為衡量標(biāo)準(zhǔn)的方法，并選擇響應(yīng)當(dāng)前請(qǐng)求所需要的時(shí)間最短的CN作為處理當(dāng)前請(qǐng)求的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)對(duì)當(dāng)前請(qǐng)求響應(yīng)時(shí)間的計(jì)算方法如式(1)所示：

Ti=p*λi

(1)

其中，p表示在節(jié)點(diǎn)i上排隊(duì)的任務(wù)數(shù)，λi表示節(jié)點(diǎn)i處理一個(gè)任務(wù)所花費(fèi)的平均時(shí)間。

利用Ti我們定義每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)，如式(2)所示：

(2)

由式(2)可知，節(jié)點(diǎn)的響應(yīng)時(shí)間越長(zhǎng)，其優(yōu)先級(jí)越低，當(dāng)其響應(yīng)時(shí)間為0時(shí)，表示該節(jié)點(diǎn)空閑，其節(jié)點(diǎn)優(yōu)先級(jí)最高。

2.2 算法介紹

為了能響應(yīng)用戶提出的請(qǐng)求，我們將CN分成主控制節(jié)點(diǎn)PCN(PrimaryControlNode)和從控制節(jié)點(diǎn)SCN(SecondaryControlNode)，PCN負(fù)責(zé)進(jìn)行任務(wù)管理，SCN負(fù)責(zé)對(duì)用戶的任務(wù)進(jìn)行處理，處理某個(gè)用戶請(qǐng)求的SCN成為當(dāng)前任務(wù)的責(zé)任節(jié)點(diǎn)。在一個(gè)AS內(nèi)的多個(gè)CN組成了一個(gè)服務(wù)組響應(yīng)用戶請(qǐng)求，并通過選舉算法選出一個(gè)PCN。每個(gè)CN都有自己的一個(gè)公共組播地址和私有IP。

經(jīng)典的bully算法是一個(gè)可靠的選舉算法，我們?cè)O(shè)計(jì)了基于bully的選舉算法，過程如下：

CN進(jìn)入選舉狀態(tài)后，向其他CN發(fā)送選舉組播包，并啟動(dòng)定時(shí)器T1，等待 AS中其它CN的響應(yīng)包。當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)有更高優(yōu)先級(jí)選舉CN時(shí)，就自動(dòng)設(shè)置狀態(tài)為SCN狀態(tài)。如果在T1時(shí)間內(nèi)，沒有收到更高優(yōu)先級(jí)CN的選舉包，則設(shè)置狀態(tài)為PCN狀態(tài)。

在SCN狀態(tài)，CN啟動(dòng)一個(gè)定時(shí)器T2，如果在T2允許的時(shí)間內(nèi)獲得PCN發(fā)來的輪詢包，就作出響應(yīng)，并更新CN優(yōu)先級(jí)隊(duì)列，將PCN發(fā)送來的任務(wù)加入任務(wù)隊(duì)列。如果在定時(shí)器T2允許之內(nèi)沒有獲得PCN發(fā)來的輪詢包，則進(jìn)入選舉狀態(tài)。如果在T2允許的時(shí)間內(nèi)收到其它SCN的選舉包，則先比較負(fù)載，若自身的負(fù)載比較低，則進(jìn)入選舉狀態(tài)。

進(jìn)入PCN狀態(tài)后，首先停止自己的任務(wù)并將任務(wù)移送至CN優(yōu)先級(jí)隊(duì)列中優(yōu)先級(jí)高的CN上，然后開始監(jiān)控整個(gè)AS中其他SCN的狀態(tài)。監(jiān)控過程為：?jiǎn)?dòng)定時(shí)器T3，并向所有SCN發(fā)送輪詢包，收集SCN的狀態(tài)和任務(wù)信息。如果有新任務(wù)，就將任務(wù)分配給最高優(yōu)先級(jí)的CN,并更新SCN優(yōu)先級(jí)隊(duì)列，然后將形成的新的SCN隊(duì)列和任務(wù)信息發(fā)送至SCN。如果在T3允許的時(shí)間內(nèi)又有新的選舉包到來，就發(fā)送回復(fù)中止其選舉。

為了更好地說明選舉算法的過程，我們給出了主節(jié)點(diǎn)選舉算法的偽代碼，具體如下：

select(IP){ //選舉函數(shù)

send(SELECT,allCN,IP);/*向其他CN發(fā)送選舉組播包*/

T1.val=0 //啟動(dòng)計(jì)時(shí)器T1

wait(T1);

if(have_receive(higher_priority_CN)){/*當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)有更高優(yōu)先級(jí)選舉CN時(shí)，就自動(dòng)設(shè)置狀態(tài)為SCN狀態(tài)*/

state=SCN;

}else{

state=PCN；/*如果沒有收到更高優(yōu)先級(jí)節(jié)點(diǎn)的選舉包，則自己成為PCN*/

send(task,highest_prirority_CN_in_priqueue)

}

}

根據(jù)上述選舉過程，圖2給出了相應(yīng)的狀態(tài)轉(zhuǎn)移圖。節(jié)點(diǎn)的狀態(tài)可以分成三種：選舉態(tài)、PCN態(tài)和SCN態(tài)。每個(gè)CN都維持一個(gè)守護(hù)進(jìn)程，在正常情況下，一個(gè)AS內(nèi)有一個(gè)PCN，當(dāng)節(jié)點(diǎn)剛加入時(shí)，默認(rèn)設(shè)置為SCN狀態(tài)。

Figure 2 State transition of CN in AS

3 基于選舉的一致性視圖構(gòu)建算法

3.1 SCVCA算法介紹

第2.2節(jié)中，我們給出了AS內(nèi)主控制節(jié)點(diǎn)的選舉算法，在本節(jié)中我們基于選舉算法的選舉結(jié)果，并根據(jù)網(wǎng)絡(luò)視圖的一致性需求和控制節(jié)點(diǎn)之間的負(fù)載均衡需求，提出一致性視圖構(gòu)建算法SCVCA (Selection-based Consistant View Contruciton Algorithm)，對(duì)用戶(網(wǎng)絡(luò)控制機(jī)制)提交的網(wǎng)絡(luò)視圖構(gòu)建任務(wù)進(jìn)行統(tǒng)一處理。其主要思想是，需要構(gòu)建AS內(nèi)一致性視圖的用戶統(tǒng)一向主控制節(jié)點(diǎn)提交一致性視圖構(gòu)建請(qǐng)求；主控制節(jié)點(diǎn)將任務(wù)分配給從控制節(jié)點(diǎn)進(jìn)行處理，同時(shí)設(shè)定一個(gè)任務(wù)等待時(shí)間，并在視圖構(gòu)建任務(wù)完成前將提交一致性視圖構(gòu)建請(qǐng)求的用戶放在等待隊(duì)列中，當(dāng)一致性視圖構(gòu)建任務(wù)處理完成后，一次性將一致性視圖交付給等待隊(duì)列中的用戶；而從控制節(jié)點(diǎn)根據(jù)主控制節(jié)點(diǎn)分配的任務(wù)構(gòu)建該控制域的局部視圖后，由其中一個(gè)從控制節(jié)點(diǎn)對(duì)這些局部視圖進(jìn)行綜合后提交給主控制節(jié)點(diǎn)。為了更清楚地說明處理過程，我們給出了一致性視圖構(gòu)建算法的步驟，具體如下：

(1)由于AS內(nèi)的每個(gè)控制節(jié)點(diǎn)都知道本AS內(nèi)的主控制節(jié)點(diǎn)的地址，當(dāng)運(yùn)行在某一控制節(jié)點(diǎn)上的網(wǎng)絡(luò)控制機(jī)制產(chǎn)生一致性視圖構(gòu)建需求時(shí)，該網(wǎng)絡(luò)控制機(jī)制向AS的主控制節(jié)點(diǎn)PCN提交網(wǎng)絡(luò)一致性視圖構(gòu)建請(qǐng)求ViewRequest1，并設(shè)定一個(gè)時(shí)間QT，如果在QT時(shí)間內(nèi)沒有收到PCN的一致性視圖構(gòu)建結(jié)果,則構(gòu)建視圖失敗。

(2)AS的主控制節(jié)點(diǎn)PCN維持一個(gè)視圖請(qǐng)求等待隊(duì)列VQueue和一個(gè)視圖構(gòu)建計(jì)時(shí)器PViewtimer。當(dāng)PCN接收到ViewRequest1后，檢查VQueue中是否存在正在等待的其他節(jié)點(diǎn)的視圖處理請(qǐng)求，如果沒有，則生成一個(gè)視圖構(gòu)建任務(wù)ViewTask1，為該任務(wù)生成一個(gè)唯一的任務(wù)標(biāo)識(shí)TaskID，并將ViewRequest1添加到VQueue中，同時(shí)將PViewtimer清零；如果有，則僅將ViewRequest1添加到VQueue中。生成網(wǎng)絡(luò)一致性視圖構(gòu)建任務(wù)ViewTask1后，PCN查看其維護(hù)的控制節(jié)點(diǎn)優(yōu)先級(jí)隊(duì)列，然后從優(yōu)先級(jí)隊(duì)列中選出具有最高優(yōu)先級(jí)的從控制節(jié)點(diǎn)SCN1；然后將網(wǎng)絡(luò)一致性視圖構(gòu)建任務(wù)ViewTask1和任務(wù)標(biāo)識(shí)TaskID分配給從控制節(jié)點(diǎn)SCN1，并設(shè)定PViewtimer的等待時(shí)間為PT以等待SCN1返回處理結(jié)果；如果PT時(shí)間內(nèi)沒有獲得SCN1的一致性視圖構(gòu)建結(jié)果，則構(gòu)建視圖失敗。其中由于從控制節(jié)點(diǎn)SCN1負(fù)責(zé)對(duì)ViewTask1任務(wù)的處理，我們稱從控制節(jié)點(diǎn)SCN1為責(zé)任從處理節(jié)點(diǎn)RSCN(Response Secondary Control Node)。

(3)RSCN收到主控制節(jié)點(diǎn)PCN分配的網(wǎng)絡(luò)一致性視圖構(gòu)建任務(wù)ViewTask1和任務(wù)標(biāo)識(shí)TaskID后，向其他從控制節(jié)點(diǎn)SCN發(fā)送網(wǎng)絡(luò)一致性視圖合作構(gòu)建請(qǐng)求CorRequest2和任務(wù)標(biāo)識(shí)TaskID，并設(shè)定等待時(shí)間RT等待其他從控制節(jié)點(diǎn)SCN返回處理結(jié)果；同時(shí)，RSCN根據(jù)ViewTask1的需求構(gòu)建本控制域的局部視圖，如果其中存在一個(gè)協(xié)助構(gòu)建視圖的從控制節(jié)點(diǎn)沒有在RT時(shí)間內(nèi)完成局部視圖構(gòu)建，則一致性視圖構(gòu)建任務(wù)失敗。其中除了RSCN以外的參與到任務(wù)ViewTask1處理的從控制節(jié)點(diǎn)的任務(wù)是協(xié)助RSCN構(gòu)建AS的一致性視圖，因此我們將這些從控制節(jié)點(diǎn)稱為協(xié)助從控制節(jié)點(diǎn)JSCN(Joint Secondary Control Node)。

(4)JSCN接收到處理任務(wù)CorRequest2和任務(wù)標(biāo)識(shí)TaskID后，根據(jù)ViewTask1任務(wù)的需求構(gòu)建相應(yīng)控制域的局部視圖，并將結(jié)果和任務(wù)標(biāo)識(shí)TaskID反饋給RSCN。

(5)RSCN收到各個(gè)JSCN的處理結(jié)果和任務(wù)標(biāo)識(shí)TaskID后，檢查任務(wù)標(biāo)識(shí)TaskID是否與當(dāng)前處理的任務(wù)的標(biāo)識(shí)一致，如果不一致則丟棄，如果一致則繼續(xù)執(zhí)行：如果每個(gè)JSCN的局部構(gòu)建視圖成功，則綜合各個(gè)控制域的局部網(wǎng)絡(luò)視圖生成AS的一致性視圖，并將該視圖反饋給主控制節(jié)點(diǎn)；如果存在一個(gè)JSCN構(gòu)建視圖失敗，則向PCN反饋構(gòu)建一致性視圖失敗的信息。

(6)主控制節(jié)點(diǎn)收到處理結(jié)果和任務(wù)標(biāo)識(shí)TaskID后，如果任務(wù)標(biāo)識(shí)TaskID與當(dāng)前處理任務(wù)一致，則將一致性視圖的構(gòu)建結(jié)果反饋給提出請(qǐng)求網(wǎng)絡(luò)控制機(jī)制，否則將收到的結(jié)果丟棄，并繼續(xù)等待。

圖3給出了AS一致性視圖構(gòu)建過程示意圖，圖中的AS劃分為五個(gè)控制域，對(duì)應(yīng)有五個(gè)控制節(jié)點(diǎn)，用戶(網(wǎng)絡(luò)控制機(jī)制)提出構(gòu)建視圖的請(qǐng)求后，其構(gòu)建過程按照上面的步驟在圖中標(biāo)出。

Figure 3 AS consistent view construction

另外值得說明的是，由于分布式網(wǎng)絡(luò)環(huán)境的網(wǎng)絡(luò)延遲以及視圖計(jì)算的時(shí)間耗費(fèi)等原因，嚴(yán)格實(shí)時(shí)的網(wǎng)絡(luò)一致性視圖是很難構(gòu)建的，網(wǎng)絡(luò)視圖與網(wǎng)絡(luò)實(shí)際狀態(tài)必然會(huì)存在一個(gè)時(shí)間差，所以一般采用不斷更新視圖版本的方法來反映網(wǎng)絡(luò)的實(shí)際狀態(tài)。為了防止網(wǎng)絡(luò)一致性視圖由于時(shí)間延遲原因造成網(wǎng)絡(luò)控制的混亂，我們?cè)诳尚趴煽鼐W(wǎng)絡(luò)中都以AS主控制節(jié)點(diǎn)的時(shí)間為準(zhǔn)，對(duì)主控制節(jié)點(diǎn)生成的每個(gè)視圖以一個(gè)時(shí)間戳為標(biāo)準(zhǔn)生成視圖版本版本號(hào)，并以五元組(PCN,View,Vision,RequestTime,ViewGenerateTime)對(duì)視圖進(jìn)行標(biāo)識(shí)，以避免網(wǎng)絡(luò)新老視圖的不一致問題。該五元組表示主控制節(jié)點(diǎn)PCN在RequestTime時(shí)刻接到用戶請(qǐng)求后，在ViewGenerateTime時(shí)刻構(gòu)建成功的版本Vision的網(wǎng)絡(luò)視圖View，其中的RequestTime和ViewGenerateTime都是以PCN的時(shí)間為標(biāo)準(zhǔn)。該五元組利用PCN的局部時(shí)間完成了對(duì)網(wǎng)絡(luò)視圖進(jìn)行統(tǒng)一的版本界定，能夠保證各個(gè)控制節(jié)點(diǎn)之間的視圖不會(huì)產(chǎn)生矛盾。

由于PCN等待RSCN返回一致性視圖以及RSCN等待JSCN返回局部性視圖時(shí)都設(shè)定了固定的等待時(shí)限，等待超時(shí)就將視圖構(gòu)建任務(wù)判為失敗，容易發(fā)生構(gòu)建新版本視圖時(shí)收到舊版本的網(wǎng)絡(luò)視圖或者舊版本的局部視圖的情況，造成網(wǎng)絡(luò)視圖的混亂。為了解決這種情況，我們?yōu)槊總€(gè)視圖構(gòu)建任務(wù)生成一個(gè)唯一的任務(wù)標(biāo)識(shí)TaskID，在PCN收到RSCN返回一致性視圖和RSCN收到JSCN返回的局部視圖時(shí)都要檢查收到的結(jié)果的TaskID是不是與當(dāng)前處理的任務(wù)的TaskID一致，如果不一致，則將收到的結(jié)果丟棄，只有收到的結(jié)果的TaskID與當(dāng)前正在處理的任務(wù)的TaskID一致時(shí)才能接受。

3.2 算法分析

在第1節(jié)的需求分析中，我們給出了網(wǎng)絡(luò)一致性視圖構(gòu)建需要解決的兩個(gè)問題：新老網(wǎng)絡(luò)視圖一致性問題和不同控制節(jié)點(diǎn)的視圖不一致性問題。針對(duì)這兩個(gè)問題，我們將針對(duì)基于選舉的一致性視圖構(gòu)建算法構(gòu)建的視圖進(jìn)行一致性分析。

在上節(jié)給出的一致性視圖構(gòu)建算法中，每個(gè)AS的主控制節(jié)點(diǎn)PCN是該AS視圖的唯一源頭，并且以PCN的局部時(shí)間作為視圖版本界定的標(biāo)準(zhǔn)，解決了視圖版本前后矛盾和多個(gè)控制節(jié)點(diǎn)不一致的問題。利用基于選舉的一致性視圖構(gòu)建算法生成的視圖具有兩個(gè)性質(zhì)：

性質(zhì)1 將用戶請(qǐng)求按照PCN的局部時(shí)間排序后，請(qǐng)求時(shí)間較晚的用戶獲得的視圖(PCN,ViewB,VisionB,tB,vtB)的版本一定不低于請(qǐng)求時(shí)間較早的用戶獲得的視圖(PCN,ViewA,VisionA,tA,vtA)，即存在兩個(gè)視圖(PCN,ViewA,VisionA,tA,vtA)和(PCN,ViewB,VisionB,tB,vtB)，如果tB≥tA，則vtB≥vtA,即VisionB≥VisionA。其中tA和tB是PCN接受任務(wù)處理請(qǐng)求的時(shí)刻。

證明 為了比較請(qǐng)求時(shí)間較晚的視圖和請(qǐng)求時(shí)間較早的視圖的版本高低，我們可以分成如下兩種情況討論：第一種情況是較晚的視圖請(qǐng)求到達(dá)時(shí)，較早的視圖請(qǐng)求正在被處理；第二種情況是較晚的視圖請(qǐng)求到達(dá)時(shí)，較早的視圖請(qǐng)求已經(jīng)被處理完成。下面我們分成兩種情況討論

第一種情況：如圖4所示，PCN分別在tA時(shí)刻和tB接受了用戶A和用戶B的請(qǐng)求，由于用戶A的請(qǐng)求QA比用戶B的請(qǐng)求QB接受的時(shí)間早，因此PCN接受QA時(shí)創(chuàng)建一個(gè)一致性視圖構(gòu)建任務(wù)，并設(shè)定時(shí)限PT等待視圖構(gòu)建；而當(dāng)PCN接受QB時(shí)，一致性視圖構(gòu)建任務(wù)正在進(jìn)行，視圖等待隊(duì)列Queue不為空，因此PCN僅將QB加入到等待隊(duì)列中，以此創(chuàng)建新的視圖構(gòu)建任務(wù)。當(dāng)視圖構(gòu)建任務(wù)完成后，PCN同時(shí)將視圖發(fā)送給用戶A和用戶B，故vtB=vtA。

第二種情況：如圖4所示，PCN分別在時(shí)刻tA和tC接受了用戶A和用戶C的請(qǐng)求，由于PCN接受用戶C的請(qǐng)求QC時(shí)，用戶A的請(qǐng)求QA已經(jīng)處理完成，很顯然，vtC>vtA。

所以，綜合上述兩種情況，性質(zhì)得證。

□

性質(zhì)2 將用戶獲得的視圖按照PCN的局部時(shí)間排序后，生成時(shí)間較晚的視圖的版本高于生成時(shí)間較早的視圖的版本，并且版本高的視圖比版本低的視圖準(zhǔn)確。即兩個(gè)視圖(PCN,ViewA,VisionA,tA,vtA)和(PCN,ViewB,VisionB,tB,vtB)，如果vtB≥vtA,則VisionB≥VisionA，并且VisionA和VisionB對(duì)應(yīng)的網(wǎng)絡(luò)真實(shí)狀態(tài)(RealStateA,trsA)和(RealStateB,trsB)滿足trsB≥trsA。

Figure 4 Consistent view for multiple users based on the selection algorithm

證明 由于網(wǎng)絡(luò)視圖是由PCN統(tǒng)一構(gòu)建的，并且視圖的構(gòu)建時(shí)刻都是按照PCN的時(shí)間為標(biāo)準(zhǔn)的，因此構(gòu)建時(shí)間較晚的視圖必然比構(gòu)建視圖較早的視圖的版本高，即兩個(gè)視圖(PCN,ViewA,VisionA,tA,vtA)和(PCN,ViewB,VisionB,tB,vtB)，如果vtB≥vtA，則VisionB≥VisionA。并且由于ViewB的構(gòu)建時(shí)間比ViewA的構(gòu)建時(shí)間晚，因此ViewB獲得的信息必然更新，即VisionA和VisionB對(duì)應(yīng)的網(wǎng)絡(luò)真實(shí)狀態(tài)(RealStateA,trsA)和(RealStateB,trsB)滿足trsB≥trsA。

□

從上面兩個(gè)定理可以看出，在可信可控網(wǎng)絡(luò)中利用基于選舉的一致性視圖構(gòu)建算法為多個(gè)控制節(jié)點(diǎn)統(tǒng)一構(gòu)建網(wǎng)絡(luò)視圖的方法保證了網(wǎng)絡(luò)視圖的一致性。

4 多粒度視圖構(gòu)建

在前文中，我們給出了在可信可控網(wǎng)絡(luò)的AS內(nèi)為多個(gè)控制節(jié)點(diǎn)構(gòu)建一致性視圖的算法。在可信可控網(wǎng)絡(luò)中，我們給出了可信可控網(wǎng)絡(luò)中控制信息描述模型[12]，以及對(duì)這些信息進(jìn)行存儲(chǔ)的控制信息數(shù)據(jù)庫。在本節(jié)中我們將基于該算法和可信可控網(wǎng)絡(luò)控制信息數(shù)據(jù)庫為AS內(nèi)多個(gè)控制節(jié)點(diǎn)提供網(wǎng)絡(luò)設(shè)備粒度和網(wǎng)絡(luò)協(xié)議粒度的一致性視圖。

AS內(nèi)設(shè)備粒度的一致性視圖構(gòu)建：設(shè)備粒度的視圖構(gòu)建主要為用戶提供以AS內(nèi)網(wǎng)絡(luò)設(shè)備的鄰接關(guān)系為主體構(gòu)建的網(wǎng)絡(luò)拓?fù)湟晥D。按照上文給出的一致性視圖構(gòu)建方法，當(dāng)用戶提出構(gòu)建設(shè)備粒度視圖的請(qǐng)求后，主控制節(jié)點(diǎn)接受該請(qǐng)求，并將構(gòu)建任務(wù)分配給優(yōu)先級(jí)最高的RSCN負(fù)責(zé)構(gòu)建視圖；RSCN將協(xié)調(diào)構(gòu)建任務(wù)分配給各個(gè)JSCN后，各個(gè)JSCN分別在其負(fù)責(zé)的控制域內(nèi)構(gòu)建設(shè)備粒度的局部視圖，并返回給RSCN；RSCN根據(jù)各個(gè)JSCN返回的局部視圖構(gòu)建AS內(nèi)設(shè)備粒度的一致性視圖后，將一致性視圖返回給PCN；最后PCN將結(jié)果返回給發(fā)出請(qǐng)求的用戶。

AS內(nèi)協(xié)議粒度的一致性視圖構(gòu)建：協(xié)議粒度的視圖在網(wǎng)絡(luò)拓?fù)湟晥D的基礎(chǔ)上進(jìn)行細(xì)化，將運(yùn)行在傳輸網(wǎng)絡(luò)上的協(xié)議之間的通信關(guān)系在視圖上反映出來。由于協(xié)議粒度的視圖比設(shè)備粒度的視圖能夠更詳細(xì)地反映網(wǎng)絡(luò)狀態(tài)以及各個(gè)協(xié)議之間的依賴關(guān)系，因此構(gòu)建協(xié)議粒度的一致性視圖對(duì)網(wǎng)絡(luò)管理和網(wǎng)絡(luò)控制更有幫助?？尚趴煽鼐W(wǎng)絡(luò)的的每個(gè)控制節(jié)點(diǎn)都對(duì)其負(fù)責(zé)的控制域內(nèi)運(yùn)行的協(xié)議狀態(tài)信息進(jìn)行采集，并存儲(chǔ)在控制信息數(shù)據(jù)庫中，使得構(gòu)建AS內(nèi)的協(xié)議粒度的一致性視圖成為可能。AS內(nèi)協(xié)議粒度的一致性視圖構(gòu)建方法與設(shè)備粒度的視圖構(gòu)建方法一樣，也是利用本節(jié)中給出的一致性視圖構(gòu)建方法進(jìn)行構(gòu)建。

5 仿真實(shí)驗(yàn)

在可信可控網(wǎng)絡(luò)網(wǎng)絡(luò)中，SCVCA保證了多個(gè)控制節(jié)點(diǎn)獲取AS內(nèi)的一致性視圖。然而在多個(gè)控制節(jié)點(diǎn)對(duì)AS進(jìn)行聯(lián)合控制的過程中，需要保證視圖能夠在較短的時(shí)間和較低的負(fù)載下構(gòu)建。為了驗(yàn)證SCVCA在構(gòu)建時(shí)間和構(gòu)建負(fù)載方面的性能，我們?cè)诜抡鎸?shí)驗(yàn)環(huán)境下對(duì)SCVCA和每個(gè)控制節(jié)點(diǎn)單獨(dú)構(gòu)建的方法SCM(SingleConstructionMethod)在時(shí)間和負(fù)載兩個(gè)方面進(jìn)行比較。為了更好地驗(yàn)證SCVCA的性能，本文利用仿真工具NS2構(gòu)建了仿真實(shí)驗(yàn)。為了檢驗(yàn)SCVCA在不同網(wǎng)絡(luò)規(guī)模下的性能，隨機(jī)生成了四個(gè)m+n不同規(guī)模的實(shí)驗(yàn)網(wǎng)絡(luò)環(huán)境，其中m表示控制節(jié)點(diǎn)的個(gè)數(shù)，n表示路由器的個(gè)數(shù)，網(wǎng)絡(luò)規(guī)模分別為3+8、5+26、8+57和12+105。

視圖構(gòu)建所需要的時(shí)間直接影響到網(wǎng)絡(luò)控制的有效性。為了比較，我們?cè)谏鲜鼍W(wǎng)絡(luò)環(huán)境下給出了SCVCA與SCM兩種算法的構(gòu)建時(shí)間，如圖5所示。從圖5中可以看出,SCVCA構(gòu)建視圖所需要的時(shí)間在各種網(wǎng)絡(luò)規(guī)模下都優(yōu)于SCM，并且隨著網(wǎng)絡(luò)規(guī)模的增大和控制節(jié)點(diǎn)數(shù)量的增加，SCVCA構(gòu)造視圖所需要的時(shí)間的增長(zhǎng)速度也低于SCM。這是因?yàn)镾CVCA通過主控制節(jié)點(diǎn)將構(gòu)造任務(wù)分配給從控制節(jié)點(diǎn)共同構(gòu)建視圖，從控制節(jié)點(diǎn)將自己控制的局部網(wǎng)絡(luò)生成視圖后返回主控制節(jié)點(diǎn)，這比SCM中將所有網(wǎng)絡(luò)信息都發(fā)送給請(qǐng)求節(jié)點(diǎn)大大降低了數(shù)據(jù)傳輸?shù)臅r(shí)間和構(gòu)造過程中的計(jì)算量，從而有效縮短了視圖構(gòu)建的時(shí)間。

Figure 5 Construction time comparison of two kinds ofview generation algorithms under different network scale

多個(gè)控制節(jié)點(diǎn)構(gòu)建視圖必然造成網(wǎng)絡(luò)傳輸?shù)呢?fù)擔(dān)，進(jìn)行網(wǎng)絡(luò)視圖構(gòu)建的算法必須具有良好的可擴(kuò)展性，不能隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)而出現(xiàn)爆炸性的消息傳輸數(shù)量。為了比較SCVCA和SCM隨著網(wǎng)絡(luò)規(guī)模的增大和網(wǎng)絡(luò)中需要構(gòu)建視圖的節(jié)點(diǎn)的數(shù)量的增加引起的網(wǎng)絡(luò)傳輸負(fù)載，我們給出了兩種算法在多種網(wǎng)絡(luò)規(guī)模下和多種需要構(gòu)建視圖的節(jié)點(diǎn)比例下引起的網(wǎng)絡(luò)傳輸?shù)南?shù)，如圖6所示。從圖6中可以看出，在各種情況下，SCVCA構(gòu)建視圖造成的網(wǎng)絡(luò)消息數(shù)均明顯低于SCM的。這是因?yàn)镾CVCA由主控制節(jié)點(diǎn)負(fù)責(zé)為全網(wǎng)的所有請(qǐng)求生成一次視圖，而SCM需要每個(gè)控制節(jié)點(diǎn)自己請(qǐng)求網(wǎng)絡(luò)視圖的構(gòu)建信息來構(gòu)建視圖，這勢(shì)必造成SCM構(gòu)建視圖過程中隨著網(wǎng)絡(luò)規(guī)模和請(qǐng)求數(shù)的增加網(wǎng)絡(luò)信息傳輸量迅速增加。

Figure 6 Number of messages of two algorithms under different network scales

6 結(jié)束語

本文首先分析了在可信可控網(wǎng)絡(luò)中利用多個(gè)控制節(jié)點(diǎn)對(duì)一個(gè)AS進(jìn)行聯(lián)合控制的情況，為多個(gè)控制節(jié)點(diǎn)提供一致性視圖的必要性，并給出了各個(gè)控制節(jié)點(diǎn)獨(dú)自構(gòu)建網(wǎng)絡(luò)視圖造成的問題；然后針對(duì)這些問題，提出了可信可控網(wǎng)絡(luò)中為多個(gè)控制節(jié)點(diǎn)構(gòu)建一致性視圖的機(jī)制，包括主控制節(jié)點(diǎn)的選舉算法和基于選舉的一致性視圖的構(gòu)建算法，保證了視圖版本一致性，并對(duì)該算法構(gòu)建的視圖的一致性進(jìn)行了分析；最后在控制信息數(shù)據(jù)庫的基礎(chǔ)上，為控制節(jié)點(diǎn)提供了AS內(nèi)設(shè)備粒度和協(xié)議粒度的一致性視圖。

本文解決的一致性視圖問題是可信可控網(wǎng)絡(luò)中多個(gè)控制節(jié)點(diǎn)對(duì)AS進(jìn)行聯(lián)合控制的基礎(chǔ)，然而多個(gè)控制節(jié)點(diǎn)對(duì)AS進(jìn)行有效控制還涉及到AS外信息的共享問題。為了更好地提高網(wǎng)絡(luò)控制的效率，建立多個(gè)控制節(jié)點(diǎn)AS間有效的信息共享機(jī)制將是非常有意義的工作。

[1]BouabeneG,JelgerC,TschudinC,etal.Theautonomicnetworkarchitecture(ANA)[J].IEEEJournalonSelectedAreasinCommunications, 2010,28(1):4-14.

[2]IqbalH,ZnatiT.Distributedcontrolplanefor4Darchitecture[C]∥ProcofGlobalTelecommunicationsConference, 2007:1901-1905.

[3]WuJie.Distributedsystemdesign[M].Beijing:MachineryIndustryPress, 2001.(inChinese)

[4]KingGT,GendreauTB,NiLM.Reliableelectioninbroadcastnetworks[J].JournalofParallelandDistributedComputing, 1989, 7(1):521-546.

[5]ChangEG,RobertsR.Animprovedalgorithmfordecentralizedextrema-findingincircularconfigurationsofprocessors[J].CommunicationsoftheACM, 1979,22(5):281-283.

[6]DolevD,KlaweM,RothM.AnO(nlogn)unidirectionaldistributedalgorithmforextremafindinginacircle[J].JournalofAlgorithms, 1982,3(3):245-260.

[7]PetersonGL.AnO(nlogn)unidirectionaldistributedalgorithmforthecircularextremaproblem[J].ACMTransactionsonProgrammingLanguagesandSystems,1982,4(4):758-762.

[8]FranklinWR.Onanimprovedalgorithmfordecentralizedextremafindingincircularconfigurationsofprocessors[J].CommunicationsoftheACM, 1982,25(5):336-337.

[9]KorachE,MoranS,ZabsS.Tightlowerandupperboundsforsomedistributedalgorithmsforacompletenetworkofprocessors[C]∥Procofthe3rdAnnualACMSymposiumonPrinciplesofDistributedComputing, 1984:199-205.

[10]MansB,SantoroN.Optimalelectionsinfaultyloopnetworksandapplications[J].IEEETransactionsonComputers, 1998,47(3):286-297.

[11]Garcia-MolinaH.Electionsinadistributedcomputingsystem[J].IEEETransactonsonComputers, 1982,C-31(1):48-59.

[12]WangP,LuoJZ,LiW,etal.Controlinformationdescriptionmodelandprocessingmechanisminthetrustworthyandcontrollablenetwork[C]∥Procofthe11thIFIP/IEEEInternationalSymposiumonIntegratedNetworkManagement(IM09), 2009:398-405.

附中文參考文獻(xiàn)：

[3] 吳杰. 分布式系統(tǒng)設(shè)計(jì)[M]. 北京：機(jī)械工業(yè)出版社,2001.

CAO Sheng-lin,born in 1976,MS,associate professor,his research interests include computer network management, and next generation network.

柳立言(1980-),女,寧夏隆德人，碩士，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)管理、下一代網(wǎng)絡(luò)和信息技術(shù)。E-mail:nxlly@163.com

LIU Li-yan,born in 1980,MS,associate professor,her research interests include computer network, next generation network, and information technology.

A consistent view construction mechanism in trustworthy and controllable network

CAO Sheng-lin,LIU Li-yan

(College of Mathematics and Computer Science,Ningxia Teachers University,Guyuan 756099,China)

Multiple control nodes are used to control an AS coordinately in trustworthy and controllable networks, thus easily resulting in the problem of inconsistent AS views of different control nodes. To solve this problem, based on the trustworthy and controllable network model, an election algorithm based consistent view construction mechanism is proposed. Firstly, an election algorithm is used to generate a primary control node. Secondly, according to the loads of the control nodes in an AS, the primary control node assigns the view construction tasks to the control node with the lowest load. Thirdly, the version of the generated view is defined by the time of the primary control node. The mechanism avoids the problem of inconsistent views due to the individual view construction of different control nodes. Besides, the simulation experiment results show that the proposal has good performance.

trustworthy and controllable network model;selection algorithm;consistent view

1007-130X(2015)01-0070-08

2013-04-18;

2013-06-04基金項(xiàng)目：寧夏自然科學(xué)基金資助項(xiàng)目(NZ14278)

TP301

A

10.3969/j.issn.1007-130X.2015.01.011

曹生林(1976-),男,寧夏中寧人，碩士，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)管理和下一代網(wǎng)絡(luò)。E-mail:nxcsl@163.com

通信地址：756099 寧夏固原市寧夏師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院

Address:College of Mathematics and Computer Science,Ningxia Teachers University,Guyuan 756099,Ningxia,P.R.China