矯培艷，張闖闖，王興偉+，黃 敏

1.東北大學(xué) 軟件學(xué)院，沈陽 110169

2.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽 110169

3.東北大學(xué) 信息科學(xué)與工程學(xué)院，沈陽 110819

1 引言

傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)復(fù)雜且封閉，使得網(wǎng)絡(luò)管理員在考慮網(wǎng)絡(luò)動(dòng)態(tài)和各種應(yīng)用需求時(shí)難以進(jìn)行操作和管理，其龐大的部署基礎(chǔ)使得互聯(lián)網(wǎng)在物理基礎(chǔ)設(shè)施、協(xié)議以及性能發(fā)展方面變得非常困難[1]。網(wǎng)絡(luò)通常是由大量網(wǎng)絡(luò)設(shè)備構(gòu)建而成，它們實(shí)現(xiàn)了許多復(fù)雜的協(xié)議。網(wǎng)絡(luò)運(yùn)營商負(fù)責(zé)配置策略以響應(yīng)各種網(wǎng)絡(luò)事件和應(yīng)用程序。他們必須手動(dòng)將這些高級(jí)策略轉(zhuǎn)換為低級(jí)配置命令，因此網(wǎng)絡(luò)管理和性能調(diào)整容易出錯(cuò)。網(wǎng)絡(luò)從業(yè)者和研究人員面臨的另一個(gè)幾乎無法克服的挑戰(zhàn)被稱為“互聯(lián)網(wǎng)僵化”[2]。然而，隨著當(dāng)前和新興的互聯(lián)網(wǎng)應(yīng)用和服務(wù)變得越來越復(fù)雜，互聯(lián)網(wǎng)必須能夠發(fā)展演進(jìn)以應(yīng)對(duì)這些新的挑戰(zhàn)。軟件定義網(wǎng)絡(luò)（software defined networking，SDN）的核心思想是“可編程網(wǎng)絡(luò)”，通過將數(shù)據(jù)平面與控制平面進(jìn)行解耦[3]，很大程度上簡化了網(wǎng)絡(luò)的管理與配置，實(shí)現(xiàn)網(wǎng)絡(luò)的智能化。

在SDN中，控制器決定交換機(jī)如何轉(zhuǎn)發(fā)數(shù)據(jù)流，交換機(jī)只負(fù)責(zé)數(shù)據(jù)流的轉(zhuǎn)發(fā)。SDN中控制平面可以采用不同形式，包括集中式（單控制器）和分布式（多控制器）體系架構(gòu)[4]。對(duì)于許多中等規(guī)模的網(wǎng)絡(luò)來說，單控制器足以應(yīng)付，然而對(duì)于許多大規(guī)模廣域網(wǎng)而言，由于單控制器架構(gòu)沒有足夠的能力在有限時(shí)間內(nèi)處理來自所有交換機(jī)的請(qǐng)求，其計(jì)算能力成為了網(wǎng)絡(luò)瓶頸。同時(shí)，利用多控制器平面對(duì)網(wǎng)絡(luò)進(jìn)行分布式管理可以有效避免單點(diǎn)故障[5]。

在SDN中，控制器是整個(gè)網(wǎng)絡(luò)的核心，它能夠?qū)W(wǎng)絡(luò)資源進(jìn)行正確的調(diào)度和控制?？刂破餍枰贫ú呗砸约跋掳l(fā)流表給交換機(jī)，以便統(tǒng)一管理。而交換機(jī)也需要向它所屬的控制器發(fā)送消息，以便控制器對(duì)其進(jìn)行監(jiān)控和統(tǒng)計(jì)。因此，交換機(jī)和控制器之間的響應(yīng)時(shí)間對(duì)SDN網(wǎng)絡(luò)的性能有很大的影響。而該響應(yīng)時(shí)間的主要影響因素為交換機(jī)與控制器之間的傳播時(shí)延和控制器的負(fù)載。本文在確定控制域的數(shù)量以及進(jìn)行控制域劃分時(shí)主要考慮控制器之間的負(fù)載均衡，因?yàn)樨?fù)載均衡是衡量控制器性能的重要指標(biāo)之一。當(dāng)控制器負(fù)載不均衡時(shí)，會(huì)導(dǎo)致控制器效率以及SDN網(wǎng)絡(luò)性能下降。

為此，本文研究了SDN 控制器確定與劃分問題，以實(shí)現(xiàn)各控制器之間負(fù)載均衡。論文的主要貢獻(xiàn)如下：

（1）設(shè)計(jì)了基于本征間隙的譜聚類算法的SDN控制域確定機(jī)制，通過建立相似矩陣計(jì)算得到控制域的最優(yōu)數(shù)量。

（2）設(shè)計(jì)了基于特征向量的聚類算法的SDN 控制域劃分機(jī)制，以控制器的負(fù)載均衡為目標(biāo)，根據(jù)確定的控制器的最優(yōu)數(shù)量實(shí)現(xiàn)SDN控制域的劃分。

（3）仿真實(shí)驗(yàn)結(jié)果表明，本文所提出的機(jī)制可以計(jì)算出最優(yōu)的控制域數(shù)量，并且可以實(shí)現(xiàn)各控制域內(nèi)交換機(jī)節(jié)點(diǎn)數(shù)量相對(duì)均衡。

2 相關(guān)工作

SDN在廣域網(wǎng)中部署時(shí)需要解決的重要問題是控制平面的可擴(kuò)展性。由于廣域網(wǎng)跨越地域廣并且擁有眾多交換機(jī)節(jié)點(diǎn)，這導(dǎo)致單個(gè)SDN 控制器難以滿足網(wǎng)絡(luò)需求，因此多控制器架構(gòu)已成為SDN 網(wǎng)絡(luò)未來的發(fā)展趨勢[6]。通過將廣域網(wǎng)劃分成若干個(gè)規(guī)模較小、節(jié)點(diǎn)數(shù)量均衡的SDN控制域，擁有平衡節(jié)點(diǎn)數(shù)量的控制器的服務(wù)能力才能顯著提高。目前，在解決控制器部署問題的時(shí)候，大部分研究都只是解決了給定控制器數(shù)量的情況下的控制器放置問題，很少有研究根據(jù)網(wǎng)絡(luò)拓?fù)浯_定控制域的最優(yōu)數(shù)量及劃分，之后再部署多控制器的機(jī)制。文獻(xiàn)[7]解釋了控制器在SDN 網(wǎng)絡(luò)中的放置問題，并且指出了控制器部署問題的關(guān)鍵是確定控制器的數(shù)量及位置。文獻(xiàn)[8]提出了基于改進(jìn)的K-means算法，該算法主要用于解決SDN控制器的部署問題。算法初始狀態(tài)只設(shè)一個(gè)分區(qū)，之后慢慢增加分區(qū)數(shù)量進(jìn)行循環(huán)迭代。然而文中只關(guān)注了控制器到各交換機(jī)的距離問題，沒有考慮到負(fù)載均衡。文獻(xiàn)[9]提出了一種基于分簇的網(wǎng)絡(luò)劃分算法（network partition algorithm based on clustering，CNPA）來劃分網(wǎng)絡(luò)，其可以保證每個(gè)分區(qū)都能夠縮短控制器和交換機(jī)之間的最大端到端延遲。為了減少控制器的排隊(duì)等待時(shí)間，此文提出了在子網(wǎng)絡(luò)中放置適當(dāng)數(shù)量的多個(gè)控制器，但是沒有給出控制器的具體數(shù)量。文獻(xiàn)[10]提出了使用博弈論解決SDN 控制器部署問題，考慮交換機(jī)到控制器的時(shí)延、控制器之間的時(shí)延和控制器的負(fù)載均衡三方面進(jìn)行博弈，尋求一種均衡方法確定控制器部署的數(shù)量和位置。然而，該算法時(shí)間復(fù)雜度較高，只適用于小型網(wǎng)絡(luò)拓?fù)洹Ｎ墨I(xiàn)[11]提出了一種彈性方案，在不同的情況下，動(dòng)態(tài)改變控制器的個(gè)數(shù)和位置，但是依舊不能自動(dòng)計(jì)算出控制域的最優(yōu)數(shù)量。綜上所述，目前關(guān)于多控制器部署問題的解決方案的前提多是控制器的數(shù)量已知，很少有研究根據(jù)當(dāng)前網(wǎng)絡(luò)拓?fù)浯_定出控制域的最優(yōu)數(shù)量。

3 模型建立

3.1 網(wǎng)絡(luò)建模

本文將控制器管理的交換機(jī)的數(shù)量定義為控制器的負(fù)載，每個(gè)控制域內(nèi)有且只有一個(gè)控制器。

將網(wǎng)絡(luò)拓?fù)浣閳DG(V,E)，其中V代表交換機(jī)節(jié)點(diǎn)集合，E代表鏈路集合。實(shí)際上，SDN控制域的確定與劃分問題就是將圖劃分成若干個(gè)子圖。

定義1如果將圖G劃分成K個(gè)子圖，則Ni可以被定義為Ni(Vi,Ei)。那么，對(duì)集合V中的節(jié)點(diǎn)進(jìn)行聚類，就相當(dāng)于依據(jù)相似度劃分集合V，得到互不相交的子集V1,V2,…,VK，即。其中Vi表示第i個(gè)控制域，K表示控制域的數(shù)量。V中的節(jié)點(diǎn)按照它們所處的控制域進(jìn)行排序的結(jié)果如式（1）所示。

本文的目標(biāo)是尋找一個(gè)最優(yōu)的SDN控制域劃分使得各控制域中交換機(jī)節(jié)點(diǎn)數(shù)量盡可能均衡?；赗atioCut 和譜聚類算法[12-13]，本文提出了一種SDN 控制域確定與劃分機(jī)制，可以實(shí)現(xiàn)控制器負(fù)載均衡。將控制域劃分問題轉(zhuǎn)化成圖的切割問題，并利用圖論中比較典型的RatioCut 分割算法來進(jìn)行控制域的劃分。通過最小化式（2）中的目標(biāo)函數(shù)可以得到平衡的SDN控制域劃分。

其中，vol(Ni)表示子圖Ni中節(jié)點(diǎn)的總數(shù)量，wij表示交換機(jī)節(jié)點(diǎn)si和交換機(jī)節(jié)點(diǎn)sj之間的鏈路的權(quán)重，也就是這兩個(gè)節(jié)點(diǎn)的相似度。

3.2 SDN控制域確定模型

本文基于譜圖理論[14]設(shè)計(jì)了SDN控制域確定機(jī)制。主要思想是使用線性代數(shù)思想研究相似矩陣的性質(zhì)。首先，介紹了改進(jìn)相似矩陣建立的方法，然后介紹了利用本征間隙自動(dòng)計(jì)算滿足目標(biāo)分區(qū)的SDN控制域的最優(yōu)數(shù)量。

譜聚類算法的性能很大程度上受相似度矩陣的影響。根據(jù)對(duì)廣域網(wǎng)中時(shí)延的分析，本文選擇傳播時(shí)延作為相似度矩陣的權(quán)重值。對(duì)于廣域網(wǎng)拓?fù)鋪碚f，交換機(jī)si和sj之間的相似度wij可以通過式（3）計(jì)算。

其中，si是數(shù)據(jù)樣本點(diǎn)，d(si,sj)是兩點(diǎn)之間的距離，σ是自定義的參數(shù)。此處d代表節(jié)點(diǎn)si和sj之間的傳播時(shí)延，即節(jié)點(diǎn)之間的最短距離。

對(duì)于σx的取值，如果只采用不同的σx值進(jìn)行實(shí)驗(yàn)后取劃分效果最佳的σx，運(yùn)算時(shí)間將會(huì)增加。而且假定σx為固定值，則兩個(gè)節(jié)點(diǎn)之間的相似性僅取決于這兩點(diǎn)之間的歐氏距離，并且忽略兩點(diǎn)的論據(jù)節(jié)點(diǎn)的分布情況，這將導(dǎo)致不理想的分區(qū)效果。因此本文對(duì)相似度函數(shù)的計(jì)算進(jìn)行了改進(jìn)，加入鄰居節(jié)點(diǎn)分布情況。如式（4）所示。

其中，用σi=d(si,sk)來計(jì)算本地σ值，sk是節(jié)點(diǎn)si的第k個(gè)鄰居節(jié)點(diǎn)。經(jīng)過多次實(shí)驗(yàn)發(fā)現(xiàn)，k取4時(shí)劃分效果最佳。相似度矩陣建立好之后，根據(jù)式Anor(i,j)=得到其規(guī)范相似度矩陣Anor。其中D為度矩陣，度值可以用來體現(xiàn)樣本點(diǎn)周圍數(shù)據(jù)的分布狀況。首先對(duì)Anor進(jìn)行分解得到由大到小的非負(fù)特征值，即λ1≥λ2≥…≥λn≥0，然后利用本征間隙序列計(jì)算出本征間隙向量，最后使用計(jì)算SDN控制域的最優(yōu)數(shù)量K。

3.3 SDN控制域劃分模型

本文基于歸一化Laplacian矩陣特征向量設(shè)計(jì)了SDN 控制域劃分機(jī)制。在SDN 控制域的劃分過程中，對(duì)Laplacian 矩陣進(jìn)行譜分解然后聚類可以被用于近似最小化式（2）中的SDNcut，從而獲得相對(duì)平衡的控制域的劃分。

為了使各個(gè)控制域之間交換機(jī)節(jié)點(diǎn)數(shù)量相對(duì)均衡，本文首先計(jì)算Laplacian矩陣，如式（5）所示。

其中，A為相似度矩陣，D為度矩陣，度值可以用來體現(xiàn)樣本點(diǎn)周圍數(shù)據(jù)的分布狀況。度矩陣是將度值作為矩陣的對(duì)角元素的矩陣，如式（6）所示。

獲得SDN控制域的最優(yōu)數(shù)量K之后進(jìn)行控制域的劃分。首先，將矩陣L分解成L=X∧XT的形式。矩陣X是L的特征向量按列存儲(chǔ)得到的。然后，取矩陣X的前K個(gè)最小特征值對(duì)應(yīng)的特征向量組成矩陣M=(x1,x2,…,xK)。最后，定義矩陣M的行是由向量Mi(i=1,2,…,n)構(gòu)成，如式（7）所示。

其中，式（8）中P是對(duì)M的每一行進(jìn)行歸一化之后的矩陣。令，根據(jù)式（9）計(jì)算特征矩陣行向量的相似度矩陣，并依據(jù)該特征矩陣對(duì)SDN網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行聚類。

當(dāng)R(si,sj)的結(jié)果為1時(shí)，說明si和sj屬于同一類，當(dāng)R(si,sj)為0時(shí)，說明si和sj為不同的類。如果最終計(jì)算的結(jié)果恰好為K時(shí)，則結(jié)束計(jì)算；否則，選擇不同的flag值重新進(jìn)行劃分。

4 算法描述

在本文中，利用Floyd 算法[15]計(jì)算任意兩個(gè)節(jié)點(diǎn)之間的最短路徑，然后根據(jù)最短路徑經(jīng)過的點(diǎn)來獲得控制路徑的path集。

算法1SDN控制域確定與劃分算法

輸入：網(wǎng)絡(luò)拓?fù)銰，劃分標(biāo)準(zhǔn)flag。

輸出：控制域的數(shù)量K以及控制域的劃分結(jié)果control。

首先利用Floyd 算法計(jì)算網(wǎng)絡(luò)拓?fù)銰距離矩陣并對(duì)該矩陣的每一行從小到大排序；然后計(jì)算相似度矩陣，對(duì)其規(guī)范得到規(guī)范相似度矩陣，并按照從大到小的順序?qū)⒂?jì)算得到的矩陣的特征值進(jìn)行排序；其次使用相似矩陣A計(jì)算得到本征間隙序列，從序列中查找到的第一個(gè)極大值所對(duì)應(yīng)的下標(biāo)就是控制域的數(shù)量K。在獲得SDN 控制域的數(shù)量K后進(jìn)行控制域的劃分，依據(jù)矩陣L的前K個(gè)最小特征向量之間的相似度進(jìn)行劃分。計(jì)算特征向量的相似矩陣，并根據(jù)該矩陣對(duì)SDN網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行聚類，如果聚類結(jié)果恰好為K，則說明K為控制域的最優(yōu)數(shù)量；否則，選取不同的flag值重新進(jìn)行域的劃分。

5 性能評(píng)價(jià)

5.1 仿真設(shè)置

本文基于Matlab平臺(tái)進(jìn)行仿真實(shí)現(xiàn)。在仿真實(shí)現(xiàn)中采用CERNET2[16]和DFN（http://www.topologyzoo.org/dataset.html）網(wǎng)絡(luò)拓?fù)?。其中，CERNET2網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)數(shù)量為25，如圖1所示；DFN網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)數(shù)量為51，如圖2所示。

Fig.1 CERNET2 network topology圖1 CERNET2網(wǎng)絡(luò)拓?fù)?/p>

Fig.2 DFN network topology圖2 DFN網(wǎng)絡(luò)拓?fù)?/p>

5.2 性能評(píng)價(jià)

對(duì)于CERNET2網(wǎng)絡(luò)拓?fù)洌紫?，通過控制域確定機(jī)制計(jì)算得到拓?fù)渲械淖顑?yōu)控制域的數(shù)量為6。然后，基于此結(jié)果分別取控制域數(shù)量為3、4、5、6、7、8、9、10，采用本文設(shè)計(jì)的控制域劃分機(jī)制進(jìn)行仿真實(shí)驗(yàn)，以控制域中節(jié)點(diǎn)數(shù)量的方差為衡量標(biāo)準(zhǔn)，根據(jù)劃分結(jié)果計(jì)算每個(gè)控制域數(shù)量下的各控制域中節(jié)點(diǎn)數(shù)量的方差，方差越小，表示劃分結(jié)果中每個(gè)控制域節(jié)點(diǎn)數(shù)量波動(dòng)越小、越均衡。

圖3為控制域數(shù)量的方差，由圖3可以看出，當(dāng)控制域的數(shù)量為6時(shí)方差最小，即該數(shù)量下各控制域節(jié)點(diǎn)數(shù)量波動(dòng)最小、最均衡。該圖中沒有表示出當(dāng)控制域的數(shù)量為2時(shí)的結(jié)果，此時(shí)兩個(gè)控制域中節(jié)點(diǎn)數(shù)量分別為21和4，均勻程度更低。

Fig.3 Variance of control domain number(CERNET2)圖3 控制域數(shù)量的方差（CERNET2）

當(dāng)控制域中只有1個(gè)控制器時(shí)可能導(dǎo)致單點(diǎn)故障。當(dāng)控制域中的控制器數(shù)量大于10時(shí)，控制器數(shù)量過多，將造成成本增加和資源浪費(fèi)。

圖4是當(dāng)控制域的數(shù)量為6時(shí)使用本文的控制域劃分算法劃分的實(shí)驗(yàn)結(jié)果。相同顏色的節(jié)點(diǎn)表示它們屬于同一個(gè)控制域。例如，對(duì)于圖中廈門這一點(diǎn)，距杭州的最大時(shí)延為37 ms，廈門到廣州的最大時(shí)延為26 ms。因此，廈門和廣州應(yīng)分為同一個(gè)控制域。對(duì)于南京來說，南京到武漢之間的時(shí)延是29 ms，從南京到合肥的時(shí)延是110 ms。因此南京應(yīng)該和武漢處于同一個(gè)控制域。同理，對(duì)于圖中的其他節(jié)點(diǎn)來說該算法在一定程度上均可以進(jìn)行正確的劃分。

圖5為以DFN 網(wǎng)絡(luò)拓?fù)錇閷?shí)驗(yàn)拓?fù)鋾r(shí)控制域的劃分結(jié)果。使用本文的控制域劃分算法計(jì)算得到的控制域最優(yōu)數(shù)量為8，相同顏色的節(jié)點(diǎn)表示它們屬于同一控制域。從圖5中可以看出，使用本文設(shè)計(jì)的算法可以得到合理的控制域劃分，并且節(jié)點(diǎn)數(shù)量相對(duì)均衡。

Fig.4 Control domain partitioning results(CERNET2)圖4 控制域劃分實(shí)驗(yàn)結(jié)果（CERNET2）

Fig.5 Control domain partitioning results(DFN)圖5 控制域劃分實(shí)驗(yàn)結(jié)果（DFN）

6 結(jié)論與展望

本文研究了SDN控制域確定與劃分機(jī)制。首先基于本征間隙設(shè)計(jì)了SDN 控制域確定機(jī)制，計(jì)算得到最優(yōu)的控制域數(shù)量；其次設(shè)計(jì)了基于歸一化Laplacian 矩陣特征向量的控制域劃分機(jī)制，可以使得劃分結(jié)果近似均衡。仿真結(jié)果表明本文設(shè)計(jì)的機(jī)制可以計(jì)算出合理的控制域數(shù)量，并且各控制域節(jié)點(diǎn)數(shù)量相對(duì)均衡。

本文在進(jìn)行控制域劃分時(shí)是將控制器所連接的交換機(jī)的數(shù)量作為控制器的負(fù)載；然而在實(shí)際情況中，SDN 控制器的負(fù)載應(yīng)該是它所控制的交換機(jī)對(duì)它的數(shù)據(jù)請(qǐng)求量，下一步工作是解決這種情況下控制域的劃分及優(yōu)化控制器的負(fù)載均衡問題。