軟件定義數據中心網絡多約束節能路由算法

何榮希 雷田穎 林子薇

(大連海事大學信息科學技術學院 遼寧大連 116026)

作為分布式存儲和計算的橋梁，數據中心網絡(data center network, DCN)的性能直接影響云計算、大數據等業務的發展[1-2].DCN最初采用傳統樹型拓撲，存在可擴展性差、部署代價高以及嚴重的單點失效等問題.近年來，出現了諸如fat-tree等新型拓撲結構，通過使用數量巨大的網絡資源來提高網絡性能和可靠性[3-4].但是，這些拓撲仍屬于分布式網絡控制模式，依然存在管理困難、資源利用率低等問題.基于OpenFlow[5]的軟件定義網絡(software defined network, SDN)，將控制平面與數據平面解耦合，支持集中化的網絡控制，能實現底層網絡設施對上層應用的透明.與傳統網絡相比，它具有靈活、開放、簡單等特點，而且可以獲得全網視圖和網絡狀態信息[6].因此，SDN與DCN相結合的軟件定義數據中心網絡(software-defined data center network, SDCN)，可以實現網絡自動部署、流量優化、故障自動探測和恢復，并支持多租戶以及虛擬機遷移等，從而克服了分布式網絡控制模式下的諸多難題[7].

隨著能源短缺等問題日益嚴重，節能減排已成為社會發展面臨的重大課題[8-9].基于fat-tree拓撲的新型DCN使網絡中出現“富連接”鏈路，雖然避免了單點故障等問題的發生，但是引入過多網絡設備會增加網絡能耗，不利于實現綠色節能.另外，DCN往往按照峰值流量需求進行資源部署[10]，而多數情況下網絡流量都遠低于其峰值需求.因此，DCN中很多設備將處于空閑狀態，導致網絡資源整體利用率較低.如果讓這些空閑設備一直處于激活狀態，無疑會造成能源浪費.據統計，從全球范圍來看，預計2020年全球數據中心(data center， DC)消耗的電量將占總耗電量的8%[11].由于DC消耗了巨大的能量，因此，近年來DC的節能問題已逐漸成為研究熱點.由于網絡部分的能耗占DC總能耗的20%左右，并且隨著硬件技術的發展，比重會進一步提高[9].因此，很有必要研究DCN網絡級節能機制.

作為DCN中一種引起廣泛關注的網絡級節能機制，節能路由的關鍵是如何合理選擇路徑，在保障網絡性能的前提下使用盡可能少的網絡設備承載流量，從而休眠更多空閑設備以降低網絡能耗[12].近年來，不少文獻[13-17]都對SDCN的節能路由進行討論.文獻[13]提出基于流量的彈性樹(elastic tree)算法，依據實時流量監測信息，通過最優化算法、貪婪算法和啟發式算法求解最優路徑，并盡可能多休眠空閑設備實現節能.文獻[14]提出一種基于網絡流量矩陣的節能路由算法，可根據預判的流量矩陣在節點對間建立路徑，以休眠盡可能多的網絡設備.文獻[15-16]從負載均衡的角度出發，分別提出PRA算法和IEER算法.二者基本思想一致，都是通過預設一個固定的可靠性參數，并根據該參數休眠網絡冗余資源，可在節能的同時提供一定的可靠性保障.文獻[17]將流量工程(traffic engineering， TE)與SDN結合，依據網絡流量選擇最優拓撲子集，并休眠該子集外的網絡設備以節能.

總的說來，上述方案本質上均是基于流量預判的節能方案，需要預先知道網絡流量，并依據節點對間的流量來選路和休眠冗余資源，屬于流量感知(traffic-aware)節能路由.其優點在于網絡負載較低時可休眠更多冗余設備，節能效果明顯.但是，該類算法性能的好壞，很大程度上取決于流量矩陣預判的準確性.然而，對于實際網絡而言，由于數據流量動態、隨機產生，往往具有突發性，因此，預判流量矩陣并不一定與網絡實時流量狀態相符，流量感知節能路由機制可能會出現過度休眠(休眠設備過多)，從而導致未包含在流量矩陣中節點對間的數據流無可用資源建立路徑，從而造成丟包.另外，即使對于流量矩陣中存在的數據流，網絡出現故障時也可能出現無冗余資源傳輸而丟包，很難保證數據的可靠傳輸.

為了避免上述流量感知節能路由方案對預判流量矩陣的依賴，文獻[18]針對傳統互聯網提出一種拓撲感知(topology-aware)節能路由算法.該算法不以流量作為考慮對象，而是基于“代數連通度”[19-20]概念，在保證網絡中所有節點全連通基礎上，通過計算每條鏈路對網絡代數連通度影響的大小，按照影響大小遞增順序休眠冗余鏈路實現節能.該算法在傳統互聯網中節能效果較為明顯，但是，對于采用fat-tree拓撲、具有“富連接”特點的SDCN，其節能效果有限(具體分析見2.2節).文獻[21]針對fat-tree拓撲的特點，提出獨立路徑集(能夠獨立滿足全網主機連線需求的路徑集合)概念，并以最小獨立路徑集為單位，休眠空閑設備以節能.該算法也屬于拓撲感知節能路由算法，當網絡規模較大時，由于最小獨立路徑集仍包含大量核心層交換機，因此，網絡中激活設備的冗余度較高，從而影響了算法的節能效果(具體分析見2.2節).

與流量感知節能路由算法不同，拓撲感知節能路由算法都是從保證網絡拓撲具有一定程度的連通性出發，通過休眠冗余設備以節能.由于該類算法保證了休眠冗余設備后的網絡仍具有一定連通性，因此，與流量感知機制相比可以較好地解決網絡中出現突發流量時冗余資源過少導致的丟包率增加問題.但是，這類算法在判定是否休眠設備時僅從保證網絡拓撲具有一定程度的連通度出發，并未考慮網絡負載的高低，因此，在低負載時其設備空閑率仍然過高，導致其節能效果有限.

通過分析流量感知和拓撲感知2類節能路由方案[13-18,21]的優缺點，本文結合二者各自的優勢，將網絡流量因素引入拓撲感知節能路由機制，針對SDCN提出一種考慮時延和可靠性要求的多約束節能路由(multi-constrained energy-saving routing, MER)算法.該算法利用SDN控制器掌控全網信息的優勢，綜合考慮數據流的可靠性和時延性能要求，利用輔助圖和SDCN連通條件，選擇源、目的節點間綜合代價最小的路徑來傳輸數據流，通過合理休眠網絡資源以實現節能.仿真結果表明：與已有算法相比，MER算法在節能的同時，具有更低的平均分組時延和丟包率.

本文的主要貢獻有3個方面：

1) 結合流量感知和拓撲感知2類節能路由算法的優勢，在拓撲感知節能路由機制中引入網絡流量因素，綜合分析SDCN的連通性、時延等因素對節能路由的影響，提出一種考慮時延和可靠性要求的多約束節能路由優化模型.

2) 針對fat-tree拓撲SDCN的結構特點，提出等效節點、最小網絡連通子集、孤島交換機、無效鏈路等概念和輔助圖模型，給出SDCN連通條件.

3) 基于輔助圖模型、SDCN連通條件，提出一種啟發式算法MER，并進行仿真評測.

1 多約束節能路由模型

Fig. 1 SDCN topology with k PoDs圖1 具有k個PoD的SDCN

為了更好地描述多約束節能路由模型，引入以下變量，如表1所示:

Table 1 Explanations of Variables表1 變量含義

本文基于Powerdown的設備能耗模型[22]，假設交換機和鏈路存在工作和休眠2種能耗狀態.與工作狀態相比，休眠狀態耗能很小.因此，節能路由就是盡可能選擇休眠更多冗余設備的路徑，也就是用盡可能少的網絡資源(交換機、鏈路等)來保證邊緣層交換機間正常通信，從而保證服務器間的正常通信.為了保證突發數據流的可靠傳輸，應避免在負載較低時休眠過多的網絡設備，即要保證網絡具有一定的冗余度，從而保證網絡的最低連通性，以滿足突發通信流的傳輸要求.

為了更好地對多約束節能模型描述，引入5個定義.

定義2.最小網絡連通子集.在G0中，如果只有一個核心層交換機，每一個PoD中只有一個匯聚層交換機，并均與該核心層交換機相連接，而且每一個匯聚層交換機又與該PoD中所有邊緣層交換機相連接，則稱該網絡子集為最小網絡連通子集.由fat-tree拓撲的特點可知，它包含|C|個最小網絡連通子集，而且每個最小網絡連通子集的代數連通度相同.顯然，當網絡子集至少包含一個最小連通子集時，網絡中所有服務器間均可正常通信.

多約束節能路由問題的輸入參數可表示為一個三元組(G0,dmax,θmin)，其目標就是從G0中源、目的服務器所連接邊緣層交換機之間所有可行路徑中找到一個最佳網絡子集G*，在滿足時延和可靠性約束條件下，使交換機和鏈路的總能耗最小，即:

(1)

s.t.

dr≤dmax,?r∈G,

(2)

λ(G)≥θmin.

(3)

式(2)要求G中任意一條可行路徑的總時延dr不超過時延閾值dmax，從而保證了數據流的時延要求.式(3)要求G的代數連通度λ(G)不小于連通度閾值θmin，從而保證了網絡的最低可靠性要求.

流量矩陣反映了網絡中所有源、目的節點對間的流量需求，可反映網絡負載情況[23-24].G0的流量矩陣Z可表示為一個主對角線元素為0的|H|×|H|矩陣，即:

(4)

為了結合拓撲感知和流量感知2類節能路由機制的優點，式(3)中θmin的取值除了要保證G中所有服務器間能正常通信外，還應結合網絡的負載情況進行調整.網絡負載越大，θmin取值相應增大，從而保證網絡有較多冗余資源以接納更多突發流，有利于降低丟包率.

θmin反映G0休眠冗余設備后網絡拓撲G*的連通情況(λ(G*)≥θmin)，其值應位于G0及其最小網絡連通子集的代數連通度θ1和θ0之間，即θ0<θmin<θ1，可表示為

(5)

其中，α(0<α<1)為常數因子，其取值大小可反映網絡可靠性要求的高低.當負載一定時，隨著α增加，θmin越大，網絡連通性越好，可靠性越高，相應地可休眠設備越少.但是，當α增加到一定程度后，θmin的值越來越接近θ1，此時能休眠設備越來越少.如果繼續增加α，盡管θmin還可進一步逼近θ1，但是可休眠設備數量變化也不太明顯.

另一方面，當α取定時，網絡負載越低，θmin越小(更靠近θ0)，可休眠設備越多，G*越接近一個最小網絡連通子集.盡管此時網絡冗余度較低，由于網絡負載較低，突發流所導致丟包現象不會太嚴重.與之對應，網絡負載越高，θmin取值越大，網絡冗余度越大，越有利于減少突發流丟包.相應地，網絡可靠性越高，能耗也會增加.可以通過減少α值來減少θmin，從而降低網絡冗余度，以休眠更多設備.可見，通過合理調整α值，可在網絡可靠性和節能效果之間進行取舍.

式(5)可實現將網絡流量因素引入拓撲感知節能路由機制，從而可結合拓撲感知和流量感知路由算法各自的優勢.在保證全網連通前提下，利用網絡流量信息來動態調整θmin.低負載時，θmin較小，可以彌補拓撲感知節能算法低負載時設備空閑率過高、節能效果有限的不足.另一方面，網絡休眠設備的多少與流量矩陣有關.而且α取值越大，θmin對流量矩陣的依賴程度越高.但是，不同于流量感知節能機制，它在休眠設備時首先要保證網絡連通性(至少保留一個最小網絡連通子集)，而不是僅根據預判流量矩陣盡可能多地休眠冗余設備，無疑可降低出現過度休眠現象，減少流量矩陣預判不準所導致的丟包，有利于降低對流量預判準確性的依賴程度.

一旦初始網絡G0給定，則θ1和θ0都是定值.并且通過矩陣完成技術[25]等方法可估算出流量矩陣Z.而α為常數，因此，根據式(5)可求出θmin，也為一定值.

由于上述節能路由可以規約為背包問題，而背包問題屬于NP難問題[26]，所以SDCN的多約束節能路由問題也是一個NP難問題.當網絡規模較大時，很難在多項式時間內求解.因此，本文提出輔助圖模型和SDCN連通條件，在此基礎上提出一種啟發式算法——多約束節能路由(MER)算法.

2 多約束節能路由(MER)算法

2.1 輔助圖模型

定義3.等效節點.在基于fat-tree拓撲的SDCN中，每個低層交換機節點連接多個高層父節點，而這些父節點對于其子節點而言具有完全相同的轉發功能，因此將同一個低層交換機節點連接的高層父節點稱為等效節點.

對于圖1所示具有k個PoD的SDCN，生成輔助圖的步驟有3步.

步驟1. 獲取任意一個最小網絡連通子集，記為G01，如圖2所示.

步驟2. 根據網絡可靠性要求，為每一個PoD增加匯聚層交換機，并添加相應的核心層交換機，同時將添加的設備與G01中原有設備相連接，將此網絡記為G02，如圖3所示.

Fig. 2 Example of G01圖2 G01示意圖

Fig. 3 Example of G02圖3 G02示意圖

步驟3. 根據等效節點定義將G02中每一個PoD的匯聚層交換機和邊緣層交換機視為一個整體，記為boundi(1≤i≤k)；將boundi中邊緣層交換機連接的所有服務器視為一個整體，記為serveri(1≤i≤k)；將所有核心層交換機節點視為一個整體，記為core，得到SDCN輔助圖，如圖4所示.可見，具有k個PoD的SDCN輔助圖由1個core、k個bound和k個server構成.

Fig. 4 Auxiliary graph of SDCN with k PoDs圖4 具有k個PoD的SDCN輔助圖

2.2 SDCN連通條件

文獻[18]將“代數連通度”概念引入傳統互聯網，要求λ2>0以保證全網所有節點全連通.與傳統互聯網不同，基于fat-tree的SDCN具有“富連接”特點，存在很多為避免“單點失效問題”而配置的等效節點.然而對于任意一個節點而言，其等效節點為冗余節點.從圖4所示輔助圖可以看出：只要保證core與每一個bound連接，而且boundi(1≤i≤k)內部邊緣層交換機全連通，同時boundi和serveri(1≤i≤k)連通，則可以保證SDCN中服務器之間全連通，也就是可以保證正常數據傳輸.可見，SDCN中并不需要所有節點全連通，只需保證服務器之間連通.由第1節描述可知，SDCN中每一個bound與對應的server始終連通，因此，SDCN中保證服務器全連通僅需在輔助圖中保證core和bound以及每一個bound中節點間的連通.為了便于描述，將其稱為保證SDCN輔助圖全連通.

如圖1所示，將邊緣層、匯聚層和核心層交換機依次編號1～k22，k22+1～k2，k2+1～5k24.用a[i][j](1≤i,j≤5k24)表示網絡中第i個交換機與第j個交換機的連接情況.如果i和j相連(即連通)，其值為1，否則其值為0.

定理1.為了保證SDCN輔助圖全連通，必須同時滿足2個條件：

條件1.存在j∈{k2+1,k2+2,…,5k24}，使得:

(6)

成立.

條件2.對于任意的n∈{0,1,2,…,k-1}，使得：

(7)

成立.

其中：

(8)

其中，j必須是滿足條件1的核心層交換機.式(8)保證滿足條件1的核心層交換機j與每一個bound中第m個匯聚層交換機相連接.

證明. 根據核心層交換機與匯聚層交換機的連接特點和數據流的轉發特點可知，條件1要求至少存在一個核心層交換機與其所有連接的匯聚層交換機均處于工作狀態，即保證輔助圖中core與每一個bound連接.根據匯聚層交換機與邊緣層交換機的連接特點可知，條件2要求條件1中所有滿足要求的核心層交換機中，至少有一個核心層交換機連接的所有匯聚層交換機分別與本bound中所有邊緣層交換機連接，即保證boundi(1≤i≤k)內部邊緣層交換機全連通.

因此，當且僅當同時滿足條件1和條件2時，可保證SDCN輔助圖全連通，也就是保證了SDCN中邊緣層交換機連通.又由于邊緣層交換機與服務器總是連通，因此保證了SDCN中服務器連通，也就是保證了SDCN連通.

證畢.

由定理1可知，SDCN中只需保證邊緣層交換機之間全連通即可保證全網服務器正常通信.因此，與文獻[18,21]相比，可以休眠更多交換機節點和鏈路，進一步減少能耗.圖5給出了與文獻[18,21]的對比情況.圖5(a)為一個具有4個PoD的SDCN，應用文獻[18]節能算法時網絡的一種刪減情況如圖5(b)所示，為了保證所有節點連通，只能刪減(休眠)4條鏈路.應用文獻[21]節能算法時網絡的一種刪減情況如圖5(c)所示(圖5(c)給出僅含一個最小獨立路徑集時的網絡拓撲)，該算法比文獻[18]算法的節能效果更好，可以刪減(休眠)16條鏈路和6個交換機.但是從圖5(c)中可以發現，在保證網絡服務器全連通時，仍然存在冗余設備(1個核心層交換機和對應的4條鏈路).而依據定理1可知，在fat-tree拓撲的SDCN中，僅需保證輔助圖全連通，此時一種可行的刪減情況如圖5(d)所示，可以刪減(休眠)20條鏈路和7個交換機節點.可見，在fat-tree拓撲SDCN中本文提出的基于輔助圖全連通的節能方案優于文獻[18,21]的節能方案.

Fig. 5 Comparison between SDCN connectivity conditions and algorithms in Ref [18,21]圖5 SDCN連通條件與文獻[18,21]算法對比

2.3 MER算法描述與實現

2.3.1 MER算法架構

MER算法的核心思想是基于SDCN輔助圖連通條件對網絡拓撲進行“剪枝”，在保證數據流可靠性和時延要求條件下，按照一定的規則從初始網絡拓撲中盡可能多地刪除冗余交換機和鏈路，使其休眠，使用較少網絡資源進行數據傳輸，以實現節能.

MER算法主要由拓撲發現模塊(topology discovery， TD)、節能路由模塊(energy-saving routing， ER)、連通性判斷模塊(connection judgement， CJ)以及流表下發模塊(flow distribution， FD)組成，整體架構如圖6所示.

Fig. 6 Algorithm architecture of MER圖6 MER算法總體架構

TD模塊是算法的基礎模塊，是整個算法得以實現的前提.首先對整個SDCN進行感知，獲取核心層、匯聚層、邊緣層交換機的連接方式以及網絡中各鏈路和節點的基本信息，如時延信息、能耗信息等.然后將所獲取信息映射成一個網絡拓撲視圖，并生成一個對應的網絡信息表供ES模塊等使用.網絡信息表由交換機間連接狀態、鏈路時延、交換機能耗和鏈路能耗4部分組成.其中，連接狀態有連通和斷開2種，分別用1和0表示.

ER模塊是實現網絡節能優化和路由選擇的核心功能模塊，用于獲取最佳路徑并完成網絡“剪枝”操作，具體描述見2.3.2節.

CJ模塊對“剪枝”操作后的網絡連通性進行判斷，即利用SDCN輔助圖連通條件判斷所有服務器是否能夠正常通信.當滿足SDCN連通的必要條件時，說明“剪枝”后的網絡可以抽象成一個輔助圖，則本模塊返回True，否則返回False.

FD模塊是MER算法能夠在整個網絡得以實現的橋梁，核心功能是告知網絡中交換機如何對流量進行傳輸.

2.3.2 節能路由模塊

為了更好地描述節能路由(ER)模塊，先引入以下定義.

定義4.孤島交換機.基于fat-tree拓撲的SDCN，如果度矩陣DG0的元素dii=0(1≤i≤|N|)，則稱第i個交換機為孤島交換機.可見，孤島交換機與其他交換機不相連.

定義5.無效鏈路.不能用于構成任何服務器對間可行路徑的鏈路為無效鏈路.具體而言，對于匯聚層和核心層交換機之間的鏈路，如果刪除該鏈路后，對應的核心層交換機成為“孤島交換機”，則此鏈路為無效鏈路；對于匯聚層和邊緣層交換機之間的鏈路，如果刪除該條鏈路后，對應的匯聚層交換機成為“孤島交換機”，則此鏈路為無效鏈路.一般而言，如果鄰接矩陣FG0中的某一個元素aij=0時，有DG0中的元素djj=0，其中k22≤i≤k2-1且k2≤j≤(5k24)-1或者0≤i≤(k22)-1且k22≤j≤k2-1，則連接第i個交換機和第j個交換機的鏈路稱為無效鏈路.

圖7給出無效鏈路和孤島交換機的示例.圖7中鏈路(s2,s4)不能用于構成任何服務器對間的可行路徑，因此為無效鏈路.刪除該無效鏈路后，交換機s2，s6未與任何其他交換機連接，因此為孤島交換機.

Fig. 7 Examples of invalid link and isolated switch圖7 無效鏈路和孤島交換機示例

ER模塊的主要步驟為

步驟1. 初始化集合Pbest和Ps為空.以每一個核心層交換機為根節點，獲取最小網絡連通子集，將對應網絡子集放入集合G+，即G+={Gj}(1≤j≤|C|).繼續步驟2.

步驟2. 計算Gj(1≤j≤|C|)中各個鏈路和交換機的總能耗Ej，求出所有網絡子集的總能耗最小值Emin=min{Ej,1≤j≤|C|}.將能耗等于Emin的網絡子集放入集合Gb，即Gb={Gb1,Gb2,…,Gbm}，Ebm=Emin，1≤m≤|C|.計算Gb中各個子集的鏈路總時延，獲取鏈路總時延最小的子集(如果存在多個總時延最小子集，則隨機選取1個)，記為Gbest.繼續步驟3.

步驟3. 計算Gbest中任意2個邊緣層交換機間的可行路徑r(?r∈Gbest)的時延dr，判斷是否滿足dr≤dmax.如果滿足，繼續步驟4；否則，轉到步驟5.

步驟4. 計算Gbest的代數連通度λ(Gbest)并與θmin進行比較.當λ(Gbest)≥θmin時，將Gbest中每對邊緣層交換機間時延最小的路徑和對應的邊緣層交換機對以鍵值對形式放入集合Pbest中，轉到步驟8；否則，對Gbest進行可靠性處理.考慮到對節能效果的影響，結合fat-tree拓撲SDCN的連接特點，在保證匯聚層和邊緣層交換機和鏈路數不變的前提下，依次增加等效的核心層交換機以及相應的與匯聚層連接的鏈路，以保證可靠性.具體方式是：

首先查看Gbest中的核心層交換機，將與該交換機等效的所有核心層交換機放入集合Cs中，并依次標號；然后按照標號從小到大依次從Cs中取出一個交換機添加到網絡中，并將該交換機與相應的匯聚層交換機連接，更新Gbest.一旦增加設備后的代數連通度λ(Gbest)≥θmin，則將修補后滿足dr≤dmax的路徑與對應的邊緣層交換機對以鍵值對形式放入集合Ps，轉到步驟8.如果Cs為空后仍然不滿足λ(Gbest)≥θmin，繼續步驟5.

步驟5. 依據G0中鏈路的時延和能耗狀態調整鏈路li(1≤i≤|L|)的代價函數pi，即

(9)

(11)

根據pi值將各鏈路從大到小排序，放入集合Lsort中并依次標號，即Lsort={l1,l2,…,li,lj,lj+1,…}，pi≥pj，1≤i≤j≤|L|.記當前網絡為Gt，繼續步驟6.

步驟6. 從集合Lsort中依次取出一條鏈路并嘗試刪除，即進行“剪枝”操作.當鏈路li(1≤i≤|L|)為無效鏈路時，將其刪除，并更新Gt;否則，首先嘗試從Gt中刪除該鏈路，并調用CJ模塊.如果返回True，則檢查是否滿足λ(Gt)≥θmin.如果滿足，則更新Gt;如果不滿足λ(Gt)≥θmin或是CJ模塊返回False，則將li恢復.然后，從Lsort中選取下一條鏈路，繼續嘗試“剪枝”操作.值得注意的是：當鏈路li被刪除時，還需檢查與li相連的2個交換機是否成為孤島交換機，將相應的孤島交換機從Gt中刪除.當嘗試刪除Lsort中標號最大鏈路后，繼續步驟7.

步驟7. 獲取Gt中每對邊緣層交換機間滿足dr≤dmax的所有可行路徑，并將其中dr值最小的路徑與對應的邊緣層交換機對以鍵值對形式放入集合Pbest中，將其余滿足條件的所有路徑與對應的邊緣層交換機對以鍵值對形式放入集合Ps中.值得注意的是：如果某對服務期間所有可行路徑都不滿足dr≤dmax要求，為了保證任何服務器間的連通，則選擇dr值最小的路徑和對應的邊緣層交換機對以鍵值對形式放入集合Ps中.更新Gbest為Gt，繼續步驟8.

步驟8. 根據Gbest中的連接信息，對網絡G0進行最終的節能休眠操作，即休眠僅包含在G0中而未包含在Gbest中的鏈路和交換機.繼續步驟9.

步驟9. 當網絡中有新流需要控制器為其選路時，控制器首先根據新流的源和目的服務器確定對應的邊緣層交換機標號；然后，依次嘗試從Pbest,Ps中獲取最佳路徑rbest.如果獲取成功，則將rbest告知FD模塊，由FD模塊通知相應交換機轉發數據流.如果從Pbest或Ps中都獲取失敗，則FD模塊通知相應的交換機丟棄該流.

現對ER模塊的復雜度進行簡要分析.

對于k個PoD的SDCN，首先要獲取k24個最小連通子集，并對每一個子集進行能耗和時延約束判斷，時間復雜度為O(k24).在可靠性處理中，一個核心層交換機至多含有k2-1個等效節點，因此至多進行k2-1次，時間復雜度為O(k2).當網絡子集均不滿足時延約束或可靠性約束時，需要根據初始網絡中k32條鏈路的性能進行節能優化，并需檢查網絡中5k24個交換機是否為孤島交換機，時間復雜度為O(k32+5k24).因此，算法總的時間復雜度為O(k2)+O(k24)+O(k32+5k24)，近似為O(k32).

3 仿真實驗與性能分析

采用Mininet[27]仿真軟件搭建支持SDN的數據中心網絡，采用Floodlight[28]作為控制器，對所提出的MER算法進行仿真評測，并與IEER算法[16]、ESACON算法[18]和IPSM算法[21]進行對比(IEER屬于流量感知算法，后2個屬于拓撲感知算法).仿真拓撲采用k=4的fat-tree拓撲，包含16個主機、20個交換機和32條鏈路.仿真中設置：交換機能耗值為36W，每條鏈路能耗值為1W[15]，鏈路帶寬為1 Gbps，鏈路時延在1～10 ms之間隨機產生，dmax=20 ms，α分別取0.2，0.4，0.6，0.7，0.8.

SDCN中常見的通信模型有1對1通信和1對多通信.為了更加逼真地模擬實際情況，本文采用混合通信模型，即1對1和1對多通信模型共存.根據Benson等人的研究成果[29]，本文規定小于100 KB的流為小流，大于100 KB的流為大流.其中90%數據流為小流，10%的數據流為大流.每次測試時的流量大小根據大小流的比例，在對應的范圍內隨機產生.實驗中利用網絡負載百分比ε[15]來模擬網絡中的不同負載情形.網絡負載百分比表示從數據中心所有服務器中隨機選取ε%個服務器來發送或者接收數據流[15].仿真評測指標為能耗節省率(energy saving rate, ESR)[15]、平均分組時延(average packet delay， APD)和丟包率(packet loss rate， PLR).仿真結果是進行10次隨機實驗后的平均值，如圖8～10所示.

Fig. 8 Comparison of energy saving rate圖8 能耗節省率比較

Fig. 9 Comparison of average packet delay圖9 平均分組時延比較

Fig. 10 Comparison of packet loss rate圖10 丟包率比較

圖8對比了不同網絡負載百分比下4種算法的能耗節省率(ESR).從圖8可以看出：隨著網絡負載百分比增加，各算法的ESR均有不同程度的下降.另外，從節能效果上看，ESACON算法的ESR最低，節能效果最差；而IEER算法和MER算法的節能效果較好，優于其他2種算法.在網絡負載百分比低于60%時，MER算法的ESR不及IEER算法；但是，隨著網絡負載百分比進一步增加，其節能效果逐漸優于IEER算法.而IPSM算法的節能效果在網絡負載百分比低于80%時不及IEER算法；但隨著網絡負載百分比繼續增大，其ESR逐漸高于IEER算法.主要原因在于：隨著網絡負載百分比增大，網絡中需要激活更多設備來傳輸數據.同時由于網絡負載增加，網絡發生擁塞概率增加，導致數據傳輸時間增加.上述因素都會導致網絡能耗增加，因此算法的ESR會隨網絡負載增加而逐漸下降.另外，ESACON算法要保證網絡中所有節點全連通，對于具有“富連接”特點的SDCN而言，該算法使SDCN中等效節點也彼此連通，因而能夠休眠的設備較少，其能耗節省率最低.IPSM算法以最小獨立路徑集為單位進行網絡刪減，與ESACON算法相比，可休眠更多網絡設備，因此，其節能效果優于ESACON算法.IEER算法未考慮網絡突發數據流，僅依據流量矩陣建立節點對間的路徑并休眠網絡設備.因此，網絡負載較小時，需要建立的路徑較少，休眠設備較多，能耗節省率較高.但是，隨著數據流量增大，需要激活更多網絡設備，能耗節省率逐漸變低.因此當網絡負載百分比較高(>80%)時，其能耗節省率不及IPSM算法.而本文提出的MER算法基于輔助圖模型和SDCN連通條件，可以休眠網絡中更多冗余設備，因此，在中、高負載情況下其節能效果都明顯優于其他算法.

圖9對比了不同網絡負載百分比下4種算法的平均分組時延(APD)性能.從圖9可以看出：隨著網絡負載百分比的增加，各算法的APD均呈上升趨勢.其中MER算法的APD最低，ESACON算法最高，而IEER算法和IPSM算法位于二者之間，并且IEER的APD值略低于IPSM.主要原因在于：隨著網絡負載增加，網絡中會出現一定程度的擁堵，因此，各個算法的APD均會有所增加.由于ESACON，IPSM，IEER這3種算法著重關注如何節能，并未考慮鏈路時延對網絡性能的影響，所選路徑的時延性能不一定理想，所以其APD較高.與上述算法不同，MER算法在節能優化過程中充分考慮鏈路時延的影響，優先嘗試刪除時延較大的冗余鏈路，因此其節能優化后的網絡所包含高時延鏈路較少.另外，MER算法在選路時，選擇總時延最小且滿足時延約束的路徑，也有利于進一步降低APD，因此，其平均分組時延性能優于其他3種算法.

圖10對比了不同網絡負載百分比下4種算法的丟包率(PLR).從圖10可以看出：隨著網絡負載百分比的增加，各算法的PLR均有不同程度的增加.其中，MER算法最低，ESACON算法最高，IEER算法和IPSM算法介于二者之間，并且依次增加.主要原因在于：隨著網絡負載增加，網絡資源逐漸緊張，會出現擁堵現象，因此平均丟包率會有所增加.由于IPSM算法較ESACON算法的平均分組時延較小，數據等待現象較少，所以IPSM算法的丟包率較小，但與IEER算法相比其丟包率仍較高.這是因為IEER算法考慮了負載均衡問題，網絡擁堵現象較IPSM算法更少發生，因而丟包率更低.而本文提出的MER算法的丟包率較IEER算法更低，原因在于：MER算法在節能時將時延也作為考慮指標之一，所獲得網絡子集時延性能較好，所選路徑時延較低，能夠減少數據等待時間，有利于降低數據包超時被丟棄現象的發生.另外，MER算法結合網絡流量和代數連通度來休眠網絡設備，通過合理增加網絡冗余度以保證非流量矩陣中突發流的正常通信，可以保證網絡的可靠性要求，減少突發數據流和網絡故障導致的丟包現象發生，也有助于進一步降低丟包率.

從圖8～10還可以看出：隨著α值增大(α≤0.6)，MER算法的節能效果有所下降(仍優于IPSM和ESACON算法，在中、高負載時優于IEER算法)，其時延降低，網絡可靠性增高，丟包率降低(時延和丟包率仍明顯優于其他算法).但是，α取值變化引起MER算法的ESR，APD，PLR值改變不大.這是因為：θmin值隨著α值的增加而增大，導致MER算法能休眠設備越少，其能耗增加.由于θmin值越大，網絡連通性越高，網絡中可用資源越多，從而可降低網絡資源不足所導致突發流被丟棄的概率，也有助于減少網絡發生擁堵現象，相應地可以降低丟包率和平均分組時延.但是，當α增加到一定程度(α≥0.6)時，θmin值已經非常接近θ1，網絡中激活設備越來越多.再繼續增加α，所需激活設備數變化不大，因此，MER算法性能變化不明顯(圖8～10中α=0.6，0.7，0.8時MER性能曲線幾乎重疊在一起).

4 結束語

本文利用SDN集中控制的特點來解決DCN的節能路由問題，結合拓撲感知和流量感知2類節能路由各自的優勢(在拓撲感知節能路由機制中引入網絡流量因素)，首先給出多約束節能路由優化模型，然后通過引入等效節點、最小網絡連通子集等概念和輔助圖模型，給出SDCN連通條件；在此基礎上，綜合考慮節能以及時延和可靠性約束條件，提出一種適用于SDCN的多約束節能路由算法(MER)；最后通過Mininet和Floodlight進行仿真評測.仿真結果表明：MER算法可以達到理想的節能效果，同時可以獲得更低的平均分組時延和丟包率.MER算法僅選取影響傳輸性能的時延和可靠性2個因素進行考慮，在下一步研究中可考慮其他因素的影響，如分析交換機中流表處理能力等性能對能耗節省率的影響.