基于多目標約束遺傳算法的SDN路徑增強算法

周 睿，何利文，唐澄澄，侯小宇，陸錢春

(1.南京郵電大學，江蘇 南京 210003；2.中興通訊股份有限公司，江蘇 南京 210012)

1 概 述

網(wǎng)絡(luò)的穩(wěn)定性是網(wǎng)絡(luò)正常運行的重要前提，減少網(wǎng)絡(luò)變更對生產(chǎn)生活的影響就變得至關(guān)重要，這同時還會減少相關(guān)設(shè)備和協(xié)議的巨大安裝成本。想在傳統(tǒng)網(wǎng)絡(luò)上有所創(chuàng)新變得困難，幾乎沒有什么辦法來嘗試新的網(wǎng)絡(luò)協(xié)議，因此人們普遍認為網(wǎng)絡(luò)設(shè)施已經(jīng)變得僵化了[1]。但是隨著移動設(shè)備和內(nèi)容的爆炸式增長、服務(wù)器虛擬化，以及云計算的出現(xiàn)推動了網(wǎng)絡(luò)的進一步發(fā)展，行業(yè)開始重新審視傳統(tǒng)的網(wǎng)絡(luò)架構(gòu)。傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)是分層的，由分布式排列的交換機和路由器構(gòu)成，這種設(shè)計在客戶機-服務(wù)器計算時是占主導地位的，但是這樣的靜態(tài)架構(gòu)不適合今天的企業(yè)數(shù)據(jù)中心、校園網(wǎng)、運營商環(huán)境的計算和存儲需求[2]。近年來，SDN(software defined networking，軟件定義網(wǎng)絡(luò))的提出，為目前出現(xiàn)的這些網(wǎng)絡(luò)問題找到了新的方向。不同于傳統(tǒng)的網(wǎng)絡(luò)，SDN控制器將網(wǎng)絡(luò)設(shè)備的數(shù)據(jù)平面和控制平面分離，使用一個集中的控制器來決定網(wǎng)絡(luò)中所有轉(zhuǎn)發(fā)組件的行為[3]。并且為相關(guān)的網(wǎng)絡(luò)應(yīng)用提供可編程的接口，利用軟件的方式對整個網(wǎng)絡(luò)的資源進行控制，革命性地改變了現(xiàn)有的網(wǎng)絡(luò)架構(gòu)[4]。

在傳統(tǒng)的網(wǎng)絡(luò)體系架構(gòu)中，路由協(xié)議改進非常困難，這主要是由于設(shè)備更新?lián)Q代以及網(wǎng)絡(luò)自身的復雜性比較高，同時也會帶來非常巨大的開銷等[5]。傳統(tǒng)的QoS體系結(jié)構(gòu)(基于分布式控制平面)被證明是過于靜態(tài)的，無法獲得更廣泛的應(yīng)用[6]。SDN的出現(xiàn)直接降低了新型網(wǎng)絡(luò)開發(fā)的成本，其倡導控制轉(zhuǎn)發(fā)分離、網(wǎng)絡(luò)能力接口的開放、軟硬件解耦和網(wǎng)絡(luò)功能的虛擬化，這將會推動網(wǎng)絡(luò)架構(gòu)向軟件化、集約化、智能化和開放化的目標網(wǎng)絡(luò)架構(gòu)演進[7]。

它的關(guān)鍵技術(shù)包括控制和轉(zhuǎn)發(fā)解耦、實現(xiàn)控制集中化和網(wǎng)絡(luò)能力開放化這幾個方面,一個SDN控制器可以對轉(zhuǎn)發(fā)平面多臺設(shè)備進行通信，同時提供了一系列的開放編程接口，這樣對網(wǎng)絡(luò)業(yè)務(wù)的加載和控制更加靈活[8]。以往的路由算法通常是由分布式實現(xiàn)，即交換機需要生成并維護轉(zhuǎn)發(fā)表，實現(xiàn)對網(wǎng)絡(luò)的集中配置與管理，而在SDN網(wǎng)絡(luò)中，數(shù)據(jù)轉(zhuǎn)發(fā)由控制器集中管理[9]，因此，只需要通過控制器來設(shè)計與數(shù)據(jù)轉(zhuǎn)發(fā)有關(guān)的程序。在具有全局的網(wǎng)絡(luò)狀態(tài)和應(yīng)用需求的情況下，可以在一個集中的系統(tǒng)中執(zhí)行得更高效[10]，SDN控制器的出現(xiàn)大大簡化了路由創(chuàng)新的門檻。

網(wǎng)絡(luò)資源的中心化讓以前的分布式算法控制路由轉(zhuǎn)發(fā)成了歷史，這也是造成網(wǎng)絡(luò)低效的原因之一?，F(xiàn)在通過中心控制器可以高效地管理數(shù)據(jù)轉(zhuǎn)發(fā)，讓網(wǎng)絡(luò)流量更加可控，可以直接使用Dijkstra算法[11]來計算最短路，達到最佳路由。然而，SDN控制器支持的最短路徑算法無法較好地部署三層路由技術(shù)，還有就是Dijkstra算法的時間復雜度并不低，隨著網(wǎng)絡(luò)結(jié)點的增加，CPU的消耗越來越高，網(wǎng)絡(luò)尋址的效率也會降低。SDN現(xiàn)在最常見的應(yīng)用是在IDC網(wǎng)絡(luò)中，這種網(wǎng)絡(luò)通常會有成千上萬個網(wǎng)絡(luò)節(jié)點，因此，提出一種效率更高的算法是極具意義的。與此同時，網(wǎng)絡(luò)服務(wù)提供商需要根據(jù)客戶的SLA(服務(wù)等級協(xié)議)為其定制特定級別的高質(zhì)量網(wǎng)絡(luò)服務(wù)，即需要滿足如帶寬、時延、嚴格下一跳等等條件[12]。Qos需求路由問題可以理解為尋找滿足多個約束條件的可行路徑問題，這是屬于NP難問題，通常無法在多項式時間內(nèi)求解[13]。所以文中采用基于啟發(fā)式算法的遺傳算法來解決這個問題。

遺傳算法(genetic algorithm，GA)是由J.H.Holland等于20世紀70年代提出并發(fā)展起來的[14]，也是啟發(fā)式算法的一種，還是一種具有全局搜索能力的直接、并行、隨機的優(yōu)化方法。它通過模仿生物的進化，遵循進化的主要原則，本質(zhì)上是先通過隨機方式選出初始種群，根據(jù)特定的評定標準，通過選擇、交叉、變異的遺傳算子的優(yōu)化作用，優(yōu)選出性能最佳的一系列個體[15]。因為遺傳算法具有很強的全局尋優(yōu)能力和適應(yīng)性，被廣泛地應(yīng)用于路徑規(guī)劃問題。所以這里采用多目標約束遺傳算法解決多約束路由問題，既能一次計算產(chǎn)生多條可選路徑路由，也可以根據(jù)業(yè)務(wù)的需求動態(tài)調(diào)整路由計算的參數(shù)，來得到所需要的路徑。

文中提出的遺傳算法是在已有物理拓撲狀態(tài)下根據(jù)具體的業(yè)務(wù)標準需求的多目標約束遺傳算法，可以在并行的情況下自適應(yīng)地計算出符合路徑約束條件的若干條可用路徑，保證每個業(yè)務(wù)都有充足的備用路徑可供調(diào)整。對該算法的主要思想和流程進行了介紹，然后對算法展開了詳細描述，最后對算法在給定的網(wǎng)絡(luò)環(huán)境下的性能進行了分析，驗證該算法對SDN路徑增強問題的有效性。

2 SDN網(wǎng)絡(luò)約束

2.1 網(wǎng)絡(luò)模型及問題描述

即如果兩節(jié)點之間有鏈路連通，則矩陣對應(yīng)的元素為1，否則為0。同理，鏈路帶寬容量矩陣用B={bi,j},vi,vj∈V,ek=(vi,vj)∈E表示，其中bi,j表示節(jié)點i和節(jié)點j之間鏈路的帶寬容量大??；時延矩陣D={dij},vi,vj∈V,ek=(vi,vj)∈E,dij表示節(jié)點i和節(jié)點j之間的鏈路時延的值，cij表示節(jié)點i和節(jié)點j之間的鏈路開銷的值。

2.2 約束優(yōu)化模型

假定兩個節(jié)點vi,vj之間有一條不帶環(huán)的通路路徑，記為：path=(vi,vj)，如果路徑path經(jīng)過鏈路ek，那么ek∈path,否則ek?path。文中路徑是由染色體個體的形式表示的，即每個染色體代表一條路徑，有x1,x2,…,xn，這里使用變長的實數(shù)編碼的方式，以s和d為其起始節(jié)點，每個個體所表示的路徑經(jīng)過的節(jié)點數(shù)量是不定的。多約束路由問題中的多約束條件可以表述為:

(1)

(2)

(3)

(4)

?(xij=1)bi,j·xi,j>BandWidth

(5)

(6)

其中，xij表示路徑x中對應(yīng)的鏈路有效因子，當(vi,vj)屬于x時，xij=1，否則xij=0。Cost、Delay、Hop、Bandwidth分別是SDN路由中要求的額定開銷、時延、跳數(shù)和帶寬的可變參數(shù)，在這里一般表示為常數(shù)。

3 改進的多目標約束的遺傳算法

3.1 路徑編碼

根據(jù)網(wǎng)絡(luò)拓撲路徑的特點，采用鏈式變長實數(shù)編碼的方式，如：源節(jié)點是0.0，目的節(jié)點是120.3，路徑依次經(jīng)過節(jié)點0.0、3.5、50.9、70,3、62.8、109.5、120.4，那么路徑編碼就是0.0→50.9→70.3→62.8→109.5→120.4。這樣的編碼和解碼的過程相對來講比較簡單，代表每一個節(jié)點的實數(shù)根據(jù)網(wǎng)絡(luò)中節(jié)點的數(shù)量會做相應(yīng)的調(diào)整，隨著網(wǎng)絡(luò)規(guī)模的變化相應(yīng)地改變小數(shù)位的位數(shù)，如圖1所示。

圖1 網(wǎng)絡(luò)拓撲

3.2 種群初始化

遺傳算法需要通過初始種群的生成的篩選滿足路徑規(guī)劃類約束條件。這里引入了He L在用混合遺傳算法解決電信網(wǎng)絡(luò)備用路由的研究中提出的SPA算法(最短路徑優(yōu)先)[16]，并且根據(jù)約束條件進行改進，在原有隨機路徑選擇生成的過程中滿足相應(yīng)的約束條件。算法流程如下：

(1)從源節(jié)點開始；

(2)尋找所有與源節(jié)點相連接的節(jié)點，記錄這些節(jié)點作為當前節(jié)點；

(3)檢查這些當前節(jié)點中是否有目的節(jié)點；

(4)如果有，則記錄源節(jié)點和目的節(jié)點之間的鏈路，計算完成，否則，繼續(xù)計算；

(5)繼續(xù)查找與當前節(jié)點相連的節(jié)點，作為當前節(jié)點；

(6)查看這些節(jié)點是否有源節(jié)點，如果有則將其從列表中刪除；

(7)重復步驟3，直到找到最短路徑為止。

約束條件為：嚴格下一跳和松散下一跳；排除某個節(jié)點；親和力屬性的處理。

改進的SPA算法：

(1)從源節(jié)點開始；

(2)尋找所有與源節(jié)點相連接的節(jié)點，記錄這些節(jié)點為當前節(jié)點集合；

(3)檢查當前節(jié)點是否有目的節(jié)點；

(4)如果有，則記錄源節(jié)點和目的節(jié)點之間的鏈路，計算完成，否則繼續(xù)計算；

(5)檢查當前節(jié)點中有無需要排除的節(jié)點，如果有則從當前節(jié)點中刪除，繼續(xù)計算；

(6)檢查當前節(jié)點集合中有無嚴格下一跳或者松散下一跳的節(jié)點，如果集合中有下一跳節(jié)點就走上去，否則繼續(xù)計算；

(7)檢查與當前節(jié)點集合中節(jié)點連接的所有鏈路上的親和力屬性有無滿足當前業(yè)務(wù)的親和力屬性，如果有就走該鏈路，否則繼續(xù)計算；

(8)繼續(xù)查找與當前節(jié)點相連的節(jié)點，作為當前節(jié)點；

(9)查看這些節(jié)點是否有源節(jié)點，如果有則將其從列表中刪除；

(10)重復步驟3，直到找到可行的路徑為止。

3.3 個體選擇

個體選擇概率取決于種群中個體的適應(yīng)度及其分布，為了簡單有效地控制選擇壓力并且使得個體有更好的魯棒性，選擇使用輪盤賭的方法。解決路徑規(guī)劃的優(yōu)化問題必須要先解決問題模型中的約束條件問題，包括一些等式和不等式的約束條件，在遺傳算法中對約束條件的處理會帶來一些額外的參數(shù)。首先要將所有的等式約束條件轉(zhuǎn)化成不等式約束條件，這樣就只處理不等式約束條件即可。文中采用靜態(tài)懲罰函數(shù)法來處理不等式約束條件，適應(yīng)度函數(shù)定義為：

(7)

3.4 交叉運算

交叉運算產(chǎn)生子代，子代繼承父代的基本特征，主要包括兩個內(nèi)容：第一是對種群中的個體進行隨機配對并按照設(shè)定的交叉概率Pm來確定需要交叉的個體對；第二是設(shè)定個體的交叉點，然后對個體的部分片段相互交換。交叉算子的設(shè)計與編碼方式有關(guān)，在最優(yōu)路徑規(guī)劃問題中有幾種代表性的交叉算子，如：順序交叉、類OX交叉等。這些交叉算子在產(chǎn)生新個體的過程中沒有目的性,對于實數(shù)編碼的最優(yōu)規(guī)劃問題,這些交叉可能破壞親代的較優(yōu)基因,從而使交叉算子的搜索能力大大降低?；诖?，文中擬用在重復節(jié)點位置交叉且只進行一點交叉的操作方式，具體實現(xiàn)步驟如下：

·隨機選取兩個個體作為帶交叉?zhèn)€體；

·找到兩個帶交叉?zhèn)€體的共同點(源節(jié)點和目的節(jié)點除外)的集合；

·從共同節(jié)點的集合中隨機選擇一個節(jié)點作為交叉節(jié)點；

·檢查兩個帶交叉?zhèn)€體在交叉節(jié)點之前和之后的內(nèi)容是否相同。如果相同，則取消此次的交叉操作。

具體的操作過程如下：

(1)設(shè)選取的兩個待交叉樣本為0.0，3.5，50.9，70.3，62.8，109.5，120.4和0.0，23.1，50.9，25.6，62.8，98.5，120.4，如圖2所示；

(2)兩者重復節(jié)點為{50.9，62.8}；

(3)隨機選擇節(jié)點50.9作為交叉節(jié)點；

(4)檢查發(fā)現(xiàn)兩者帶交叉樣本在節(jié)點50.9之前和之后的內(nèi)容均不相同，因此可以進行此次操作，交叉之后會產(chǎn)生新的個體：

0.0,3.5,50.9,25.6,62.8,98.5,120.4

0.0,23.1,50.9,70.3,62.8,109.5,120.4

圖2 交叉操作

3.5 變異操作

變異操作是對個體的某些基因值做變動。目的有兩個，第一使遺傳算法具有局部的隨機搜索能力,當經(jīng)過交叉操作群體已接近最優(yōu)解時,利用變異算子可以加速向最優(yōu)解收斂;第二是使遺傳算法可維持群體的多樣性,以防止早熟現(xiàn)象。變異算子的設(shè)計也與編碼方法有關(guān),對于實數(shù)編碼的TSP問題，可采用逆轉(zhuǎn)變異、對換變異和插入變異等。逆轉(zhuǎn)變異,也稱倒位變異,是指在個體編碼中隨機選擇兩點,再將這兩點內(nèi)的字串按反序插入到原位置中。倒位變異考慮了與原邊的鄰接關(guān)系,能將巡回路線上的優(yōu)良基因性能較好地遺傳到下一代,提高尋優(yōu)速度?；诖?，該項目具體實現(xiàn)步驟如下：

(1)隨機選取一個個體作為待變異個體；

(2)在待變異個體中隨機選擇一個節(jié)點(起點和終點除外)作為待變異節(jié)點；

(3)找到與當前待變異節(jié)點直接相連的節(jié)點集合(該集合中不包括起點、終點以及待變異個體中的節(jié)點)；

(4)從節(jié)點集合中隨機選取一個節(jié)點作為變異后節(jié)點；

(5)檢查待變異節(jié)點之前和之后的節(jié)點是否與變異后節(jié)點直接相連。若直接相連，則用變異后節(jié)點替代待變異節(jié)點完成變異過程；否則，放棄此次操作，回到第4步，直至將節(jié)點集合中的所有節(jié)點全部選遍。

操作的實現(xiàn)過程如下：

(1)選擇待變異的個體為0.0，23.1，50.9，70.3，62.8，109.5，120.4，如圖3所示；

(2)隨機選擇節(jié)點50.9為變異節(jié)點；

(3)與節(jié)點50.9直接相連的節(jié)點集合為{3.5，31.9，25.6}；

(4)隨機選擇節(jié)點3.5作為變異后節(jié)點；

(5)經(jīng)過檢查發(fā)現(xiàn)節(jié)點23.1與節(jié)點3.5并不直接相連，所以取消此次變異操作，接著選取節(jié)點31.9作為變異后的節(jié)點，檢查后發(fā)現(xiàn)節(jié)點23.1和節(jié)點31.9、節(jié)點31.9和節(jié)點70.3直接相連，所以此次變異操作是可以的，變異后的新個體為：0.0，23.1，31.9，70.3，62.8，109.5，120.4。

圖3 變異操作

3.6 終止條件

初始種群規(guī)模相對較大或者網(wǎng)絡(luò)拓撲規(guī)模相對較小時，算法收斂速度則相對較快。基于這一原因，算法終止條件選定為“迭代達到最大世代數(shù)”或者“種群中半數(shù)以上位置被生成的最優(yōu)個體占據(jù)”。

3.7 算法完整流程

第六步：檢查代數(shù)是否已經(jīng)達到設(shè)定的值，如果滿足則停止遺傳算法，否則重復第二步。

4 實驗仿真與分析

實驗的網(wǎng)絡(luò)路由模型采用滿足多約束的最小費用模型，網(wǎng)絡(luò)規(guī)模為500節(jié)點24 k鏈路，費用和時延皆在[1,10]中隨機選取。帶寬以1 M為單位，鏈路的帶寬分別在10 G、20 G、30 G、40 G中隨機選取，隨機網(wǎng)絡(luò)生成后，隨機選取源點和宿點并用最短路算法求解最小時延路的時延D1和最小費用路的時延D2，取d=(D2-D1)/4。時延約束取不大于D2+d；請求的業(yè)務(wù)的帶寬要求在1 G、800 M、500 M、50 M中隨機選取，跳數(shù)約束為不大于80跳。

圖4的實驗結(jié)果是在初始種群規(guī)模為50，交叉變異概率分別為0.5，0.3的情況下生成的，由此說明文中算法對這種大規(guī)模的約束網(wǎng)絡(luò)模型具有比較快的收斂速度。

圖4 遺傳代數(shù)與最優(yōu)個體適應(yīng)度值的變化

Dijkstra算法在求解最短路徑的過程中,無論起始節(jié)點距離終點多遠都需要遍歷整網(wǎng)的拓撲，在節(jié)點數(shù)為n的網(wǎng)絡(luò)中，Dijkstra算法的復雜度為O(n)。對于節(jié)點數(shù)和邊數(shù)比較大的大規(guī)模圖，當n比較大時,該算法所需計算機的時間資源與空間資源將急劇增加；對GA算法,路徑長度主要影響算法的收斂時間，GA算法的搜索空間大小為路徑的長度，所以根據(jù)算法的特點決定文中的遺傳算法更適合大規(guī)模網(wǎng)絡(luò)路徑的計算。圖5是KSP算法和改進遺傳算法同時計算10條無約束路徑的耗時，實驗結(jié)果也驗證了這個結(jié)論。

圖5 KSP算法與文中算法的耗時比較

5 結(jié)束語

文中提出的基于多目標多約束的改進遺傳算法可以在保證一定性能的前提下，在大規(guī)模網(wǎng)絡(luò)中計算出符合所有約束的最優(yōu)路徑。并且，該算法主要具有以下特點:改進了初始路徑的生成方式，顯著提高了算法的搜索效率，可以解決嚴格下一跳和松散下一跳的約束;實數(shù)編碼,簡化了編碼和解碼的操作,省略了復雜的解碼過程;啟發(fā)式交叉策略,加快了算法收斂的速度；該算法較傳統(tǒng)的K最短路徑算法更適合大規(guī)模網(wǎng)絡(luò)路徑的計算。