基于多層虛擬拓撲節能的SDN數據中心網絡流量調度算法

李宏慧 李煒東 付學良

(內蒙古農業大學計算機與信息工程學院 內蒙古 呼和浩特 010011)

0 引 言

隨著云計算、物聯網和大數據技術的快速發展，數據中心的規模變得越來越大，其能源消耗巨大并且不斷增長[1]，極大限制了其運營及發展。據統計，2015年我國數據中心能耗高達1 000億kW·h，超過我國社會用電量1.5%，相當于整個三峽大壩一年的發電量[2]。隨著近期5G通信等技術的快速增長，預計到2020年我國數據中心能耗占比將增長至8%[3]。

數據中心設備包括外圍設備和網絡設備。數據中心網絡的能耗占數據中心的總能耗達到了15%～20%[4]。隨著外圍設備，例如服務器、存儲設備、制冷設備等節能技術的快速發展及部署，網絡部分的能耗占比將會變得越來越多。為了保證數據中心的可靠性和可用性，交換機等網絡設備幾乎永不關機，不論數據中心網絡負載量大小，均以接近100%的功率持續運行。

為了提高數據中心網絡可靠性和網絡容量，人們提出了許多“富連接”的數據中心網絡架構，如，Fat-Tree[5]、Monsoon[6]、BCube[7]、Helios[8]等。其中Fat-Tree結構簡單，對分帶寬大，并且可提供服務器之間的多條等價路由，成為熱門候選。但是，相對于傳統數據中心，這種結構引入較多的交換機，進一步增加了網絡的能耗。

當今的數據中心網絡多采用等價多路徑(Equal-CostMultipath，ECMP)路由算法[9]對數據流進行調度。在Fat-Tree型數據中心網絡中，到達任意一個目的服務器結點存在多條等價路徑，ECMP算法利用靜態哈希函數從中選擇一條路徑來路由數據流。由此實現負載均衡。但是，ECMP未考慮網絡的能耗問題。

在Fat-Tree型數據中心網絡中，當網絡流量負載較低時，可以通過節能流量調度方法和休眠空閑的交換機設備降低網絡能耗，提高能源利用率[10-11]。這種方法的基本思想就是利用部分交換機設備及端口承載當前的數據流，同時休眠空閑的網絡交換機及端口，從而實現降低網絡的總能耗。為此，要求能夠對數據中心網絡進行全局監控和對資源的統一管理調度，并且需要交換機具有較強的計算能力，以及方便可行的狀態轉換(開啟/休眠)能力。但是，傳統的數據中心網絡中，交換機的路由轉發表都是采用分布式的方法，獨立地進行計算。

軟件定義網絡(Software Defined Networking,SDN)[12]作為一種新型的網絡架構，為實現數據中心網絡的節能流量調度提供了新的平臺。SDN實現了網絡交換設備控制平面和數據轉發平面的分離，形成了邏輯上統一的控制器，實現對網絡通信流量和網絡資源的集中調度和管理。在SDN數據中心網絡中，可以方便地實現交換設備及其端口的休眠或開啟[13]。

針對“富連接”數據中心網絡在低負載時能源利用率較低的問題，本文在Fat-Tree拓撲的SDN數據中心網絡中，提出了一種節能的多層虛擬子拓撲的流量調度算法(EMV-SDN)。實驗結果表明，在網絡能源消耗和延時方面，EMV-SDN算法均優于ECMP以及Dijkstra算法。

1 相關工作

SDN技術使得數據中心網絡的計算能力大大提高，能夠對網絡資源，例如交換機、端口等進行細粒度化管理，并且較易實現休眠或喚醒設備。由此，基于SDN的數據中心網絡節能問題成為了當下的一個研究熱點[14]。

Heller等[10]提出了彈性樹(ElasticTree)機制實現數據中心網絡節能，提供網絡的可擴展性。該機制根據網絡通信負載的大小，動態調整交換機和鏈路的活躍狀態。實驗結果表明，該方法在保證能承載激增的通信數據量的同時，可以節省高達50%的網絡能耗。但是，所提出的優化算法計算復雜度高，使得流量調度的實時性較差。另外，引入的接口計數器增加了額外的硬件開銷。

為了節省“富連接”(如Fat-Tree型)數據中心網絡的能源消耗，Shang等[11]從路由角度出發，提出了能量感知路由方法。核心思想是：在無損網絡性能的前提下，用盡可能少的網絡設備來提供路由服務，同時，休眠空閑的網絡設備，從而達到節能的目的。但是，該算法需要進一步完善以適應延遲敏感型的流量調度問題。

Tu等[15]提出了兩種不同的數據中心網絡節能算法，可應用在不同場景中，例如，延時敏感型的應用或延時不敏感的應用，并且與網絡拓撲無關，通過SDN集中化管理和流量預處理，可以達到較好的節能效果。但是，當網絡負載較重時，使用的貪心算法會產生一定的時延。另外，其未考慮鏈路和交換機的開啟時間對網絡時延的影響。

Li等[16]提出了一種新的能量感知流量調度方法EXR(EXclusive Routing)。它的核心思想就是按照時間先后順序調度數據流，使得每個數據流獨占路由途中的鏈路帶寬。由此數據中心網絡不會出現瓶頸鏈路，改善了活躍的交換機和鏈路的利用率，從而實現了數據中心網絡的節能。實驗結果表明，該方法在節能和平均完成時間上均優于公平共享路由方法。但是，EXR不能保證交換機的能效，因為它通過貪婪策略選擇可用鏈路的路徑，按優先級順序調度數據流。

文獻[17]提出了新的路由算法，解決數據中心網絡的負載均衡和能耗問題。其基本思想是，首先定量分析負載均衡，然后提出了將負載均衡與節能有效結合的節能路由算法，實現了在降低網絡能耗的同時保證網絡具有較高的可靠性。該算法在應對突發流量上存在提升的空間。

文獻[18]針對通用拓撲的數據中心網絡的節能問題，推導出了能效數學模型，提出了一種基于果蠅優化算法的節能路由機制求解數學模型。該機制模擬果蠅覓食過程，在尋路過程中，不斷調整方向和位置，確定路由的下一個節點，最終找到最優節能路徑。該機制既可以提高能效又能使得網絡性能優于已有的方法。但該算法的時間復雜度較高。

文獻[19]提出了一種新的節能調度和路由方法。該方法在時間維度上最小化數據中心流量的總能源消耗，提高了交換機的利用率，并且滿足了數據流的要求，例如截止時間等。實驗結果表明，該算法能有效降低通信流量的總能耗，并且縮短了數據流的平均完成時間。但是，該方法主要針對的是有特定時延限制的網絡數據流的調度問題。

針對彈性拓撲節能機制中利用貪心算法計算節能路徑時，解的質量無法保證的問題，文獻[1]提出了改進的混合遺傳算法求解優化路徑。基于SDN，該算法能夠規劃出優化的節能路由，避免了局部最優和收斂較慢的問題，進一步提高了數據中心網絡的能源利用率。

文獻[20]提出了Fat-Tree型數據中心網絡的節能路徑規劃系統ESPP，利用SDN控制器收集網絡狀態信息，計算節能路徑來調度數據流，從而實現降低能源消耗的目標。測試結果證明了算法的有效性。但是，ESPP的能耗模型需要進一步完善，需要更全面考慮能耗影響因子。

綜上所述，現有的節能流量調度算法尚在以下幾方面存在可以提升的空間。首先，算法應能隨著網絡流量的動態變化動態地路由流量，在節省能耗的同時滿足流量調度實時性的需求。同時，從網絡全局角度考慮節能流量路由問題，在節能的同時保證網絡的性能。

2 節能流量調度問題數學模型

數據中心網絡總能源消耗定義為網絡中所有活躍的(處于工作狀態的)交換機和鏈路的能源消耗。任意鏈路的能源消耗表示為COSTl，是該鏈路兩個端點(即交換機端口)的能耗，交換機節點v的能耗COSTv是指該交換機機架和線卡的能源消耗。

節能流量調度問題的優化數學模型如下:

(1)

s.t.

(2)

(3)

xl≤yvv∈V,l∈Lv

(4)

(5)

(6)

式(1)為優化目標函數，即數據中心網絡總能源消耗。式(2)為鏈路容量限制約束條件。它說明任意活躍鏈路l能承載的數據流總帶寬不能超過鏈路l的總容量。處于休眠狀態的鏈路不能承載任何數據流。式(3)為流守恒約束條件。對于任意數據流f，如果節點v是其源節點，則該節點只有流出數據流；如果v是數據流的目的節點，則該節點只有流入數據流；否則，任意中間節點v的流入數據流與流出數據流相同。式(4)說明，對于任意交換機節點v，如果v處于休眠狀態，則與之相連的鏈路狀態均為休眠狀態。式(5)的含義為如果與交換機節點v相連的鏈路均處于休眠狀態，則可將交換機v置于休眠狀態。式(6)說明了變量的取值范圍。

3 節能流量調度算法EMV-SDN

為了求解上述優化數學模型，針對文獻中存在的不足，本文提出了基于多層虛擬拓撲的SDN數據中心網絡節能流量調度算法EMV_SDN。首先將SDN控制器收集的數據中心網絡拓撲劃分為多層虛擬拓撲(即第一層、第二層、第三層等多層虛擬子拓撲)，開啟第一層虛擬拓撲,關閉其他高層虛擬拓撲。對于每一條到達的數據流，根據當前虛擬拓撲的最大鏈路利用率，決定是否需要開啟高一層虛擬拓撲，然后在已開啟的虛擬拓撲結構中，利用改進的貪婪算法計算路徑調度該數據流。最后依據一定的條件，關閉已開啟的高一層虛擬拓撲，以此實現節能的目標。

3.1 算法描述

節能流量調度算法EMV-SDN流程如圖1所示。輸入為SDN控制器收集的數據中心網絡拓撲以及新到達網絡的數據流。輸出為數據流的路由以及已開啟的一層或多層虛擬拓撲。SDN控制器根據數據流路由生成流表項下發交換機，調度數據流。

圖1 節能流量調度算法流程

EMV-SDN算法步驟如下：

步驟1初始化。

1) 在給定的數據中心網絡拓撲中，計算出任意兩服務器節點之間的K-最短路徑。

2) 將給定的網絡拓撲分成多層虛擬拓撲。

3) 開啟第一層虛擬拓撲,關閉其他高層拓撲。

對于新到達的數據流f，執行如下步驟。

步驟2利用SDN控制器的sflow軟件，收集當前開啟的虛擬拓撲鏈路利用情況，計算出最大鏈路利用率μ。

步驟3若μ>閾值1，預開啟高一層虛擬拓撲，即喚醒其中的交換機，但是其中的鏈路狀態保持不變。基于此，在節能的同時，可以盡快地響應并調度突發數據流，減少平均網絡時延。否則，轉步驟5。

步驟4若μ>閾值2，開啟并使用高一層虛擬拓撲,即喚醒已欲開啟的高一層虛擬拓撲中的鏈路，使其處于活躍狀態。否則，轉步驟5。

步驟6在選中的路徑上路由數據流。

步驟7調用sflow收集鏈路狀態，計算最大鏈路利用率μ。

步驟8若μ<閾值1并且持續時間>T,若已開啟過高一層拓撲，則在數據流傳遞結束后休眠高一層虛擬拓撲，即休眠其中的交換機和鏈路。由此實現數據中心網絡的節能。這樣做的目的也是為了避免頻繁開啟/休眠交換機及鏈路引起網絡震蕩。

步驟9如果流量調度未完成，轉步驟2；否則，算法結束。

綜上所述，EMV-SDN采用了高一層虛擬拓撲預開啟機制應對突發數據流，對數據流實時調度，減少平均網絡時延。利用改進的貪心算法選擇路由降低了算法的復雜度。采用的逐層開啟/休眠更高一層虛擬拓撲，可以在節能的同時簡化交換機的配置，節省配置時間。通過將數據流路由到最大鏈路利用率最小的路徑上，實現網絡的負載均衡。另外，為了防止網絡震蕩，當網絡負載較輕(μ<閾值1)并且持續了一定時間后，EMV-SDN算法才將高一層拓撲休眠。

3.2 多層虛擬拓撲生成算法

生成多層虛擬拓撲就是把實際物理拓撲劃分為第一層、第二層、第三層等多層虛擬拓撲。多層虛擬拓撲生成算法具體步驟如下：

步驟1SDN控制器利用地址解析協議ARP收集數據中心網絡拓撲信息。

步驟2利用Kruskal最小生成樹算法，根據核心交換機數量n生成n個以核心交換機為根結點的獨立最小生成樹MSTi(i=0,1,…,n)。將每個MSTi中的結點交換機和鏈路分別存入圖Gi(Vi,Li)(i=0,1,…,n)中。

步驟3將選作第一層虛擬拓撲VG1=G0(V0,L0)。

步驟4將VG1與G1(V1,L1)合并構成第二層虛擬拓撲VG2。構成方法定義為：

1)VG2的結點集合定義為V0∪V1-V0。

2)VG2的鏈路集合定義為L0∪L1-L0。

步驟5將第二層拓撲VG2與G2(V2,L2)合并構成第三層虛擬拓撲VG3。

步驟6以此類推，依次構成更高層拓撲。

對于數據中心網絡的Fat-Tree拓撲結構，每個MDTi均是唯一的，合并后構成的最高層拓撲即為原始物理拓撲。

對于如圖2所示的K=4的Fat-Tree拓撲結構，利用上述多層虛擬拓撲生成算法，可以得到如圖3所示的第一層、第二層、第三層和第四層虛擬拓撲。

圖2 K=4的Fat-Tree 拓撲結構

圖3 多層虛擬拓撲

采用上述方法依次構成更高一層虛擬拓撲的主要目的是簡化交換機和鏈路的開啟/關閉操作，節省了網絡配置時間，減少了網絡時延。因為在開啟高一層虛擬拓撲，例如VG2時，只需開啟休眠中的結點和鏈路，而不需要重復開啟VG1中的結點和鏈路，并且在關閉高一層拓撲,如VG2時，只需關閉其中包含的節點和鏈路。

4 實 驗

為了檢驗提出的多層虛擬拓撲節能流量算法EMV-SDN的性能，本文利用Floodlight控制器和Mininet[21]仿真平臺搭建Fat-tree型數據中心網絡拓撲。采用能源消耗比例和數據流的平均完成時間作為算法性能的衡量指標。能源消耗比例計算公式為：

(7)

式中：COSTe為在節能調度算法下的能源消耗;COSTo為沒有采用任何節能措施的能源消耗。由此可知，對于不同的節能調度算法，能源消耗比例越低，算法節能效果越好。

在多層虛擬拓撲下，將提出的EMV-SDN與ECMP和Dijkstra最短路徑算法進行比較。實驗結果表明，EMV-SDN在能源消耗比例和平均完成時間等方面優于其他兩種算法。

4.1 實驗設置

4.1.1網絡拓撲

選用如圖2所示的K=4的Fat-tree型網絡拓撲，在Mininet平臺上進行仿真實驗。其中所有交換機均為48個端口的OpenFlow交換機，各條鏈路帶寬均設置為100 Mbit/s。

4.1.2流量模式

選用工具軟件Iperf產生數據中心網絡中的數據流。每臺主機產生的流的長度、產生時間均不同，其中數據流的長度服從指數分布，流的產生時間服從泊松分布。分別采用隨機模式(Random)、交錯模式(Staggered)和間隔模式(Stride)來確定數據流的目的節點[5]。

(1) Random：主機i向主機j以相等概率p隨機發送數據。

(2) Staggered(pe,pp)：主機i以pe的概率向上層同屬邊緣交換機發送數據，以pp的概率向同屬于一個pod的主機發送數據，以1-(pe+pp)的概率向其他pod的主機發送數據。

(3) Stride(x):主機向主機(i+x)modn發送數據，n為數據中心網絡中主機的總數。

4.1.3交換機能耗

交換機的能耗包括機架、線卡、端口等組件的能耗。不同類型的交換機中各組件的能耗不盡相同。表1給出了不同類型交換機的組件能耗數據[1]。

表1 交換機組件能耗 W

4.2 能源消耗比例比較

在上述三種流量模式下，本文比較了算法EMV-SDN與ECMP和Dijkstra的能耗消耗比例。進行了多次實驗，每次實驗持續時間約為30分鐘，取中間10分鐘計算數據中心網絡能耗。圖4-圖6為三種流量模式下三種算法比較結果。其中：橫坐標為實驗持續時間；縱坐標為數據中心網絡能源消耗比例。

圖4 Random(0.25)模式下的能源消耗比例

圖5 Staggered(0,0.2)模式下的能源消耗比例

圖6 Stride(6)模式下的能源消耗比例

4.2.1Random流量模式

圖4展示了在Random通信模式下三種算法的能耗比較結果。可以看出，EMV-SDN算法比ECMP的能源消耗比例降低了1.50～7.81百分點，平均能源消耗比例降低了2.25百分點。EMV-SDN算法與Dijkstra算法相比，能源消耗比例降低了0.75～42.92百分點，平均能源消耗比例降低了6.52百分點。

4.2.2Staggered模式

在Staggered模式中，pe、pp分別取值為0和0.2。圖5給出在該種通信模式下三種算法的能耗比。可以看出，EMV-SDN算法與ECMP算法相比，能源消耗比例降低了1.44～24.61百分點；與Dijkstra算法相比能源消耗比例降低了1.25～42.91百分點。與ECMP和Dijkstra相比，EMV-SDN平均能源消耗比例分別降低了2.52百分點和6.65百分點。

4.2.3Stride模式

在Stride間隔通信模式中，x取值為6。圖6展示了在Stride模式下三種算法的能耗比，可以看出，EMV-SDN的能源消耗比例比ECMP降低了0.75到24.62百分點，比Dijkstra算法降低了0.63～42.89百分點。EMV-SDN算法的平均能源消耗比例比ECMP和Dijkstra算法分別降低了4.27百分點和10.77百分點。

從圖4-圖6可見，在三種通信模式下，所提出的EMV-SDN算法能源消耗比均低于ECMP和Dijkstra算法。這是由于EMV-SDN能夠根據當前鏈路利用率，動態調整高一層虛擬子拓撲的工作狀態，從而達到節能的目的。另外，EMV-SDN算法能夠在開啟的子拓撲中找到跳數最少并且最大鏈路利用率最小的路徑來路由數據流。而ECMP算法未考慮鏈路狀態，隨機將流調度到一條最短路徑上，未能根據拓撲變化進行路徑的調整。Dijkstra算法只計算出最短路徑，不能很好地結合鏈路的狀態和鏈路利用率，可能會使得最短路徑上的鏈路過于擁堵，導致過早開啟高一層虛擬子拓撲，造成能源消耗均高于其他兩種算法。

4.3 平均完成時間比較

圖7從時延方面比較了EMV-SDN、ECMP和Dijkstra三種算法。可以看出，在三種通信模式下，EMV-SDN算法的平均完成時間均最短。與ECMP和Dijkstra相比，采用EMV-SDN節能調度算法，在Random模式下，數據流平均完成時間分別降低了22%和40%；在Staggered模式下，平均完成時間分別降低了21%和39%；在Stride模式下，平均完成時間分別降低了14%和31%。

圖7 不同通信模式下算法的平均完成時間比較

就平均完成時間而言，EMV-SDN算法的性能也優于ECMP和Dijkstra。這主要是由于EMV-SDN算法能夠在拓撲結構發生變化時及時通過鏈路著色和鏈路利用率計算出路徑來對數據流進行調度，減少了鏈路的擁塞，從而使數據流較快地到達終點。而ECMP算法在對流的調度上沒有考慮鏈路利用率，隨機將流量分配到一條最短路徑中，可能導致鏈路擁堵，延緩了流到達時間。Dijkstra算法找一條最短路徑來路由數據流，同樣未考慮鏈路利用率，并且它不能很好地適應網絡虛擬拓撲的變化，從而使得Dijkstra算法調度的數據流平均完成時間最長。

5 結 語

針對“富連接”數據中心網絡在負載較低時能源利用率較低的問題，本文提出Fat-Tree型SDN數據中心網絡的節能流量調度機制。首先對節能流量調度問題建立整形線性規劃(ILP)優化數學模型，然后利用多層虛擬拓撲下的節能流量調度算法求解該數學模型，得到節能的數據流調度路徑。通過休眠空閑的網絡交換設備和端口，實現降低數據中心總能源消耗的目標。仿真實驗結果表明，提出的多層虛擬拓撲的節能流量調度機制EMV-SDN優于ECMP和Dijkstra最短路徑算法。在三種不同的通信模式下，不論能源消耗比例還是平均完成時間，EMV-SDN均比其他兩種算法表現優異。