可信可控網(wǎng)絡(luò)中控制節(jié)點(diǎn)優(yōu)化選取算法

張效娟 羅軍舟 李 偉

(1青海師范大學(xué)計(jì)算機(jī)學(xué)院，西寧 810008)

(2東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210096)

隨著網(wǎng)絡(luò)技術(shù)和應(yīng)用的迅猛發(fā)展，互聯(lián)網(wǎng)日益呈現(xiàn)出復(fù)雜、異構(gòu)等特點(diǎn)，保證網(wǎng)絡(luò)的可控性成為當(dāng)今網(wǎng)絡(luò)發(fā)展的迫切需求，國(guó)內(nèi)外研究人員已陸續(xù)開(kāi)展了相關(guān)研究.Greenberg等［1］提出了4D網(wǎng)絡(luò)控制模型，將網(wǎng)絡(luò)控制功能從路由器中剝離出來(lái)，建立了獨(dú)立的網(wǎng)絡(luò)控制層.Caesar等［2］提出并實(shí)現(xiàn)了一個(gè)路由控制平臺(tái)，集中實(shí)現(xiàn)域內(nèi)路由決策.林闖等［3］對(duì)下一代網(wǎng)絡(luò)的可信可控關(guān)鍵技術(shù)進(jìn)行了研究，提出了可信可控可擴(kuò)展的下一代互聯(lián)網(wǎng)體系結(jié)構(gòu)，同樣指出需要構(gòu)建一個(gè)獨(dú)立的網(wǎng)絡(luò)控制層面.根據(jù)當(dāng)前國(guó)內(nèi)外對(duì)可控網(wǎng)絡(luò)的研究成果，本項(xiàng)目組在前期研究工作中提出了一種新的可信可控網(wǎng)絡(luò)模型［4-6］，將網(wǎng)絡(luò)控制與數(shù)據(jù)傳輸相分離，形成域內(nèi)集中、域間分布的控制方式，以提高網(wǎng)絡(luò)的可控性.但是，域內(nèi)集中的單一控制節(jié)點(diǎn)存在性能瓶頸問(wèn)題，容易產(chǎn)生單點(diǎn)故障.為了增強(qiáng)網(wǎng)絡(luò)控制的魯棒性和可擴(kuò)展性，一些研究人員提出在域內(nèi)采用多控制節(jié)點(diǎn)進(jìn)行協(xié)同控制的方式，將一個(gè)自治域劃分為多個(gè)控制域，每個(gè)控制域有一個(gè)控制節(jié)點(diǎn)對(duì)隸屬于該控制域的路由器進(jìn)行控制，自治域內(nèi)的多控制節(jié)點(diǎn)通過(guò)協(xié)同控制達(dá)到控制決策的一致性.然而，要實(shí)現(xiàn)自治域內(nèi)多控制節(jié)點(diǎn)間的協(xié)同控制，首先要解決的問(wèn)題是如何將一個(gè)給定網(wǎng)絡(luò)拓?fù)涞淖灾斡騽澐殖扇舾煽刂朴?，即如何確定每個(gè)控制域的管轄范圍以及控制節(jié)點(diǎn)位置的選取.文獻(xiàn)［7］基于4D網(wǎng)絡(luò)模型，在已知多個(gè)候選控制節(jié)點(diǎn)位置前提下，給出了控制節(jié)點(diǎn)選取及控制域劃分的方法，但是其控制節(jié)點(diǎn)的候選位置是預(yù)先指定的，缺乏合理性.本文基于可信可控網(wǎng)絡(luò)模型，提出了一種有效的控制節(jié)點(diǎn)優(yōu)化選取算法CNSA(control nodes selection algorithm)，無(wú)需指定控制節(jié)點(diǎn)候選位置，即可實(shí)現(xiàn)控制節(jié)點(diǎn)的優(yōu)化選取及控制域的劃分.實(shí)驗(yàn)結(jié)果表明，在相同控制節(jié)點(diǎn)規(guī)模下，CNSA算法得到的結(jié)果在保證控制實(shí)時(shí)性方面優(yōu)于文獻(xiàn)［7］中的算法.

1 可信可控網(wǎng)絡(luò)模型

圖1 可信可控網(wǎng)絡(luò)模型

可信可控網(wǎng)絡(luò)模型通過(guò)建立一個(gè)獨(dú)立的控制平面，將網(wǎng)絡(luò)控制邏輯集中到自治域內(nèi)的控制節(jié)點(diǎn)，由控制節(jié)點(diǎn)進(jìn)行網(wǎng)絡(luò)控制決策并對(duì)網(wǎng)絡(luò)實(shí)施控制，從而實(shí)現(xiàn)了網(wǎng)絡(luò)控制邏輯與數(shù)據(jù)傳輸?shù)姆蛛x.如圖1所示，該模型在不破壞傳統(tǒng)TCP/IP網(wǎng)絡(luò)體系結(jié)構(gòu)的基礎(chǔ)上，增加了一個(gè)由決策層、觀測(cè)層、資源層和可信接口層構(gòu)成的網(wǎng)絡(luò)控制邏輯結(jié)構(gòu).資源層通過(guò)可信接口層以協(xié)議跨層的方式獲取各種網(wǎng)絡(luò)組元及用戶(hù)行為的狀態(tài)信息，并提供給觀測(cè)層，由觀測(cè)層對(duì)其進(jìn)行描述，以實(shí)現(xiàn)網(wǎng)絡(luò)控制的抽象化，同時(shí)為決策層提供一致的網(wǎng)絡(luò)全局狀態(tài)可觀性視圖，保證決策層的高效性和準(zhǔn)確性.決策層根據(jù)觀測(cè)層提供的全網(wǎng)可觀一致性視圖，從系統(tǒng)當(dāng)前狀態(tài)以及全局利益最大化的角度出發(fā)，進(jìn)行集中決策并提出相應(yīng)的控制方案，通過(guò)可信接口層提供給TCP/IP網(wǎng)絡(luò)的各個(gè)層面，以達(dá)到控制目的.

2 控制節(jié)點(diǎn)優(yōu)化選取算法

集中式的域內(nèi)控制方式下，單一的控制節(jié)點(diǎn)會(huì)造成性能瓶頸和單點(diǎn)故障問(wèn)題，因此在自治域內(nèi)多控制節(jié)點(diǎn)進(jìn)行協(xié)同控制已成為相關(guān)研究者的共識(shí)［7］.可信可控網(wǎng)絡(luò)將自治域內(nèi)的控制邏輯集中到域內(nèi)的控制節(jié)點(diǎn)上，為了提高網(wǎng)絡(luò)控制的可擴(kuò)展性和魯棒性，將每個(gè)自治域劃分成多個(gè)控制域，每個(gè)控制域中有一個(gè)控制節(jié)點(diǎn)通過(guò)某一路由器接入到網(wǎng)絡(luò)中，并對(duì)隸屬于該控制域的所有路由器實(shí)施控制，自治域內(nèi)的多控制節(jié)點(diǎn)通過(guò)協(xié)同控制保證決策的一致性，如圖2所示.然而，自治域內(nèi)實(shí)現(xiàn)多控制節(jié)點(diǎn)協(xié)同控制的首要問(wèn)題是如何選取控制節(jié)點(diǎn)實(shí)現(xiàn)控制域的劃分，使其既能滿(mǎn)足控制實(shí)時(shí)性的需求，又能降低控制代價(jià).為此，本文提出了一種控制節(jié)點(diǎn)優(yōu)化選取算法，在不需要預(yù)先確定控制節(jié)點(diǎn)候選位置的情況下，實(shí)現(xiàn)對(duì)控制域的劃分，使得選取的控制節(jié)點(diǎn)數(shù)目盡量少，并且每個(gè)控制節(jié)點(diǎn)到所管轄路由器的時(shí)延盡量短.

圖2 自治域內(nèi)多控制節(jié)點(diǎn)間的協(xié)同控制

2.1 算法思想

可信可控網(wǎng)絡(luò)將給定的自治域劃分成多個(gè)控制域，每個(gè)控制域中設(shè)置一個(gè)控制節(jié)點(diǎn)并通過(guò)域內(nèi)某一路由器接入到網(wǎng)絡(luò)中，對(duì)該控制域內(nèi)的所有路由器進(jìn)行直接控制，多控制節(jié)點(diǎn)通過(guò)協(xié)同控制實(shí)現(xiàn)一致性決策方案.為了減少因設(shè)置控制節(jié)點(diǎn)帶來(lái)的軟硬件開(kāi)銷(xiāo)，選取的控制節(jié)點(diǎn)應(yīng)盡量少.同時(shí)，控制節(jié)點(diǎn)與所管轄路由器之間的時(shí)延需要盡可能小，以保證控制的實(shí)時(shí)性.

本文設(shè)定控制節(jié)點(diǎn)與所管轄路由器間的最大傳輸時(shí)延為Dmax，自治域內(nèi)控制節(jié)點(diǎn)選取以及控制域劃分問(wèn)題的理想情況是在Dmax的約束下選取最少的控制節(jié)點(diǎn)數(shù)目，并且路由器到所屬控制節(jié)點(diǎn)的平均時(shí)延最短.由于控制節(jié)點(diǎn)需要通過(guò)域內(nèi)的某個(gè)路由器接入到網(wǎng)絡(luò)中，所以控制節(jié)點(diǎn)的位置等同于其接入路由器的位置.因此，自治域內(nèi)控制節(jié)點(diǎn)的優(yōu)化選取問(wèn)題就是給定一個(gè)有n個(gè)路由器的網(wǎng)絡(luò)，將其劃分為m個(gè)控制域，在每個(gè)控制域中確定一個(gè)路由器作為控制節(jié)點(diǎn)的接入位置，使得每個(gè)路由器只隸屬于一個(gè)控制域.選擇的約束條件是使m最小，并且路由器到其對(duì)應(yīng)控制節(jié)點(diǎn)的最大時(shí)延不超過(guò)Dmax且平均時(shí)延最短.

2.2 數(shù)學(xué)模型

自治域G的網(wǎng)絡(luò)拓?fù)溆脽o(wú)向圖G=(V，E)表示，其中V={r1，r2，…，rn}，表示G中路由器節(jié)點(diǎn)集合，E={e1，e2，…，ek}，表示邊的集合.控制節(jié)點(diǎn)優(yōu)化選取問(wèn)題就是將給定的圖G=(V，E)劃分為m個(gè)不相交的節(jié)點(diǎn)集 U1，U2，…，Um，其中 Ui∩Uj=?(i，j=1，2，…，m;i≠j)并且 U1∪U2∪…∪Um=V，在每個(gè)節(jié)點(diǎn)集Ui中選擇一個(gè)控制節(jié)點(diǎn)Pi對(duì)其他的路由器進(jìn)行控制，控制節(jié)點(diǎn)選取的目標(biāo)為m最小，同時(shí)從路由器到其所屬控制節(jié)點(diǎn)的最大時(shí)延不超過(guò)Dmax且所有路由器到其所屬控制節(jié)點(diǎn)的總時(shí)延最短.

設(shè)二值變量ci表示路由器ri是否被設(shè)定為其所屬控制域內(nèi)控制節(jié)點(diǎn)的接入點(diǎn).若ci=1，表示ri為控制節(jié)點(diǎn)的接入點(diǎn)，反之，表示ri不是控制節(jié)點(diǎn)的接入點(diǎn).為了簡(jiǎn)化描述，下面假定ri等同于控制節(jié)點(diǎn).設(shè)二值變量δij表示路由器ri是否被控制節(jié)點(diǎn)rj控制，δij=1表示 ri受控于 rj，否則表示 ri不受控于rj.令hij表示2個(gè)路由器ri和rj之間的最大時(shí)延，則自治域內(nèi)控制節(jié)點(diǎn)優(yōu)化選取問(wèn)題可轉(zhuǎn)化為如下形式的線(xiàn)性規(guī)劃問(wèn)題:

式(1)和式(2)表示2個(gè)規(guī)劃目標(biāo)，前者為在n個(gè)路由器節(jié)點(diǎn)中選擇最少的節(jié)點(diǎn)成為控制節(jié)點(diǎn)，后者為同一控制域內(nèi)所有路由器到所屬控制節(jié)點(diǎn)的總時(shí)延最小;式(3)和式(4)分別定義了2個(gè)二值變量;式(5)表示每一個(gè)路由器僅被關(guān)聯(lián)到一個(gè)控制節(jié)點(diǎn);式(6)保證了每個(gè)路由器到其所屬控制節(jié)點(diǎn)的最大時(shí)延不超過(guò)設(shè)定的閾值Dmax.

2.3 算法描述

2.2節(jié)對(duì)自治域內(nèi)控制節(jié)點(diǎn)優(yōu)化選取問(wèn)題建立了一個(gè)多目標(biāo)約束的線(xiàn)性規(guī)劃模型，然而該問(wèn)題是一個(gè)NP-hard問(wèn)題［8］.因此，本文提出了根據(jù)域內(nèi)節(jié)點(diǎn)間的狀況劃分控制域并選擇控制節(jié)點(diǎn)的啟發(fā)式算法CNSA，主要思想為先選定在Dmax時(shí)間內(nèi)能夠到達(dá)最多網(wǎng)絡(luò)中其他路由節(jié)點(diǎn)的節(jié)點(diǎn)作為控制節(jié)點(diǎn)，再將網(wǎng)絡(luò)中剩余的路由器分配給相應(yīng)的控制節(jié)點(diǎn)構(gòu)成控制域.將與較多節(jié)點(diǎn)傳輸時(shí)延小的節(jié)點(diǎn)選為控制節(jié)點(diǎn)，能夠?qū)χ車(chē)?jié)點(diǎn)的情況快速感知并做出快速?zèng)Q策，保證網(wǎng)絡(luò)控制的實(shí)時(shí)性.

設(shè)Ni和Ri分別表示與路由器ri的最大時(shí)延小于等于Dmax的路由器的個(gè)數(shù)和集合，P表示控制節(jié)點(diǎn)集合.CNSA算法的主要步驟如下:

①對(duì)自治域的每個(gè)路由器計(jì)算與其最大時(shí)延不超過(guò)Dmax的路由器的個(gè)數(shù)，取出當(dāng)前網(wǎng)絡(luò)中Nj值最大的節(jié)點(diǎn)rj，設(shè)定其為控制節(jié)點(diǎn);

②將Rj從拓?fù)鋱D中刪除;

③對(duì)剩余的網(wǎng)絡(luò)拓?fù)渲匦掠?jì)算并選擇一個(gè)Nj值最大的節(jié)點(diǎn)作為控制節(jié)點(diǎn);

④再將Rj從拓?fù)鋱D中刪除;

⑤重復(fù)這個(gè)過(guò)程，直到網(wǎng)絡(luò)中沒(méi)有剩余節(jié)點(diǎn).

算法1 控制節(jié)點(diǎn)選取算法

1.Generate G=(V，E);

2.While(V!=?)

3. {For(i=0;i＜V.Size;i++)//V.size表示拓?fù)渲泄?jié)點(diǎn)個(gè)數(shù)

4. For(j=0;j＜ V.Size;j++)

5. {If(hij≤Dmax)

6. {Ni++;

7. Ri=Ri∪{rj};}}

8. If Njis max(Ni)

9. P=P∪{rj};//將該節(jié)點(diǎn)選為控制節(jié)點(diǎn)

10. Delete Rjfrom G;//將該節(jié)點(diǎn)及其Dmax時(shí)間內(nèi)可達(dá)節(jié)點(diǎn)從G中刪除

11.}

12.While(1≤i≤n)//為每個(gè)路由器選取其相應(yīng)控制節(jié)點(diǎn)

13. {If himis min(hij)(1≤j≤n)

//為每個(gè)路由器ri選取時(shí)延最小的控制節(jié)點(diǎn)

14. δim=1;

15. i++;}

16.Output P，δ;

算法CNSA最終輸出的節(jié)點(diǎn)集合P即為域內(nèi)的控制節(jié)點(diǎn)集合，δ中包含了每個(gè)路由器與相應(yīng)控制節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系.算法的第2～11行進(jìn)行控制節(jié)點(diǎn)的選取，其中第3～7行計(jì)算每個(gè)節(jié)點(diǎn)在Dmax時(shí)間內(nèi)可達(dá)的節(jié)點(diǎn)個(gè)數(shù)Ni及其能夠控制的節(jié)點(diǎn)集Ri，第8，9行選取在Dmax時(shí)間內(nèi)可達(dá)節(jié)點(diǎn)數(shù)目最多的節(jié)點(diǎn)作為控制節(jié)點(diǎn)，第10行將該節(jié)點(diǎn)及其控制集從拓?fù)渲袆h除.然而，上述過(guò)程并不能保證在控制節(jié)點(diǎn)集為P的情況下，每個(gè)路由器都隸屬于到其時(shí)延最短的控制節(jié)點(diǎn).因此，第12～16行在確定了域內(nèi)控制節(jié)點(diǎn)集為P的基礎(chǔ)上對(duì)控制域的劃分進(jìn)行了優(yōu)化，確保每個(gè)路由器都被與其相連的最近控制節(jié)點(diǎn)控制.

3 實(shí)驗(yàn)分析

為了進(jìn)一步驗(yàn)證和比較CNSA算法的有效性，本文采用了與文獻(xiàn)［7］相同的實(shí)驗(yàn)拓?fù)?，利用SSFNet仿真工具進(jìn)行了仿真實(shí)驗(yàn).表1給出了3個(gè)自治域內(nèi)拓?fù)涞膶傩裕渲蠰max表示拓?fù)渲?個(gè)節(jié)點(diǎn)間的最大時(shí)延，Lavg表示2個(gè)節(jié)點(diǎn)間的平均時(shí)延.

表1 實(shí)驗(yàn)拓?fù)鋵傩?/p>

首先，在3個(gè)不同規(guī)模的網(wǎng)絡(luò)拓?fù)湎拢疾爝x取的控制節(jié)點(diǎn)個(gè)數(shù)隨Dmax變化的情況.Dmax值分別設(shè)定為5，10，15，20，25，30 ms.從圖3 中可看出，控制節(jié)點(diǎn)的個(gè)數(shù)隨最大時(shí)延的增大而減少，表明CNSA算法是有效的.

圖3 控制節(jié)點(diǎn)個(gè)數(shù)與最大時(shí)延的關(guān)系

其次，將本文算法CNSA與文獻(xiàn)［7］的算法DCNSA進(jìn)行了比較.仍然采用表1所示的3個(gè)AS的拓?fù)?，將在相同控制?jié)點(diǎn)規(guī)模下2個(gè)算法分別選取的控制節(jié)點(diǎn)到路由器的平均時(shí)延以及最大時(shí)延作為評(píng)價(jià)指標(biāo).在DCNSA算法實(shí)驗(yàn)中，將拓?fù)渲械乃新酚善魑恢枚荚O(shè)定為候選位置，分別計(jì)算不同控制節(jié)點(diǎn)規(guī)模下的控制節(jié)點(diǎn)到路由器的平均時(shí)延以及最大時(shí)延.由于CNSA中Dmax為輸入，控制節(jié)點(diǎn)的個(gè)數(shù)為輸出，因此本文將Dmax的值從Lmax以0.5 ms的梯度依次遞減，計(jì)算控制節(jié)點(diǎn)個(gè)數(shù)與控制節(jié)點(diǎn)到路由器的平均時(shí)延及最大時(shí)延的對(duì)應(yīng)關(guān)系，結(jié)果如圖4所示.由圖4可看出，在相同控制節(jié)點(diǎn)規(guī)模下，2種算法的平均時(shí)延接近，但本文算法擁有更小的最大時(shí)延.這是因?yàn)镃NSA選取控制節(jié)點(diǎn)時(shí)在路由器與控制節(jié)點(diǎn)最大時(shí)延不超過(guò)Dmax的情況下，首先考慮減少控制節(jié)點(diǎn)的個(gè)數(shù)，以降低成本開(kāi)銷(xiāo)，而不是控制節(jié)點(diǎn)與路由器間的平均時(shí)延.所以，實(shí)驗(yàn)結(jié)果表明CNSA算法性能優(yōu)于DCNSA算法.

圖4 CNSA算法與DCNSA算法的比較

4 結(jié)語(yǔ)

本文針對(duì)可信可控網(wǎng)絡(luò)中自治域內(nèi)控制節(jié)點(diǎn)的選取以及控制域的劃分問(wèn)題，基于圖論的思想提出了一種自治域內(nèi)控制節(jié)點(diǎn)優(yōu)化選取的啟發(fā)式算法.該算法將控制節(jié)點(diǎn)選取問(wèn)題轉(zhuǎn)換為多目標(biāo)線(xiàn)性規(guī)劃問(wèn)題，以控制節(jié)點(diǎn)數(shù)目最少和控制節(jié)點(diǎn)到所屬路由器的總時(shí)延最短為優(yōu)化目標(biāo)，既能夠降低系統(tǒng)軟硬件開(kāi)銷(xiāo)，又能夠保證控制的實(shí)時(shí)性;并且實(shí)驗(yàn)結(jié)果表明CNSA算法是有效的，在相同控制節(jié)點(diǎn)規(guī)模下，該算法的性能優(yōu)于已有其他算法.下一步工作是研究自治域內(nèi)多控制節(jié)點(diǎn)如何進(jìn)行協(xié)同以達(dá)到高效的一致性控制.

References)

［1］ Greenberg A，Hjalmtysson G，Maltz D A，et al.A clean slate 4D approach to network control and management［J］.ACM SIGCOMM Computer Communications Review，2005，35(5):41-54.

［2］Caesar M，Caldwell D，F(xiàn)eamster N，et al.Design and implementation of a routing control platform［C］//Proceedings of the 2nd Conference on Symposium on Networked Systems Design and Implementation.Boston，MA，USA，2005:15-28.

［3］林闖，雷蕾.下一代互連網(wǎng)絡(luò)體系結(jié)構(gòu)研究［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(5):693-711.Lin Chuang，Lei Lei.Research on next generation internet architecture ［J］.Chinese Journal of Computers，2007，30(5):693-711.(in Chinese)

［4］羅軍舟，韓志耕，王良民.一種可信可控的網(wǎng)絡(luò)體系及協(xié)議結(jié)構(gòu)［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32(3):391-404.Luo Junzhou，Han Zhigeng，Wang Liangmin.Trustworthy and controllable network architecture and protocol framework ［J］.Chinese Journal of Computers，2009，32(3):391-404.(in Chinese)

［5］王鵬，羅軍舟，李偉，等.可控網(wǎng)絡(luò)中多agent系統(tǒng)信念可達(dá)性和收斂速度分析［J］.軟件學(xué)報(bào)，2010，21(4):782-792.Wang Peng，Luo Junzhou，Li Wei，et al.Analysis on belief reachability and convergence rate of multi-agent system in controllable networks［J］.Journal of Software，2010，21(4):782-792.(in Chinese)

［6］譚晶，羅軍舟，李偉，等.基于可信度的域間路由機(jī)制［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(9):1763-1774.Tan Jing，Luo Junzhou，Li Wei，et al.Trust degree based inter-domain routing mechanism［J］.Chinese Journal of Computers，2010，33(9):1763-1774.(in Chinese)

［7］ Iqbal H，Znati T.Distributed control plane for 4D architecture［C］//Proceedings of IEEE Global Communications Conference.Washington DC，USA，2007:1901-1905.

［8］ He Bing，Xie Bin，Agrawal D P.Internet gateway deployment optimization in a multi-channel multi-radio wireless mesh network［C］//Proceedingsof IEEE Wireless Communications and Networking Conference.Las Vegas，NV，USA，2008:2259-2264.