吳菁晶，尹嘉麒

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

0 引 言

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

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

1 問題描述

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

變量定義如下：

e：表示網絡中的鏈路；

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

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

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

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

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

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

x(P)：表示一條路徑P上的流量大?。?/p>

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

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

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

約束條件為：

式（1）表示優(yōu)化目標為最小化網絡中的鏈路最大利用率。式（2）表示整個網絡中的流量需要守恒，即節(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)解而枚舉所有可能情況所消耗的大量時間。這個最小化網絡鏈路利用率問題可以轉化為最小化數(shù)據(jù)傳輸代價問題?？梢园焰溌窓嘀囟閭鬏敭斍皵?shù)據(jù)流后鏈路的利用率即：

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

模型可以轉化為：

約束條件為：

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

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

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

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

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

（2）網絡中所有路由器均為SDN路由器。

（3）網絡只有一個控制中心。

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

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

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

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

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

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

（2）網絡中所有路由器均為SDN路由器。

（3）網絡只有一個控制中心。

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

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

情況一：路徑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配置下的多跳丟棄算法，該算法首要考慮網絡中的鏈路不能過載，網絡一直處于暢通狀態(tài)。當轉發(fā)該業(yè)務會造成鏈路擁堵時SDN控制中心將擱置該業(yè)務，稍后轉發(fā)或丟棄。

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

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

（2）網絡中所有路由器均為SDN路由器。

（3）網絡只有一個控制中心。

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

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

（5）網絡中所有鏈路都不得超載。

根據(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è)務會造成網絡鏈路的擁堵。將該業(yè)務完全丟棄，網絡鏈路狀態(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個指標分別是：鏈路最大利用率、網絡中過載鏈路數(shù)、經過擁堵鏈路的業(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單跳方式經過擁堵鏈路的業(yè)務數(shù)、全SDN多跳方式經過擁堵鏈路的業(yè)務數(shù)目使用的是左側y軸。

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

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

4 結 語

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