張效娟 羅軍舟 李 偉

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

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

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

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

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

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

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

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

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

2.1 算法思想

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

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

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

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

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

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

2.3 算法描述

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

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

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

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

③對剩余的網(wǎng)絡(luò)拓?fù)渲匦掠嬎悴⑦x擇一個Nj值最大的節(jié)點作為控制節(jié)點;

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

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

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

1.Generate G=(V，E);

2.While(V!=?)

3. {For(i=0;i＜V.Size;i++)//V.size表示拓?fù)渲泄?jié)點個數(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é)點選為控制節(jié)點

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

11.}

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

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

//為每個路由器ri選取時延最小的控制節(jié)點

14. δim=1;

15. i++;}

16.Output P，δ;

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

3 實驗分析

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

表1 實驗拓?fù)鋵傩?/p>

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

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

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

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

4 結(jié)語

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