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

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

0 引 言

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

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

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

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

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

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

1.1.1 TE++簡介

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

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

1.1.2 TE++工作流程

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

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

圖1 TE++的拆分和合并過程

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

1.2 諾基亞的STAR算法

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

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

1.2.2 STAR路徑算法目標

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

圖2 給定拓撲和鏈路利用率的優(yōu)化樣例

圖2顯示了給定拓撲和鏈路利用率的優(yōu)化樣例。源節(jié)點和目標節(jié)點之間有三種不同的路徑：P1，P2和P3。可以選擇較長的路徑P3(6跳)，避免使用鏈路60%容量的路徑P1；或選擇最具成本效益的途徑，否則將會導致未來請求的死鎖；在另一種路由協(xié)議下，如Min-max，犧牲更長的路線以達到平衡，確保當前最大鏈路利用率盡可能小，選擇路徑P3。

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

2 基于遺傳算法SDN增強路徑裝箱方法

2.1 模型設(shè)計

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

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

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

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

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

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

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

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

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

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

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

2.2 算法思路

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

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

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

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

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

2.3 裝箱問題的數(shù)學模型

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

Y=minf=min[f1,f2]

(1)

(2)

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

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

3 實驗仿真與分析

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

圖6 實驗結(jié)果分析

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

4 結(jié)束語

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