軟件定義網絡中基于分段路由的流量調度方法

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

?

軟件定義網絡中基于分段路由的流量調度方法

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

（1. 中國科學院計算機網絡信息中心，北京 100190；2. 中國科學院大學，北京 100049； 3. 佛山科學技術學院電子信息工程學院，廣東 佛山 528000）

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

分段路由；軟件定義網絡；流量調度；線性規劃

1 引言

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

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

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

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

2) SR網絡中的硬件設備一般有最大SLD限制，能用于某條流轉發的候選路徑使用segment列表來表示，而且每個segment列表的SLD不應超過其硬件限制，因此候選路徑不是任意的，必須將最大SLD限制以適當形式加入相應的數學模型中[5]。考慮路徑的編碼問題，將其表示為segment列表[9]，使最終求出的解可行。

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

為此，本文分析了SDN中基于SR的流量調度模型，針對多個應用的流量需求并存的情況即 MCF問題，結合最大SLD限制等與應用無關的約束條件，提出一種有效的方法以便求解，同時使網絡設備也具備一定的對流轉發路徑進行管理和控制的能力；還簡要分析了如何盡量滿足網絡的節能需求。本文的主要貢獻如下。

1) 針對SDN流量調度的MCF問題，結合SR的特點，設計整體架構，對問題進行建模和分析；

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

3) 基于流的候選路徑集合，簡化SDN中的MCF模型，為控制器集中控制和各節點自主控制的工作方式設計相應處理流程；

4) 針對網絡的節能需求，討論如何減少可參與流轉發的鏈路數量。

2 SR簡介和相關工作

2.1 SR簡介

SR采用源路由范式，節點根據一個有序指令列表轉發數據分組，這些指令稱為segment。由于SR和MPLS之間的繼承關系，MPLS的轉發面本身并不用修改，segment以MPLS標簽的形式表現時，一個有序segment列表也就是一個標簽棧，棧內標簽數量即SLD，轉發時從棧頂標簽開始處理；如果SR應用于IPv6，segment可利用IPv6頭部中的路由擴展，通過指針來控制當前segment[12]。

segment標識符簡稱為SID，最常用的SID是節點（node）SID和鄰接（adjacency）SID，用于標識SR路由器和它們間的鄰接關系。源節點將segment列表封裝進數據分組的頭部，收到數據分組的路由器基于當前（active）segment處理，對segment的動作則有push、next、continue 3種。push，在分組頭部插入一組segment；next，處理當前segment完畢后轉到下一個segment，與之對應的是MPLS中的POP；continue，當前segment并未處理完畢因而保留，與之對應的是MPLS中的SWAP[12]。

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

總之，在源節點處對流配置一個segment列表，這條流的轉發路徑就確定了。通過SR能方便地對每條流進行細粒度管理，卻無需修改IGP參數，從而保證了網絡基礎配置的穩定性。

2.2 相關工作

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

表1 幾種基于SR的流量調度方法

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

表1說明，流量調度的主要目的是降低最大鏈路利用率，如要使用SR技術，一般應考慮SLD約束條件。SR支持ECMP，但流轉發是否支持多路徑應從實際情況出發，并在建模時體現。針對MCF問題，一般先收集相關信息然后求解，再由控制器或網絡管理員根據求得的結果將規則分別下發到相關的設備。

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

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

因此，對于SDN中相對復雜的流量調度模型，本方法結合SR的特點提出了一種預計算候選路徑集合的算法，不僅能滿足各類需求和約束條件，還記錄了候選路徑對應的segment列表并使其SLD最小；根據候選路徑集合計算流量分擔比例，能夠簡化MCF模型，降低求解難度；本方法也支持各節點自主控制，各節點預先從控制器獲取已經計算好的候選路徑集合，調度時只需根據流的需求和當前網絡狀態在候選路徑中選擇合適路徑。

3 問題分析

3.1 整體架構

在SDN中，控制器能通過南向接口協議獲取網絡信息，下發規則。在IP網絡中，基于IGP的擴展能收集當前鏈路狀態等必要信息。SDN中的流量調度如圖1所示。

圖1 SDN中的流量調度示意

圖1中實線表示節點間的鄰接關系即鏈路，假定有一條流從節點1先后經過節點5、節點4轉發到節點3，粗箭頭表示流的轉發路徑走向，虛線表示OpenFlow[21]等接口協議中控制器與節點間的packet-in和packet-out交互，控制器需要給這條流轉發路徑上的每個節點下發相應的轉發規則。

將源路由技術SR引入SDN后，流量調度如圖2所示。對于同樣的一條流，此時控制器只需與源節點1交互，對路徑進行編碼并下發相應的segment列表。與圖1中的SDN不同的是，SR網絡通過SR控制面傳播SID信息，控制器無需對中間節點下發轉發規則，節省了控制器建立流轉發路徑所需的時間，減輕了控制器的負擔；控制器可專注于根據MCF需求和約束條件進行流量調度優化計算，即使控制器失效，SR網絡也具備轉發能力，各節點能作為源節點自主控制某條流。

圖2 SDN中基于SR的流量調度示意

3.2 模型建立與分析

式(8)表示鏈路可參與流轉發的條件。如優化任務是最小化最大鏈路利用率，可表示為

min(9)

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

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

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

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

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

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

1) 通過4.1節中的路徑產生過程可獲得網絡拓撲中所有源—目的節點間的候選路徑集合和相應路徑的屬性。源節點和目的節點間的候選路徑集合再記為，所有()應大于等于1；所有節點對之間的及相應的屬性作為控制器進行后續處理和MCF計算的依據；對于每個網絡節點，可預先將以它為源節點的及相應的屬性下發給它，使網絡節點無需進行復雜計算便可篩選得出候選并對流轉發進行控制。

式(12)和式(13)為鏈路容量條件和鏈路可參與流轉發的條件，流量平衡條件體現在和式(10)及式(11)中，其他需求和約束條件體現在中，的取值范圍由式(5)確定，至此簡化了SDN中的MCF模型；式(9)是TE的經典優化任務[4]，還可添加其他優化目標，并對每個優化目標設定合適優先級和權重[23]。

4 方法描述

本文方法首先求出網絡拓撲中所有源—目的節點間的候選路徑集合，記錄相應路徑的屬性，然后以此為基礎，針對控制器和各節點自主控制分別設計相應處理流程進行流量調度。

4.1 路徑產生

在SR網絡中，sld為1表示segment列表中只有目的節點的SID，此時轉發路徑是從源節點到目的節點的最短路徑或存在ECMP負載均衡的多條等價最短路徑。網絡拓撲確定則鏈路的路由代價即權重已知，可由最短路徑算法得到所有節點對之間的最短路徑或多條等價最短路徑；最短路徑不存在環路，這是后續排除有環路路徑過程的前提。

將,間的最短路徑集合再記為-1，將sld=2,3,…,的候選路徑集合分別再記為-2、-3、…、，且-2、-3、…、在計算前應初始化為空集即行數為0的空矩陣，為所允許的最大sld，即sld≤。為便于表述，本文也將所允許的最大sld稱為sld最大值。先根據最短路徑算法求出網絡拓撲中所有節點對之間的-1，顯然任意一對,間的-1都只有一個，且這個的sl為目的節點的SID，sld=1；若,間只有一條最短路徑，則這個表示這條最短路徑；若有多條等價最短路徑，則這個表示存在ECMP負載均衡的多條等價最短路徑；記錄相應的屬性。

圖3 預計算p的過程示意

簡要給出計算所有節點對之間的-2的算法，如算法1所示。

算法1 計算所有節點對之間的-2

1) 輸入，所有節點對之間的-1，相應的屬性

2) for each∈do

3) for each∈ {} do

4) 初始化-2為空集即行數為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 流量調度

控制器預計算得出所有節點對之間的。流量調度目標為min時，控制器先收集流集合、當前鏈路信息，所有鏈路l通常為1，也可根據要求設定l。然后由對應的篩選得出，設定的精度要求，控制對應的臨時變量用于試探求解，所有流轉發支持多路徑時為LP模型，只支持單路徑時為ILP模型。簡要給出求解算法，如算法2所示。

算法2 優化任務為min時控制器求解

1) 輸入，所有節點對之間的，相應的屬性，當前鏈路信息，所有鏈路l，的精度要求

2) for each∈do

3) 根據對應的篩選得出

4) end for

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

6) if有解 then

7)←

8) else

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

10)←

11) end if

調整的方式也可使用其他更高效的方式。控制器根據當前條件及精度要求下求得的最小值對應的解配置流轉發，segment列表直接取自sl。

各節點自主控制進行流量調度時，先從控制器獲取其作為源節點的所有。當它自主控制某條流時，只考慮當前網絡狀況，收集鏈路信息，此時MCF問題變為這條流的路徑選擇問題，一般來說求解算法與算法2相似，只是變為{}，變為，若想使求得的解是唯一的，可添加其他優化目標。

4.3 節能控制

定義節能效果即不可休眠或關閉的物理連接數量為，將節能控制的優化任務設為使最小，即可參與流轉發的鏈路數量最少，有

min(16)

根據式(16)進行優化計算并通過流量調度實現時，一般是約束條件而非優化目標，應設定值，將其代入相關約束條件。此時除式(10)~式(13)外，還應滿足式(14)~式(15)。根據式(12)，l包含在中，求解前應先收集鏈路信息，根據收集的信息設定所有鏈路l的取值范圍：u>0時鏈路已使用，相應的l必為1；u=0時鏈路暫未使用，相應的l可取0或1。控制器進行流量調度時，需求解和所有鏈路l，所有流轉發支持多路徑時為MILP模型，只支持單路徑時為ILP模型。簡要給出求解算法，如算法3所示。

算法3 優化任務為min時控制器，求解和所有鏈路l

1) 輸入，所有節點對之間的，相應的屬性，當前鏈路信息，

2) for each∈do

3) 根據對應的篩選得出

4) end for

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

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

各節點自主控制進行流量調度時，先從控制器獲取其作為源節點的所有。當它自主控制某條流時，只考慮當前網絡狀況，收集鏈路信息，設定所有鏈路l的取值范圍，此時MCF問題變為這條流的路徑選擇問題，求解算法與算法3相似，只是變為{}，變為，優先選擇已用鏈路。

4.4 算法分析

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

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

5 性能評估

本文從公開數據集SNDLib[27]獲取網絡拓撲信息（包括節點、鏈路、鏈路的容量及路由代價）和流量數據，拓撲為GéANT和Germany50，分別有22個和50個節點，考慮分別有72條和176條鏈路。

5.1 實驗拓撲分析

首先基于GéANT的網絡拓撲信息進行分析，根據最短路徑算法，GéANT中所有節點對之間的最短路徑均無ECMP，故ecmp必然為0；分別設定sld≤2, 3, 4，根據4.1節中的原則1)~原則2)，分別計算得出所有462對源—目的節點間相應的；統計所有節點對中()小于等于個的源—目的節點對的數量，除以此拓撲中源—目的節點對的總數即462后得到比例()，()表示()在數量上的分布情況。結果如圖4所示。再基于Germany50的網絡拓撲信息進行分析，根據最短路徑算法，Germany50中部分節點對之間的最短路徑有ECMP，故ecmp為0或1；分別設定sld≤2, 3，再用SP表示所有流轉發只支持單路徑，MP表示所有流轉發支持多路徑，區別在于前者ecmp應為0而后者無此要求，根據4.1節中的原則1)~原則3)，分別計算得出所有2 450對源—目的節點間相應的。結果如圖5所示。

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

5.2 流量調度優化效果評估

5.2.1 GéANT拓撲流量調度優化效果

圖4 GéANT網絡拓撲分析結果

圖5 Germany50網絡拓撲分析結果

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

式(19)中，SDN使用多路徑指采用3.2節中約束條件為式(1)~式(7)的流量調度模型且所有流轉發支持多路徑，此時只考慮了基本約束且多路徑能更合理地均衡負載，因此每個在此條件下求得的是相應精度要求下的最優值，故越小越好且最小值為1。基于5.1節中計算得出的sld≤4的，對每條流篩選其對應的，分別得出sld最大值為2、3、4條件下的（因ecmp必然為0，故SP和MP這兩種情況下使用相同的）。以所有流沿最短路徑轉發的情況作為對比，表示為sld最大值為1。

圖6 GéANT流量調度優化效果?Θ

從圖6中可以總結如下規律。

1) 有控制器時，流量調度是全局優化，可以取得相對理想的效果，所有流轉發支持多路徑時為1，意味著求得的能達到最優值；所有流轉發只支持單路徑時為1.06~1.14，意味著求得的接近最優值；無控制器時，流量調度是局部優化，在候選路徑集合相同的情況下，有控制器時的全局優化比局部優化的效果更好；即使是局部優化，效果也比所有流沿最短路徑轉發時更好，支持多路徑時求得的相比所有流沿最短路徑轉發時的值降低42%以上，只支持單路徑時也可降低27%以上。

2) 有控制器時，sld最大值分別為2、3、4時的優化效果相同；無控制器時，sld最大值為2、3、4時的效果可能存在一定波動，不一定sld最大值越大效果越好，這也是局部優化導致的。

3) 無論有無控制器，一般來說所有流轉發支持多路徑時求得的比只支持單路徑時略小（也可能在有控制器時相同，如表2所示），這是因為單路徑的約束更嚴格，多路徑能更合理地均衡負載。

5.2.2 Germany50拓撲流量調度優化效果

為驗證本方法在不同規模拓撲下以及基于的屬性做合適篩選得出的優化效果，先從Germany50的TM數據集中取出3個，然后分別取每個TM中源—目的節點間流量需求大小在本TM最大前200的流量數據，作為用于評估的3個TM；設TM中的每對源—目的節點間有一條流，size為它們之間的流量需求大小；這3個分別用Germany50-1、Germany50-2、Germany50-3表示，各有200條流。

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

從表2中可以總結如下規律。

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

表2 Germany50流量調度優化效果?Θ

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

5.2.3 Germany50拓撲流量調度求解時間

考慮5.2.2節有控制器時的情況，與3.2節中約束條件為式(1)~式(7)即無sld、cost約束條件的SDN流量調度模型對比；均區分所有流轉發支持多路徑和只支持單路徑，即區分LP模型和ILP模型，統計其中的變量數量如圖7所示。

圖7表明，cost相對最短路徑的比值上限越大，變量數量越多；cost相對最短路徑的比值上限相同時，所有流轉發支持多路徑時的變量數量比只支持單路徑時的變量數量更多；對進行篩選后，變量數量相對于SDN流量調度模型更少。

再將設定為當前條件優化計算求得的，不添加其他優化目標，此時模型有解，以代入求解一次所需時間作為求解時間；硬件為i7-6700處理器和12 GB內存，軟件為Windows 10操作系統，在Matlab R2017a下用Gurobi[26]7.5.1求解并統計時間，用同一軟硬件環境下的求解時間衡量求解難度。結果如圖8所示。

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

圖7 5.2.2節有控制器時流量調度模型中的變量數量

5.3 節能控制優化效果評估

節能控制優化任務為min，優化效果用當前條件優化計算求得的評估且越小越好；仍使用GéANT-1、GéANT-2、GéANT-3并將設定為典型值0.5[25]，為減輕計算負擔由各節點對流進行自主控制；以所有流沿最短路徑轉發的情況作為對比，表示為sld=1。結果如表3所示。

圖8 5.2.2節有控制器時流量調度求解時間

表3 GéANT節能控制優化效果-SUM

從表3中可以總結出如下規律。

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

2) 當sld最大值相同時，所有流轉發支持多路徑與只支持單路徑求得的相同，這是因為當設定的較大也就是鏈路可用容量足夠大時，節能控制優化目標與流量負載分擔因素關聯不大。

5.4 評估結果討論

首先，對GéANT和Germany50拓撲的分析表明，根據4.1節中的原則1)~原則3)計算能使()的大小控制在相對有限的范圍。

然后，若將優化任務設為最小化最大鏈路利用率，基于GéANT和Germany50拓撲的評估結果表明，選擇合適的候選路徑集合后，本方法的優化效果良好，有控制器且所有流轉發支持多路徑時為1即求得的達到最優值，有控制器且所有流轉發只支持單路徑時為1~1.14即達到或接近最優值，無控制器即各節點自主控制時也有較好效果。

另外，基于Germany50拓撲的評估結果還表明，考慮有控制器時的情況，當cost相對最短路徑的比值小于1.75時不僅為1即求得的達到最優值，所有流轉發支持多路徑時求解時間也比約束條件更少的SDN流量調度模型少83%以上，只支持單路徑時求解時間比SDN流量調度模型少23%以上，說明當網絡拓撲規模較大時，基于的屬性做合適篩選得出，能在獲得較好優化效果的同時減少流量調度模型中的變量數量，減輕計算負擔。

最后，基于GéANT拓撲的評估結果表明，本方法能較好滿足節能控制需求，候選路徑越多則節能效果越有可能更好，設定為0.5時求得的可達到所有流沿最短路徑轉發時的60%左右。

6 結束語

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

[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] 周桐慶, 蔡志平, 夏竟, 等. 基于軟件定義網絡的流量工程[J]. 軟件學報, 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?），男，湖北咸寧人，中國科學院計算機網絡信息中心博士生，佛山科學技術學院講師，主要研究方向為未來互聯網、軟件定義網絡、流量工程等。

李俊（1968?），男，安徽桐城人，博士，中國科學院計算機網絡信息中心研究員、總工程師、博士生導師，主要研究方向為未來互聯網、網絡安全等。

馬宇翔（1991?），男，河南開封人，中國科學院計算機網絡信息中心博士生，主要研究方向為網絡體系結構、網絡安全等。

韓淑君（1986?），女，山東高唐人，中國科學院計算機網絡信息中心博士生，主要研究方向為網絡體系結構、網絡功能虛擬化等。

2018?05?31；

2018?10?10

李俊，lijun@cnic.cn

國家重點研發計劃基金資助項目（No.2017YFB1401500）；中國科技云建設工程資助項目（No.Y72923）；國家自然科學基金資助項目（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)