基于SDN的流量工程

陳鴻文，王麗

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

基于SDN的流量工程

陳鴻文，王麗

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

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

軟定義網(wǎng)絡(luò)；流量工程

0　引言

軟定義網(wǎng)絡(luò)是一種新興的網(wǎng)絡(luò)范例［1-3］，它在網(wǎng)絡(luò)中將控制層和數(shù)據(jù)層分離。這種功能的分離和控制在不同的控制平面執(zhí)行由于其預(yù)期的收益引發(fā)了很多的研究。分離單獨(dú)路由器的域間路由和使用邏輯路由控制系統(tǒng)作為讓路由系統(tǒng)可管理化、簡(jiǎn)單化在文獻(xiàn)［2，4］總有提到。軟路由器結(jié)構(gòu)［11］提出不允許路由進(jìn)入到包的轉(zhuǎn)發(fā)單元中，使用開(kāi)放的標(biāo)準(zhǔn)接口。這種方法是作為更快引入一些像流量工程，新的VPN特點(diǎn)之類的網(wǎng)絡(luò)功能提出的。文獻(xiàn)［9］提出將控制層重新引入到傳播平面和決策平面。通過(guò)傳播平面將信息可靠地分布到網(wǎng)絡(luò)元素和決策平面決策層來(lái)做所有的決策來(lái)作用于網(wǎng)絡(luò)。這種重新引入的方案讓決策層很容易有全網(wǎng)的視圖和允許操作更輕松地表達(dá)所需的網(wǎng)絡(luò)行為。

上面所有的常見(jiàn)的方法是包含兩種組件的SDN：

（1）SDN Controller（SDN-C）：控制器是一種邏輯集中功能［3］。一個(gè)網(wǎng)絡(luò)是被一個(gè)或者多個(gè)控制器控制的。控制器決定在網(wǎng)絡(luò)中一個(gè)流的轉(zhuǎn)發(fā)路徑。

（2）SDN Forwarding Element（SDN-FE）：軟定義轉(zhuǎn)發(fā)單元組成了網(wǎng)絡(luò)的數(shù)據(jù)層。包的轉(zhuǎn)發(fā)邏輯是由SDN控制器決定的，并且在SDN-FE轉(zhuǎn)發(fā)表中實(shí)現(xiàn)。

OpenFlow是控制器與轉(zhuǎn)發(fā)單元交互的一種標(biāo)準(zhǔn)接口。當(dāng)在網(wǎng)絡(luò)中一個(gè)流初始化后將會(huì)有以下的這些反應(yīng)：①流的第一個(gè)包通過(guò)SDN-FE傳送到SDN-C，②流的轉(zhuǎn)發(fā)路徑由SDN-C來(lái)計(jì)算，③SDN-C發(fā)送適當(dāng)?shù)臈l目來(lái)在SDN轉(zhuǎn)發(fā)單元從起點(diǎn)到目的地的路徑上安裝轉(zhuǎn)發(fā)表，④在流中之后所有的包都在數(shù)據(jù)層進(jìn)行轉(zhuǎn)發(fā)而不需要控制層任何的功能。

SDN控制器是負(fù)責(zé)路徑的選擇并且因此所有的策略信息都會(huì)保存在控制器中。例如，Google通過(guò)OpenFlow路由器建立了一種SDN來(lái)連接它的數(shù)據(jù)中心（G-Scale）［5］。Google希望通過(guò)使用SDN來(lái)提高網(wǎng)絡(luò)利用率同時(shí)優(yōu)化延遲和丟包。

我們考慮是在現(xiàn)有網(wǎng)絡(luò)中不斷部署SDN時(shí)的流量工程。在這樣一個(gè)網(wǎng)絡(luò)當(dāng)中，不是所有的流量都通過(guò)一個(gè)單一的控制器來(lái)控制。在不同的部分網(wǎng)絡(luò)中可能有多個(gè)控制器并且也有一部分網(wǎng)絡(luò)可能會(huì)使用已存在的網(wǎng)絡(luò)路由規(guī)則。關(guān)鍵的問(wèn)題是當(dāng)在網(wǎng)絡(luò)中所有的流不能被一個(gè)SDN控制器集中控制的時(shí)候是否還可能執(zhí)行有效的流量工程。

在本文中，我們考慮在網(wǎng)絡(luò)中一個(gè)SDN控制器僅僅控制一些SDN轉(zhuǎn)發(fā)單元的流量的工程。剩余的網(wǎng)絡(luò)使用標(biāo)準(zhǔn)網(wǎng)關(guān)協(xié)議OSPF來(lái)完成hop-by-hop路由。

本文的目的是建立一個(gè)SDN部署方案可以在網(wǎng)絡(luò)中自適應(yīng)和動(dòng)態(tài)的管理流以致適應(yīng)不同的流量模式。本文的主要主要貢獻(xiàn)有以下幾點(diǎn)：

①我們提出了SDN控制器優(yōu)化問(wèn)題并提出FPTAS方案來(lái)解決控制器問(wèn)題。

②我們通過(guò)分析展示了當(dāng)網(wǎng)絡(luò)中部署有限的SDN轉(zhuǎn)發(fā)單元時(shí)在延遲和丟包方面的有效作用。

③給定一個(gè)數(shù)量的SDN轉(zhuǎn)發(fā)單元，我們提出一個(gè)算法用來(lái)確定這些轉(zhuǎn)發(fā)單元的位置。

1　系統(tǒng)描述

我們考慮一種一個(gè)集中SDN控制器對(duì)一部分SDN轉(zhuǎn)發(fā)單元的路由表進(jìn)行計(jì)算的網(wǎng)絡(luò)。假設(shè)在網(wǎng)絡(luò)中SDN轉(zhuǎn)發(fā)單元是所有節(jié)點(diǎn)的一個(gè)分支。剩余的節(jié)點(diǎn)執(zhí)行像OSPF之類的標(biāo)準(zhǔn)網(wǎng)管協(xié)議。我們假設(shè)SDN控制器同網(wǎng)絡(luò)一樣采集鏈路狀態(tài)信息。此外對(duì)于轉(zhuǎn)發(fā)包，在它們轉(zhuǎn)發(fā)到控制器時(shí)SDN轉(zhuǎn)發(fā)單元做一些簡(jiǎn)單的流測(cè)量。控制器用這些信息在隨著信息通過(guò)OSPE-TE傳送到網(wǎng)絡(luò)中來(lái)在SDN轉(zhuǎn)發(fā)單元中動(dòng)態(tài)的改變路由表來(lái)適應(yīng)改變的轉(zhuǎn)發(fā)條件。該控制器還利用這些使它可以在不同的SDN轉(zhuǎn)發(fā)單元中協(xié)調(diào)的變化，使它在控制不斷變化的流時(shí)更有效。常規(guī)節(jié)點(diǎn)，也可以說(shuō)是那些非SDN轉(zhuǎn)發(fā)單元，還是使用標(biāo)準(zhǔn)的轉(zhuǎn)發(fā)機(jī)制來(lái)執(zhí)行逐跳。與SDN混合的傳統(tǒng)網(wǎng)絡(luò)和這種混合網(wǎng)絡(luò)在文獻(xiàn)［10］中也有考慮到。

在圖1中展示了一種有SDN轉(zhuǎn)發(fā)單元和控制器的網(wǎng)絡(luò)。SDN轉(zhuǎn)發(fā)單元2，9，14由外部控制。我們將用這個(gè)網(wǎng)絡(luò)來(lái)闡明我們?cè)谖恼率Ｓ嗖糠种械母拍睢＜僭O(shè)在網(wǎng)絡(luò)中所有的鏈路都是雙向的并且所有的鏈路負(fù)載都設(shè)置為1。我們現(xiàn)在從更細(xì)節(jié)的方面來(lái)介紹SDN控制器和SDN轉(zhuǎn)發(fā)單元。在控制器中執(zhí)行的算法將在第二部分中介紹。

（1）SDN轉(zhuǎn)發(fā)單元

SDN轉(zhuǎn)發(fā)單元執(zhí)行以下功能：

轉(zhuǎn)發(fā)：SDN轉(zhuǎn)發(fā)單元充當(dāng)基本的轉(zhuǎn)發(fā)單元。SDN轉(zhuǎn)發(fā)單元的路由表由SDN控制器計(jì)算。假設(shè)當(dāng)SDN轉(zhuǎn)發(fā)單元在給出一個(gè)目標(biāo)時(shí)候可以執(zhí)行多個(gè)下一跳。如果對(duì)于一個(gè)給定目標(biāo)有多個(gè)下一跳，那么SDN轉(zhuǎn)發(fā)單元可以在預(yù)先設(shè)定多次下一跳方式下將流分離發(fā)送到目標(biāo)。

圖1　SDN 控制器和SDN轉(zhuǎn)發(fā)單元

對(duì)控制器來(lái)說(shuō)計(jì)算多個(gè)下一跳和對(duì)轉(zhuǎn)發(fā)單元加載路由表是很容易的［11］。對(duì)將流量分離成多個(gè)下一跳同時(shí)確定一個(gè)給定的流不是分離成多個(gè)下一跳有多種方法。部分這些方法需要一些額外的測(cè)量并且這很容易擴(kuò)展現(xiàn)有的方法來(lái)獲取額外的信息。因此在后文中，我們假設(shè)SDN轉(zhuǎn)發(fā)單元對(duì)給定一個(gè)目標(biāo)時(shí)可以將流分離成多個(gè)下一跳。也假設(shè)SDN轉(zhuǎn)發(fā)單元可以用文獻(xiàn)［14］中的技術(shù)來(lái)進(jìn)行流量測(cè)量。

測(cè)量：在SDN轉(zhuǎn)發(fā)單元中的路由表現(xiàn)對(duì)于標(biāo)準(zhǔn)的路由表是有細(xì)微的改變的，目的是幫助SDN轉(zhuǎn)發(fā)單元的流量測(cè)量。圖2中展示了SDN轉(zhuǎn)發(fā)單元中路由表和標(biāo)準(zhǔn)路由表的不同。需要注意的是在網(wǎng)絡(luò)中的節(jié)點(diǎn)能夠到達(dá)目的地的地址的一個(gè)額外的列。當(dāng)一個(gè)包被SDN轉(zhuǎn)發(fā)單元處理時(shí)它的前綴同目的地址IP匹配來(lái)確定下一跳。它也增加由包的長(zhǎng)度相應(yīng)于目的節(jié)點(diǎn)計(jì)數(shù)器。這些是為了確定SDN轉(zhuǎn)發(fā)單元和其他節(jié)點(diǎn)流量的數(shù)量。考慮路由表節(jié)點(diǎn)2。假設(shè)節(jié)點(diǎn)15（45.67.2.5）宣稱要到達(dá)子網(wǎng)135.2316。讓節(jié)點(diǎn)11（43.2.34.7）成為節(jié)點(diǎn)2到節(jié)點(diǎn)15最短路徑中的下一跳。節(jié)點(diǎn)2的一部分路由表在圖2中。對(duì)應(yīng)的流量列跟蹤來(lái)自節(jié)點(diǎn)2到節(jié)點(diǎn)15的目的前綴135.2316傳送的字節(jié)數(shù)。

圖2　SDN轉(zhuǎn)發(fā)單元路由表

（2）SDN控制器

SDN控制有所有的選擇邏輯并且協(xié)調(diào)所有SDN轉(zhuǎn)發(fā)單元的路由以實(shí)現(xiàn)良好的網(wǎng)絡(luò)性能。控制器有以下功能：

比較：SDN控制器使用OSPF-TE與在網(wǎng)絡(luò)中的其他節(jié)點(diǎn)交換鏈路負(fù)載和其他的拓?fù)湫畔ⅰ＃ㄎ墨I(xiàn)［9］中有實(shí)例。）在OSPF-TE中需要注意，在網(wǎng)絡(luò)中節(jié)點(diǎn)也可以交換鏈路上的帶寬信息。因此控制器知道當(dāng)前OSPF權(quán)重和每一條鏈路上的流量流的數(shù)量（平均時(shí)間段內(nèi)）。

路由計(jì)算：在網(wǎng)絡(luò)中控制器負(fù)責(zé)所有SDN轉(zhuǎn)發(fā)單元路由表的計(jì)算。對(duì)SDN轉(zhuǎn)發(fā)單元的路由表計(jì)算的算法必須確定路由將沿著無(wú)環(huán)路路徑且網(wǎng)絡(luò)中的擁塞最小化。我們將會(huì)在文章的第二部分和第三部分描述控制器規(guī)劃問(wèn)題和解決技術(shù)。

2　SDN控制器問(wèn)題

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

我們將用圖3來(lái)闡明上面的觀點(diǎn)。假設(shè)所有的鏈路權(quán)重都是1并且實(shí)線表示到13節(jié)點(diǎn)的最短路徑。這是會(huì)導(dǎo)致SDN轉(zhuǎn)發(fā)單元也使用標(biāo)準(zhǔn)最短路徑計(jì)算的樹(shù)。節(jié)點(diǎn)2，9，14是SDN轉(zhuǎn)發(fā)單元。注意NH（6，13）= 10，NH（1，13）=2等。網(wǎng)絡(luò)中的虛線顯示在SDN轉(zhuǎn)發(fā)單元的可替代的路徑。例如，節(jié)點(diǎn)2可以將到節(jié)點(diǎn)13的流分離成一個(gè)到節(jié)點(diǎn)5另一個(gè)到節(jié)點(diǎn)11的兩個(gè)不同的下一跳。

圖3　到節(jié)點(diǎn)13的最短路徑樹(shù)

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

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

通過(guò)定義，指出一條路徑如果對(duì)所有非SDN轉(zhuǎn)發(fā)單元對(duì)目標(biāo)節(jié)點(diǎn)的下一跳是通過(guò)最短路徑算法給定的那么就是可行的。其他的可行路徑只有在它是無(wú)回路時(shí)才是被允許的。因此，我們需要確定在節(jié)點(diǎn)s和節(jié)點(diǎn)d中的流必須在P∈Psd路由上。

舉例說(shuō)明，在圖3中，3-2-5-12-13是節(jié)點(diǎn)3到節(jié)點(diǎn)13的允許路徑。需要注意的是相對(duì)于3-2-11-13這并不是最短路徑。路徑3-6-11-13不是一個(gè)被允許的路徑，因?yàn)楣?jié)點(diǎn)3的下一跳應(yīng)該是節(jié)點(diǎn)2。

定義二：在非SDN轉(zhuǎn)發(fā)單元給定最短路徑路由，從起點(diǎn)到目標(biāo)節(jié)點(diǎn)不經(jīng)過(guò)SDN轉(zhuǎn)發(fā)單元的流被看做是不可控流。如果包的起點(diǎn)是SDN轉(zhuǎn)發(fā)單元，或者在它到達(dá)目標(biāo)節(jié)點(diǎn)之前至少經(jīng)過(guò)一個(gè)SDN轉(zhuǎn)發(fā)單元都將被看做可控流。

在SDN轉(zhuǎn)發(fā)單元至少有一次機(jī)會(huì)去操作路徑對(duì)于可控流。例如，流從節(jié)點(diǎn)6到節(jié)點(diǎn)13通過(guò)OSPF計(jì)算出的路徑是6-10-13，因此不管是6還是10都不是SDN轉(zhuǎn)發(fā)單元，流從節(jié)點(diǎn)6到節(jié)點(diǎn)13是不可控的。相反，流從節(jié)點(diǎn)8到節(jié)點(diǎn)13要經(jīng)過(guò)SDN轉(zhuǎn)發(fā)單元9，那么這個(gè)流就是可控流。

定義三：我們說(shuō)一個(gè)SDN轉(zhuǎn)發(fā)單元u∈C添加到一個(gè)包，如果：

①節(jié)點(diǎn)u對(duì)于包來(lái)說(shuō)是在OSPF路由路徑上。

②包在經(jīng)過(guò)u之前經(jīng)過(guò)其他SDN轉(zhuǎn)發(fā)單元。

通過(guò)SDN轉(zhuǎn)發(fā)單元u∈C的流被添加到一些目標(biāo)節(jié)點(diǎn)d∈N將被表示為Iud。

因此，對(duì)于所有的可控流都有一個(gè)獨(dú)立的SDN轉(zhuǎn)發(fā)單元被添加的這個(gè)流。需要注意被添加的SDN轉(zhuǎn)發(fā)單元可以是也可以不是流的起點(diǎn)。我們將用圖4來(lái)闡述這些觀點(diǎn)。在圖中，到下一節(jié)點(diǎn)的數(shù)字表示節(jié)點(diǎn)到節(jié)點(diǎn)13的速率。比如節(jié)點(diǎn)1到節(jié)點(diǎn)13（T（11，13））的流是3。通過(guò)定義三，從節(jié)點(diǎn)3到節(jié)點(diǎn)13的流將會(huì)因?yàn)镾DN轉(zhuǎn)發(fā)單元2被添加。如果對(duì)于所有的起始對(duì)（s，d）的值Tsd都是已知的，那么Iud的值可以通過(guò)以下方式計(jì)算：移除SDN轉(zhuǎn)發(fā)單元的出路，并且讓OSPF發(fā)送所有的要求直到它到達(dá)SDN轉(zhuǎn)發(fā)單元或者目標(biāo)節(jié)點(diǎn)。在圖3中舉例說(shuō)明，I2，13=9，I9，13=13和I14，13=5。如上所述，控制器是不知道Tsd的值的。在SDN控制器中唯一可以測(cè)量的值是經(jīng)過(guò)節(jié)點(diǎn)u∈C到目標(biāo)節(jié)點(diǎn)d的流的Wud。

（1）SDN控制器問(wèn)題的公式

因?yàn)橹挥薪?jīng)過(guò)SDN轉(zhuǎn)發(fā)單元的流我們才能對(duì)其進(jìn)行操作，所有我們只關(guān)注這種流。通過(guò)SDN轉(zhuǎn)發(fā)單元被添加的流Iud必須到達(dá)目標(biāo)節(jié)點(diǎn)d。它只能沿著允許路徑P∈Pud這樣做。讓g（e）表示在鏈路e上不可控流。SDN控制器的目的是發(fā)送可控流，讓在鏈路上得延遲和丟包最小化。我們使用鏈路利用率來(lái)替代延遲和丟包。SDN控制器的最基本目的就是提高在網(wǎng)絡(luò)中的鏈路利用率。在公式中，在路徑中的流的變量是x（P）。SDN控制器解決以下的優(yōu)化問(wèn)題：

圖4　SDN轉(zhuǎn)發(fā)單元的獨(dú)立路由流量

服從

θ在所有鏈路利用率最大化時(shí)有最優(yōu)解。需要注意的是當(dāng)θ＜1時(shí)，所有鏈路都不會(huì)出現(xiàn)過(guò)載情況。一旦SDN控制器解決了優(yōu)化問(wèn)題，那么對(duì)于計(jì)算下一跳就很簡(jiǎn)單了。

在上面的公式當(dāng)中，我們假設(shè)Iud和g（e）的值是已知的。實(shí)際上Iud和g（e）都必須通過(guò)SDN控制器基于SDN轉(zhuǎn)發(fā)單元的測(cè)量和通過(guò)SDN控制器接收的OSPF-TE信息來(lái)計(jì)算。

（2）計(jì)算Iud和g（e）

對(duì)于SDN控制器唯一可行的測(cè)量數(shù)據(jù)是：

①對(duì)所有鏈路e∈E的鏈路權(quán)重f（e）都可以從OSPF-TE信息中獲取

②Wud數(shù)量對(duì)所有的u∈C和d∈N。這可以通過(guò)SDN轉(zhuǎn)發(fā)單元測(cè)量并發(fā)送到SDN控制器

使用這兩個(gè)工程量，SDN控制器必須計(jì)算出Iud和g（e）。我們首先來(lái)闡述Iud的計(jì)算。考慮一個(gè)固定的目標(biāo)節(jié)點(diǎn)d。SDN控制器知道到目標(biāo)節(jié)點(diǎn)d的當(dāng)前路由。它知道在D中所有節(jié)點(diǎn)的下一跳并且在所有SDN轉(zhuǎn)發(fā)單元中它不知道對(duì)目標(biāo)節(jié)點(diǎn)的下一跳和當(dāng)有多個(gè)下一跳時(shí)怎么分離它們。

定義四：在網(wǎng)絡(luò)中給一個(gè)目標(biāo)節(jié)點(diǎn)d和通用路由，在C中節(jié)點(diǎn)的關(guān)于目標(biāo)d的路由順序被定義成在C/d中的節(jié)點(diǎn)的順序，這樣如果在列表中u∈C比ν∈C先表現(xiàn)出來(lái)那么將沒(méi)有目標(biāo)是d從u發(fā)送到v的流。我們用R（d）表示目標(biāo)是d的路由順序并且在R（d）中用u?d v表示u先于v表現(xiàn)出來(lái)。

路由順序?yàn)榱藢?duì)任何目標(biāo)節(jié)點(diǎn)d定義的，因此在到目標(biāo)d的流量流不能有任何的路由循環(huán)。假設(shè)在到節(jié)點(diǎn)13的現(xiàn)有路由在圖5中。我們只給出了與SDN轉(zhuǎn)發(fā)單元相關(guān)的路由。這里有一個(gè)從節(jié)點(diǎn)9出發(fā)經(jīng)過(guò)節(jié)點(diǎn)14的流。因此9?1314。一個(gè)路由順序是（2，9，14）。除了節(jié)點(diǎn)14的順序必須在節(jié)點(diǎn)9之后，其他的順序都是可能的。

圖5　路由順序的闡明

下面給出計(jì)算Iud的算法。

對(duì)于每個(gè)目標(biāo)d∈N

①計(jì)算路由順序R（d）

②對(duì)在R（d）中的第一個(gè)節(jié)點(diǎn)u設(shè)Iud=Wud

③發(fā)送一個(gè)從u到d的單元流并設(shè)βν（u，d）為

④對(duì)于在R（d）中的每個(gè)連續(xù)節(jié)點(diǎn)w

發(fā)送一個(gè)從w到d的單位流并計(jì)算βν（w，d）至此可以計(jì)算g（e）

這樣Iud和g（e）都已經(jīng)計(jì)算出來(lái)了。

（3）動(dòng)態(tài)路由問(wèn)題公式

SDN控制器發(fā)送流以在網(wǎng)絡(luò)中盡量最小化鏈路的最大利用率。

服從

為了對(duì)上面描述的動(dòng)態(tài)路由規(guī)劃寫(xiě)出一個(gè)雙重線性規(guī)劃，我們?cè)O(shè)在（4）范圍中的變量l（e）和在（5）范圍中的，則有：

服從

假設(shè)我們?cè)O(shè)l（e）為鏈路e∈E的權(quán)重。讓Iud表示從u到d權(quán)重最小的路徑。那么公式現(xiàn)在可以寫(xiě)成：

3　選擇SDN轉(zhuǎn)發(fā)單元的位置

給出一個(gè)網(wǎng)絡(luò)拓?fù)鋱D，首先要確定SDN轉(zhuǎn)發(fā)單元的位置。一旦確定了SDN轉(zhuǎn)發(fā)單元的位置，SDN控制器就可以解決在SDN轉(zhuǎn)發(fā)單元的動(dòng)態(tài)路由問(wèn)題了。理論上來(lái)說(shuō)如果SDN控制獲得的信息是準(zhǔn)確的那么有SDN轉(zhuǎn)發(fā)單元的系統(tǒng)將會(huì)比沒(méi)有SDN轉(zhuǎn)發(fā)單元的系統(tǒng)做的更好。在實(shí)際情況中有SDN轉(zhuǎn)發(fā)單元的系統(tǒng)的性能的提升依賴于SDN轉(zhuǎn)發(fā)單元的位置。節(jié)點(diǎn)的最佳選擇依賴于在選擇之前不能精確知道的流量矩陣。這里有兩個(gè)選擇。第一種是選擇獨(dú)立于流量矩陣的節(jié)點(diǎn)，第二種是用流量矩陣的估計(jì)來(lái)選擇SDN轉(zhuǎn)發(fā)單元。我們嘗試這兩種方法但是在本文中我們只介紹第二種方法。假設(shè)在網(wǎng)絡(luò)中我們知道SDN轉(zhuǎn)發(fā)單元的數(shù)量并且我們給出Tsd在節(jié)點(diǎn)s∈N和節(jié)點(diǎn)d∈N的流的流量矩陣。實(shí)際上流量可以并且在普通網(wǎng)絡(luò)中也會(huì)偏離這個(gè)流量矩陣。假設(shè)我們必須確定SDN轉(zhuǎn)發(fā)單元d。我們使用T來(lái)決定SDN轉(zhuǎn)發(fā)單元h在網(wǎng)絡(luò)中的位置。

定義四：在一組SDN轉(zhuǎn)發(fā)單元C中的流量矩陣T的吞吐量被記為最大的標(biāo)量λ，這樣λT就可以沿著允許的路徑發(fā)送到網(wǎng)絡(luò)中。我們用λ（T，C）來(lái)表示吞吐量的值。

需要注意的事如果C=?怎對(duì)應(yīng)于沒(méi)有SDN轉(zhuǎn)發(fā)單元的網(wǎng)絡(luò)或者網(wǎng)絡(luò)的行為同OSPF網(wǎng)絡(luò)一樣。當(dāng)C= N時(shí)對(duì)應(yīng)于所有節(jié)點(diǎn)都是SDN轉(zhuǎn)發(fā)單元的網(wǎng)絡(luò)。定義可得：

同樣需要注意的是λ（T，N）也可以從解決網(wǎng)絡(luò)中標(biāo)準(zhǔn)的最大并發(fā)流問(wèn)題中得到。

因此給出T和f，目標(biāo)就是確定：

我們使用貪婪算法來(lái)解決這個(gè)問(wèn)題。首先我們假設(shè)一組SDN轉(zhuǎn)發(fā)單元是空的。在算法的每一步，我們將給出最大吞吐量提升的節(jié)點(diǎn)添加到那個(gè)已存在的SDN轉(zhuǎn)發(fā)單元組。重復(fù)這個(gè)過(guò)程知道在網(wǎng)絡(luò)中我們有hSDN轉(zhuǎn)發(fā)單元組。因?yàn)門(mén)sd的值是已知的，那么吞吐量的問(wèn)題可以這樣解決：

服從

因?yàn)檫@個(gè)問(wèn)題從結(jié)構(gòu)上同SDN控制的問(wèn)題一樣，所以我們可以用同樣的方法解決這種問(wèn)題。

4　結(jié)語(yǔ)

在SDN和傳統(tǒng)的網(wǎng)絡(luò)中不斷地部署SDN是一個(gè)值得考慮的重要方案。這對(duì)于那些需要完全部署SDN的大型網(wǎng)絡(luò)非常重要。我們已經(jīng)展示了在一個(gè)已經(jīng)存在的網(wǎng)絡(luò)中部署SDN對(duì)提高網(wǎng)絡(luò)性能是可行的。及時(shí)部署少數(shù)的SDN轉(zhuǎn)發(fā)單元都可以提高網(wǎng)絡(luò)性能。該方案對(duì)網(wǎng)絡(luò)中剩余節(jié)點(diǎn)不存在任何修改協(xié)議的操作。初步性能測(cè)試也表明了該理論可以提高總體網(wǎng)絡(luò)的吞吐量并且在網(wǎng)絡(luò)中提供更好的延遲和丟包操作。

［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，”O(jiān)pening 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-），男，四川閬中人，碩士，研究方向?yàn)檐浂x網(wǎng)絡(luò)

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

王麗（1991-），女，山西臨汾人，碩士，研究方向?yàn)檐浂x網(wǎng)絡(luò)