基于SPEA-Ⅱ算法的SDN多控制器優(yōu)化部署機制

郭夢娜， 王興偉， 張闖闖， 黃 敏

(1. 東北大學 軟件學院 遼寧 沈陽 110169； 2. 東北大學 計算機科學與工程學院 遼寧 沈陽 110169； 3. 東北大學 信息科學與工程學院 遼寧 沈陽 110819)

0 引言

廣泛使用的移動設備、蓬勃發(fā)展的大數(shù)據(jù)、云計算及虛擬化技術激發(fā)了對網(wǎng)絡容量和擴展性的新要求，同時這又導致了現(xiàn)有的網(wǎng)絡設備安裝、配置復雜度的飛快上升.面對這些問題，SDN可以發(fā)揮其優(yōu)勢[1].SDN解耦網(wǎng)絡的控制平面與數(shù)據(jù)平面，將“智能”集中在控制平面，控制平面中的控制器通過可編程接口集中控制交換機，交換機僅按照控制器的“指示”處理數(shù)據(jù)包.SDN控制器及其合理部署可以提高網(wǎng)絡資源利用率、簡化網(wǎng)絡的管理以及減少操作開銷，并且可以極大提高網(wǎng)絡的性能.早期的SDN架構中控制平面通常只有一個控制器，F(xiàn)loodlight[2]、Maestro[3]等都是典型的單控制器.然而單控制器無法應對網(wǎng)絡中流量過大的情況，而且單控制器明顯會成為網(wǎng)絡的瓶頸，一旦發(fā)生單點故障，網(wǎng)絡將會整體癱瘓.為了解決單控制器的上述問題，HyperFlow[4]、FlowVisor[5]等多控制器案例相繼被提出，但這些多控制器大都存在弱一致性問題，而且維持控制器的一致性會消耗大量時間，導致系統(tǒng)的性能下降.

目前國內(nèi)外已有不少學者致力于多控制器部署方面的研究，也取得了很多優(yōu)秀的研究成果.文獻[6]提出了一個容量控制器布局的數(shù)學模型，其優(yōu)化目標是最小化交換機與控制器之間的最壞情況時延.文獻[7]提出了一種混合整數(shù)線性程序的控制器布局策略，其優(yōu)化目標包括交換機到距離其最近控制器以及最近控制器到第二近控制器的時延.文獻[8]提出了LiDy+算法，將交換機到控制器時延及網(wǎng)絡流量的動態(tài)性考慮在內(nèi)，解決了控制器動態(tài)部署的問題.文獻[9]提出了雙向匹配策略及相應的控制器部署方案，考慮的目標包括時延及控制器負載.文獻[10]基于NSGA-Ⅱ 算法，考慮了交換機到控制器的時延、控制器之間的時延以及節(jié)點和鏈路故障.文獻[11]提出了一種基于密度的控制器放置方法，利用基于密度的交換機聚類算法將網(wǎng)絡分成幾個子網(wǎng)絡，并在每個子網(wǎng)絡中部署一個控制器，考慮了控制器與交換機之間的時延、控制器數(shù)量與交換機失效情況.文獻[12]提出了一種快速有效的進化算法來解決大規(guī)模多目標控制器放置問題，考慮的目標包括交換機到控制器的時延、控制器之間的時延及網(wǎng)元故障.以上研究關注交換機到控制器的時延、控制器之間的時延等因素，解決了多控制部署問題.然而，同時考慮時延、交換機擁有從控制器數(shù)量及控制路徑故障率的研究還較少.因此，本文提出一種基于SPEA-Ⅱ 算法的SDN多控制器優(yōu)化部署機制，在給定控制域的情況下，建立了多控制器優(yōu)化部署數(shù)學模型；綜合考慮交換機到控制器的時延、控制器之間的時延、控制路徑故障率和平均交換機擁有從控制器數(shù)量4個優(yōu)化目標，提出了基于SPEA-Ⅱ 算法的多控制器優(yōu)化部署機制.仿真結果表明，相較于基準算法，該機制可以在一定程度上提高網(wǎng)絡的可靠性.

1 多控制器優(yōu)化部署數(shù)學模型

將網(wǎng)絡建模為無向帶權圖G(V,E)，其中V與E分別表示交換機集合和鏈路集合.n和m分別表示交換機數(shù)目和鏈路數(shù)目，邊權重eij表示網(wǎng)絡時延.將網(wǎng)絡劃分為多個控制域，用1,2,…,k表示，第i個控制域中交換機節(jié)點的編號用i1,i2,…，iq表示，q為節(jié)點總數(shù).

假定每個控制域中只有一個控制器，稱為此控制域內(nèi)交換機的主控制器，主控制器位于該控制域內(nèi)的某一個交換機節(jié)點處.除主控制器以外，交換機還會被分配給位于其他控制域中的控制器，稱為此交換機的從控制器.只有當主控制器失效后，從控制器才會接管此交換機.部署方案的解為CP=[c1,c2,…,ck]，ci為控制域i中控制器所處節(jié)點的編號，C={c1,c2,…，ck}為控制器集合.X=[xij]n×k代表交換機到其主控制器的分配矩陣，若交換機i的主控制器是控制域j中的控制器cj，則xij=1，否則xij=0.Y=[yij]n×k代表交換機到其從控制器的分配矩陣，若交換機i的從控制器是控制域j中的控制器cj，則yij=1，否則yij=0.本文中控制路徑是指交換機與主控制器之間和任意兩個控制器之間最短路徑的集合，用path={path1,path2,…,paths}表示，其中s可以表示為

(1)

網(wǎng)元(包括交換機和鏈路)集合用L=V∪E={l1,l2,…，lw}表示，其中w=m+n.ei表示網(wǎng)元li所處控制路徑的數(shù)量，交換機到控制器的最大時延為Dmax，節(jié)點i和j之間的傳播時延為d(i,j).

為了加快算法收斂，基于最小化交換機到主控制器的時延進行控制器的初步部署.將初步部署問題簡化為：遍歷控制域內(nèi)所有交換機的位置，計算此控制域中所有交換機到此位置的平均時延ls，使得ls最小的位置即為主控制器初步部署的位置.ls可以表示為

(2)

接下來加入了其他3個優(yōu)化目標，對控制器的部署方案進行優(yōu)化.本文的優(yōu)化目標可以表示為

minF(CP)=[f1(CP),f2(CP),f3(CP), -f4(CP)],

(3)

式中：CP表示控制器的部署方案；f1(CP)、f2(CP)、f3(CP)、f4(CP)分別表示最小化交換機到控制器的時延、最小化控制器之間的時延、最小化控制路徑故障率、最大化平均交換機擁有從控制器數(shù)量這4個優(yōu)化目標，具體可以表示為

(4)

控制路徑故障率是指平均每個網(wǎng)元故障所造成的故障控制路徑數(shù)量占總控制路徑數(shù)量的比例.約束條件為：

1)xijd(i,cj)≤Dmax，即交換機到其主控制器的時延不可超過最大時延；

2)yijd(i,cj)≤Dmax，即交換機到其從控制器的時延不可超過最大時延；

4)xijyij=0，即交換機的主、從控制器不能相同；

5)i1≤ci≤ip，即控制域i中的控制器只能位于此控制域中的節(jié)點上；

6)ci≠cj，即任意兩個控制器不可處于相同節(jié)點上.

2 算法設計

2.1 基于SPEA-Ⅱ算法的多控制器優(yōu)化部署機制

SPEA-Ⅱ[13]算法為SPEA的改進算法，在適應度計算和環(huán)境選擇等方面均有改進，而且在求解高維度優(yōu)化問題上，此算法的解集分布更加均勻.SPEA-Ⅱ算法的基本步驟如下.

Step 1： 初始化.對控制器初步部署中得到的初始解進行交叉或變異，獲得由N個解構成的初始種群.初始化Dmax，由初始種群和Dmax得到分配矩陣X和Y、控制路徑集合path以及每個網(wǎng)元li所處控制路徑的數(shù)量ei.計算出每個個體的4個目標函數(shù)值，創(chuàng)建空的歸檔集集合，并將迭代次數(shù)t置為0.

Step 2： 適應值計算.計算此次迭代中歸檔集集合和種群集合中個體的適應值.

Step 3： 環(huán)境選擇.拷貝歸檔集集合和種群集合中非支配個體進入下一代歸檔集集合，并對下一代歸檔集集合的大小進行控制.

Step 4： 終止.如果迭代次數(shù)達到預先設定的最大值T或滿足停止條件則算法停止，將下一代歸檔集中的非支配個體拷貝到集合A中，即為結果集合，否則進入Step 5.

Step 5： 配對池選擇.使用二進制錦標賽算法選擇歸檔集中的個體放入配對池中.

Step 6： 交叉和變異.將配對池中的個體取出，經(jīng)交叉和變異生成子代，并保存到下一代種群中.迭代次數(shù)加1，轉(zhuǎn)到Step 2.

設M和N分別為優(yōu)化目標函數(shù)的數(shù)量和種群大小，初始化階段的時間復雜度為O(N)，適應值計算階段的時間復雜度為O(MN2)，環(huán)境選擇階段的時間復雜度為O(MN3)，終止階段的時間復雜度為O(1)，配對池選擇階段的時間復雜度為O(N)，交叉和變異階段的時間復雜度為O(N2).因此，此算法的時間復雜度應為O(MN3).

2.2 基于熵權多目標決策法的唯一解選擇機制

2.2.1熵權 假定評估問題有a個待評項目和b個評價指標，建立多對象關于多指標的非模糊評價矩陣R=(rij)a×b，rij表示評價指標j下項目i的評價值.評價指標j的熵權值為

(5)

2.2.2算法流程 基于熵權多目標決策法的唯一解選擇機制的基本思想為：使用熵權多目標決策法，從多個非支配近似最優(yōu)解中選擇出一個最優(yōu)解，作為最終的控制器部署方案.算法具體流程如下.

1) 形成分析評價表.Pareto解集中第1層的n個解作為n個方案，4個優(yōu)化目標作為4個因素，方案分析評價表如表1所示，其中bij是相應方案j中優(yōu)化目標i的目標函數(shù)值.

表1 方案分析評價表Tab.1 Plan analysis evaluation table

2) 標準化分析評價表.按照式(6)所示的損失性指標的標準化公式標準化表1中的值.

(6)

3) 計算熵權值.根據(jù)式(5)計算各因素的熵權值Hi.H1、H2、H3、H4分別表示平均交換機到主控制器時延的熵權值、最大控制器之間時延的熵權值、平均控制路徑故障率的熵權值、平均交換機擁有從控制器數(shù)量的相反數(shù)的熵權值.借助各因素的熵權值，得到如式(7)所示的Hi規(guī)格化屬性矩陣.

(7)

(8)

(9)

式中：Oj=(a1j,a2j,a3j,a4j)T；Tj∈[0,1].

控制器部署方案的偽代碼如算法1所示.

算法1基于熵權多目標決策法的唯一解選擇機制.

輸入：方案分析評價矩陣analysis4*N；輸出：控制器放置方案CP.

BEGIN

1. 計算所有方案在4個指標上的最大值max和最小值min；

2. FORi←1 TO 4 DO

3. FORj←1 TONDO

4. 根據(jù)max，min以及式(6)標準化analysis矩陣得到analysis′；

5. END FOR

6. END FOR

7.kk←1/logn；

8. 根據(jù)式(5)和kk計算熵H；

9.analysis′←analysis′*H；

10. 根據(jù)式(8)計算被評對象到理想點P*的距離；

11. 根據(jù)式(9)計算被評對象與理想點的貼近度；

12. 根據(jù)距離和貼近度對方案進行排序；

13. 選出最優(yōu)控制器放置方案CP；

END

3 仿真實驗與性能評價

3.1 仿真實驗

圖1 控制器部署方案Fig.1 Controller deployment scheme

采用第2代中國教育科研計算機網(wǎng)CERNET2[14]作為測試拓撲，該拓撲節(jié)點數(shù)量和邊數(shù)量分別為25和29，選用的開發(fā)工具為Matlab，開發(fā)環(huán)境為Windows 7.實驗參數(shù)設置為：種群大小為200，最大迭代次數(shù)為30，交叉率與變異率分別為0.8和0.1，得到的控制器部署方案如圖1所示.相同形狀代表同一個控制域，右上角標有六角星圖案的圖形代表控制器所在的位置.

3.2 性能評價

為了對本文提出的SDN多控制器優(yōu)化部署機制(簡稱S機制)進行評價，選擇了文獻[15]中的機制(簡稱M機制)與文獻[10]中的多目標優(yōu)化機制(簡稱MN機制)作為對比算法.其中M機制中控制器的部署考慮的是最小化交換機到控制器的時延.本文選擇交換機到控制器時延、控制器之間時延、控制路徑故障率、交換機擁有從控制器數(shù)量作為4個評價指標.圖2顯示了不同控制器數(shù)量下交換機到控制器時延的變化曲線.可以看出，交換機到控制器時延隨控制器數(shù)量的增加而減小，這是因為控制器數(shù)量越多，網(wǎng)絡中控制域數(shù)量就越多，平均每個交換機到其所屬主控制器的時延就會越小.在不同控制器數(shù)量下S機制的時延要比M機制增加8%～38%，這是因為M機制僅僅考慮了最小化交換機到控制器的時延.S機制的交換機到控制器時延要略大于MN機制.圖3顯示了不同控制器數(shù)量下控制器之間時延的變化曲線.可以看出，控制器數(shù)量增多之后，控制器之間時延也隨之增加了，這是因為整個網(wǎng)絡被劃分成更多的控制域，導致控制器的部署范圍更廣闊，從而使得控制器之間時延增大.S機制控制器之間時延要比M機制減少5%～20%，主要是因為M機制在放置控制器的時候沒有考慮最小化控制器之間的最大時延.S機制與MN機制在控制器之間時延上基本持平.

圖2 交換機到控制器時延的變化曲線Fig.2 Variation curve of delay between switch and controller

圖3 控制器之間時延的變化曲線Fig.3 Variation curve of delay between controllers

圖4顯示了不同控制器數(shù)量下控制路徑故障率的變化曲線.可以看出，控制路徑故障率隨控制器數(shù)量的增多而逐漸減小，這是因為當控制器數(shù)量增多時，交換機到其主控制器的最短路徑數(shù)量不變，與此同時，控制器之間的控制路徑數(shù)量增多，此時總控制路徑數(shù)量的增幅大于平均每個網(wǎng)元故障所造成的故障控制路徑數(shù)量的增幅.由于M機制在部署控制器的時候，優(yōu)化目標并沒有考慮控制路徑故障率，所以S機制的控制路徑故障率比M機制減少23%～46%.S機制在控制路徑故障率上與MN機制基本持平.圖5顯示了不同控制器數(shù)量下平均交換機擁有從控制器數(shù)量的變化曲線.可以看出，平均交換機擁有從控制器數(shù)量隨控制器數(shù)量的增多而增加.控制器數(shù)量增多，意味著每個交換機滿足時延約束的控制器的數(shù)量也會增加，可能成為交換機從控制器的控制器數(shù)目就會增加.同樣是因為M機制沒有對該指標進行優(yōu)化，S機制平均交換機擁有從控制器數(shù)量比M機制要增加20%～32%.與MN機制相比，S機制平均交換機擁有從控制器數(shù)量要略多一點，這主要也是由于MN機制沒有考慮這一優(yōu)化目標.

圖4 控制路徑故障率的變化曲線Fig.4 Variation curve of control path failure ratio

圖5 平均交換機擁有從控制器數(shù)量的變化曲線Fig.5 Variation curve of average number of slave controllers belonging to switches

與M機制相比，本文提出的S機制的交換機到控制器時延略高，然而在控制器之間時延、控制路徑故障率、平均交換機擁有從控制器數(shù)量方面優(yōu)勢明顯.與MN機制相比，本文提出的S機制的交換機到控制器時延略高，然而其能有效提高平均交換機擁有從控制器數(shù)量.

4 小結

本文首先對多控制器部署及其優(yōu)化問題進行了數(shù)學描述，對控制器進行了初步部署.通過分析控制器部署問題建立了包含4個優(yōu)化目標在內(nèi)的數(shù)學模型，并利用SPEA-Ⅱ算法針對這4個目標函數(shù)提出了控制器部署的優(yōu)化機制.同時，提出了基于熵權多目標決策法的唯一解選擇機制.仿真結果表明，本文提出的多控制器優(yōu)化部署機制可以在一定程度上最小化時延，提高網(wǎng)絡的可靠性.本文僅考慮了網(wǎng)絡靜態(tài)的情況，而實際網(wǎng)絡中的流量是動態(tài)變化的；此外，本文假定每個控制域中僅放置一個控制器，而實際網(wǎng)絡中，特別是大規(guī)模網(wǎng)絡中，一個控制器往往是難以滿足網(wǎng)絡需求的.因此，今后的工作重點將集中在擴大網(wǎng)絡規(guī)模和考慮網(wǎng)絡流量的動態(tài)性.