謝 燕,張 爽

(1. 湖南信息學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院,湖南 長(zhǎng)沙 410151;2. 沈陽(yáng)理工大學(xué)自動(dòng)化與電氣工程學(xué)院,遼寧 沈陽(yáng) 110180)

1 引言

數(shù)據(jù)流量的大規(guī)模增加以及網(wǎng)絡(luò)服務(wù)需求的日益增加,加快了傳統(tǒng)網(wǎng)絡(luò)升級(jí)的步伐。為了滿足日益增長(zhǎng)的網(wǎng)絡(luò)需求,軟件定義網(wǎng)絡(luò)采用數(shù)據(jù)思想改變傳統(tǒng)網(wǎng)絡(luò)控制和轉(zhuǎn)發(fā)緊密耦合的工作模型,同時(shí)還能夠有效提升網(wǎng)絡(luò)管理的靈活性和開放性[1,2]。在大規(guī)模網(wǎng)絡(luò)中,SDN會(huì)因?yàn)榭刂破餍阅艿南拗茖?dǎo)致網(wǎng)絡(luò)整體性能受到影響,所以SDN作為未來(lái)網(wǎng)絡(luò)發(fā)展的主要趨勢(shì),受到社會(huì)的高度重視。傳統(tǒng)網(wǎng)絡(luò)無(wú)法進(jìn)行鏈路流量和帶寬可視化操作,而且整體的拓展性和靈活性也無(wú)法滿足當(dāng)前網(wǎng)絡(luò)技術(shù)的發(fā)展需求,使網(wǎng)絡(luò)部署以及管理難度增加。

為了有效解決上述問題,國(guó)內(nèi)相關(guān)專家給出了一些較好的研究方案,例如史久根等人[3]將最小傳播時(shí)延以及排隊(duì)時(shí)延等作為目標(biāo),構(gòu)建多控制器放置策略,采用負(fù)載均衡算法與遺傳算法進(jìn)行實(shí)時(shí)在線調(diào)整。尚秋峰等人[4]在建模過程中引入節(jié)點(diǎn)重要度概念,通過和聲搜索算法進(jìn)行求解,獲取最優(yōu)控制器部署方案。當(dāng)前已有方法未能考慮時(shí)延對(duì)部署結(jié)果的影響,導(dǎo)致可靠性指數(shù)下降,平均時(shí)延增加。因此,本文提出一種SDN中多控制器均衡部署優(yōu)化方法。經(jīng)實(shí)驗(yàn)測(cè)試證明,所提方法可以有效減少平均時(shí)延,同時(shí)獲取較高的部署方案可靠性指數(shù)。

2 多控制器均衡部署優(yōu)化方法

2.1 SDN中多控制器均衡部署模型

對(duì)于已知的網(wǎng)絡(luò)場(chǎng)景,進(jìn)行多控制器均衡部署需要優(yōu)先滿足以下需求,分別為:

1)成本低廉

將控制器的成本下降至最低,同時(shí)在控制器性能配置相同的情況下,應(yīng)該盡可能少量部署控制器。

2)較低的時(shí)延

如果在管轄區(qū)域內(nèi),有一個(gè)全新的數(shù)據(jù)包抵達(dá)交換機(jī),需要優(yōu)先檢查流表中是否存在對(duì)應(yīng)的流向項(xiàng)。假設(shè)沒有,繼續(xù)發(fā)送安裝請(qǐng)求,同時(shí)等待全新的流規(guī)則送達(dá),此過程中會(huì)形成時(shí)延開銷。由此可見,流安裝時(shí)延會(huì)對(duì)網(wǎng)絡(luò)的信息傳輸速度和實(shí)時(shí)性產(chǎn)生不良影響。所以,在安裝過程中需要有效降低安裝時(shí)延,確保網(wǎng)絡(luò)整體的服務(wù)質(zhì)量得到有效增強(qiáng)。

3)負(fù)載均衡

在每一個(gè)控制器對(duì)應(yīng)的管轄區(qū)域內(nèi)均放置一個(gè)交換機(jī)。放置交換機(jī)的主要目的是實(shí)時(shí)接收區(qū)域內(nèi)的流安裝請(qǐng)求。另外,在進(jìn)行區(qū)域劃分的過程中,需要確保流請(qǐng)求速度和控制器處理速度兩者完全相同,最終可以更好完成網(wǎng)絡(luò)負(fù)載均衡[5,6]。

在上述分析的基礎(chǔ)上,SDN中多控制器均衡部署問題可以描述為以下形式:

對(duì)于已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)而言,需要優(yōu)先計(jì)算不同控制器的處理能力,將其作為判定依據(jù),設(shè)定最大流安裝延時(shí),同時(shí)確保其不能超過設(shè)定的閾值。在上述條件下,需要優(yōu)先求解控制器部署的最佳數(shù)量和位置,同時(shí)還需要確保各個(gè)控制器達(dá)到負(fù)載均衡。

為了方便組建SDN中多控制器均衡部署模型[7,8],需要設(shè)定以下形式的網(wǎng)絡(luò)場(chǎng)景

設(shè)定網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為G(V,E),V代表管轄區(qū)域內(nèi)全部交換機(jī)組成的集合;E代表管轄區(qū)域內(nèi)全部交換機(jī)組成的鏈路集合。由于不同交換機(jī)所對(duì)應(yīng)的控制器不同,管轄區(qū)域也就不同,所以對(duì)應(yīng)的到達(dá)速率和消息發(fā)送率也會(huì)存在十分明顯的差異。假設(shè)全部控制器的處理能力相同,針對(duì)網(wǎng)絡(luò)拓?fù)銰而言,需要制定對(duì)應(yīng)的控制器部署方案。

將事先設(shè)定的約束條件設(shè)定為選取最佳交換機(jī)節(jié)點(diǎn)的依據(jù),同時(shí)對(duì)不同的管轄區(qū)域內(nèi)放置對(duì)應(yīng)的控制器。根據(jù)控制器的處理能力設(shè)定控制器的放置數(shù)量,以此為依據(jù)進(jìn)行區(qū)域劃分。另外,還需要對(duì)各個(gè)交換機(jī)的安裝時(shí)延以及負(fù)載能力進(jìn)行計(jì)算,并且借助對(duì)應(yīng)的優(yōu)化方法進(jìn)行求解,獲取控制器的最佳部署方案[9,10]。

對(duì)于已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),結(jié)合對(duì)應(yīng)的控制器部署思想,分別在不同的子區(qū)域內(nèi)放置一定數(shù)量的控制器。其中,控制器進(jìn)行通信的方式主要為以下幾種形式:

1)帶外模式內(nèi)的交換機(jī);

2)區(qū)域內(nèi)的交換機(jī)。

如果研究區(qū)域規(guī)模比較大,需要以控制器處理速度為依據(jù)進(jìn)行區(qū)域劃分,同時(shí)各個(gè)管轄區(qū)域內(nèi)的交換機(jī)是由控制器對(duì)應(yīng)區(qū)域內(nèi)的控制器進(jìn)行管理。

當(dāng)網(wǎng)絡(luò)中隨機(jī)一個(gè)交換機(jī)接收到全新的數(shù)據(jù)包時(shí),需要優(yōu)先將Packet-in信息傳輸至控制器中,同時(shí)形成全新的流規(guī)則,將得到的流規(guī)則發(fā)送到交換機(jī)中,此時(shí)會(huì)形成流安裝時(shí)延。設(shè)定網(wǎng)絡(luò)被劃分為k個(gè)區(qū)域,根據(jù)交換機(jī)的信息處理能力設(shè)定控制器數(shù)量。對(duì)于整個(gè)網(wǎng)絡(luò)而言,平均流安裝時(shí)延Lavg和交換機(jī)總數(shù)兩者之間的比值可以表示為式(1)的形式

(1)

上式中,Nj代表交換機(jī)的總數(shù);Li,cj代表第j個(gè)交換機(jī)和控制器cj之間產(chǎn)生的信息交換時(shí)延。

由于控制器和交換機(jī)之間存在十分明顯的差異,所以流安裝時(shí)延可以劃分為兩個(gè)部分,每一部分都代表不同形式的時(shí)延。

針對(duì)于分組交換的網(wǎng)絡(luò)而言,時(shí)延可以劃分為以下幾種形式,分別為:

1)發(fā)送時(shí)延;

2)傳播時(shí)延;

3)排隊(duì)時(shí)延;

4)處理時(shí)延。

在已知的網(wǎng)絡(luò)設(shè)備中,3)和4)可以被統(tǒng)稱為逗留時(shí)延,以下分別針對(duì)不同形式的時(shí)延進(jìn)行建模和分析,詳細(xì)的操作步驟如下所示:

假設(shè)初始交換機(jī)i和控制器cj兩者進(jìn)行信息交換的路徑上共有hi,s(j)個(gè)中間交換機(jī),其中主要包含Packet-in信息和Packet-out信息。當(dāng)進(jìn)行流安裝時(shí),會(huì)產(chǎn)生發(fā)送時(shí)延Ti,cj,具體的計(jì)算公式如下

(2)

式中,Ms和Mc代表不同字節(jié)在交換機(jī)中所占比例;Rs和Rc分別代表交換機(jī)和控制器的發(fā)送速率。

(3)

(4)

設(shè)定交換機(jī)和控制器兩者進(jìn)行信息交換的路徑為Pi,則交換機(jī)內(nèi)傳播時(shí)延總和與鏈路傳播速率兩者之間的比值Wi,cj為

(5)

(6)

上式中,k代表常數(shù)。

通過負(fù)載方差理論計(jì)算各個(gè)控制器之間的負(fù)載均衡度,以此為依據(jù),計(jì)算研究區(qū)域內(nèi)控制器中Packet-in消息的平均到達(dá)速度方差,具體計(jì)算式如下:

(7)

在上述分析的基礎(chǔ)上,需要考慮時(shí)延、負(fù)載以及成本等因素,同時(shí)構(gòu)建SDN中多控制器均衡部署模型min(Lavg,D,k),如式(8)所示:

(8)

2.2 模型求解

遺傳算法是一種進(jìn)化計(jì)算方法[13,14],同時(shí)也屬于人工智能的重要組成部分。遺傳算法的詳細(xì)操作步驟如圖1所示。

圖1 遺傳算法的基本操作流程圖

1)對(duì)算法的全部參數(shù)進(jìn)行初始化處理,同時(shí)隨機(jī)形成n個(gè)染色體。

2)根據(jù)已知的目標(biāo)函數(shù),需要分別計(jì)算不同染色體的函數(shù)值,即適應(yīng)度。

3)對(duì)全部染色體進(jìn)行變異和交叉操作,使其形成全新的后代。

4)分別計(jì)算后代和父代的適應(yīng)度,同時(shí)根據(jù)適應(yīng)度規(guī)則形成下一代。

5)重復(fù)上述操作步驟,直至達(dá)到設(shè)定的終止條件則結(jié)束操作。

在遺傳算法中[15],初始化的過程就是隨機(jī)形成一組解。但是,隨機(jī)形成的解并不一定能夠具有良好的表現(xiàn)性能。所以,以下采用K-Center算法進(jìn)行初始化處理,確保初始化過程中能夠獲取性能良好的解。

K-Center算法屬于一種無(wú)監(jiān)督學(xué)習(xí)算法,優(yōu)先隨機(jī)選取K個(gè)中心,通過適應(yīng)度函數(shù)不斷迭代更新中心點(diǎn)的位置,直至中心點(diǎn)位置不發(fā)生改變時(shí),則停止收斂。以下主要通過K-Center算法來(lái)解決遺傳算法中結(jié)果容易受到初始節(jié)點(diǎn)選擇影響的弊端,整個(gè)算法的核心操作步驟為:

1)設(shè)定聚類中心;

2)針對(duì)數(shù)據(jù)集中的各個(gè)點(diǎn)而言,需要計(jì)算它和其它已知聚類中心的距離;

3)重新選取一個(gè)新的數(shù)據(jù)點(diǎn)作為全新的聚類中心;

4)重復(fù)步驟2)和步驟3),直至聚類中心全部被選出來(lái);

5)通過k個(gè)初始聚類中心來(lái)執(zhí)行K-Center算法。

在遺傳算法得到基礎(chǔ)上,為了有效避免隨機(jī)選擇初始父代對(duì)算法的運(yùn)行結(jié)果以及運(yùn)行時(shí)間產(chǎn)生影響,通過K-Center算法能夠形成初始父代解,確保算法能夠獲取更加良好的性能。

遺傳算法進(jìn)行變異以及交叉操作的主要目的是擴(kuò)大搜索空間,提升最優(yōu)解的可能性。為了盡可能使變異所得到的解具有良好的表現(xiàn)性能,性能優(yōu)良的解更應(yīng)該進(jìn)行高概率的變異操作,所以每個(gè)解發(fā)生變異操作的概率probmi如式(9)所示

(9)

式中,fi代表解pi的適應(yīng)度取值;fmax和favg分別代表最大適應(yīng)度以及平均適應(yīng)度取值。

其中,遺傳算法中交叉操作的詳細(xì)操作步驟如下所示:

1)隨機(jī)選擇當(dāng)前父代Pi中的隨機(jī)兩個(gè)解pi和pj;

2)計(jì)算pi和pj的適應(yīng)度取值,同時(shí)獲取最大適應(yīng)度以及平均適應(yīng)度取值;

3)假設(shè)fi>favg且fj>favg,則執(zhí)行交叉操作;

4)假設(shè)fi

5)假設(shè)不能夠滿足步驟3)和步驟4),則以一定概率執(zhí)行交叉操作。

其中,交叉操作發(fā)生的概率probcij可以表示為式(10)的形式:

(10)

在完成變異以及交叉操作之后,在進(jìn)行下一步前期,還需要進(jìn)行排序操作。

在上述分析的基礎(chǔ)上,通過遺傳算法對(duì)SDN中多控制器均衡部署模型進(jìn)行求解,獲取最優(yōu)均衡部署方案rfu,v,如式(11)所示

(11)

3 仿真研究

為了驗(yàn)證所提SDN中多控制器均衡部署優(yōu)化方法的有效性,選取典型的網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真測(cè)試。

實(shí)驗(yàn)主要選取文獻(xiàn)[3]方法和文獻(xiàn)[4]方法作為對(duì)比對(duì)象,在圖2中分別部署多個(gè)控制器,分析可靠性指數(shù)和控制器數(shù)量之間的關(guān)系。

圖2 不同方法部署方案可靠性指數(shù)和控制器數(shù)量之間的關(guān)系分析

分析圖2中的實(shí)驗(yàn)數(shù)據(jù)可知,當(dāng)控制器數(shù)量增加,各個(gè)部署方案的可靠性指數(shù)呈直線下降趨勢(shì)。相比另外兩種方法,所提方法的部署方案可靠性指數(shù)明顯更高一些,有效驗(yàn)證了所提方法的有效性。

在上述實(shí)驗(yàn)的基礎(chǔ)上,進(jìn)一步分析不同時(shí)延限制下各個(gè)部署方案的可靠性指數(shù)變化情況,如表1所示:

表1 不同時(shí)延限制下各個(gè)方法的部署方案可靠性指數(shù)對(duì)比結(jié)果

分析表1中的實(shí)驗(yàn)數(shù)據(jù)可知,當(dāng)時(shí)延持續(xù)增加,各個(gè)部署方案的可靠性指數(shù)呈直線下降趨勢(shì)。主要是因?yàn)殡S著控制數(shù)量和時(shí)延同時(shí)增加,鏈路故障帶來(lái)的擾動(dòng)也會(huì)持續(xù)增加,對(duì)應(yīng)的部署方案可靠性指數(shù)下降。所提方法在三種方法中,能夠獲取相對(duì)較高的部署方案可靠性指數(shù)。

在上述實(shí)驗(yàn)的基礎(chǔ)上,還需要深入分析平均時(shí)延和控制器數(shù)量?jī)烧咧g的變化關(guān)系,詳細(xì)實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 不同方法平均時(shí)延和控制器數(shù)量之間的關(guān)系分析

分析圖3中的實(shí)驗(yàn)數(shù)據(jù)可知,當(dāng)控制器的數(shù)量開始增加,各個(gè)方法中交換機(jī)到控制器的平均時(shí)延開始降低。和另外兩種方法相比,所提方法的平均時(shí)延明顯更低一些。由于所提方法在構(gòu)建模型的過程中,充分考慮了時(shí)延對(duì)部署結(jié)果產(chǎn)生的影響,這樣可以有效降低時(shí)延,獲取更加滿意的部署方案。

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)方法存在的一系列問題,設(shè)計(jì)并提出一種SDN中多控制器均衡部署優(yōu)化方法。經(jīng)實(shí)驗(yàn)測(cè)試證明,所提方法可以有效提升部署方案的可靠性指數(shù),同時(shí)有效減少平均時(shí)延,獲取更加滿意的部署方案。