基于SDN的流分類多指標(biāo)負(fù)載均衡策略研究

張正之

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

隨著數(shù)據(jù)中心網(wǎng)絡(luò)（Data Center Networks，DCN）規(guī)模的不斷擴(kuò)大，數(shù)據(jù)中心內(nèi)部之間東西向的流量不斷增多，可能會(huì)造成部分鏈路的擁塞，而其余鏈路利用率則低；時(shí)延長和高丟包率等問題。而軟件定義網(wǎng)絡(luò)（SDN）采用數(shù)控分離的網(wǎng)絡(luò)架構(gòu)，擁有靈活的可編程性和全局信息控制的特點(diǎn)，可以實(shí)現(xiàn)流的路徑調(diào)度和控制?？刂破魇褂肙penFlow[1]南向協(xié)議下發(fā)流表項(xiàng)到支持OpenFlow的交換機(jī)來控制路由轉(zhuǎn)發(fā)，使得底層轉(zhuǎn)發(fā)設(shè)備可以被統(tǒng)一的控制和管理。

目前針對數(shù)據(jù)層面的流量調(diào)度工作可以分為路徑和服務(wù)流量的負(fù)載均衡兩大類，進(jìn)一步可將前者分為基于大象流（超過一定大小且持續(xù)時(shí)間長的流）識(shí)別的調(diào)度，面向QoS的調(diào)度以及其他算法[2]。有研究表明，數(shù)據(jù)中心網(wǎng)絡(luò)中90%的流小于100KB（老鼠流），而10%的流則具有大量的數(shù)據(jù)（100KB到1GB）或更長的生存周期（大象流），它們產(chǎn)生超過80%的數(shù)據(jù)量[3]。大象流對帶寬要求高，而老鼠流則更看重時(shí)延，因此如何選擇合理的路徑對大象流和老鼠流調(diào)度，避免網(wǎng)絡(luò)擁塞，是十分有必要的。

當(dāng)前在DCN中應(yīng)用較為多的是等價(jià)多路徑ECMP[4]算法，其通過哈希散列的方式，基于流的數(shù)量平均分配流量，在一定程度上提高了負(fù)載均衡度，適合老鼠流的調(diào)度，但其有可能將多條大象流映射到同一路徑上，從而加劇網(wǎng)絡(luò)擁塞?？紤]到數(shù)據(jù)中心流量大小分布不均及傳統(tǒng)的ECMP機(jī)制的弊端。本文針對Fat-Tree拓?fù)浣Y(jié)構(gòu)，提出一種基于流分類多指標(biāo)負(fù)載均衡（LB-FC?MI）方案。利用SDN對網(wǎng)絡(luò)全局掌握和對流進(jìn)行分類處理的同時(shí)，對判斷出來的大象流和老鼠流按照各自的綜合評價(jià)方案分別進(jìn)行評分，選出最高得分的路徑進(jìn)行轉(zhuǎn)發(fā)。最后通過實(shí)驗(yàn)驗(yàn)證方案的有效性。

1 近年來相關(guān)研究工作

自SDN誕生以來，基于SDN的數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡研究一直是學(xué)術(shù)界和工業(yè)界追捧的熱點(diǎn)，許多學(xué)者和專家從不同的方面采用不同的方法進(jìn)行了研究。在基于識(shí)別大象流調(diào)度的研究中，文獻(xiàn)[5]提出一種面向Fat-Tree拓?fù)涞膭?dòng)態(tài)流量負(fù)載均衡機(jī)制（LBFC），采用動(dòng)態(tài)調(diào)整流分類閾值來判定大小流，大象流采用動(dòng)態(tài)自適應(yīng)算法調(diào)度，老鼠流采用輪詢算法調(diào)度，適應(yīng)了不同的流對傳輸性能需求不同這一特點(diǎn)。文獻(xiàn)[6]提出一種基于流概率路徑選擇的方法，通過分離出傳輸流中占比較大的大象流，算出數(shù)據(jù)流量轉(zhuǎn)發(fā)時(shí)對每條路徑的利用率，根據(jù)利用率求得此路徑被選擇的概率，最后綜合參照概率大小和路徑長度來確定轉(zhuǎn)發(fā)路徑。而小流則采用ECMP算法計(jì)算路徑。文獻(xiàn)[7]提出一種分裂大象流的負(fù)載均衡方法，當(dāng)網(wǎng)絡(luò)負(fù)載超過設(shè)置的閾值時(shí)，控制器將采集到的大象流分裂成許多老鼠流，再根據(jù)實(shí)際的網(wǎng)絡(luò)情況算出負(fù)載最小的下一跳交換機(jī)來傳輸老鼠流，從而保證負(fù)載均衡。文獻(xiàn)[8]提出一種基于蟻群優(yōu)化的流調(diào)度系統(tǒng)（TSACO），該系統(tǒng)通過Open?Flow和sFlow發(fā)現(xiàn)大象流，然后通過基于蟻群的自適應(yīng)多路徑算法來調(diào)度大象流，而老鼠流則通過路徑數(shù)據(jù)表轉(zhuǎn)發(fā)。

在針對基于k條最短路徑評價(jià)方案的研究中，文獻(xiàn)[9]提出一種基于多路徑傳輸?shù)膭?dòng)態(tài)負(fù)載均衡路由（MTDLR）算法，該算法綜合了路徑層面的多個(gè)因素進(jìn)行分析，包括鏈路帶寬均衡度，路徑帶寬最優(yōu)度和路由跳數(shù)，能夠?qū)崿F(xiàn)為每一條數(shù)據(jù)流提供最佳路徑選擇。文獻(xiàn)[10]提出一種基于流調(diào)度選擇的動(dòng)態(tài)負(fù)載均衡（DLBFSS）算法，該算法首先計(jì)算滿足帶寬需求的多條等價(jià)最短路徑，然后選擇其中剩余吞吐量最大的路徑作為最佳調(diào)度路徑;最后以最佳調(diào)度路徑的負(fù)載和流量的帶寬來決定調(diào)度的擁塞概率，并把概率大小作為流調(diào)度的依據(jù)。文獻(xiàn)[11]提出一種基于多指標(biāo)的鏈路負(fù)載均衡（MI-LB）模型，該模型計(jì)算出起始節(jié)點(diǎn)到目的節(jié)點(diǎn)的k條可達(dá)路徑，再用多指標(biāo)的綜合評價(jià)算法對k條可達(dá)路徑進(jìn)行評分，最后選擇評分最高的路徑作為轉(zhuǎn)發(fā)路徑。

然而上述文獻(xiàn)中的研究要么沒有考慮到老鼠流的合理調(diào)度，要么路徑選擇的評價(jià)指標(biāo)過于單一，只是對指標(biāo)進(jìn)行簡單加權(quán)，可能會(huì)導(dǎo)致評價(jià)不合理。鑒于此本文首先計(jì)算出源目的節(jié)點(diǎn)對的k條最短路徑，對大象流和老鼠流路徑選擇采用不同的評價(jià)指標(biāo)進(jìn)行綜合評分，最后選擇最優(yōu)的轉(zhuǎn)發(fā)路徑。

2 總體架構(gòu)設(shè)計(jì)

SDN作為一種新提出的網(wǎng)絡(luò)架構(gòu)，與傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)相比，具有實(shí)現(xiàn)控制平面與數(shù)據(jù)平面分離的特性，能夠集中控制網(wǎng)絡(luò)狀態(tài)，實(shí)現(xiàn)底層網(wǎng)絡(luò)對上層應(yīng)用的透明化。針對數(shù)據(jù)中心網(wǎng)絡(luò)中對大小流調(diào)度不均衡，對路徑選擇的評價(jià)指標(biāo)過于單一的情況，本文提出基于流分類多指標(biāo)路徑綜合評價(jià)機(jī)制，該機(jī)制首先在交換機(jī)檢測識(shí)別大象流和老鼠流，并計(jì)算源目的節(jié)點(diǎn)的k條最短路徑，并分別對大小流用不同的評價(jià)指標(biāo)進(jìn)行評分選路，選出綜合評分最高的鏈路，最后進(jìn)行流表下發(fā)。LB-FCMI模型包含以下幾個(gè)模塊：網(wǎng)絡(luò)監(jiān)測模塊，多路徑計(jì)算模塊，大象流評價(jià)模塊和老鼠流評價(jià)模塊。框架如圖1所示。

圖1 基于Ryu控制器的負(fù)載均衡框架

2.1 大流的發(fā)現(xiàn)與標(biāo)記

本文對大小流進(jìn)行分別選路，因此需要有一種機(jī)制來檢測大小流。當(dāng)前業(yè)界沒有確切統(tǒng)一大象流閾值的大小。研究者們針對不同的網(wǎng)絡(luò)規(guī)模情況，有不同的閾值設(shè)定。一般是將占用1%到10%鏈路帶寬的流設(shè)定為大象流[12]?？刂破魍ㄟ^定期獲取每個(gè)交換機(jī)的每條流條目的統(tǒng)計(jì)信息來實(shí)現(xiàn)，本文設(shè)定平均傳輸速率不小于鏈路帶寬5%的流條目對應(yīng)的網(wǎng)絡(luò)流為大象流。

2.2 網(wǎng)絡(luò)檢測模塊

該模塊用于實(shí)時(shí)收集底層交換機(jī)的流量統(tǒng)計(jì)信息，利用這些信息計(jì)算網(wǎng)絡(luò)的負(fù)載狀態(tài)，并統(tǒng)計(jì)鏈路上的大小流。收集的接口狀態(tài)信息即是評價(jià)系統(tǒng)中的指標(biāo)，主要包括：鏈路帶寬利用率，傳輸時(shí)延，數(shù)據(jù)包丟失率，并把這些采集到的數(shù)據(jù)信息傳輸?shù)娇刂破鳌?/p>

將數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)洳捎脠D論方法表示為G=(V,E)；其中V={v1,v2,…,vn}是所有節(jié)點(diǎn)集合；E是網(wǎng)絡(luò)中所有鏈路的集合；eij∈E表示節(jié)點(diǎn)vi和vj之間有連接。

（1）鏈路帶寬利用率

傳輸鏈路上已承載的負(fù)載與鏈路總大小的比例。eij鏈路利用率，如式（1）所示：

其中bwij為鏈路負(fù)載，bc為鏈路帶寬總?cè)萘俊τ诿織l完整的路徑p=，選取鏈路eij利用率占比最大的max{buij}作為路徑帶寬利用率，也稱瓶頸鏈路利用率bur。這里需假設(shè)路徑中所有鏈路的帶寬總?cè)萘肯嗤?/p>

（2）時(shí)延

控制器利用發(fā)送的LLDP數(shù)據(jù)包到相應(yīng)的交換機(jī)開始的時(shí)間戳，然后交換機(jī)轉(zhuǎn)發(fā)該數(shù)據(jù)包到另一臺(tái)交換機(jī)，最后回到控制器的時(shí)間戳相減來計(jì)算鏈路時(shí)延。假設(shè)此過程的時(shí)延為T1，同理測得反向的時(shí)延為T2;控制器發(fā)送echo報(bào)文測得到交換機(jī)i，j的往返時(shí)延為Ti，Tj。則最后的鏈路eij前向后向的平均時(shí)延為dij=(T1+T2-Ti-Tj)/2。對于構(gòu)成路徑p的鏈路集合，有max{dij};稱為路徑p的瓶頸時(shí)延dr。

（3）丟包率

丟失數(shù)據(jù)包數(shù)量占所發(fā)送數(shù)據(jù)包的比率。對于一條完整的路徑p，其丟包率rlp計(jì)算公式為：

2.3 k路由算法

對于Fat-Tree的數(shù)據(jù)中心網(wǎng)絡(luò)來說，任意兩臺(tái)端主機(jī)之間的可選路徑非常多。從所有可到達(dá)的路徑中選出最佳的一條轉(zhuǎn)發(fā)路徑會(huì)造成計(jì)算資源的巨大浪費(fèi)。因此只需要考慮找到源目的節(jié)點(diǎn)對之間的多條最短路徑，在最短路徑之間進(jìn)行傳輸即可。在Fat-Tree結(jié)構(gòu)下，源目的節(jié)點(diǎn)在同一個(gè)pod層之間的等價(jià)路徑有k/2條，在不同pod層中的等價(jià)路徑有k2/4。k為pod的數(shù)量。

本文采用基于跳數(shù)的k條最短路徑（KSP）算法找出前k條最短的路徑集合P。該算法如下思想如下：首先使用Dijkstra算法計(jì)算出原始節(jié)點(diǎn)s到目的節(jié)點(diǎn)d的第一條最短的路徑p()1，并將其放到設(shè)置好的最短路徑集合A中，之后以第一條最短路徑上的節(jié)點(diǎn)為基礎(chǔ)，逐個(gè)計(jì)算其余的k-1條次最短路徑。在計(jì)算的時(shí)候，把上除開停止節(jié)點(diǎn)以外的全部節(jié)點(diǎn)分別當(dāng)作偏移節(jié)點(diǎn)vi，在逐個(gè)算出每個(gè)偏移節(jié)點(diǎn)vi到停止節(jié)點(diǎn)d的最短路徑，同前面的p(i)上原始節(jié)點(diǎn)到偏移節(jié)點(diǎn)的路徑相連接，組成備選路徑的集合B，從B中選擇最短的路徑作為p( i +1)加入到A中，重述上述步驟求得最終的k條最短路徑。此外在計(jì)算時(shí)應(yīng)注意以下兩點(diǎn)：

防止從起點(diǎn)到終點(diǎn)的整體路徑有環(huán)。即從vi到d的最短路徑不能包含s到vi的路徑上的任何節(jié)點(diǎn)。

避免與已經(jīng)在結(jié)果列表中的路徑重復(fù)。即從vi發(fā)出的邊應(yīng)該與結(jié)果列表中的路徑p1,p2,…,pk上從vi發(fā)出邊的方向保持不相同。

2.4 大象流和老鼠流評價(jià)模塊

大象流評分模塊選擇鏈路帶寬利用率和丟包率兩個(gè)參數(shù)作為評價(jià)的標(biāo)準(zhǔn)，而老鼠流評分模塊選擇鏈路利用率和時(shí)延兩個(gè)參數(shù)作為評價(jià)的標(biāo)準(zhǔn)。然而這些指標(biāo)中存在量綱上的不同，必須考慮各個(gè)指標(biāo)因單位和數(shù)量級(jí)的巨大差異而造成錯(cuò)誤的結(jié)果，為此要標(biāo)準(zhǔn)化各項(xiàng)評分指標(biāo)，從而更好地反映真實(shí)情況。本文采用極值法[13]對帶寬利用率、時(shí)延、丟包率進(jìn)行負(fù)指標(biāo)處理。公式如下：

基于這三個(gè)參數(shù)提出本文的流分類多指標(biāo)綜合路徑評分公式。由于大象流對帶寬要求更高，對時(shí)延要求不敏感，所以設(shè)置其綜合評價(jià)方案公式為：

ge為大象流路徑評價(jià)的得分，xbu，xrlp分別表示帶寬利用率和丟包率標(biāo)準(zhǔn)化后的權(quán)數(shù)值。瓶頸鏈路帶寬利用率越低，說明該路徑負(fù)載較輕，xbu值越大；丟包率越低，說明該路徑質(zhì)量越好，xrlp值越大；則ge的值越大，代表路徑性能越好，其中w1+w2=1。

而老鼠流則對時(shí)延敏感，對帶寬要求不高，所以設(shè)置其綜合評價(jià)方案公式為：

gm為老鼠流的路徑評價(jià)的得分，xdr，xrlp分別代表時(shí)延和丟包率標(biāo)準(zhǔn)化后的權(quán)數(shù)值。瓶頸時(shí)延越低，說明該路徑傳輸?shù)脑娇?，xdr值也越高；同理丟包率越低，說明該路徑質(zhì)量越好，xrlp值越高，則gm的值越大，代表路徑性能越好。其中w3+w4=1。

2.5 模型總體過程：

（1）確定數(shù)據(jù)流源地址與目的地址的信息并找到與其直連的交換機(jī)，然后區(qū)分大象流和老鼠流。

（2）調(diào)用多路徑計(jì)算模塊算出前k條最短可達(dá)的路徑；

（3）分別調(diào)用大象流和老鼠流的評價(jià)模塊對選出的k條可達(dá)路徑評分，然后大象流和老鼠流分別選擇對應(yīng)評分最大的最優(yōu)轉(zhuǎn)發(fā)路徑進(jìn)行轉(zhuǎn)發(fā)；

（4）最后派發(fā)流表給此路徑上的全部交換機(jī)，引導(dǎo)流量轉(zhuǎn)發(fā)。

3 仿真實(shí)驗(yàn)與分析

3.1 仿真實(shí)驗(yàn)架構(gòu)搭建

本實(shí)驗(yàn)在較為穩(wěn)定的Ubuntu16.04系統(tǒng)上搭建，并選擇在輕量級(jí)網(wǎng)絡(luò)仿真工具M(jìn)ininet[14]上進(jìn)行模擬，控制器使用開源的Ryu控制器，對于實(shí)驗(yàn)拓?fù)洳捎肒=4的胖樹DCN拓?fù)洌捎贔at-Tree架構(gòu)可以采用一般商業(yè)的交換機(jī)來構(gòu)建，因此網(wǎng)絡(luò)鏈路的帶寬能夠保持一致。其架構(gòu)在20臺(tái)交換機(jī)下面連接16臺(tái)終端機(jī)，其中核心交換機(jī)有4臺(tái)位于頂層，匯聚層8臺(tái)，邊緣層8臺(tái)，依次排列。構(gòu)如圖2所示。

通過Iperf流量工具產(chǎn)生模擬網(wǎng)絡(luò)流量，網(wǎng)絡(luò)鏈路帶寬均設(shè)為10Mbit/s；SDN控制器的網(wǎng)絡(luò)負(fù)載監(jiān)控周期為5秒，權(quán)重指標(biāo)W大象流和老鼠流的都分別設(shè)為0.6，0.4。采用的的數(shù)據(jù)中心流量模型為:

Staggered Prob（Subnet_P，Pod_P）模式：網(wǎng)絡(luò)中的主機(jī)以Subnet_P的概率向連接到同一邊緣層的交換機(jī)的主機(jī)發(fā)送數(shù)據(jù)，以Pod_P的概率向同一Pod內(nèi)其他主機(jī)發(fā)生數(shù)據(jù)，以1-Subnet_P-Pod_P的概率向不同Pod內(nèi)的其他主機(jī)發(fā)生數(shù)據(jù)。

本文算法將和ECMP、FlowFit[15]算法分別在傳輸時(shí)延、鏈路利用率兩個(gè)指標(biāo)間來衡量對比。驗(yàn)證負(fù)載均衡效果的評價(jià)指標(biāo)則選取平均帶寬利用率和平均時(shí)延來衡量。其中平均帶寬利用率是指取所有流的接收端收到的帶寬與發(fā)送端帶寬流量的比值之和再取的平均值。平均時(shí)延是指一條流從一端到另一端傳輸時(shí)延的平均值。

3.2 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)所提出的負(fù)載均衡策略性能的優(yōu)越性，在實(shí)驗(yàn)中將LB-FCMI依次與經(jīng)典的ECMP算法和比較新的FlowFit大象流調(diào)度算法做對比，用平均帶寬利用率和平均時(shí)延兩個(gè)指標(biāo)來對數(shù)據(jù)流進(jìn)行分析比較。其中ECMP是一種在所有的可用路徑上分配相同數(shù)量的流量的一種算法，當(dāng)數(shù)據(jù)流大小一致時(shí)負(fù)載均衡效果較好；FlowFit是一種針對大象流的負(fù)載均衡算法，主要方法是將出現(xiàn)擁塞路徑上的最大流調(diào)度到剩余負(fù)載輕的路徑上來，以此緩解網(wǎng)絡(luò)擁塞程度。

Staggered Prob模式下的仿真結(jié)果如圖3所示：以Staggered（0.5，0.3）模式每隔1秒向其他主機(jī)發(fā)送數(shù)據(jù)流，流量負(fù)載從0.1逐步增加至0.9。

圖2 4元Fat-Tree網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

由圖3可知，LB-FCMI的平均帶寬利用率要高于ECMP和FlowFit。剛開始時(shí)網(wǎng)絡(luò)負(fù)載較低，三種方式都有足夠的帶寬傳輸，平均帶寬利用率較高。隨著負(fù)載增加，三種方式的利用率開始下降，其中ECMP下降最快，這是因?yàn)镋CMP并未考慮鏈路帶寬情況，可能將數(shù)據(jù)流分配到負(fù)載較高的一條路徑上，造成網(wǎng)絡(luò)擁塞。FlowFit僅僅對路徑上最大的大象流進(jìn)行調(diào)度而忽略了其余大象流，因此可能導(dǎo)致鏈路擁塞。而LB-FC?MI采用綜合評級(jí)指標(biāo)來對大流進(jìn)行調(diào)度，選擇評分最高的最佳路徑來對大流進(jìn)行調(diào)度，減小了調(diào)度路徑擁塞的可能，提高了平均帶寬利用率。

圖3 平均帶寬利用率

圖4 描述了在Staggered Prob模式下三種方式的平均時(shí)延隨著流量負(fù)載變化的情況?？梢钥吹?，隨著負(fù)載從0.1逐步增加至0.9，其時(shí)延也不斷上升，其中ECMP上升的最快，LB-FCMI最慢。這是因?yàn)镋CMP沒有考慮鏈路狀態(tài)信息，只是使用簡單的哈希散列方式隨機(jī)分發(fā)流量，可能會(huì)把流分發(fā)到鏈路負(fù)載已很高的路徑上去，從而加重網(wǎng)絡(luò)擁塞層度，導(dǎo)致數(shù)據(jù)包的傳輸時(shí)間過長，平均時(shí)延較高。而FlowFit和LB-FCMI不僅僅注意路徑的負(fù)載，并可以隨著路徑情況的變化將流調(diào)度到其余負(fù)載層度較低的路徑上去，從而降低數(shù)據(jù)包的傳輸時(shí)間。FlowFit在調(diào)度時(shí)僅考慮對各條大象流進(jìn)行選擇，而LB-FCMI不僅考慮對大象流進(jìn)行調(diào)度，還對老鼠流進(jìn)行合理的調(diào)度分配，避免了部分小流因大流長時(shí)間占據(jù)帶寬而導(dǎo)致的時(shí)延增加，從而進(jìn)一步減小網(wǎng)絡(luò)擁塞，所以平均時(shí)延低于FlowFit。

圖4 平均時(shí)延

4 結(jié)語

本文根據(jù)SDN網(wǎng)絡(luò)架構(gòu)的特點(diǎn)提出了一種對大象流和老鼠流分類，并用多種指標(biāo)評估的負(fù)載均衡模型。該模型計(jì)算出源目的節(jié)點(diǎn)對之間的k條最短可用路徑后，基于多指標(biāo)對大小流分別進(jìn)行綜合評價(jià)，并分別轉(zhuǎn)發(fā)。與傳統(tǒng)的ECMP、FlowFit負(fù)載均衡方法相比性能更好，增加網(wǎng)絡(luò)資源的利用率，提高網(wǎng)絡(luò)的整體性能。