軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)多約束節(jié)能路由算法

何榮希 雷田穎 林子薇

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

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

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

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

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

為了避免上述流量感知節(jié)能路由方案對預(yù)判流量矩陣的依賴，文獻(xiàn)[18]針對傳統(tǒng)互聯(lián)網(wǎng)提出一種拓?fù)涓兄?topology-aware)節(jié)能路由算法.該算法不以流量作為考慮對象，而是基于“代數(shù)連通度”[19-20]概念，在保證網(wǎng)絡(luò)中所有節(jié)點全連通基礎(chǔ)上，通過計算每條鏈路對網(wǎng)絡(luò)代數(shù)連通度影響的大小，按照影響大小遞增順序休眠冗余鏈路實現(xiàn)節(jié)能.該算法在傳統(tǒng)互聯(lián)網(wǎng)中節(jié)能效果較為明顯，但是，對于采用fat-tree拓?fù)洹⒕哂小案贿B接”特點的SDCN，其節(jié)能效果有限(具體分析見2.2節(jié)).文獻(xiàn)[21]針對fat-tree拓?fù)涞奶攸c，提出獨立路徑集(能夠獨立滿足全網(wǎng)主機(jī)連線需求的路徑集合)概念，并以最小獨立路徑集為單位，休眠空閑設(shè)備以節(jié)能.該算法也屬于拓?fù)涓兄?jié)能路由算法，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，由于最小獨立路徑集仍包含大量核心層交換機(jī)，因此，網(wǎng)絡(luò)中激活設(shè)備的冗余度較高，從而影響了算法的節(jié)能效果(具體分析見2.2節(jié)).

與流量感知節(jié)能路由算法不同，拓?fù)涓兄?jié)能路由算法都是從保證網(wǎng)絡(luò)拓?fù)渚哂幸欢ǔ潭鹊倪B通性出發(fā)，通過休眠冗余設(shè)備以節(jié)能.由于該類算法保證了休眠冗余設(shè)備后的網(wǎng)絡(luò)仍具有一定連通性，因此，與流量感知機(jī)制相比可以較好地解決網(wǎng)絡(luò)中出現(xiàn)突發(fā)流量時冗余資源過少導(dǎo)致的丟包率增加問題.但是，這類算法在判定是否休眠設(shè)備時僅從保證網(wǎng)絡(luò)拓?fù)渚哂幸欢ǔ潭鹊倪B通度出發(fā)，并未考慮網(wǎng)絡(luò)負(fù)載的高低，因此，在低負(fù)載時其設(shè)備空閑率仍然過高，導(dǎo)致其節(jié)能效果有限.

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

本文的主要貢獻(xiàn)有3個方面：

1) 結(jié)合流量感知和拓?fù)涓兄?類節(jié)能路由算法的優(yōu)勢，在拓?fù)涓兄?jié)能路由機(jī)制中引入網(wǎng)絡(luò)流量因素，綜合分析SDCN的連通性、時延等因素對節(jié)能路由的影響，提出一種考慮時延和可靠性要求的多約束節(jié)能路由優(yōu)化模型.

2) 針對fat-tree拓?fù)銼DCN的結(jié)構(gòu)特點，提出等效節(jié)點、最小網(wǎng)絡(luò)連通子集、孤島交換機(jī)、無效鏈路等概念和輔助圖模型，給出SDCN連通條件.

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

1 多約束節(jié)能路由模型

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

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

Table 1 Explanations of Variables表1 變量含義

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

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

定義2.最小網(wǎng)絡(luò)連通子集.在G0中，如果只有一個核心層交換機(jī)，每一個PoD中只有一個匯聚層交換機(jī)，并均與該核心層交換機(jī)相連接，而且每一個匯聚層交換機(jī)又與該P(yáng)oD中所有邊緣層交換機(jī)相連接，則稱該網(wǎng)絡(luò)子集為最小網(wǎng)絡(luò)連通子集.由fat-tree拓?fù)涞奶攸c可知，它包含|C|個最小網(wǎng)絡(luò)連通子集，而且每個最小網(wǎng)絡(luò)連通子集的代數(shù)連通度相同.顯然，當(dāng)網(wǎng)絡(luò)子集至少包含一個最小連通子集時，網(wǎng)絡(luò)中所有服務(wù)器間均可正常通信.

多約束節(jié)能路由問題的輸入?yún)?shù)可表示為一個三元組(G0,dmax,θmin)，其目標(biāo)就是從G0中源、目的服務(wù)器所連接邊緣層交換機(jī)之間所有可行路徑中找到一個最佳網(wǎng)絡(luò)子集G*，在滿足時延和可靠性約束條件下，使交換機(jī)和鏈路的總能耗最小，即:

(1)

s.t.

dr≤dmax,?r∈G,

(2)

λ(G)≥θmin.

(3)

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

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

(4)

為了結(jié)合拓?fù)涓兄土髁扛兄?類節(jié)能路由機(jī)制的優(yōu)點，式(3)中θmin的取值除了要保證G中所有服務(wù)器間能正常通信外，還應(yīng)結(jié)合網(wǎng)絡(luò)的負(fù)載情況進(jìn)行調(diào)整.網(wǎng)絡(luò)負(fù)載越大，θmin取值相應(yīng)增大，從而保證網(wǎng)絡(luò)有較多冗余資源以接納更多突發(fā)流，有利于降低丟包率.

θmin反映G0休眠冗余設(shè)備后網(wǎng)絡(luò)拓?fù)銰*的連通情況(λ(G*)≥θmin)，其值應(yīng)位于G0及其最小網(wǎng)絡(luò)連通子集的代數(shù)連通度θ1和θ0之間，即θ0<θmin<θ1，可表示為

(5)

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

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

式(5)可實現(xiàn)將網(wǎng)絡(luò)流量因素引入拓?fù)涓兄?jié)能路由機(jī)制，從而可結(jié)合拓?fù)涓兄土髁扛兄酚伤惴ǜ髯缘膬?yōu)勢.在保證全網(wǎng)連通前提下，利用網(wǎng)絡(luò)流量信息來動態(tài)調(diào)整θmin.低負(fù)載時，θmin較小，可以彌補(bǔ)拓?fù)涓兄?jié)能算法低負(fù)載時設(shè)備空閑率過高、節(jié)能效果有限的不足.另一方面，網(wǎng)絡(luò)休眠設(shè)備的多少與流量矩陣有關(guān).而且α取值越大，θmin對流量矩陣的依賴程度越高.但是，不同于流量感知節(jié)能機(jī)制，它在休眠設(shè)備時首先要保證網(wǎng)絡(luò)連通性(至少保留一個最小網(wǎng)絡(luò)連通子集)，而不是僅根據(jù)預(yù)判流量矩陣盡可能多地休眠冗余設(shè)備，無疑可降低出現(xiàn)過度休眠現(xiàn)象，減少流量矩陣預(yù)判不準(zhǔn)所導(dǎo)致的丟包，有利于降低對流量預(yù)判準(zhǔn)確性的依賴程度.

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

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

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

2.1 輔助圖模型

定義3.等效節(jié)點.在基于fat-tree拓?fù)涞腟DCN中，每個低層交換機(jī)節(jié)點連接多個高層父節(jié)點，而這些父節(jié)點對于其子節(jié)點而言具有完全相同的轉(zhuǎn)發(fā)功能，因此將同一個低層交換機(jī)節(jié)點連接的高層父節(jié)點稱為等效節(jié)點.

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

步驟1. 獲取任意一個最小網(wǎng)絡(luò)連通子集，記為G01，如圖2所示.

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

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

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

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

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

2.2 SDCN連通條件

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

如圖1所示，將邊緣層、匯聚層和核心層交換機(jī)依次編號1～k22，k22+1～k2，k2+1～5k24.用a[i][j](1≤i,j≤5k24)表示網(wǎng)絡(luò)中第i個交換機(jī)與第j個交換機(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的核心層交換機(jī).式(8)保證滿足條件1的核心層交換機(jī)j與每一個bound中第m個匯聚層交換機(jī)相連接.

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

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

證畢.

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

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

2.3 MER算法描述與實現(xiàn)

2.3.1 MER算法架構(gòu)

MER算法的核心思想是基于SDCN輔助圖連通條件對網(wǎng)絡(luò)拓?fù)溥M(jìn)行“剪枝”，在保證數(shù)據(jù)流可靠性和時延要求條件下，按照一定的規(guī)則從初始網(wǎng)絡(luò)拓?fù)渲斜M可能多地刪除冗余交換機(jī)和鏈路，使其休眠，使用較少網(wǎng)絡(luò)資源進(jìn)行數(shù)據(jù)傳輸，以實現(xiàn)節(jié)能.

MER算法主要由拓?fù)浒l(fā)現(xiàn)模塊(topology discovery， TD)、節(jié)能路由模塊(energy-saving routing， ER)、連通性判斷模塊(connection judgement， CJ)以及流表下發(fā)模塊(flow distribution， FD)組成，整體架構(gòu)如圖6所示.

Fig. 6 Algorithm architecture of MER圖6 MER算法總體架構(gòu)

TD模塊是算法的基礎(chǔ)模塊，是整個算法得以實現(xiàn)的前提.首先對整個SDCN進(jìn)行感知，獲取核心層、匯聚層、邊緣層交換機(jī)的連接方式以及網(wǎng)絡(luò)中各鏈路和節(jié)點的基本信息，如時延信息、能耗信息等.然后將所獲取信息映射成一個網(wǎng)絡(luò)拓?fù)湟晥D，并生成一個對應(yīng)的網(wǎng)絡(luò)信息表供ES模塊等使用.網(wǎng)絡(luò)信息表由交換機(jī)間連接狀態(tài)、鏈路時延、交換機(jī)能耗和鏈路能耗4部分組成.其中，連接狀態(tài)有連通和斷開2種，分別用1和0表示.

ER模塊是實現(xiàn)網(wǎng)絡(luò)節(jié)能優(yōu)化和路由選擇的核心功能模塊，用于獲取最佳路徑并完成網(wǎng)絡(luò)“剪枝”操作，具體描述見2.3.2節(jié).

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

FD模塊是MER算法能夠在整個網(wǎng)絡(luò)得以實現(xiàn)的橋梁，核心功能是告知網(wǎng)絡(luò)中交換機(jī)如何對流量進(jìn)行傳輸.

2.3.2 節(jié)能路由模塊

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

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

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

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

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

ER模塊的主要步驟為

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

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

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

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

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

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

(9)

(11)

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

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

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

步驟8. 根據(jù)Gbest中的連接信息，對網(wǎng)絡(luò)G0進(jìn)行最終的節(jié)能休眠操作，即休眠僅包含在G0中而未包含在Gbest中的鏈路和交換機(jī).繼續(xù)步驟9.

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

現(xiàn)對ER模塊的復(fù)雜度進(jìn)行簡要分析.

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

3 仿真實驗與性能分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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