SDN路由器全配置下的網(wǎng)絡流量工程仿真優(yōu)化分析

吳菁晶，尹嘉麒

（1.東北大學 計算機科學與工程學院，遼寧 沈陽 110819；2.中北大學 電氣與控制工程學院，山西 太原 030051）

0 引 言

隨著網(wǎng)絡業(yè)務多媒體化、物聯(lián)網(wǎng)化的發(fā)展，網(wǎng)絡中新業(yè)務需求量迅速增長[1]。但是，目前網(wǎng)絡提供的流量并不足以應對這種增長，需要更好的路由方式對網(wǎng)絡中的新業(yè)務進行更有效的規(guī)劃。當前，網(wǎng)絡中普遍使用兩種常見的路由協(xié)議，內(nèi)部網(wǎng)關協(xié)議（Interior Gateway Protocol, IGP）和多協(xié)議標簽交換（Multi-Protocol Label Switching, MPLS）[2]。IGP協(xié)議在建立路由轉發(fā)表時是由計算最短路徑方式來建立的。因此，這樣的路由方式對網(wǎng)絡鏈路帶寬和業(yè)務本身的特點并不關心，前者會造成鏈路擁塞，后者則不能滿足業(yè)務的服務質量需求。MPLS協(xié)議在一定程度上能夠隨網(wǎng)絡情況動態(tài)調(diào)整，但是該協(xié)議算法復雜度較高，路由器之間需要頻繁的交互信息。在業(yè)務量較多的情況下，需要存儲大量的網(wǎng)絡狀態(tài)信息和路由信息，而且這些信息都需要人工配置，因此配置過程十分繁瑣而且配置成本高[3]。綜上所述，目前這兩種主要的路由協(xié)議，即IGP協(xié)議和MPLS協(xié)議都不能很好地適應目前的情況，因此急需設計一種成本低，并且能夠隨網(wǎng)絡變化動態(tài)調(diào)整，同時避免網(wǎng)絡擁塞的流量工程技術以解決上面提到的問題。

近年來，為了解決傳統(tǒng)網(wǎng)絡不能靈活操控網(wǎng)絡流量的問題，軟件定義網(wǎng)絡（Software Defined Network, SDN）的網(wǎng)絡架構被提出[4-6]。SDN技術可通過軟件編程的形式定義和控制網(wǎng)絡，形成獨立的控制層，掌握全局網(wǎng)絡信息，方便對業(yè)務轉發(fā)路徑進行集中計算，這樣路由器只需要根據(jù)控制平面配置的路由表對數(shù)據(jù)進行轉發(fā)，就可以大大降低鏈路堵塞的概率，提高數(shù)據(jù)包轉發(fā)效率[7-8]。通過上述分析，SDN使得網(wǎng)絡在垂直方向上變得開放化、標準化、可編程化，能夠很好地解決當前網(wǎng)絡面臨的流量控制僵化問題。

1 問題描述

設在網(wǎng)絡中所有路由器都是SDN路由器，并且網(wǎng)絡中只有一個集中的SDN控制器。將網(wǎng)絡抽象為一個有向圖G（N，E），N代表網(wǎng)絡中的路由器集合，E代表網(wǎng)絡中的鏈路集合。假定流量矩陣對SDN控制中心來說是已知的，根據(jù)這些已知的流量信息，SDN控制器為每個業(yè)務計算轉發(fā)路徑，使得當前網(wǎng)絡獲得最好的性能指標，最優(yōu)的流量工程優(yōu)化效果。源節(jié)點s和目的節(jié)點d之間的業(yè)務矩陣用fsd來表示。

變量定義如下：

e：表示網(wǎng)絡中的鏈路；

map(e)：表示鏈路e上的權重；

c(e)：表示鏈路e上的鏈路容量；

fsd：表示輸入業(yè)務矩陣；

u(e)：表示鏈路e上的利用率；

INi：表示注入點i的數(shù)據(jù)流；

OUTi：表示流出點i的數(shù)據(jù)流；

x(P)：表示一條路徑P上的流量大??；

W(P)：表示路徑權重；

Pi：表示從s到d的路徑集合。

約束條件的具體描述如下：

約束條件為：

式（1）表示優(yōu)化目標為最小化網(wǎng)絡中的鏈路最大利用率。式（2）表示整個網(wǎng)絡中的流量需要守恒，即節(jié)點發(fā)出的總流量等于節(jié)點接收的總流量。式（3）表示鏈路利用率與鏈路容量和鏈路負載的關系。式（4）表示輸入業(yè)務流不能為負數(shù)。式（5）表示單個節(jié)點的流量守恒。當一個節(jié)點既不是目的節(jié)點也不是源節(jié)點時，它的輸入流量等于輸出流量；當該節(jié)點是源節(jié)點時，它的輸出流量減去輸入流量等于該節(jié)點發(fā)出的流量；當該節(jié)點是目的節(jié)點時，它的輸出流量減去輸入流量等于該節(jié)點的接收流量。

2 基于貪婪算法的模型求解

貪婪算法（Greedy Algorithm, GA）是一種快速求解問題較優(yōu)解的方法。貪婪算法的特點是一步一步進行問題求解，以某個因素評價當前解，尋找當前階段的最優(yōu)解，它通常以當前情況為基礎根據(jù)某個優(yōu)化標準做出最優(yōu)選擇，將所求問題簡化成規(guī)模更小的子問題，省去了為尋找最優(yōu)解而枚舉所有可能情況所消耗的大量時間。這個最小化網(wǎng)絡鏈路利用率問題可以轉化為最小化數(shù)據(jù)傳輸代價問題?？梢园焰溌窓嘀囟閭鬏敭斍皵?shù)據(jù)流后鏈路的利用率即：

式中，f表示當前需要路由的數(shù)據(jù)流大小，由此可以看出，在尋路過程中選擇權重較小的路徑就能夠達到減小網(wǎng)絡中最大鏈路利用率的目的。

模型可以轉化為：

約束條件為：

式（7）表示需要最小化網(wǎng)絡的最大鏈路利用率。式（8）表示數(shù)據(jù)流選擇的路徑是源節(jié)點與目的節(jié)點之間權重最小的一條路徑，其中Pi代表源節(jié)點和目的節(jié)點間所有存在路徑。

式（9）是對鏈路上數(shù)據(jù)流大小的約束。式（10）表示路徑上業(yè)務流為非負。

2.1 全SDN配置下的單跳轉發(fā)算法

關于SDN單跳模式本節(jié)做如下假設：

（1）SDN控制中心能夠正確并及時感知網(wǎng)絡中的相關信息。

（2）網(wǎng)絡中所有路由器均為SDN路由器。

（3）網(wǎng)絡只有一個控制中心。

（4）同一個數(shù)據(jù)流在一個SDN路由器中只能在同一個轉發(fā)口進行轉發(fā)。

算法主要分為兩部分，其一是配置鏈路權重，其二是擇路。每個業(yè)務在轉發(fā)之前都需要配置鏈路權重，所有鏈路的初始權重均為1，由鏈路權重公式（6）可知，鏈路權重隨著業(yè)務轉發(fā)過程的進行在不斷改變。在擇路部分，采用基于貪婪算法的Dijkstra算法，選擇權重系數(shù)最小的路徑。

2.2 全SDN配置下的多跳全傳算法

在移動化、物聯(lián)網(wǎng)和多媒體化的趨勢下，網(wǎng)絡流量增長迅速，業(yè)務類型也越來越多樣化。前文介紹了SDN不同業(yè)務類型對于服務質量要求的不同。有些業(yè)務對丟包的容忍度很低，例如，交互類業(yè)務；有些業(yè)務允許少量數(shù)據(jù)包被重傳或丟棄，例如語音、視頻業(yè)務等。因此，根據(jù)業(yè)務類型的不同設計了不同的SDN轉發(fā)算法。

本小節(jié)介紹的是適合對丟包容忍度很低的業(yè)務的全SDN配置下的多跳全傳算法，關于此算法本節(jié)做如下假設：

（1）SDN控制中心能夠正確并及時感知網(wǎng)絡相關信息。

（2）網(wǎng)絡中所有路由器均為SDN路由器。

（3）網(wǎng)絡只有一個控制中心。

（4）同一個數(shù)據(jù)流在網(wǎng)絡中能夠在不同路徑上轉發(fā)。

（5）所有業(yè)務在網(wǎng)絡中都必須傳輸。

情況一：路徑P上所有鏈路均未飽和；分別計算路徑P上所有鏈路的剩余容量，根據(jù)“木桶短板原理”，路徑P的容量即路徑P中剩余容量最小鏈路的剩余容量，記為F(P)。

若F(P)小于fsd，則在該路徑上傳輸大小為F(P)的數(shù)據(jù)流，fsd=fsd-F(P)，進入下一次迭代；若F(P)大于fsd，則fsd全在該路徑上傳輸。

情況二：若路徑P上有過載鏈路，剩余容量全部都在鏈路P上傳輸。

2.3 全SDN配置下的多跳丟棄算法

本算法考慮的是適合允許數(shù)據(jù)包被稍后轉發(fā)或丟棄的業(yè)務的全SDN配置下的多跳丟棄算法，該算法首要考慮網(wǎng)絡中的鏈路不能過載，網(wǎng)絡一直處于暢通狀態(tài)。當轉發(fā)該業(yè)務會造成鏈路擁堵時SDN控制中心將擱置該業(yè)務，稍后轉發(fā)或丟棄。

全SDN配置下的多跳丟棄算法適用于允許部分數(shù)據(jù)流被擱置或丟棄的業(yè)務，做如下假設：

（1）SDN控制中心能夠正確并及時感知網(wǎng)絡相關信息。

（2）網(wǎng)絡中所有路由器均為SDN路由器。

（3）網(wǎng)絡只有一個控制中心。

馬鈴薯早疫病的癥狀通常在植株處于逆境時期易發(fā)生，而這些逆境經(jīng)常來自于缺肥（如缺氮及其他營養(yǎng)）、氣溫偏高、植株缺水、生長衰弱。

（4）同一個數(shù)據(jù)流在網(wǎng)絡中能夠在不同的路徑上轉發(fā)。

（5）網(wǎng)絡中所有鏈路都不得超載。

根據(jù)公式（6）配置每條鏈路權重，借助Dijkstra算法計算權重最小的路徑P，找到的路徑P有兩種情況：

情況一：路徑P上所有鏈路均未飽和；分別計算路徑P上所有鏈路的剩余容量，根據(jù)“木桶短板原理”，路徑P的容量即路徑P中剩余容量最小鏈路的剩余容量，記為F(P)。

若F(P)小于fsd，則在該路徑上傳輸大小為F(P)的數(shù)據(jù)流，fsd=fsd-F(P)，進入下一次迭代；若F(P)大于fsd，則fsd全在該路徑上傳輸。

情況二：若路徑P上有過載鏈路，表示如果傳輸該業(yè)務會造成網(wǎng)絡鏈路的擁堵。將該業(yè)務完全丟棄，網(wǎng)絡鏈路狀態(tài)恢復到上一個業(yè)務傳輸完成狀態(tài)。

丟棄算法與全傳算法的主要區(qū)別就在于發(fā)現(xiàn)傳輸當前業(yè)務會造成鏈路擁堵時將當前業(yè)務擱置或丟棄，直接傳輸下一個業(yè)務。

3 仿真結果對比與分析

為驗證算法性能，本章在不同條件下對OSPF（Open Shortest Path Firs, OSPF）算法、全SDN單跳算法、全SDN多跳不丟棄算法進行了比較。

從圖1可以看出，在業(yè)務矩陣較小，業(yè)務大小遠小于鏈路容量，路由完成所有業(yè)務矩陣后未出現(xiàn)鏈路過載的情況下，SDN單跳模式與SDN多跳模式優(yōu)化效果相同且遠優(yōu)于OSPF轉發(fā)模式。這說明，在業(yè)務矩陣較小時SDN單跳模式與SDN多跳模式均可行。接下來討論業(yè)務矩陣較大的情況下，哪種轉發(fā)模式優(yōu)化效果更好。

圖1 小業(yè)務矩陣下三種方案最大鏈路利用率對比

從圖2可看出，在業(yè)務矩陣較大時，SDN單跳與多跳模式均遠遠優(yōu)于OSPF轉發(fā)模式。且SDN單跳模式的表現(xiàn)差于SDN多跳模式，可以假設SDN多跳轉發(fā)模式更適合業(yè)務矩陣較大的情況，為驗證假設的正確性制定了3個指標比較SDN單跳與多跳模式。這3個指標分別是：鏈路最大利用率、網(wǎng)絡中過載鏈路數(shù)、經(jīng)過擁堵鏈路的業(yè)務數(shù)目。下面用另外的指標對2種SDN轉發(fā)模式的仿真結果進行評價。

圖2 大業(yè)務矩陣下三種方案鏈路最大利用率

圖3中參數(shù)全SDN單跳方式鏈路最大利用率、全SDN多跳方式鏈路最大利用率使用的是右側y軸；參數(shù)全SDN單跳方式過載鏈路數(shù)、全SDN多跳方式的過載鏈路數(shù)目使用的是左側y軸。圖4中參數(shù)全SDN單跳方式鏈路最大利用率、全SDN多跳方式鏈路最大利用率使用的是右側y軸；參數(shù)全SDN單跳方式經(jīng)過擁堵鏈路的業(yè)務數(shù)、全SDN多跳方式經(jīng)過擁堵鏈路的業(yè)務數(shù)目使用的是左側y軸。

圖3 大業(yè)務矩陣SDN單跳與多跳模式下過載鏈路

圖4 大業(yè)務矩陣SDN單跳與多跳模式下?lián)矶聵I(yè)務數(shù)

4 結 語

通過仿真分析將傳統(tǒng)算法、單跳SDN轉發(fā)算法和多跳SDN轉發(fā)算法進行了比較，對比了這些路由策略后指出了它們各自的優(yōu)缺點和適用情況。