軟件定義網(wǎng)絡(luò)中基于分段路由的流量調(diào)度方法

董謙，李俊，馬宇翔,2，韓淑君,2

?

軟件定義網(wǎng)絡(luò)中基于分段路由的流量調(diào)度方法

董謙1,2,3，李俊1，馬宇翔1,2，韓淑君1,2

（1. 中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心，北京 100190；2. 中國科學(xué)院大學(xué)，北京 100049； 3. 佛山科學(xué)技術(shù)學(xué)院電子信息工程學(xué)院，廣東 佛山 528000）

針對(duì)軟件定義網(wǎng)絡(luò)流量調(diào)度的多商品流問題，提出一種基于分段路由的方法。所提方法預(yù)先計(jì)算所有源—目的節(jié)點(diǎn)間的候選路徑集合和相應(yīng)路徑的屬性，再結(jié)合流的各種需求和約束條件設(shè)置候選路徑的屬性應(yīng)滿足的要求，據(jù)此篩選得出流的候選路徑集合；基于流的候選路徑集合簡(jiǎn)化了軟件定義網(wǎng)絡(luò)中的多商品流模型，降低了求解難度，支持控制器集中控制和各節(jié)點(diǎn)自主控制的工作方式，緩解了控制器的可擴(kuò)展性問題；還討論了如何滿足網(wǎng)絡(luò)的節(jié)能需求，減少可參與流轉(zhuǎn)發(fā)的鏈路數(shù)量。性能評(píng)估結(jié)果表明，所提方法可滿足流的各種需求和約束條件，提高網(wǎng)絡(luò)性能，減輕求解流量調(diào)度問題的計(jì)算負(fù)擔(dān)。

分段路由；軟件定義網(wǎng)絡(luò)；流量調(diào)度；線性規(guī)劃

1 引言

互聯(lián)網(wǎng)服務(wù)在人們的工作和生活中扮演著十分關(guān)鍵的角色，為此，人們提出多種類型的流量工程（TE, traffic engineering）技術(shù)以完成一系列網(wǎng)絡(luò)優(yōu)化任務(wù)。與此同時(shí)，網(wǎng)絡(luò)管理員對(duì)網(wǎng)絡(luò)流的細(xì)粒度管理也變得越來越重要。例如，網(wǎng)絡(luò)管理員不僅要考慮傳統(tǒng)的QoS（quality of service）需求，如時(shí)延、帶寬、抖動(dòng)、丟失分組率等[1]，還要考慮新出現(xiàn)的調(diào)度任務(wù)類型，如選擇若干條不相交路徑、部署服務(wù)鏈等。多協(xié)議標(biāo)簽交換（MPLS, multi-protocol label switching）是一種十分重要的機(jī)制，在這種場(chǎng)景下，標(biāo)簽解耦了轉(zhuǎn)發(fā)路徑控制和路由協(xié)議。但是，基于MPLS的TE相對(duì)復(fù)雜，特別是在多條流并存的情況下，通常難以取得性能和開銷的平衡[2]。

近年來，分段路由（SR, segment routing）以及它與軟件定義網(wǎng)絡(luò)（SDN, software-defined networking）的結(jié)合引起了人們的廣泛關(guān)注。SR支持無狀態(tài)源路由，可以減輕控制器和中間節(jié)點(diǎn)的開銷，對(duì)路徑的管理和控制也十分靈活[2]；SDN能提供網(wǎng)絡(luò)全局視角，能高效地部署TE任務(wù)[3]。顯然， SDN結(jié)合基于SR的全局源路由可針對(duì)具體應(yīng)用需求，對(duì)多條流分別進(jìn)行細(xì)粒度的路徑管理和控制[4]；相對(duì)于MPLS或傳統(tǒng)SDN而言，SR極大簡(jiǎn)化了控制面，使控制器無需對(duì)中間節(jié)點(diǎn)下發(fā)轉(zhuǎn)發(fā)規(guī)則，從而降低了控制器的負(fù)載，更好地平衡了網(wǎng)絡(luò)性能與開銷。

所有應(yīng)用都需要滿足特定的要求（約束條件），最典型的例子就是QoS。除此之外，SR網(wǎng)絡(luò)還有一個(gè)特有且非常重要的約束條件是進(jìn)行路徑控制時(shí)必須滿足的：由于設(shè)備性能的限制，標(biāo)簽棧最大深度是有限的，這意味著segment列表深度（SLD, segment list depth）是有限的[5]。對(duì)于有具體優(yōu)化目標(biāo)和約束條件的TE問題，一方面可建立相應(yīng)的數(shù)學(xué)模型，另一方面也需要找到合適的算法來求解。如果基于SR解決SDN中的流量調(diào)度問題，以滿足多個(gè)應(yīng)用即多條流的需求，通常會(huì)面臨以下挑戰(zhàn)。

1) 各種各樣的需求及約束條件會(huì)極大地提高求解問題的難度。一般來說，可用線性規(guī)劃（LP, linear programming）、整數(shù)線性規(guī)劃（ILP, integer linear programming）、混合整數(shù)線性規(guī)劃（MILP, mixed integer linear programming）模型來表示多商品流（MCF, multi-commodity flow）問題[5-8]，但在多數(shù)情況下，它們是NP-Hard問題[4,7]，相應(yīng)的算法必須足夠高效。

2) SR網(wǎng)絡(luò)中的硬件設(shè)備一般有最大SLD限制，能用于某條流轉(zhuǎn)發(fā)的候選路徑使用segment列表來表示，而且每個(gè)segment列表的SLD不應(yīng)超過其硬件限制，因此候選路徑不是任意的，必須將最大SLD限制以適當(dāng)形式加入相應(yīng)的數(shù)學(xué)模型中[5]?？紤]路徑的編碼問題，將其表示為segment列表[9]，使最終求出的解可行。

3) 在很多場(chǎng)景下，控制器到網(wǎng)絡(luò)設(shè)備間的往返時(shí)延不可忽視，一旦時(shí)延偏高，甚至由于種種原因超時(shí)，將會(huì)影響設(shè)備對(duì)相應(yīng)流的轉(zhuǎn)發(fā)[10-11]，這要求網(wǎng)絡(luò)設(shè)備也具備一定的對(duì)流轉(zhuǎn)發(fā)進(jìn)行路徑管理和控制的能力。支持SR的網(wǎng)絡(luò)設(shè)備具有這種能力，但其計(jì)算性能有限，必須考慮網(wǎng)絡(luò)設(shè)備如何在不依靠控制器的情況下對(duì)流進(jìn)行控制，同時(shí)無需復(fù)雜的計(jì)算過程。

為此，本文分析了SDN中基于SR的流量調(diào)度模型，針對(duì)多個(gè)應(yīng)用的流量需求并存的情況即 MCF問題，結(jié)合最大SLD限制等與應(yīng)用無關(guān)的約束條件，提出一種有效的方法以便求解，同時(shí)使網(wǎng)絡(luò)設(shè)備也具備一定的對(duì)流轉(zhuǎn)發(fā)路徑進(jìn)行管理和控制的能力；還簡(jiǎn)要分析了如何盡量滿足網(wǎng)絡(luò)的節(jié)能需求。本文的主要貢獻(xiàn)如下。

1) 針對(duì)SDN流量調(diào)度的MCF問題，結(jié)合SR的特點(diǎn)，設(shè)計(jì)整體架構(gòu)，對(duì)問題進(jìn)行建模和分析；

2) 提出一種簡(jiǎn)便的算法，預(yù)先計(jì)算所有源—目的節(jié)點(diǎn)間滿足SLD、等價(jià)多路徑（ECMP, equal cost multi path）等約束條件的候選路徑集合和相應(yīng)路徑的屬性，再結(jié)合流的各種需求和約束條件篩選得出流的候選路徑集合，降低了后續(xù)求解的難度；

3) 基于流的候選路徑集合，簡(jiǎn)化SDN中的MCF模型，為控制器集中控制和各節(jié)點(diǎn)自主控制的工作方式設(shè)計(jì)相應(yīng)處理流程；

4) 針對(duì)網(wǎng)絡(luò)的節(jié)能需求，討論如何減少可參與流轉(zhuǎn)發(fā)的鏈路數(shù)量。

2 SR簡(jiǎn)介和相關(guān)工作

2.1 SR簡(jiǎn)介

SR采用源路由范式，節(jié)點(diǎn)根據(jù)一個(gè)有序指令列表轉(zhuǎn)發(fā)數(shù)據(jù)分組，這些指令稱為segment。由于SR和MPLS之間的繼承關(guān)系，MPLS的轉(zhuǎn)發(fā)面本身并不用修改，segment以MPLS標(biāo)簽的形式表現(xiàn)時(shí)，一個(gè)有序segment列表也就是一個(gè)標(biāo)簽棧，棧內(nèi)標(biāo)簽數(shù)量即SLD，轉(zhuǎn)發(fā)時(shí)從棧頂標(biāo)簽開始處理；如果SR應(yīng)用于IPv6，segment可利用IPv6頭部中的路由擴(kuò)展，通過指針來控制當(dāng)前segment[12]。

segment標(biāo)識(shí)符簡(jiǎn)稱為SID，最常用的SID是節(jié)點(diǎn)（node）SID和鄰接（adjacency）SID，用于標(biāo)識(shí)SR路由器和它們間的鄰接關(guān)系。源節(jié)點(diǎn)將segment列表封裝進(jìn)數(shù)據(jù)分組的頭部，收到數(shù)據(jù)分組的路由器基于當(dāng)前（active）segment處理，對(duì)segment的動(dòng)作則有push、next、continue 3種。push，在分組頭部插入一組segment；next，處理當(dāng)前segment完畢后轉(zhuǎn)到下一個(gè)segment，與之對(duì)應(yīng)的是MPLS中的POP；continue，當(dāng)前segment并未處理完畢因而保留，與之對(duì)應(yīng)的是MPLS中的SWAP[12]。

SR數(shù)據(jù)面決定了設(shè)備如何根據(jù)segment來處理數(shù)據(jù)分組；SR控制面定義了如何在設(shè)備間傳播SID信息。SR一般使用IGP（interior gateway protocol）通告SID信息，與MPLS的LDP（label distribution protocol）等協(xié)議相比，簡(jiǎn)化了控制面；SR只需在源節(jié)點(diǎn)維護(hù)流狀態(tài)，根據(jù)源路由的原理和SR的轉(zhuǎn)發(fā)過程，中間設(shè)備無需各類復(fù)雜的資源配置機(jī)制，只需按照當(dāng)前segment處理數(shù)據(jù)分組即可，流的轉(zhuǎn)發(fā)完全由源節(jié)點(diǎn)通過segment列表控制；SR還能很好地支持ECMP[12]。

總之，在源節(jié)點(diǎn)處對(duì)流配置一個(gè)segment列表，這條流的轉(zhuǎn)發(fā)路徑就確定了。通過SR能方便地對(duì)每條流進(jìn)行細(xì)粒度管理，卻無需修改IGP參數(shù)，從而保證了網(wǎng)絡(luò)基礎(chǔ)配置的穩(wěn)定性。

2.2 相關(guān)工作

目前已有很多工作討論如何在SDN中進(jìn)行流量調(diào)度，如周桐慶等[13]總結(jié)了基于SDN的流量工程，將其分為數(shù)據(jù)層流量調(diào)度和控制層流量調(diào)度兩大類。數(shù)據(jù)層流量調(diào)度的主要目的是借助控制器的全局視角提高鏈路利用率，避免擁塞；控制層流量調(diào)度的主要目的是解決控制器的可擴(kuò)展性問題。本文注意到，源路由技術(shù)與SDN結(jié)合用于流量調(diào)度有突出優(yōu)勢(shì)。Li等[10]對(duì)SD-WAN（SDN for wide-area network）的研究表明，源路由可顯著節(jié)省控制器建立流轉(zhuǎn)發(fā)路徑的時(shí)間；Dong等[11]則提出了AJSR，利用基于MPLS的源路由，平衡了下發(fā)規(guī)則的開銷以及網(wǎng)絡(luò)性能。因此，源路由技術(shù)不僅有利于減少控制器建立流轉(zhuǎn)發(fā)路徑所需的時(shí)間，提高網(wǎng)絡(luò)性能，還能緩解控制器的可擴(kuò)展性問題。

表1 幾種基于SR的流量調(diào)度方法

也有一些工作討論如何將SR用于流量調(diào)度。Bhatia等[6]認(rèn)為SR的關(guān)鍵思想是將路徑分解或表達(dá)成為若干個(gè)segment，他們只考慮兩段segment的情況，分別開發(fā)了離線和在線流量調(diào)度優(yōu)化算法。Hartert等[7]提出了一種新的混合約束規(guī)劃框架來解決SR中的流量放置問題，設(shè)計(jì)了一種名為SR路徑變量的數(shù)據(jù)結(jié)構(gòu)，記錄已經(jīng)過的節(jié)點(diǎn)，列出接下來可能到達(dá)的節(jié)點(diǎn)，減小對(duì)計(jì)算資源的消耗。Hartert等[4]還設(shè)計(jì)了一種方法，用來控制電信級(jí)網(wǎng)絡(luò)中的轉(zhuǎn)發(fā)路徑，提出名為DFEO的集中式優(yōu)化器，通過中間點(diǎn)路由（MR, middle point routing）模型進(jìn)行計(jì)算，而MR基于轉(zhuǎn)發(fā)圖，因此可支持多路徑。Moreno等[5]分析了SR網(wǎng)絡(luò)中的流量模型，認(rèn)為ECMP會(huì)導(dǎo)致數(shù)據(jù)分組重新排序，因此考慮流轉(zhuǎn)發(fā)不使用ECMP而使用單路徑，還要滿足SLD約束條件。在現(xiàn)實(shí)環(huán)境下特別是運(yùn)營商網(wǎng)絡(luò)中，并非所有設(shè)備都支持SR，混合網(wǎng)絡(luò)或漸進(jìn)式部署也是很重要的場(chǎng)景，為此Cianfrani等[14]引入分段路由域（SRD, segment routing domain）的概念，區(qū)分單個(gè)SRD和多個(gè)SRD的場(chǎng)景，建立MILP模型以求解SRD設(shè)計(jì)問題，在SRD內(nèi)部則配置合適的流表?？偨Y(jié)上述工作的特點(diǎn)如表1所示。

表1說明，流量調(diào)度的主要目的是降低最大鏈路利用率，如要使用SR技術(shù)，一般應(yīng)考慮SLD約束條件。SR支持ECMP，但流轉(zhuǎn)發(fā)是否支持多路徑應(yīng)從實(shí)際情況出發(fā)，并在建模時(shí)體現(xiàn)。針對(duì)MCF問題，一般先收集相關(guān)信息然后求解，再由控制器或網(wǎng)絡(luò)管理員根據(jù)求得的結(jié)果將規(guī)則分別下發(fā)到相關(guān)的設(shè)備。

由于SR中路徑編碼的重要性，一些工作專門就此進(jìn)行討論。Giorgetti等[9]提出兩種算法，保證對(duì)一條路徑求出的SLD最??；Guedrez等[15]提出兩種算法，對(duì)于鄰接SID再將其區(qū)分為本地和全局兩種類型；Cianfrani等[16]將路徑編碼與TE模型相結(jié)合，先基于網(wǎng)絡(luò)圖創(chuàng)建輔助圖，然后列出源—目的節(jié)點(diǎn)間所有可選擇的路徑，再基于輔助圖求解MCF問題。上述工作表明，如果先設(shè)定segment類型，則可根據(jù)路徑求出其對(duì)應(yīng)的segment列表且使其SLD最小。

相關(guān)工作分析驗(yàn)證了SDN中基于SR的流量調(diào)度的優(yōu)勢(shì)、可行性和效果，表1中基于SR的流量調(diào)度方式多為集中式計(jì)算求解路徑及流量分擔(dān)比例。然而，實(shí)際MCF問題中的約束條件種類較多，加之SR網(wǎng)絡(luò)必須考慮最大SLD限制，單路徑或多路徑也使流量模型更加復(fù)雜，即使求出了模型的解，有時(shí)還需考慮路徑的編碼問題，集中式的計(jì)算方式如應(yīng)用于各節(jié)點(diǎn)自主控制的場(chǎng)景也較為不便。另外，Lee等[17-18]提出MPLS中的多路徑負(fù)載均衡算法通常分為兩步，第一步計(jì)算候選路徑，第二步計(jì)算流量分割比例。本文還注意到，在進(jìn)行流量調(diào)度相關(guān)計(jì)算前，預(yù)先計(jì)算好候選路徑的方案有突出優(yōu)勢(shì)：Suchara等[19]提出預(yù)計(jì)算多條路徑則路由器不再需要進(jìn)行路徑計(jì)算，能夠減輕路由器的負(fù)擔(dān)；Leconte等[20]提出只要選擇合適的預(yù)計(jì)算路徑集合并將其控制在相對(duì)小的規(guī)模，可極大提高優(yōu)化計(jì)算的速度。

因此，對(duì)于SDN中相對(duì)復(fù)雜的流量調(diào)度模型，本方法結(jié)合SR的特點(diǎn)提出了一種預(yù)計(jì)算候選路徑集合的算法，不僅能滿足各類需求和約束條件，還記錄了候選路徑對(duì)應(yīng)的segment列表并使其SLD最?。桓鶕?jù)候選路徑集合計(jì)算流量分擔(dān)比例，能夠簡(jiǎn)化MCF模型，降低求解難度；本方法也支持各節(jié)點(diǎn)自主控制，各節(jié)點(diǎn)預(yù)先從控制器獲取已經(jīng)計(jì)算好的候選路徑集合，調(diào)度時(shí)只需根據(jù)流的需求和當(dāng)前網(wǎng)絡(luò)狀態(tài)在候選路徑中選擇合適路徑。

3 問題分析

3.1 整體架構(gòu)

在SDN中，控制器能通過南向接口協(xié)議獲取網(wǎng)絡(luò)信息，下發(fā)規(guī)則。在IP網(wǎng)絡(luò)中，基于IGP的擴(kuò)展能收集當(dāng)前鏈路狀態(tài)等必要信息。SDN中的流量調(diào)度如圖1所示。

圖1 SDN中的流量調(diào)度示意

圖1中實(shí)線表示節(jié)點(diǎn)間的鄰接關(guān)系即鏈路，假定有一條流從節(jié)點(diǎn)1先后經(jīng)過節(jié)點(diǎn)5、節(jié)點(diǎn)4轉(zhuǎn)發(fā)到節(jié)點(diǎn)3，粗箭頭表示流的轉(zhuǎn)發(fā)路徑走向，虛線表示OpenFlow[21]等接口協(xié)議中控制器與節(jié)點(diǎn)間的packet-in和packet-out交互，控制器需要給這條流轉(zhuǎn)發(fā)路徑上的每個(gè)節(jié)點(diǎn)下發(fā)相應(yīng)的轉(zhuǎn)發(fā)規(guī)則。

將源路由技術(shù)SR引入SDN后，流量調(diào)度如圖2所示。對(duì)于同樣的一條流，此時(shí)控制器只需與源節(jié)點(diǎn)1交互，對(duì)路徑進(jìn)行編碼并下發(fā)相應(yīng)的segment列表。與圖1中的SDN不同的是，SR網(wǎng)絡(luò)通過SR控制面?zhèn)鞑ID信息，控制器無需對(duì)中間節(jié)點(diǎn)下發(fā)轉(zhuǎn)發(fā)規(guī)則，節(jié)省了控制器建立流轉(zhuǎn)發(fā)路徑所需的時(shí)間，減輕了控制器的負(fù)擔(dān)；控制器可專注于根據(jù)MCF需求和約束條件進(jìn)行流量調(diào)度優(yōu)化計(jì)算，即使控制器失效，SR網(wǎng)絡(luò)也具備轉(zhuǎn)發(fā)能力，各節(jié)點(diǎn)能作為源節(jié)點(diǎn)自主控制某條流。

圖2 SDN中基于SR的流量調(diào)度示意

3.2 模型建立與分析

式(8)表示鏈路可參與流轉(zhuǎn)發(fā)的條件。如優(yōu)化任務(wù)是最小化最大鏈路利用率，可表示為

min(9)

所有鏈路l為1時(shí)，式(1)~式(7)是SDN流量調(diào)度的MCF模型里的基本約束，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)為LP模型，只支持單路徑時(shí)為ILP模型。然而，如對(duì)流進(jìn)行細(xì)粒度管理，例如滿足應(yīng)用的時(shí)延要求，或滿足服務(wù)鏈中必經(jīng)某節(jié)點(diǎn)的要求，每條流的需求都應(yīng)體現(xiàn)，使得約束條件更多，通常導(dǎo)致求解難度增加；有些條件甚至難以表達(dá)，例如SR特有的SLD約束難以用線性關(guān)系式寫出。

為此，本文提出一種基于SR的流量調(diào)度方法，為簡(jiǎn)化討論只使用節(jié)點(diǎn)SID，不使用鄰接SID。先做如下說明。

1) 將路徑集合記為，每個(gè)都以矩陣形式表示。矩陣的列數(shù)等于，為中元素的數(shù)量，對(duì)所有鏈路編號(hào)，將鏈路記為e，鏈路編號(hào)=1,2,…,。矩陣的行數(shù)表示為()，因此，由()個(gè)一行列的一維數(shù)組即行向量組成，即()是矩陣中的數(shù)量。若考慮空集即行數(shù)為0的空矩陣[22]，則()最小為0。

2) 每個(gè)的實(shí)際意義是能用一個(gè)segment列表表示的一條路徑或多條等價(jià)路徑，分別規(guī)定如下：若表示一條路徑，則中第列元素的值表示當(dāng)這條路徑負(fù)擔(dān)的流量為1時(shí)鏈路e上的流量大小，故路徑?jīng)]有重復(fù)使用e，則路徑經(jīng)過e時(shí)元素值為1，不經(jīng)過時(shí)為0；若表示多條等價(jià)路徑且這些路徑可編碼為一個(gè)segment列表（按某些segment轉(zhuǎn)發(fā)且存在ECMP負(fù)載均衡時(shí)，相應(yīng)各條等價(jià)路徑上的流量分擔(dān)比例一般是固定的），則根據(jù)這些等價(jià)路徑負(fù)擔(dān)的流量之和為1時(shí)鏈路e上的流量大小設(shè)定中第列元素的值。流量平衡條件體現(xiàn)在的元素值中。

3) 對(duì)每個(gè)設(shè)置若干屬性，的屬性也就是路徑的屬性，例如：ecmp表示中是否存在ECMP負(fù)載均衡，存在則為1，否則為0；sld表示對(duì)編碼所需SID數(shù)量的最小值；表示的segment列表記為sl，sl的獲得基于4.1節(jié)中的路徑產(chǎn)生過程；cost表示的路由代價(jià)；hop表示的跳數(shù)；delay表示的時(shí)延；nodein、nodeout分別表示負(fù)擔(dān)流量時(shí)每個(gè)節(jié)點(diǎn)是否有流量流入、流出，均為一行列的一維數(shù)組即行向量形式，為中元素的數(shù)量，對(duì)所有節(jié)點(diǎn)編號(hào)，將節(jié)點(diǎn)再記為n，節(jié)點(diǎn)編號(hào)=1,2,…,，nodein、nodeout中第列元素的值為1分別表示節(jié)點(diǎn)n在負(fù)擔(dān)流量時(shí)有流量流入、流出，否則為0。還可根據(jù)需要設(shè)置其他類型的屬性。

本文方法的主要步驟如下。

1) 通過4.1節(jié)中的路徑產(chǎn)生過程可獲得網(wǎng)絡(luò)拓?fù)渲兴性础康墓?jié)點(diǎn)間的候選路徑集合和相應(yīng)路徑的屬性。源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的候選路徑集合再記為，所有()應(yīng)大于等于1；所有節(jié)點(diǎn)對(duì)之間的及相應(yīng)的屬性作為控制器進(jìn)行后續(xù)處理和MCF計(jì)算的依據(jù)；對(duì)于每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，可預(yù)先將以它為源節(jié)點(diǎn)的及相應(yīng)的屬性下發(fā)給它，使網(wǎng)絡(luò)節(jié)點(diǎn)無需進(jìn)行復(fù)雜計(jì)算便可篩選得出候選并對(duì)流轉(zhuǎn)發(fā)進(jìn)行控制。

式(12)和式(13)為鏈路容量條件和鏈路可參與流轉(zhuǎn)發(fā)的條件，流量平衡條件體現(xiàn)在和式(10)及式(11)中，其他需求和約束條件體現(xiàn)在中，的取值范圍由式(5)確定，至此簡(jiǎn)化了SDN中的MCF模型；式(9)是TE的經(jīng)典優(yōu)化任務(wù)[4]，還可添加其他優(yōu)化目標(biāo)，并對(duì)每個(gè)優(yōu)化目標(biāo)設(shè)定合適優(yōu)先級(jí)和權(quán)重[23]。

4 方法描述

本文方法首先求出網(wǎng)絡(luò)拓?fù)渲兴性础康墓?jié)點(diǎn)間的候選路徑集合，記錄相應(yīng)路徑的屬性，然后以此為基礎(chǔ)，針對(duì)控制器和各節(jié)點(diǎn)自主控制分別設(shè)計(jì)相應(yīng)處理流程進(jìn)行流量調(diào)度。

4.1 路徑產(chǎn)生

在SR網(wǎng)絡(luò)中，sld為1表示segment列表中只有目的節(jié)點(diǎn)的SID，此時(shí)轉(zhuǎn)發(fā)路徑是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑或存在ECMP負(fù)載均衡的多條等價(jià)最短路徑。網(wǎng)絡(luò)拓?fù)浯_定則鏈路的路由代價(jià)即權(quán)重已知，可由最短路徑算法得到所有節(jié)點(diǎn)對(duì)之間的最短路徑或多條等價(jià)最短路徑；最短路徑不存在環(huán)路，這是后續(xù)排除有環(huán)路路徑過程的前提。

將,間的最短路徑集合再記為-1，將sld=2,3,…,的候選路徑集合分別再記為-2、-3、…、，且-2、-3、…、在計(jì)算前應(yīng)初始化為空集即行數(shù)為0的空矩陣，為所允許的最大sld，即sld≤。為便于表述，本文也將所允許的最大sld稱為sld最大值。先根據(jù)最短路徑算法求出網(wǎng)絡(luò)拓?fù)渲兴泄?jié)點(diǎn)對(duì)之間的-1，顯然任意一對(duì),間的-1都只有一個(gè)，且這個(gè)的sl為目的節(jié)點(diǎn)的SID，sld=1；若,間只有一條最短路徑，則這個(gè)表示這條最短路徑；若有多條等價(jià)最短路徑，則這個(gè)表示存在ECMP負(fù)載均衡的多條等價(jià)最短路徑；記錄相應(yīng)的屬性。

圖3 預(yù)計(jì)算p的過程示意

簡(jiǎn)要給出計(jì)算所有節(jié)點(diǎn)對(duì)之間的-2的算法，如算法1所示。

算法1 計(jì)算所有節(jié)點(diǎn)對(duì)之間的-2

1) 輸入，所有節(jié)點(diǎn)對(duì)之間的-1，相應(yīng)的屬性

2) for each∈do

3) for each∈ {} do

4) 初始化-2為空集即行數(shù)為0的空矩陣

5) for each∈ {,} do

6) if-1為空集即空矩陣 then

7) else

8) for= 1 to(-1) do

11) else

13) end if

14) end for

15) end if

16) end for

17) end for

18) end for

4.2 流量調(diào)度

控制器預(yù)計(jì)算得出所有節(jié)點(diǎn)對(duì)之間的。流量調(diào)度目標(biāo)為min時(shí)，控制器先收集流集合、當(dāng)前鏈路信息，所有鏈路l通常為1，也可根據(jù)要求設(shè)定l。然后由對(duì)應(yīng)的篩選得出，設(shè)定的精度要求，控制對(duì)應(yīng)的臨時(shí)變量用于試探求解，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)為LP模型，只支持單路徑時(shí)為ILP模型。簡(jiǎn)要給出求解算法，如算法2所示。

算法2 優(yōu)化任務(wù)為min時(shí)控制器求解

1) 輸入，所有節(jié)點(diǎn)對(duì)之間的，相應(yīng)的屬性，當(dāng)前鏈路信息，所有鏈路l，的精度要求

2) for each∈do

3) 根據(jù)對(duì)應(yīng)的篩選得出

4) end for

5) 根據(jù)式(5)，結(jié)合的精度要求設(shè)定的取值范圍，再將設(shè)定為其取值下限即滿足式(5)且符合的精度要求的最小值，并以試探求解

6) if有解 then

7)←

8) else

9) 使按的精度要求增加并在增加后再以試探求解，無解則重復(fù)此步驟直到有解為止

10)←

11) end if

調(diào)整的方式也可使用其他更高效的方式?？刂破鞲鶕?jù)當(dāng)前條件及精度要求下求得的最小值對(duì)應(yīng)的解配置流轉(zhuǎn)發(fā)，segment列表直接取自sl。

各節(jié)點(diǎn)自主控制進(jìn)行流量調(diào)度時(shí)，先從控制器獲取其作為源節(jié)點(diǎn)的所有。當(dāng)它自主控制某條流時(shí)，只考慮當(dāng)前網(wǎng)絡(luò)狀況，收集鏈路信息，此時(shí)MCF問題變?yōu)檫@條流的路徑選擇問題，一般來說求解算法與算法2相似，只是變?yōu)閧}，變?yōu)?i>，若想使求得的解是唯一的，可添加其他優(yōu)化目標(biāo)。

4.3 節(jié)能控制

定義節(jié)能效果即不可休眠或關(guān)閉的物理連接數(shù)量為，將節(jié)能控制的優(yōu)化任務(wù)設(shè)為使最小，即可參與流轉(zhuǎn)發(fā)的鏈路數(shù)量最少，有

min(16)

根據(jù)式(16)進(jìn)行優(yōu)化計(jì)算并通過流量調(diào)度實(shí)現(xiàn)時(shí)，一般是約束條件而非優(yōu)化目標(biāo)，應(yīng)設(shè)定值，將其代入相關(guān)約束條件。此時(shí)除式(10)~式(13)外，還應(yīng)滿足式(14)~式(15)。根據(jù)式(12)，l包含在中，求解前應(yīng)先收集鏈路信息，根據(jù)收集的信息設(shè)定所有鏈路l的取值范圍：u>0時(shí)鏈路已使用，相應(yīng)的l必為1；u=0時(shí)鏈路暫未使用，相應(yīng)的l可取0或1?？刂破鬟M(jìn)行流量調(diào)度時(shí)，需求解和所有鏈路l，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)為MILP模型，只支持單路徑時(shí)為ILP模型。簡(jiǎn)要給出求解算法，如算法3所示。

算法3 優(yōu)化任務(wù)為min時(shí)控制器，求解和所有鏈路l

1) 輸入，所有節(jié)點(diǎn)對(duì)之間的，相應(yīng)的屬性，當(dāng)前鏈路信息，

2) for each∈do

3) 根據(jù)對(duì)應(yīng)的篩選得出

4) end for

5) 設(shè)定所有鏈路l的取值范圍

6) 求解和所有鏈路l，根據(jù)式(15)得

各節(jié)點(diǎn)自主控制進(jìn)行流量調(diào)度時(shí)，先從控制器獲取其作為源節(jié)點(diǎn)的所有。當(dāng)它自主控制某條流時(shí)，只考慮當(dāng)前網(wǎng)絡(luò)狀況，收集鏈路信息，設(shè)定所有鏈路l的取值范圍，此時(shí)MCF問題變?yōu)檫@條流的路徑選擇問題，求解算法與算法3相似，只是變?yōu)閧}，變?yōu)?i>，優(yōu)先選擇已用鏈路。

4.4 算法分析

控制器進(jìn)行流量調(diào)度時(shí)，根據(jù)算法2和算法3，的元素?cái)?shù)量等于所有流的()之和，鏈路的數(shù)量即l的數(shù)量是固定的，流量調(diào)度模型中的變量數(shù)量通常較多，控制器可使用Gurobi[26]等優(yōu)化器求解；已有工作表明，選擇合適的預(yù)計(jì)算路徑集合[20]能縮小后續(xù)求解的搜索空間，降低求解難度，還能避免使用過長的路徑[25]，而5.2.3節(jié)的評(píng)估結(jié)果表明，對(duì)進(jìn)行篩選減少流量調(diào)度模型中的變量數(shù)量后，后續(xù)求解的難度降低。網(wǎng)絡(luò)設(shè)備作為源節(jié)點(diǎn)自主控制某條流時(shí)，只考慮這條流的路徑選擇問題，求解難度更低；特別是當(dāng)流轉(zhuǎn)發(fā)只支持單路徑時(shí)，通常無需求解ILP模型，只需依次檢驗(yàn)中的每個(gè)是否可行，若都不可行則調(diào)整或l后再次檢驗(yàn)。

對(duì)于所有流可使用任意多路徑或單路徑轉(zhuǎn)發(fā)的SDN流量調(diào)度模型，增加約束條件通常會(huì)增加求解難度，部分約束例如SLD約束甚至難以表達(dá)；本方法預(yù)先計(jì)算候選路徑集合，根據(jù)一定要求即約束條件對(duì)進(jìn)行篩選意味著在后續(xù)求解時(shí)無需再考慮這些約束條件，從而簡(jiǎn)化了MCF模型。本方法基于源路由技術(shù)，控制器無需給中間節(jié)點(diǎn)下發(fā)轉(zhuǎn)發(fā)規(guī)則；即使控制器失效，各節(jié)點(diǎn)只要已獲得了相關(guān)便能自主控制；對(duì)進(jìn)行篩選降低了后續(xù)求解的難度。這些特點(diǎn)均緩解了控制器的可擴(kuò)展性問題。

5 性能評(píng)估

本文從公開數(shù)據(jù)集SNDLib[27]獲取網(wǎng)絡(luò)拓?fù)湫畔ⅲòü?jié)點(diǎn)、鏈路、鏈路的容量及路由代價(jià)）和流量數(shù)據(jù)，拓?fù)錇镚éANT和Germany50，分別有22個(gè)和50個(gè)節(jié)點(diǎn)，考慮分別有72條和176條鏈路。

5.1 實(shí)驗(yàn)拓?fù)浞治?/h3>

首先基于GéANT的網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行分析，根據(jù)最短路徑算法，GéANT中所有節(jié)點(diǎn)對(duì)之間的最短路徑均無ECMP，故ecmp必然為0；分別設(shè)定sld≤2, 3, 4，根據(jù)4.1節(jié)中的原則1)~原則2)，分別計(jì)算得出所有462對(duì)源—目的節(jié)點(diǎn)間相應(yīng)的；統(tǒng)計(jì)所有節(jié)點(diǎn)對(duì)中()小于等于個(gè)的源—目的節(jié)點(diǎn)對(duì)的數(shù)量，除以此拓?fù)渲性础康墓?jié)點(diǎn)對(duì)的總數(shù)即462后得到比例()，()表示()在數(shù)量上的分布情況。結(jié)果如圖4所示。再基于Germany50的網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行分析，根據(jù)最短路徑算法，Germany50中部分節(jié)點(diǎn)對(duì)之間的最短路徑有ECMP，故ecmp為0或1；分別設(shè)定sld≤2, 3，再用SP表示所有流轉(zhuǎn)發(fā)只支持單路徑，MP表示所有流轉(zhuǎn)發(fā)支持多路徑，區(qū)別在于前者ecmp應(yīng)為0而后者無此要求，根據(jù)4.1節(jié)中的原則1)~原則3)，分別計(jì)算得出所有2 450對(duì)源—目的節(jié)點(diǎn)間相應(yīng)的。結(jié)果如圖5所示。

圖4和圖5表明sld最大值不同時(shí)，()隨變化的趨勢(shì)相似；()相同時(shí)，sld最大值越大則越大。根據(jù)4.1節(jié)中的原則1)~原則3)計(jì)算能使()的大小控制在相對(duì)有限的范圍。圖5還表明，sld最大值及()相同時(shí)，若部分節(jié)點(diǎn)對(duì)之間的最短路徑有ECMP，由于ecmp還應(yīng)為0，所有流轉(zhuǎn)發(fā)只支持單路徑時(shí)的通常小于支持多路徑時(shí)的。

5.2 流量調(diào)度優(yōu)化效果評(píng)估

5.2.1 GéANT拓?fù)淞髁空{(diào)度優(yōu)化效果

圖4 GéANT網(wǎng)絡(luò)拓?fù)浞治鼋Y(jié)果

圖5 Germany50網(wǎng)絡(luò)拓?fù)浞治鼋Y(jié)果

中的每對(duì)源—目的節(jié)點(diǎn)間有一條流，size為它們之間的流量需求大??；這3個(gè)分別用GéANT-1、GéANT-2、GéANT-3從GéANT的流量矩陣（TM, traffic matrix）數(shù)據(jù)集中取出3個(gè)作為用于評(píng)估的3個(gè)TM；設(shè)TM表示，各有462條流。再用Con表示有控制器，用nCon表示無控制器即各節(jié)點(diǎn)自主控制。流量調(diào)度優(yōu)化任務(wù)為min，的精度要求設(shè)為1?，優(yōu)化效果用當(dāng)前條件優(yōu)化計(jì)算求得的評(píng)估且越小越好，為方便表示，再定義最大鏈路利用率優(yōu)化效果為

式(19)中，SDN使用多路徑指采用3.2節(jié)中約束條件為式(1)~式(7)的流量調(diào)度模型且所有流轉(zhuǎn)發(fā)支持多路徑，此時(shí)只考慮了基本約束且多路徑能更合理地均衡負(fù)載，因此每個(gè)在此條件下求得的是相應(yīng)精度要求下的最優(yōu)值，故越小越好且最小值為1?；?.1節(jié)中計(jì)算得出的sld≤4的，對(duì)每條流篩選其對(duì)應(yīng)的，分別得出sld最大值為2、3、4條件下的（因ecmp必然為0，故SP和MP這兩種情況下使用相同的）。以所有流沿最短路徑轉(zhuǎn)發(fā)的情況作為對(duì)比，表示為sld最大值為1。

圖6 GéANT流量調(diào)度優(yōu)化效果?Θ

從圖6中可以總結(jié)如下規(guī)律。

1) 有控制器時(shí)，流量調(diào)度是全局優(yōu)化，可以取得相對(duì)理想的效果，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)為1，意味著求得的能達(dá)到最優(yōu)值；所有流轉(zhuǎn)發(fā)只支持單路徑時(shí)為1.06~1.14，意味著求得的接近最優(yōu)值；無控制器時(shí)，流量調(diào)度是局部?jī)?yōu)化，在候選路徑集合相同的情況下，有控制器時(shí)的全局優(yōu)化比局部?jī)?yōu)化的效果更好；即使是局部?jī)?yōu)化，效果也比所有流沿最短路徑轉(zhuǎn)發(fā)時(shí)更好，支持多路徑時(shí)求得的相比所有流沿最短路徑轉(zhuǎn)發(fā)時(shí)的值降低42%以上，只支持單路徑時(shí)也可降低27%以上。

2) 有控制器時(shí)，sld最大值分別為2、3、4時(shí)的優(yōu)化效果相同；無控制器時(shí)，sld最大值為2、3、4時(shí)的效果可能存在一定波動(dòng)，不一定sld最大值越大效果越好，這也是局部?jī)?yōu)化導(dǎo)致的。

3) 無論有無控制器，一般來說所有流轉(zhuǎn)發(fā)支持多路徑時(shí)求得的比只支持單路徑時(shí)略小（也可能在有控制器時(shí)相同，如表2所示），這是因?yàn)閱温窂降募s束更嚴(yán)格，多路徑能更合理地均衡負(fù)載。

5.2.2 Germany50拓?fù)淞髁空{(diào)度優(yōu)化效果

為驗(yàn)證本方法在不同規(guī)模拓?fù)湎乱约盎诘膶傩宰龊线m篩選得出的優(yōu)化效果，先從Germany50的TM數(shù)據(jù)集中取出3個(gè)，然后分別取每個(gè)TM中源—目的節(jié)點(diǎn)間流量需求大小在本TM最大前200的流量數(shù)據(jù)，作為用于評(píng)估的3個(gè)TM；設(shè)TM中的每對(duì)源—目的節(jié)點(diǎn)間有一條流，size為它們之間的流量需求大小；這3個(gè)分別用Germany50-1、Germany50-2、Germany50-3表示，各有200條流。

基于5.1節(jié)中計(jì)算得出的SP和MP這兩種情況下sld≤3的，對(duì)每條流篩選其對(duì)應(yīng)的，仍將sld最大值設(shè)定為3，同樣區(qū)分SP和MP這兩種情況，分別得出cost相對(duì)其對(duì)應(yīng)的源—目的節(jié)點(diǎn)之間最短路徑的cost的比值在（以下簡(jiǎn)稱為cost相對(duì)最短路徑的比值）小于1.25、1.5、1.75的。結(jié)果如表2所示。

從表2中可以總結(jié)如下規(guī)律。

1) 無論所有流轉(zhuǎn)發(fā)是支持多路徑還是只支持單路徑，以及有無控制器，在取得相同條件下無cost約束時(shí)的值以前，候選路徑數(shù)量對(duì)優(yōu)化效果影響較大，cost相對(duì)最短路徑的比值上限增加意味著候選路徑數(shù)量增多，優(yōu)化效果通常也會(huì)更好。

表2 Germany50流量調(diào)度優(yōu)化效果?Θ

2) 有控制器時(shí)，流量調(diào)度是全局優(yōu)化，無論所有流轉(zhuǎn)發(fā)是支持多路徑還是只支持單路徑，當(dāng)cost相對(duì)最短路徑的比值小于1.75時(shí)為1，意味著求得的都能達(dá)到最優(yōu)值，因此只要基于cost做合適篩選，既可減小()，也能獲得較好的優(yōu)化效果。

5.2.3 Germany50拓?fù)淞髁空{(diào)度求解時(shí)間

考慮5.2.2節(jié)有控制器時(shí)的情況，與3.2節(jié)中約束條件為式(1)~式(7)即無sld、cost約束條件的SDN流量調(diào)度模型對(duì)比；均區(qū)分所有流轉(zhuǎn)發(fā)支持多路徑和只支持單路徑，即區(qū)分LP模型和ILP模型，統(tǒng)計(jì)其中的變量數(shù)量如圖7所示。

圖7表明，cost相對(duì)最短路徑的比值上限越大，變量數(shù)量越多；cost相對(duì)最短路徑的比值上限相同時(shí)，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)的變量數(shù)量比只支持單路徑時(shí)的變量數(shù)量更多；對(duì)進(jìn)行篩選后，變量數(shù)量相對(duì)于SDN流量調(diào)度模型更少。

再將設(shè)定為當(dāng)前條件優(yōu)化計(jì)算求得的，不添加其他優(yōu)化目標(biāo)，此時(shí)模型有解，以代入求解一次所需時(shí)間作為求解時(shí)間；硬件為i7-6700處理器和12 GB內(nèi)存，軟件為Windows 10操作系統(tǒng)，在Matlab R2017a下用Gurobi[26]7.5.1求解并統(tǒng)計(jì)時(shí)間，用同一軟硬件環(huán)境下的求解時(shí)間衡量求解難度。結(jié)果如圖8所示。

圖7和圖8表明，對(duì)于LP和ILP模型，通常變量數(shù)量越少求解越快。cost相對(duì)最短路徑的比值小于1.75時(shí)，根據(jù)5.2.2節(jié)的結(jié)果和統(tǒng)計(jì)求解時(shí)間的前提，此時(shí)本方法與SDN流量調(diào)度模型設(shè)定的相同，對(duì)于LP模型，本方法的求解時(shí)間比SDN流量調(diào)度模型少83%以上；對(duì)于ILP模型，本方法的求解時(shí)間比SDN流量調(diào)度模型少23%以上；一般而言，相同情況下ILP模型的求解時(shí)間相對(duì)LP模型更長。上述結(jié)果說明本方法在約束條件更多的情況下能簡(jiǎn)化MCF模型，通過對(duì)進(jìn)行篩選可降低后續(xù)求解的難度，使求解時(shí)間更短，且求得的可達(dá)到最優(yōu)值，能較好平衡網(wǎng)絡(luò)性能與求解時(shí)間。無控制器時(shí)，參見4.2節(jié)，每條流求解時(shí)的變量數(shù)量只取決于()，比有控制器的全局優(yōu)化時(shí)的變量數(shù)量更少，根據(jù)上述結(jié)果，每條流的求解時(shí)間會(huì)更短，更適合性能相對(duì)較弱的網(wǎng)絡(luò)節(jié)點(diǎn)。

圖7 5.2.2節(jié)有控制器時(shí)流量調(diào)度模型中的變量數(shù)量

5.3 節(jié)能控制優(yōu)化效果評(píng)估

節(jié)能控制優(yōu)化任務(wù)為min，優(yōu)化效果用當(dāng)前條件優(yōu)化計(jì)算求得的評(píng)估且越小越好；仍使用GéANT-1、GéANT-2、GéANT-3并將設(shè)定為典型值0.5[25]，為減輕計(jì)算負(fù)擔(dān)由各節(jié)點(diǎn)對(duì)流進(jìn)行自主控制；以所有流沿最短路徑轉(zhuǎn)發(fā)的情況作為對(duì)比，表示為sld=1。結(jié)果如表3所示。

圖8 5.2.2節(jié)有控制器時(shí)流量調(diào)度求解時(shí)間

表3 GéANT節(jié)能控制優(yōu)化效果-SUM

從表3中可以總結(jié)出如下規(guī)律。

1)sld最大值越大，求得的越小，這是由于sld最大值決定了候選路徑的數(shù)量，候選路徑越多則越有可能讓所有流使用更少的鏈路轉(zhuǎn)發(fā)。

2) 當(dāng)sld最大值相同時(shí)，所有流轉(zhuǎn)發(fā)支持多路徑與只支持單路徑求得的相同，這是因?yàn)楫?dāng)設(shè)定的較大也就是鏈路可用容量足夠大時(shí)，節(jié)能控制優(yōu)化目標(biāo)與流量負(fù)載分擔(dān)因素關(guān)聯(lián)不大。

5.4 評(píng)估結(jié)果討論

首先，對(duì)GéANT和Germany50拓?fù)涞姆治霰砻?，根?jù)4.1節(jié)中的原則1)~原則3)計(jì)算能使()的大小控制在相對(duì)有限的范圍。

然后，若將優(yōu)化任務(wù)設(shè)為最小化最大鏈路利用率，基于GéANT和Germany50拓?fù)涞脑u(píng)估結(jié)果表明，選擇合適的候選路徑集合后，本方法的優(yōu)化效果良好，有控制器且所有流轉(zhuǎn)發(fā)支持多路徑時(shí)為1即求得的達(dá)到最優(yōu)值，有控制器且所有流轉(zhuǎn)發(fā)只支持單路徑時(shí)為1~1.14即達(dá)到或接近最優(yōu)值，無控制器即各節(jié)點(diǎn)自主控制時(shí)也有較好效果。

另外，基于Germany50拓?fù)涞脑u(píng)估結(jié)果還表明，考慮有控制器時(shí)的情況，當(dāng)cost相對(duì)最短路徑的比值小于1.75時(shí)不僅為1即求得的達(dá)到最優(yōu)值，所有流轉(zhuǎn)發(fā)支持多路徑時(shí)求解時(shí)間也比約束條件更少的SDN流量調(diào)度模型少83%以上，只支持單路徑時(shí)求解時(shí)間比SDN流量調(diào)度模型少23%以上，說明當(dāng)網(wǎng)絡(luò)拓?fù)湟?guī)模較大時(shí)，基于的屬性做合適篩選得出，能在獲得較好優(yōu)化效果的同時(shí)減少流量調(diào)度模型中的變量數(shù)量，減輕計(jì)算負(fù)擔(dān)。

最后，基于GéANT拓?fù)涞脑u(píng)估結(jié)果表明，本方法能較好滿足節(jié)能控制需求，候選路徑越多則節(jié)能效果越有可能更好，設(shè)定為0.5時(shí)求得的可達(dá)到所有流沿最短路徑轉(zhuǎn)發(fā)時(shí)的60%左右。

6 結(jié)束語

本文針對(duì)SDN流量調(diào)度的MCF問題，將SR引入SDN，設(shè)計(jì)整體架構(gòu)；通過建模分析，結(jié)合SR的特點(diǎn)設(shè)計(jì)算法，預(yù)先計(jì)算所有源—目的節(jié)點(diǎn)間的候選路徑集合和相應(yīng)路徑的屬性，再結(jié)合流的需求和約束條件根據(jù)路徑的屬性篩選得出流的候選路徑集合，不僅簡(jiǎn)化了SDN中的MCF模型，降低了后續(xù)求解的難度，還支持控制器集中控制和各節(jié)點(diǎn)自主控制的工作方式，也緩解了控制器的可擴(kuò)展性問題；討論如何滿足網(wǎng)絡(luò)節(jié)能需求，減少可參與流轉(zhuǎn)發(fā)的鏈路數(shù)量。評(píng)估結(jié)果表明，SDN中基于SR的流量調(diào)度方法能滿足流的各種需求和約束條件，提高網(wǎng)絡(luò)性能，減輕求解流量調(diào)度問題的計(jì)算負(fù)擔(dān)。

[1] WANG N, HO K, PAVLOU G, et al. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1): 36-56.

[2] FILSFILS C, NAINAR N K, PIGNATARO C, et al. The segment routing architecture[C]//IEEE Global Communications Conference. 2015: 1-6.

[3] KREUTZ D, RAMOS F M V, VERISSIMO P E, et al. Software-defined networking: a comprehensive survey[J]. Proceedings of the IEEE, 2015, 103(1): 14-76.

[4] HARTERT R, VISSICCHIO S, SCHAUS P, et al. A declarative and expressive approach to control forwarding paths in carrier-grade networks[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 15-28.

[5] MORENO E, BEGHELLI A, CUGINI F. Traffic engineering in segment routing networks[J]. Computer Networks, 2017, 114: 23-31.

[6] BHATIA R, HAO F, KODIALAM M, et al. Optimized network traffic engineering using segment routing[C]//IEEE International Conference on Computer Communications. 2015: 657-665.

[7] HARTERT R, SCHAUS P, VISSICCHIO S, et al. Solving segment routing problems with hybrid constraint programming techniques[C]//International Conference on Principles and Practice of Constraint Programming. 2015: 592-608.

[8] SCHüLLER T, ASCHENBRUCK N, CHIMANI M, et al. Traffic engineering using segment routing and considering requirements of a carrier IP network[C]//IFIP Networking Conference and Workshops. 2017: 1-9.

[9] GIORGETTI A, CASTOLDI P, CUGINI F, et al. Path encoding in segment routing[C]//IEEE Global Communications Conference. 2015: 1-6.

[10] LI S, HU D, FANG W, et al. Source routing with protocol-oblivious forwarding (POF) to enable efficient e-health data transfers[C]//IEEE International Conference on Communications. 2016: 1-6.

[11] DONG X, GUO Z, ZHOU X, et al. AJSR: an efficient multiple jumps forwarding scheme in software-defined WAN[J]. IEEE Access, 2017, 5: 3139-3148.

[12] FILSFILS C, MICHIELSEN K, TALAULIKAR K. Segment routing, part I[M]. North Charleston: CreateSpace Independent Publishing Platform, 2017.

[13] 周桐慶, 蔡志平, 夏竟, 等. 基于軟件定義網(wǎng)絡(luò)的流量工程[J]. 軟件學(xué)報(bào), 2016, 27(2): 394-417.

ZHOU T Q, CAI Z P, XIA J, et al. Traffic engineering for software defined networks[J]. Journal of Software, 2016, 27(2): 394-417.

[14] CIANFRANI A, LISTANTI M, POLVERINI M. Incremental deployment of segment routing into an ISP network: a traffic engineering perspective[J]. IEEE/ACM Transactions on Networking, 2017, 25(5): 3146-3160.

[15] GUEDREZ R, DUGEON O, LAHOUD S, et al. Label encoding algorithm for MPLS segment routing[C]//IEEE International Symposium on Network Computing and Applications. 2016: 113-117.

[16] CIANFRANI A, LISTANTI M, POLVERINI M. Translating traffic engineering outcome into segment routing paths: the encoding problem[C]//IEEE Conference on Computer Communications Workshops. 2016: 245-250.

[17] LEE K, TOGUYENI A, NOCE A, et al. Comparison of multipath algorithms for load balancing in a MPLS network[C]//International Conference on Information Networking. 2005: 463-470.

[18] LEE K, TOGUYENI A, RAHMANI A. Hybrid multipath routing algorithms for load balancing in MPLS based IP network[C]//IEEE International Conference on Advanced Information Networking and Applications. 2006.

[19] SUCHARA M, XU D, DOVERSPIKE R, et al. Network architecture for joint failure recovery and traffic engineering[C]//ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems. 2011: 97-108.

[20] LECONTE M, DESTOUNIS M, PASCHOS G. Traffic engineering with precomputed pathbooks[C]//IEEE International Conference on Computer Communications. 2018.

[21] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow: enabling innovation in campus networks[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[22] HIGHAM D J, HIGHAM N J. MATLAB guide[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2016.

[23] BRANKE J, DEB K., MIETTINEN K, et al. Multiobjective optimization: interactive and evolutionary approaches[M]. Berlin: Springer Science & Business Media, 2008.

[24] ZHANG J, YU F R, WANG S, et al. Load balancing in data center networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 2324-2352.

[25] ZHANG M, YI C, LIU B, et al. GreenTE: power-aware traffic engineering[C]//The 18th IEEE International Conference on Network Protocols. 2010: 21-30.

[26] GUROBI OPTIMIZATION, LLC. Gurobi optimizer reference manual [M]. Beaverton: Gurobi Optimization, 2018.

[27] ORLOWSKI S, WESS?LY R, PIóRO M, et al. SNDlib 1.0 - survivable network design library[J]. Networks, 2010, 55(3): 276-286.

Traffic scheduling method based on segment routing in software-defined networking

DONG Qian1,2,3, LI Jun1, MA Yuxiang1,2, HAN Shujun1,2

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China 2. University of Chinese Academy of Sciences, Beijing 100049, China 3. Department of Electronic and Information Engineering, Foshan University, Foshan 528000, China

In order to address the multi-commodity flow problem for traffic scheduling in software-defined networking, a method based on segment routing was proposed. The proposed method pre-computed sets of candidate paths and attributes of these paths for all source-target nodes, and set the requirements of attributes of candidate paths that should be met combined with various demands and constraints of flows, then generated sets of candidate paths for flows. In the proposed scheme, multi-commodity flow model in software-defined networking was simplified based on sets of candidate paths for flows, the difficulty of solving was reduced, the centralized control by the controller and the autonomous control by nodes were supported, the scalability of controller was improved. In addition, how to meet the energy-saving needs of the network was proposed, i.e., reducing the number of links that could participate in flow forwarding. The performance evaluation results indicate that the proposed method can meet various demands and constraints of flows, improve network performance, and reduce the computational load of solving the problem of traffic scheduling.

segment routing, software-defined networking, traffic scheduling, linear programming

TP393

A

10.11959/j.issn.1000-436x.2018245

董謙（1986?），男，湖北咸寧人，中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心博士生，佛山科學(xué)技術(shù)學(xué)院講師，主要研究方向?yàn)槲磥砘ヂ?lián)網(wǎng)、軟件定義網(wǎng)絡(luò)、流量工程等。

李俊（1968?），男，安徽桐城人，博士，中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心研究員、總工程師、博士生導(dǎo)師，主要研究方向?yàn)槲磥砘ヂ?lián)網(wǎng)、網(wǎng)絡(luò)安全等。

馬宇翔（1991?），男，河南開封人，中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)安全等。

韓淑君（1986?），女，山東高唐人，中國科學(xué)院計(jì)算機(jī)網(wǎng)絡(luò)信息中心博士生，主要研究方向?yàn)榫W(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)功能虛擬化等。

2018?05?31；

2018?10?10

李俊，lijun@cnic.cn

國家重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目（No.2017YFB1401500）；中國科技云建設(shè)工程資助項(xiàng)目（No.Y72923）；國家自然科學(xué)基金資助項(xiàng)目（No.61672490）

The National Key R&D Program of China (No.2017YFB1401500), The China Science and Technology Cloud Project (No.Y72923), The National Natural Science Foundation of China (No.61672490)