基于SDN的流量工程

陳鴻文，王麗

（四川大學計算機學院，成都　610065）

基于SDN的流量工程

陳鴻文，王麗

（四川大學計算機學院，成都610065）

軟定義網絡是一種新興的網絡，它將控制平面與數據層分離。通過控制的集中化和提供控制接口的開放，使網絡管理簡單化與靈活化。Google正在用軟定義網絡連接其數據中心，由于它在執行流量工程功能中的易操作性、有效性和靈活性。他們希望通過SDN結構來使網絡利用率更好并且優化延遲和丟包。講述當SDN逐步引入一個現有網絡的時候SDN對流量工程的影響。主要將展示如何利用集中控制器在網絡利用率和減少包丟失和延遲上得到顯著改善，指出在網絡中只有部分網絡部署SDN能力的時候這些改進都是可能實現的。

軟定義網絡；流量工程

0　引言

軟定義網絡是一種新興的網絡范例［1-3］，它在網絡中將控制層和數據層分離。這種功能的分離和控制在不同的控制平面執行由于其預期的收益引發了很多的研究。分離單獨路由器的域間路由和使用邏輯路由控制系統作為讓路由系統可管理化、簡單化在文獻［2，4］總有提到。軟路由器結構［11］提出不允許路由進入到包的轉發單元中，使用開放的標準接口。這種方法是作為更快引入一些像流量工程，新的VPN特點之類的網絡功能提出的。文獻［9］提出將控制層重新引入到傳播平面和決策平面。通過傳播平面將信息可靠地分布到網絡元素和決策平面決策層來做所有的決策來作用于網絡。這種重新引入的方案讓決策層很容易有全網的視圖和允許操作更輕松地表達所需的網絡行為。

上面所有的常見的方法是包含兩種組件的SDN：

（1）SDN Controller（SDN-C）：控制器是一種邏輯集中功能［3］。一個網絡是被一個或者多個控制器控制的。控制器決定在網絡中一個流的轉發路徑。

（2）SDN Forwarding Element（SDN-FE）：軟定義轉發單元組成了網絡的數據層。包的轉發邏輯是由SDN控制器決定的，并且在SDN-FE轉發表中實現。

OpenFlow是控制器與轉發單元交互的一種標準接口。當在網絡中一個流初始化后將會有以下的這些反應：①流的第一個包通過SDN-FE傳送到SDN-C，②流的轉發路徑由SDN-C來計算，③SDN-C發送適當的條目來在SDN轉發單元從起點到目的地的路徑上安裝轉發表，④在流中之后所有的包都在數據層進行轉發而不需要控制層任何的功能。

SDN控制器是負責路徑的選擇并且因此所有的策略信息都會保存在控制器中。例如，Google通過OpenFlow路由器建立了一種SDN來連接它的數據中心（G-Scale）［5］。Google希望通過使用SDN來提高網絡利用率同時優化延遲和丟包。

我們考慮是在現有網絡中不斷部署SDN時的流量工程。在這樣一個網絡當中，不是所有的流量都通過一個單一的控制器來控制。在不同的部分網絡中可能有多個控制器并且也有一部分網絡可能會使用已存在的網絡路由規則。關鍵的問題是當在網絡中所有的流不能被一個SDN控制器集中控制的時候是否還可能執行有效的流量工程。

在本文中，我們考慮在網絡中一個SDN控制器僅僅控制一些SDN轉發單元的流量的工程。剩余的網絡使用標準網關協議OSPF來完成hop-by-hop路由。

本文的目的是建立一個SDN部署方案可以在網絡中自適應和動態的管理流以致適應不同的流量模式。本文的主要主要貢獻有以下幾點：

①我們提出了SDN控制器優化問題并提出FPTAS方案來解決控制器問題。

②我們通過分析展示了當網絡中部署有限的SDN轉發單元時在延遲和丟包方面的有效作用。

③給定一個數量的SDN轉發單元，我們提出一個算法用來確定這些轉發單元的位置。

1　系統描述

我們考慮一種一個集中SDN控制器對一部分SDN轉發單元的路由表進行計算的網絡。假設在網絡中SDN轉發單元是所有節點的一個分支。剩余的節點執行像OSPF之類的標準網管協議。我們假設SDN控制器同網絡一樣采集鏈路狀態信息。此外對于轉發包，在它們轉發到控制器時SDN轉發單元做一些簡單的流測量。控制器用這些信息在隨著信息通過OSPE-TE傳送到網絡中來在SDN轉發單元中動態的改變路由表來適應改變的轉發條件。該控制器還利用這些使它可以在不同的SDN轉發單元中協調的變化，使它在控制不斷變化的流時更有效。常規節點，也可以說是那些非SDN轉發單元，還是使用標準的轉發機制來執行逐跳。與SDN混合的傳統網絡和這種混合網絡在文獻［10］中也有考慮到。

在圖1中展示了一種有SDN轉發單元和控制器的網絡。SDN轉發單元2，9，14由外部控制。我們將用這個網絡來闡明我們在文章剩余部分中的概念。假設在網絡中所有的鏈路都是雙向的并且所有的鏈路負載都設置為1。我們現在從更細節的方面來介紹SDN控制器和SDN轉發單元。在控制器中執行的算法將在第二部分中介紹。

（1）SDN轉發單元

SDN轉發單元執行以下功能：

轉發：SDN轉發單元充當基本的轉發單元。SDN轉發單元的路由表由SDN控制器計算。假設當SDN轉發單元在給出一個目標時候可以執行多個下一跳。如果對于一個給定目標有多個下一跳，那么SDN轉發單元可以在預先設定多次下一跳方式下將流分離發送到目標。

圖1　SDN 控制器和SDN轉發單元

對控制器來說計算多個下一跳和對轉發單元加載路由表是很容易的［11］。對將流量分離成多個下一跳同時確定一個給定的流不是分離成多個下一跳有多種方法。部分這些方法需要一些額外的測量并且這很容易擴展現有的方法來獲取額外的信息。因此在后文中，我們假設SDN轉發單元對給定一個目標時可以將流分離成多個下一跳。也假設SDN轉發單元可以用文獻［14］中的技術來進行流量測量。

測量：在SDN轉發單元中的路由表現對于標準的路由表是有細微的改變的，目的是幫助SDN轉發單元的流量測量。圖2中展示了SDN轉發單元中路由表和標準路由表的不同。需要注意的是在網絡中的節點能夠到達目的地的地址的一個額外的列。當一個包被SDN轉發單元處理時它的前綴同目的地址IP匹配來確定下一跳。它也增加由包的長度相應于目的節點計數器。這些是為了確定SDN轉發單元和其他節點流量的數量。考慮路由表節點2。假設節點15（45.67.2.5）宣稱要到達子網135.2316。讓節點11（43.2.34.7）成為節點2到節點15最短路徑中的下一跳。節點2的一部分路由表在圖2中。對應的流量列跟蹤來自節點2到節點15的目的前綴135.2316傳送的字節數。

圖2　SDN轉發單元路由表

（2）SDN控制器

SDN控制有所有的選擇邏輯并且協調所有SDN轉發單元的路由以實現良好的網絡性能。控制器有以下功能：

比較：SDN控制器使用OSPF-TE與在網絡中的其他節點交換鏈路負載和其他的拓撲信息。（文獻［9］中有實例。）在OSPF-TE中需要注意，在網絡中節點也可以交換鏈路上的帶寬信息。因此控制器知道當前OSPF權重和每一條鏈路上的流量流的數量（平均時間段內）。

路由計算：在網絡中控制器負責所有SDN轉發單元路由表的計算。對SDN轉發單元的路由表計算的算法必須確定路由將沿著無環路路徑且網絡中的擁塞最小化。我們將會在文章的第二部分和第三部分描述控制器規劃問題和解決技術。

2　SDN控制器問題

我們現在來詳細描述SDN控制器需要解決的問題。假設網絡由一包含N個節點的定向鏈路E組成。假設在網絡中有n個節點和m條鏈路。讓C（C?N）表示SDN轉發單元部分，表示非SDN轉發單元部分。讓w（e）和c（e）分別表示鏈路e的OPSF鏈路權重和容量。我們使用f（e）來表示鏈路e的流量流。在鏈路e上的所有流都可以從OSPF到控制器。我們使用Tsd來表示從節點s到節點d的傳送速率并且用Wud來表示那些通過或者始發與SDN轉發單元u?C的目標節點d?N的通信總量。需要注意是Wud＞Tud。SDN控制器u可以用圖2中的信息對所有的目標節點d測量它們的Wud。對于所有節點對（s，d）的值Tsd控制器都不會知道。每個節點都計算到網絡中其他節點的最短路徑。在節點u?N的路由表中包括到網絡中其他節點最短路徑的下一跳。我們使用NH（u，d）來表示節點d到節點u的下一跳。換句話說，NH（u，d）在u到d最短路徑上第一個節點。在本文的其他部分，我們假設對于所有的非SDN轉發單元下一跳是獨立的，i.e，NH（u，d）對于所有的u∈D僅僅只有一個單元。我們做這個假設純粹是為了便于說明。需要注意的是當NH（u，d）是基于所有節點u∈D最短路徑計算時，NH（u，d）當u∈C如果沒有路由環路時可以任意設定。

我們將用圖3來闡明上面的觀點。假設所有的鏈路權重都是1并且實線表示到13節點的最短路徑。這是會導致SDN轉發單元也使用標準最短路徑計算的樹。節點2，9，14是SDN轉發單元。注意NH（6，13）= 10，NH（1，13）=2等。網絡中的虛線顯示在SDN轉發單元的可替代的路徑。例如，節點2可以將到節點13的流分離成一個到節點5另一個到節點11的兩個不同的下一跳。

圖3　到節點13的最短路徑樹

定義一：給定一部分SDN轉發單元C，路徑s=u0，u1，…，uk=d從節點s到節點d是可行的如果j=1，2，…，k，（uj-1，uj）∈E并且：

一條u0，u1，…，uk不同的可行路徑被稱為允許路徑。讓Psd表示節點s和節點d中的一組允許路徑。

通過定義，指出一條路徑如果對所有非SDN轉發單元對目標節點的下一跳是通過最短路徑算法給定的那么就是可行的。其他的可行路徑只有在它是無回路時才是被允許的。因此，我們需要確定在節點s和節點d中的流必須在P∈Psd路由上。

舉例說明，在圖3中，3-2-5-12-13是節點3到節點13的允許路徑。需要注意的是相對于3-2-11-13這并不是最短路徑。路徑3-6-11-13不是一個被允許的路徑，因為節點3的下一跳應該是節點2。

定義二：在非SDN轉發單元給定最短路徑路由，從起點到目標節點不經過SDN轉發單元的流被看做是不可控流。如果包的起點是SDN轉發單元，或者在它到達目標節點之前至少經過一個SDN轉發單元都將被看做可控流。

在SDN轉發單元至少有一次機會去操作路徑對于可控流。例如，流從節點6到節點13通過OSPF計算出的路徑是6-10-13，因此不管是6還是10都不是SDN轉發單元，流從節點6到節點13是不可控的。相反，流從節點8到節點13要經過SDN轉發單元9，那么這個流就是可控流。

定義三：我們說一個SDN轉發單元u∈C添加到一個包，如果：

①節點u對于包來說是在OSPF路由路徑上。

②包在經過u之前經過其他SDN轉發單元。

通過SDN轉發單元u∈C的流被添加到一些目標節點d∈N將被表示為Iud。

因此，對于所有的可控流都有一個獨立的SDN轉發單元被添加的這個流。需要注意被添加的SDN轉發單元可以是也可以不是流的起點。我們將用圖4來闡述這些觀點。在圖中，到下一節點的數字表示節點到節點13的速率。比如節點1到節點13（T（11，13））的流是3。通過定義三，從節點3到節點13的流將會因為SDN轉發單元2被添加。如果對于所有的起始對（s，d）的值Tsd都是已知的，那么Iud的值可以通過以下方式計算：移除SDN轉發單元的出路，并且讓OSPF發送所有的要求直到它到達SDN轉發單元或者目標節點。在圖3中舉例說明，I2，13=9，I9，13=13和I14，13=5。如上所述，控制器是不知道Tsd的值的。在SDN控制器中唯一可以測量的值是經過節點u∈C到目標節點d的流的Wud。

（1）SDN控制器問題的公式

因為只有經過SDN轉發單元的流我們才能對其進行操作，所有我們只關注這種流。通過SDN轉發單元被添加的流Iud必須到達目標節點d。它只能沿著允許路徑P∈Pud這樣做。讓g（e）表示在鏈路e上不可控流。SDN控制器的目的是發送可控流，讓在鏈路上得延遲和丟包最小化。我們使用鏈路利用率來替代延遲和丟包。SDN控制器的最基本目的就是提高在網絡中的鏈路利用率。在公式中，在路徑中的流的變量是x（P）。SDN控制器解決以下的優化問題：

圖4　SDN轉發單元的獨立路由流量

服從

θ在所有鏈路利用率最大化時有最優解。需要注意的是當θ＜1時，所有鏈路都不會出現過載情況。一旦SDN控制器解決了優化問題，那么對于計算下一跳就很簡單了。

在上面的公式當中，我們假設Iud和g（e）的值是已知的。實際上Iud和g（e）都必須通過SDN控制器基于SDN轉發單元的測量和通過SDN控制器接收的OSPF-TE信息來計算。

（2）計算Iud和g（e）

對于SDN控制器唯一可行的測量數據是：

①對所有鏈路e∈E的鏈路權重f（e）都可以從OSPF-TE信息中獲取

②Wud數量對所有的u∈C和d∈N。這可以通過SDN轉發單元測量并發送到SDN控制器

使用這兩個工程量，SDN控制器必須計算出Iud和g（e）。我們首先來闡述Iud的計算。考慮一個固定的目標節點d。SDN控制器知道到目標節點d的當前路由。它知道在D中所有節點的下一跳并且在所有SDN轉發單元中它不知道對目標節點的下一跳和當有多個下一跳時怎么分離它們。

定義四：在網絡中給一個目標節點d和通用路由，在C中節點的關于目標d的路由順序被定義成在C/d中的節點的順序，這樣如果在列表中u∈C比ν∈C先表現出來那么將沒有目標是d從u發送到v的流。我們用R（d）表示目標是d的路由順序并且在R（d）中用u?d v表示u先于v表現出來。

路由順序為了對任何目標節點d定義的，因此在到目標d的流量流不能有任何的路由循環。假設在到節點13的現有路由在圖5中。我們只給出了與SDN轉發單元相關的路由。這里有一個從節點9出發經過節點14的流。因此9?1314。一個路由順序是（2，9，14）。除了節點14的順序必須在節點9之后，其他的順序都是可能的。

圖5　路由順序的闡明

下面給出計算Iud的算法。

對于每個目標d∈N

①計算路由順序R（d）

②對在R（d）中的第一個節點u設Iud=Wud

③發送一個從u到d的單元流并設βν（u，d）為

④對于在R（d）中的每個連續節點w

發送一個從w到d的單位流并計算βν（w，d）至此可以計算g（e）

這樣Iud和g（e）都已經計算出來了。

（3）動態路由問題公式

SDN控制器發送流以在網絡中盡量最小化鏈路的最大利用率。

服從

為了對上面描述的動態路由規劃寫出一個雙重線性規劃，我們設在（4）范圍中的變量l（e）和在（5）范圍中的，則有：

服從

假設我們設l（e）為鏈路e∈E的權重。讓Iud表示從u到d權重最小的路徑。那么公式現在可以寫成：

3　選擇SDN轉發單元的位置

給出一個網絡拓撲圖，首先要確定SDN轉發單元的位置。一旦確定了SDN轉發單元的位置，SDN控制器就可以解決在SDN轉發單元的動態路由問題了。理論上來說如果SDN控制獲得的信息是準確的那么有SDN轉發單元的系統將會比沒有SDN轉發單元的系統做的更好。在實際情況中有SDN轉發單元的系統的性能的提升依賴于SDN轉發單元的位置。節點的最佳選擇依賴于在選擇之前不能精確知道的流量矩陣。這里有兩個選擇。第一種是選擇獨立于流量矩陣的節點，第二種是用流量矩陣的估計來選擇SDN轉發單元。我們嘗試這兩種方法但是在本文中我們只介紹第二種方法。假設在網絡中我們知道SDN轉發單元的數量并且我們給出Tsd在節點s∈N和節點d∈N的流的流量矩陣。實際上流量可以并且在普通網絡中也會偏離這個流量矩陣。假設我們必須確定SDN轉發單元d。我們使用T來決定SDN轉發單元h在網絡中的位置。

定義四：在一組SDN轉發單元C中的流量矩陣T的吞吐量被記為最大的標量λ，這樣λT就可以沿著允許的路徑發送到網絡中。我們用λ（T，C）來表示吞吐量的值。

需要注意的事如果C=?怎對應于沒有SDN轉發單元的網絡或者網絡的行為同OSPF網絡一樣。當C= N時對應于所有節點都是SDN轉發單元的網絡。定義可得：

同樣需要注意的是λ（T，N）也可以從解決網絡中標準的最大并發流問題中得到。

因此給出T和f，目標就是確定：

我們使用貪婪算法來解決這個問題。首先我們假設一組SDN轉發單元是空的。在算法的每一步，我們將給出最大吞吐量提升的節點添加到那個已存在的SDN轉發單元組。重復這個過程知道在網絡中我們有hSDN轉發單元組。因為Tsd的值是已知的，那么吞吐量的問題可以這樣解決：

服從

因為這個問題從結構上同SDN控制的問題一樣，所以我們可以用同樣的方法解決這種問題。

4　結語

在SDN和傳統的網絡中不斷地部署SDN是一個值得考慮的重要方案。這對于那些需要完全部署SDN的大型網絡非常重要。我們已經展示了在一個已經存在的網絡中部署SDN對提高網絡性能是可行的。及時部署少數的SDN轉發單元都可以提高網絡性能。該方案對網絡中剩余節點不存在任何修改協議的操作。初步性能測試也表明了該理論可以提高總體網絡的吞吐量并且在網絡中提供更好的延遲和丟包操作。

［1］M.Casado，M.Freedman，J.Petit，J.Luo，N.McKeown，S.Shenker.Ethane：Taking Control of the Enterprise.ACM SIGCOMM CCR，37（4）：1-12，2007

［2］M.Caesar，D.Caldwell，N.Feamster，J.Rexford，A.Shaikh，and K.van der Merwe.Design and Implementation of a Routing Control Platform.Networked Systems Design and Implementation，May 2005

［3］N.Gude，T.Koponen，J.Petit，B.Pfaff，M.Casado，N.McKeown.Nox：Towards a Network Operating System.ACM SIGCOMM CCR，July，2008

［4］N.Feamster，H.Balakrishnan，J.Rexford，A.Shaikh，K.van der Merwe.The Case for Separating Routing from Routers.FDNA 2004.

［5］U.Holzle，”Opening Address：2012 Open Network Summit”，April 2012

［6］Network Development and Deployment Initiative（NDDI）”.http：//www.internet2.edu/network/ose/.

［7］Onix：A Distributed Control Platform for Large Scale Production Networks.T.Koponen et.al.，OSDI 2010，October，2010.

［8］Virtual Routers as a Service：the RouteFlow Approach Leveraging Software-Defined Networks.M.R.Nascimento，C.E.Rothenberg，M.R.Salvador，C.N.A.Correa，S.C.de Lucena，M.F.Magalhaes CFI 2011.

［9］J.Rexford et.al..Network-Wide Decision Making：Toward a Wafer-Thin Control Plane.HotNets-III，November 2004.

［10］C.Rothernberg，C.N.A.Correa，R.Raszuk.Revisiting Routing Control Platforms with the Eyes and Muscles of Software-Defined Networking.ACM-SIGCOMM HotSDN Workshop，2012

［11］T.V.Lakshman，T.Nandagopal，R.Ramjee，K.Sabnani，T.Woo.The SoftRouter Architecture.Proceeding of Hotnets 2004，November 2004.

CHEN Hong-wen ，WANG Li
（College of Computer Science，Sichuan University，Chengdu 610065）

Software Defined Networking is a new paradigm that separates the network control plane from the packet forwarding plane.Leveraging the centralized control ability and open programming interface SDN provides，network management can be dramatically simplified and flexibility.Google is using a Software Defined Network to interconnect its data centers due to ease，efficiency and flexibility in performing traffic engineering functions.It expects the SDN architecture to result in better network capacity utilization and improved delay and loss performance.Uses SDNs for traffic engineering especially when SDNs are incrementally introduced into an existing network，shows how to leverage the centralized controller to get significant improvements are possible even in cases where there is only a partial deployment of SDN capability in a network.

Software Defined Network（SDN）；Traffic Engineering

1007-1423（2016）26-0003-07DOI：10.3969/j.issn.1007-1423.2016.26.001

陳鴻文（1991-），男，四川閬中人，碩士，研究方向為軟定義網絡

2016-07-22修改日期：2016-09-10Traffic Engineering Based on SDN

王麗（1991-），女，山西臨汾人，碩士，研究方向為軟定義網絡