基于遺傳算法的SDN增強(qiáng)路徑裝箱問(wèn)題研究

何利文，唐澄澄，周 睿，侯小宇

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

0 引 言

在SDN路由器的網(wǎng)絡(luò)環(huán)境中，帶寬是非常緊俏的資源。當(dāng)網(wǎng)絡(luò)流量負(fù)載不均衡時(shí)，網(wǎng)絡(luò)中部分線路帶寬利用率過(guò)高，其余網(wǎng)絡(luò)資源利用率過(guò)低，導(dǎo)致無(wú)法添加新的業(yè)務(wù)，系統(tǒng)負(fù)載下降[1]。為了解決該問(wèn)題，對(duì)SDN網(wǎng)絡(luò)增強(qiáng)路徑裝箱問(wèn)題進(jìn)行研究。文中的研究目標(biāo)是調(diào)整已有業(yè)務(wù)所在的通信鏈路，達(dá)到網(wǎng)絡(luò)中帶寬利用率的負(fù)載均衡，部署新的業(yè)務(wù)，并且在調(diào)整業(yè)務(wù)所在的通信鏈路時(shí)對(duì)系統(tǒng)的擾動(dòng)最小[2]。

在傳統(tǒng)的路由器解決方案中，路由的選擇是通過(guò)以跳數(shù)，延遲，所占帶寬資源與鏈路代價(jià)為量度的最短路徑優(yōu)先算法實(shí)現(xiàn)的。傳統(tǒng)方案的缺陷在于：如果從一個(gè)源節(jié)點(diǎn)到目的節(jié)點(diǎn)的流量超過(guò)了最短路徑的容量，最短路徑將變得擁塞，但同時(shí)這兩點(diǎn)之間可能有一條更長(zhǎng)的路徑?jīng)]有被充分利用[3]；在來(lái)自不同源節(jié)點(diǎn)的最短路徑在一條鏈路上重疊的情況下，如果通過(guò)該鏈路的總流量超過(guò)了該鏈路的容量，就會(huì)發(fā)生擁塞[4]。

在現(xiàn)有的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，為優(yōu)化路由選擇的路徑，找到流量分配的最優(yōu)方案，需要對(duì)網(wǎng)絡(luò)實(shí)施流量工程。負(fù)載均衡是流量工程中的重要功能，其本質(zhì)是一類裝箱問(wèn)題，即在帶寬等不變的信道中容納最多業(yè)務(wù)的問(wèn)題[5]。

無(wú)論是多約束路由算法還是對(duì)現(xiàn)有的網(wǎng)絡(luò)路徑，實(shí)現(xiàn)新增業(yè)務(wù)路徑的部署，這些都是具有復(fù)雜約束條件的組合優(yōu)化問(wèn)題,在理論上屬NP問(wèn)題。由于其目標(biāo)解的搜索涉及解空間的組合爆炸,傳統(tǒng)優(yōu)化方法難以求最優(yōu)解的完全問(wèn)題，通常采用啟發(fā)式算法求其近似解[6]。實(shí)踐表明，引入遺傳算法、采用新陳代謝的選擇策略、保持進(jìn)化過(guò)程中的遺傳多樣性，可以使裝箱效率有明顯的改善和提高。

1 當(dāng)前網(wǎng)絡(luò)裝箱問(wèn)題的解決方案

1.1 瞻博網(wǎng)絡(luò)TE++方案

1.1.1 TE++簡(jiǎn)介

瞻博網(wǎng)絡(luò)公司為解決網(wǎng)絡(luò)裝箱問(wèn)題，使用TE++方案來(lái)最大限度地提高帶寬利用率[7]。網(wǎng)絡(luò)流量工程結(jié)構(gòu)中的包轉(zhuǎn)發(fā)單元是多協(xié)議標(biāo)記交換(MPLS)，MPLS負(fù)責(zé)引導(dǎo)IP包流按一條預(yù)先確定的路徑通過(guò)網(wǎng)絡(luò)，這條路徑被稱作標(biāo)記交換路徑(LSP)。瞻博網(wǎng)絡(luò)定義了一個(gè)稱為“容器LSP”的新結(jié)構(gòu)，這些LSP被稱為“成員LSP”。為了處理網(wǎng)絡(luò)條件和帶寬需求的變化，TE++使用“拆分”和“合并”技術(shù)。

在“拆分”過(guò)程中，新增成員LSP重新發(fā)送帶有更新帶寬的成員LSP。在“合并”過(guò)程中，流量需求顯著下降，一個(gè)或多個(gè)成員LSP被動(dòng)態(tài)移除，把該部分帶寬給其他容器LSP使用。通過(guò)計(jì)算幾個(gè)小帶寬LSP來(lái)滿足應(yīng)用程序或服務(wù)的帶寬需求的方法，啟用容器LSP來(lái)創(chuàng)建多個(gè)帶寬較小的成員LSP。

1.1.2 TE++工作流程

容器LSP在入口路由器上管理成員LSP，入口路由器負(fù)責(zé)從成員LSP的帶寬樣本中計(jì)算容器LSP的總帶寬。每個(gè)LSP成員都可以啟用自動(dòng)帶寬機(jī)制，TE++會(huì)根據(jù)網(wǎng)絡(luò)中的流量情況動(dòng)態(tài)調(diào)整成員數(shù)量和每個(gè)成員的帶寬。通過(guò)“拆分”將現(xiàn)有容器LSP細(xì)分成更多的成員LSP，如果需要的LSP不多，則入口路由器將移除多余的成員來(lái)“合并”，或用更高的帶寬重新通知所保留的成員承擔(dān)累計(jì)帶寬。

圖1說(shuō)明了TE++的拆分和合并過(guò)程。最小信令帶寬和最大信令帶寬是在規(guī)范化期間使用的兩個(gè)閾值，以確定應(yīng)該有多少LSP以及與每個(gè)成員關(guān)聯(lián)的帶寬。示例：最小信令帶寬：2 Gbps，最大信令帶寬：8 Gbps，合并帶寬：2 Gbps，拆分帶寬：9 Gbps。容器LSP創(chuàng)建具有最小信令帶寬的最小數(shù)目LSP(AE-1)的2 Gbps，虛線表示正在被移除的LSP。當(dāng)流量開(kāi)始在LSP上移動(dòng)時(shí)，入口路由器A將從樣本中計(jì)算總帶寬。假設(shè)由于自動(dòng)帶寬機(jī)制調(diào)整，LSP增長(zhǎng)到7 Gbps。容器LSP流量激增到10 Gbps。由于原路由路徑帶寬不夠，所以通過(guò)計(jì)算將決定拆分原LSP。經(jīng)過(guò)拆分，重新創(chuàng)建一個(gè)帶有5 Gbps帶寬的新成員LSPA-E-2，并以先斷后合的方式用5 GB帶寬重新發(fā)送現(xiàn)有成員LSP A-E-1。

圖1 TE++的拆分和合并過(guò)程

經(jīng)過(guò)規(guī)范化過(guò)程合并后，容器LSP上的聚合流量已經(jīng)下降到4 Gbps，當(dāng)規(guī)格化定時(shí)器到期時(shí)，由于每個(gè)成員的利用率達(dá)到了2 Gbps的合并帶寬，因此發(fā)生合并。容器LSP刪除成員LSP-A-E-2，并以4 Gbps的帶寬重新給現(xiàn)有成員A-E-1發(fā)送信號(hào)。

1.2 諾基亞的STAR算法

1.2.1 諾基亞貝爾實(shí)驗(yàn)室的自適應(yīng)路由(STAR)算法

諾基亞貝爾實(shí)驗(yàn)室對(duì)傳統(tǒng)網(wǎng)絡(luò)最短路徑算法和多目標(biāo)的路徑計(jì)算要求進(jìn)行改進(jìn)，提出了基于集中路徑計(jì)算元件(PCE)自適應(yīng)路由調(diào)整(STAR)算法[8]。采用IP/MPLS網(wǎng)絡(luò)使用的鏈路狀態(tài)協(xié)議，開(kāi)放最短路徑優(yōu)先協(xié)議(OSPF)，中間系統(tǒng)到中間系統(tǒng)協(xié)議(IS-IS)，路由標(biāo)簽交換路徑協(xié)議(LSP)來(lái)選擇更高效的路徑，提高網(wǎng)絡(luò)利用率。

1.2.2 STAR路徑算法目標(biāo)

從數(shù)學(xué)的角度來(lái)看，網(wǎng)絡(luò)容量的調(diào)整是一個(gè)多維的裝箱問(wèn)題，在這個(gè)網(wǎng)絡(luò)利用率的優(yōu)化問(wèn)題中，每個(gè)服務(wù)請(qǐng)求代表一定數(shù)值的項(xiàng)目，為了優(yōu)化網(wǎng)絡(luò)容量利用率，優(yōu)化兩個(gè)目標(biāo)條件是：效率，在消耗最少的總網(wǎng)絡(luò)帶寬的前提下，優(yōu)化資源利用；平衡，避免鏈路的重載，以避免出現(xiàn)擁塞和死鎖的情況。

圖2 給定拓?fù)浜玩溌防寐实膬?yōu)化樣例

圖2顯示了給定拓?fù)浜玩溌防寐实膬?yōu)化樣例。源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間有三種不同的路徑：P1，P2和P3?？梢赃x擇較長(zhǎng)的路徑P3(6跳)，避免使用鏈路60%容量的路徑P1；或選擇最具成本效益的途徑，否則將會(huì)導(dǎo)致未來(lái)請(qǐng)求的死鎖；在另一種路由協(xié)議下，如Min-max，犧牲更長(zhǎng)的路線以達(dá)到平衡，確保當(dāng)前最大鏈路利用率盡可能小，選擇路徑P3。

STAR算法旨在找到最佳的鏈路平衡率和網(wǎng)絡(luò)利用率，在避免鏈路擁塞的同時(shí)，確保路徑不占用過(guò)多網(wǎng)絡(luò)資源。

2 基于遺傳算法SDN增強(qiáng)路徑裝箱方法

2.1 模型設(shè)計(jì)

通過(guò)遺傳算法計(jì)算每條業(yè)務(wù)的多條優(yōu)秀的可行路徑，在該路徑的基礎(chǔ)上再次使用遺傳算法將每條業(yè)務(wù)的路徑放置到網(wǎng)絡(luò)中的合適位置，滿足新添加的業(yè)務(wù)的網(wǎng)絡(luò)需求，并使已有業(yè)務(wù)的擾動(dòng)最小[9]。利用遺傳算法這類啟發(fā)式算法替代傳統(tǒng)算法，逐代產(chǎn)生適應(yīng)新增業(yè)務(wù)之后的網(wǎng)絡(luò)環(huán)境的個(gè)體，最終產(chǎn)生高質(zhì)量的可行解作為最優(yōu)解。

如圖3所示，SDN網(wǎng)絡(luò)增強(qiáng)路徑裝箱問(wèn)題基本框架的執(zhí)行過(guò)程大概分為如下幾個(gè)步驟：

圖3 SDN網(wǎng)絡(luò)增強(qiáng)路徑裝箱問(wèn)題基本架構(gòu)

步驟一：新的業(yè)務(wù)進(jìn)入系統(tǒng)；一個(gè)新業(yè)務(wù)的第一個(gè)數(shù)據(jù)分組進(jìn)入SDN時(shí)，到達(dá)SDN交換機(jī)，執(zhí)行步驟二。

步驟二：SDN交換機(jī)將該數(shù)據(jù)分組或者數(shù)據(jù)分組頭部發(fā)送給SDN控制器，執(zhí)行步驟四。

步驟三：SDN控制器收集其控制的網(wǎng)絡(luò)中的所有業(yè)務(wù)信息與資源信息：交換機(jī)、鏈路、業(yè)務(wù)等使用情況[10]，進(jìn)入步驟五。

步驟四：SDN控制器啟動(dòng)PCE，計(jì)算出該業(yè)務(wù)需要通過(guò)的路徑，如果成功計(jì)算出，則將該業(yè)務(wù)的路徑信息加入到SDN交換機(jī)的流表項(xiàng)中部署；如果SDN控制器無(wú)法查找到合適的路由路徑，執(zhí)行步驟三。

步驟五：SDN控制器啟動(dòng)PCE,生成每條業(yè)務(wù)的多條備用路徑，將這些路徑作為輸入使用遺傳算法，算出業(yè)務(wù)裝箱的最佳方案，保證新業(yè)務(wù)可以加入到SDN網(wǎng)絡(luò)中，實(shí)現(xiàn)負(fù)載均衡，進(jìn)入步驟六。

步驟六：SDN控制器將計(jì)算出的配置信息傳輸給網(wǎng)絡(luò)中的SDN交換機(jī)，進(jìn)入步驟七。

步驟七：SDN交換機(jī)收到配置信息，調(diào)整不滿足要求的業(yè)務(wù)流的路徑、修改該業(yè)務(wù)流所經(jīng)過(guò)的SDN交換機(jī)的流表項(xiàng)，同時(shí)將新添加的業(yè)務(wù)下發(fā)給相應(yīng)交換機(jī)的流表中，完成新業(yè)務(wù)的轉(zhuǎn)發(fā)。

步驟八：完成新業(yè)務(wù)的部署并完成SDN網(wǎng)絡(luò)的負(fù)載均衡[11]。

2.2 算法思路

在圖4中，鏈路中三元組(0/1,0/1,0/1)第一個(gè)位置代表業(yè)務(wù)1是否經(jīng)過(guò)該鏈路，經(jīng)過(guò)為1，不經(jīng)過(guò)為0，第二、三個(gè)位置代表業(yè)務(wù)2、3是否經(jīng)過(guò)該鏈路，經(jīng)過(guò)為1，不經(jīng)過(guò)為0。

圖5是優(yōu)化后的網(wǎng)絡(luò)狀態(tài)。

圖4 負(fù)載均衡示意(優(yōu)化前)(最大帶寬利用率ω=0.90)

圖5 負(fù)載均衡示意(優(yōu)化后)(最大帶寬利用率ω=0.57)

優(yōu)化的目標(biāo)是使經(jīng)過(guò)調(diào)整后的全局網(wǎng)絡(luò)路徑部署相對(duì)于裝箱前網(wǎng)絡(luò)擾動(dòng)率最小，同時(shí)鏈路的剩余帶寬得到最大化，網(wǎng)絡(luò)對(duì)將來(lái)到達(dá)的連接請(qǐng)求具有更高的接納能力[13]。

2.3 裝箱問(wèn)題的數(shù)學(xué)模型

在SDN網(wǎng)絡(luò)中，鏈路裝箱問(wèn)題的核心是如何妥善地部署新增的若干業(yè)務(wù)，通過(guò)遺傳找到合適的路徑組合優(yōu)化目標(biāo)使得整個(gè)網(wǎng)絡(luò)相較原來(lái)的部署擾動(dòng)率最小并且負(fù)載最優(yōu)。裝箱問(wèn)題的優(yōu)化目標(biāo)：

Y=minf=min[f1,f2]

(1)

(2)

2.4 算法的時(shí)間復(fù)雜度分析

文中算法是基于路徑選擇進(jìn)行原有的路徑優(yōu)化并裝入新增業(yè)務(wù)，算法復(fù)雜度由備用路由集的計(jì)算和遺傳算法的搜索尋優(yōu)過(guò)程決定[14]。遺傳算法本質(zhì)是一個(gè)群體迭代尋優(yōu)過(guò)程，其算法運(yùn)行時(shí)間與參數(shù)的選擇(包括群體規(guī)模popSize和遺傳算法終止條件，如最大運(yùn)行代數(shù)maxGen)相關(guān)。各備用路由集的計(jì)算采用多約束路徑遺傳算法，其復(fù)雜度為O(m·maxGen1·n·(n+popSize1))，其中m是業(yè)務(wù)個(gè)數(shù)，popSize1是多約束路由計(jì)算的種群規(guī)模，n是網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)，maxGen1是多約束路由計(jì)算的迭代次數(shù)。裝箱時(shí)，對(duì)染色體的每一條鏈路的適應(yīng)度評(píng)價(jià)是算法執(zhí)行次數(shù)最多的基本運(yùn)算，文中算法的編碼長(zhǎng)度是m+φ，m是已經(jīng)存在的業(yè)務(wù)，φ是新增業(yè)務(wù)個(gè)數(shù)。通過(guò)計(jì)算，可以知道一個(gè)解的總復(fù)雜度為：O(maxGen2·popSize2·(popSize2+m)+φ·maxGen1·n·(n+popSize1))。其中popSize2是遺傳算法的種群規(guī)模，maxGen2是迭代次數(shù)。

3 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)基于500節(jié)點(diǎn)的網(wǎng)絡(luò)，現(xiàn)有24k鏈路，50條業(yè)務(wù)。請(qǐng)求的新業(yè)務(wù)的帶寬要求在1 G、800 M、500 M、50 M中隨機(jī)選取，跳數(shù)約束為不大于80跳。

圖6 實(shí)驗(yàn)結(jié)果分析

圖6的實(shí)驗(yàn)結(jié)果是在初始種群規(guī)模為50，遺傳算法迭代次數(shù)在250，500，750，和1 000代時(shí)生成的結(jié)果。由此可說(shuō)明文中算法對(duì)大規(guī)模的約束網(wǎng)絡(luò)模型具有良好的收斂速度。

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

基于遺傳算法的SDN增強(qiáng)路徑裝箱方法，將SDN控制器負(fù)責(zé)路徑計(jì)算和流量規(guī)劃的PCE模塊中遇到的裝箱問(wèn)題抽象成整數(shù)規(guī)劃的多約束數(shù)學(xué)模型[15]。當(dāng)網(wǎng)絡(luò)空載時(shí)，多個(gè)不同要求的業(yè)務(wù)同時(shí)部署進(jìn)當(dāng)前網(wǎng)絡(luò)中，可以調(diào)用本算法計(jì)算每個(gè)業(yè)務(wù)使用的工作路由的整數(shù)序列，找出最優(yōu)的備用路由序列組合；當(dāng)部分業(yè)務(wù)不能直接計(jì)算出可行路徑時(shí)，可以調(diào)用全局尋優(yōu)的方式找到一個(gè)新的路由整數(shù)序列，使得新業(yè)務(wù)部署后網(wǎng)絡(luò)的整體擾動(dòng)率最小，實(shí)現(xiàn)網(wǎng)絡(luò)資源的優(yōu)化。