張效娟 羅軍舟 李 偉

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

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

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

1 可信可控網絡模型

圖1 可信可控網絡模型

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

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

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

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

2.1 算法思想

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

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

2.2 數學模型

自治域G的網絡拓撲用無向圖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對其他的路由器進行控制，控制節(jié)點選取的目標為m最小，同時從路由器到其所屬控制節(jié)點的最大時延不超過Dmax且所有路由器到其所屬控制節(jié)點的總時延最短.

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

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

2.3 算法描述

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

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

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

②將Rj從拓撲圖中刪除;

③對剩余的網絡拓撲重新計算并選擇一個Nj值最大的節(jié)點作為控制節(jié)點;

④再將Rj從拓撲圖中刪除;

⑤重復這個過程，直到網絡中沒有剩余節(jié)點.

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

1.Generate G=(V，E);

2.While(V!=?)

3. {For(i=0;i＜V.Size;i++)//V.size表示拓撲中節(jié)點個數

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時間內可達節(jié)點從G中刪除

11.}

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

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

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

14. δim=1;

15. i++;}

16.Output P，δ;

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

3 實驗分析

為了進一步驗證和比較CNSA算法的有效性，本文采用了與文獻［7］相同的實驗拓撲，利用SSFNet仿真工具進行了仿真實驗.表1給出了3個自治域內拓撲的屬性，其中Lmax表示拓撲中2個節(jié)點間的最大時延，Lavg表示2個節(jié)點間的平均時延.

表1 實驗拓撲屬性

首先，在3個不同規(guī)模的網絡拓撲下，考察選取的控制節(jié)點個數隨Dmax變化的情況.Dmax值分別設定為5，10，15，20，25，30 ms.從圖3 中可看出，控制節(jié)點的個數隨最大時延的增大而減少，表明CNSA算法是有效的.

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

其次，將本文算法CNSA與文獻［7］的算法DCNSA進行了比較.仍然采用表1所示的3個AS的拓撲，將在相同控制節(jié)點規(guī)模下2個算法分別選取的控制節(jié)點到路由器的平均時延以及最大時延作為評價指標.在DCNSA算法實驗中，將拓撲中的所有路由器位置都設定為候選位置，分別計算不同控制節(jié)點規(guī)模下的控制節(jié)點到路由器的平均時延以及最大時延.由于CNSA中Dmax為輸入，控制節(jié)點的個數為輸出，因此本文將Dmax的值從Lmax以0.5 ms的梯度依次遞減，計算控制節(jié)點個數與控制節(jié)點到路由器的平均時延及最大時延的對應關系，結果如圖4所示.由圖4可看出，在相同控制節(jié)點規(guī)模下，2種算法的平均時延接近，但本文算法擁有更小的最大時延.這是因為CNSA選取控制節(jié)點時在路由器與控制節(jié)點最大時延不超過Dmax的情況下，首先考慮減少控制節(jié)點的個數，以降低成本開銷，而不是控制節(jié)點與路由器間的平均時延.所以，實驗結果表明CNSA算法性能優(yōu)于DCNSA算法.

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

4 結語

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

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，Feamster 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］林闖，雷蕾.下一代互連網絡體系結構研究［J］.計算機學報，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］羅軍舟，韓志耕，王良民.一種可信可控的網絡體系及協(xié)議結構［J］.計算機學報，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］王鵬，羅軍舟，李偉，等.可控網絡中多agent系統(tǒng)信念可達性和收斂速度分析［J］.軟件學報，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］.計算機學報，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.