付瓊霄 孫恩昌 王倩雯 李 萌 張延華

(北京工業(yè)大學(xué)信息學(xué)部信息與通信工程學(xué)院 北京 100124)

0 引 言

隨著云計(jì)算、大數(shù)據(jù)等技術(shù)的興起，數(shù)據(jù)中心網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大[1]。具有多條并行路徑的Fat-tree[2]、VL2[3]、hypercube[4]等拓?fù)浣Y(jié)構(gòu)為數(shù)據(jù)中心網(wǎng)絡(luò)提供了高帶寬、高拓展性以及良好的容錯(cuò)能力，從而被廣泛應(yīng)用。但受限于傳統(tǒng)網(wǎng)絡(luò)管理部署困難等問(wèn)題，網(wǎng)絡(luò)性能無(wú)法得到保障[5]。軟件定義網(wǎng)絡(luò)(software defined network, SDN)的出現(xiàn)為解決以上問(wèn)題提供了新思路，并越來(lái)越多地被部署到數(shù)據(jù)中心網(wǎng)絡(luò)中。其借助集中控制的優(yōu)勢(shì)，實(shí)時(shí)獲取網(wǎng)絡(luò)全局視圖和網(wǎng)絡(luò)狀態(tài)，為網(wǎng)絡(luò)管理與流量控制提供了有利條件。OpenFlow作為一種標(biāo)準(zhǔn)南向接口協(xié)議被廣泛部署于SDN交換機(jī)中。然而，由于芯片的功耗和成本較高，大多數(shù)與OpenFlow協(xié)議兼容的交換機(jī)的流表容量有限。當(dāng)網(wǎng)絡(luò)中流量爆發(fā)時(shí)，容易引起流表溢出,網(wǎng)絡(luò)丟包率升高[6]。

為了在數(shù)據(jù)中心網(wǎng)絡(luò)中實(shí)現(xiàn)有效的流量管理，流量通常被分為兩大類：大象流(elephant-flows)和老鼠流(mice-flows)[7]。大象流攜帶數(shù)據(jù)量多，持續(xù)時(shí)間長(zhǎng)；老鼠流攜帶數(shù)據(jù)量少，持續(xù)時(shí)間短。特別地，在所有流中，大象流的占比不到10%，但卻承載了全網(wǎng)80%的帶寬[8]。由此可知，大象流容易引發(fā)鏈路負(fù)載不均衡，導(dǎo)致鏈路擁塞。而老鼠流容易引發(fā)流表負(fù)載不均衡，導(dǎo)致流表溢出。

目前，基于SDN的數(shù)據(jù)中心網(wǎng)絡(luò)負(fù)載均衡策略大多只考慮了鏈路負(fù)載均衡。L2RM[9]通過(guò)為網(wǎng)絡(luò)中到來(lái)的流量提供備份路徑來(lái)分擔(dān)主路徑流量，均衡網(wǎng)絡(luò)鏈路負(fù)載。LABERIO[10]通過(guò)設(shè)置負(fù)載均衡閾值來(lái)判斷網(wǎng)絡(luò)鏈路負(fù)載均衡情況，根據(jù)鏈路狀態(tài)計(jì)算網(wǎng)絡(luò)負(fù)載均衡度，當(dāng)負(fù)載均衡度超過(guò)閾值時(shí)，選擇負(fù)載最高鏈路上的最大流進(jìn)行調(diào)度。Sehery 等人[11]提出了 SRL 和 FlowFit 2個(gè)鏈路負(fù)載均衡算法，SRL 作為路由初始化算法，隨機(jī)選擇2條等價(jià)最短路徑，其中負(fù)載最小的路徑作為初始路徑；當(dāng)某條鏈路出現(xiàn)擁塞時(shí)，F(xiàn)lowFit 依次選擇該鏈路上對(duì)負(fù)載影響最大的流進(jìn)行調(diào)度，直到鏈路的負(fù)載小于擁塞閾值。以上策略只考慮到了網(wǎng)絡(luò)中的鏈路情況，忽略了SDN中流表容量有限的問(wèn)題，容易引發(fā)流表溢出。并且，后2種方案當(dāng)網(wǎng)絡(luò)鏈路負(fù)載不均衡時(shí)選擇最大流進(jìn)行調(diào)度，容易造成調(diào)度路徑負(fù)載過(guò)高甚至發(fā)生擁塞，不利于網(wǎng)絡(luò)的鏈路負(fù)載均衡。

對(duì)于上述算法中的流表溢出問(wèn)題，DIFF算法[12]提出了流表負(fù)載均衡的概念。路由初始化時(shí)執(zhí)行流表負(fù)載均衡策略以緩解流表溢出；在最大最小公平帶寬分配原則下，對(duì)大象流進(jìn)行重路由，以實(shí)現(xiàn)最大吞吐量。在這里，大象流大小被視為一致，并且流量也被假設(shè)為不可分割的。在大象流大小差異大、網(wǎng)絡(luò)負(fù)載較重的環(huán)境下，該方案難以達(dá)到好的負(fù)載均衡效果。

針對(duì)以上算法的缺點(diǎn)，本文提出一種高效的數(shù)據(jù)中心網(wǎng)絡(luò)流表與鏈路聯(lián)合均衡算法(joint load balancing algorithm for flow tables and links, JLBFTL)。結(jié)合數(shù)據(jù)中心網(wǎng)絡(luò)流量特點(diǎn)，將新到達(dá)網(wǎng)絡(luò)中的流量視為老鼠流進(jìn)行流表負(fù)載均衡，并把新流中監(jiān)測(cè)到的大象流調(diào)度到帶寬資源更多的路徑上。同時(shí)當(dāng)網(wǎng)絡(luò)鏈路負(fù)載不均衡時(shí)，選擇合適的大象流，利用備份路徑和組表實(shí)現(xiàn)快速有效的分流來(lái)使其恢復(fù)均衡。仿真結(jié)果表明本文算法能夠有效提升網(wǎng)絡(luò)性能。

1 基于SDN的數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)

本文選取Fat-tree拓?fù)渥鳛閿?shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?，由SDN控制器對(duì)網(wǎng)絡(luò)中交換機(jī)進(jìn)行集中控制，如圖1所示[13]。Fat-tree拓?fù)浞譃?層，自上而下分別為核心層、匯聚層和邊緣層。對(duì)于參數(shù)為k的Fat-tree拓?fù)?，其包含k個(gè)Pod，每個(gè)Pod中匯聚層和邊緣層交換機(jī)數(shù)均為k/2，核心交換機(jī)總數(shù)為(k/2)2，各邊緣交換機(jī)連接k/2個(gè)服務(wù)器。最重要的是，各源目的節(jié)點(diǎn)間擁有(k/2)2條等價(jià)路徑，為數(shù)據(jù)中心提供了高帶寬及良好的容錯(cuò)能力。基于此網(wǎng)絡(luò)架構(gòu)，本文提出一種高效的數(shù)據(jù)中心網(wǎng)絡(luò)流表與鏈路聯(lián)合均衡算法。利用SDN集中控制的優(yōu)勢(shì)，對(duì)網(wǎng)絡(luò)中的老鼠流和大象流進(jìn)行有效管理，實(shí)現(xiàn)網(wǎng)絡(luò)的流表負(fù)載均衡與鏈路負(fù)載均衡，從而緩解流表溢出和鏈路擁塞。

圖1 基于SDN的數(shù)據(jù)中心網(wǎng)絡(luò)架構(gòu)

2 流表與鏈路聯(lián)合均衡算法

2.1 算法架構(gòu)

本文提出的流表與鏈路聯(lián)合均衡算法架構(gòu)如圖2所示。主要包括備選路徑集計(jì)算模塊、路由初始化模塊、大象流監(jiān)測(cè)模塊、大象流調(diào)度模塊、分流模塊以及流表下發(fā)模塊。

圖2 流表與鏈路聯(lián)合均衡算法架構(gòu)

2.1.1 備選路徑集計(jì)算模塊

網(wǎng)絡(luò)初始化時(shí)，該模塊針對(duì)Fat-tree拓?fù)涮攸c(diǎn)，采用動(dòng)態(tài)負(fù)載均衡(dynamic load balancing，DLB)中的分層路由算法[14]，得到各接入層交換機(jī)間的k條路徑，并將所得路徑存儲(chǔ)到備選路徑集中，為后續(xù)的路由算法所使用。本文僅考慮網(wǎng)絡(luò)拓?fù)渥兓活l繁的情況，因此從預(yù)生成的備選路徑集中選擇路徑能夠顯著減少控制器路由計(jì)算的計(jì)算量。

2.1.2 路由初始化模塊

當(dāng)網(wǎng)絡(luò)中有新到來(lái)的流量，該模塊從備選路徑集中獲取該流源目的節(jié)點(diǎn)間所有路徑，并按照本文提出的路徑流表評(píng)價(jià)指標(biāo)對(duì)各條路徑上的流表進(jìn)行評(píng)分，選取評(píng)分最高的路徑作為路由路徑。

2.1.3 大象流監(jiān)測(cè)模塊

周期性監(jiān)測(cè)源交換機(jī)傳輸流的總字節(jié)數(shù)和統(tǒng)計(jì)周期來(lái)估計(jì)流大小。流帶寬大小可用式(1)[15]求出：

v=(bt+T-bt)/T

(1)

其中，bt為t時(shí)刻統(tǒng)計(jì)到的流傳輸字節(jié)數(shù)，bt+T為t+T時(shí)刻的流傳輸字節(jié)數(shù)。

設(shè)置一個(gè)流量閾值vth來(lái)區(qū)分大小流，當(dāng)v>vth時(shí)，流量被判定為大象流，否則為老鼠流。

2.1.4 大象流調(diào)度模塊

當(dāng)監(jiān)測(cè)到大象流，該模塊對(duì)該流源目的節(jié)點(diǎn)間各條路徑上的鏈路進(jìn)行評(píng)分，選取評(píng)分最高的2條路徑分別作為主路徑和備份路徑。其中，主路徑用于大象流重路由，備份路徑用于后期鏈路負(fù)載不均衡時(shí)為主路徑分擔(dān)部分流量。

2.1.5 分流模塊

周期性監(jiān)測(cè)網(wǎng)絡(luò)鏈路負(fù)載均衡情況，當(dāng)負(fù)載不均衡時(shí)，選取要進(jìn)行分流的大象流，并計(jì)算主、備份路徑上的流量分配比例，得到組表權(quán)重。

2.1.6 流表下發(fā)模塊

該模塊負(fù)責(zé)為路由路徑上交換機(jī)下發(fā)流表及組表以實(shí)現(xiàn)流量轉(zhuǎn)發(fā)。特別地，對(duì)于從大象流調(diào)度模塊得到的主備份路徑，為這2條路徑上的所有交換機(jī)下發(fā)流表，并為源交換機(jī)下發(fā)組表，將大象流路由到主路徑上。當(dāng)分流模塊被觸發(fā)，調(diào)整源交換機(jī)組表權(quán)重以實(shí)現(xiàn)流量在主備份路徑間的分配與傳輸。

2.2 算法描述

本文提出的流表與鏈路聯(lián)合均衡算法主要分為流表負(fù)載均衡算法與鏈路負(fù)載均衡算法。流表負(fù)載均衡算法的主要目標(biāo)是減少由網(wǎng)絡(luò)中大量老鼠流導(dǎo)致的交換機(jī)流表溢出。同時(shí)，為了緩解鏈路擁塞，鏈路負(fù)載均衡算法為網(wǎng)絡(luò)帶寬的主要承載者大象流選擇帶寬資源最優(yōu)的路徑作為路由路徑，并為其準(zhǔn)備備選路徑。在流量高峰期時(shí)，網(wǎng)絡(luò)中大量的突發(fā)流量可能導(dǎo)致部分鏈路負(fù)載過(guò)重，造成鏈路負(fù)載不均衡，此時(shí)可通過(guò)選擇合適的大象流，利用備份路徑和組表進(jìn)行有效分流實(shí)現(xiàn)鏈路快速均衡。

2.2.1 流表負(fù)載均衡算法

該算法運(yùn)行于路由初始化模塊中。由數(shù)據(jù)中心網(wǎng)絡(luò)流量特點(diǎn)可知：老鼠流帶寬需求小且持續(xù)時(shí)間短，對(duì)網(wǎng)絡(luò)鏈路負(fù)載影響不大，但其數(shù)量龐大,占全網(wǎng)流量的絕大多數(shù)，會(huì)導(dǎo)致大量的流表下發(fā)，從而引發(fā)交換機(jī)流表溢出，導(dǎo)致網(wǎng)絡(luò)丟包率升高。本文采用流表負(fù)載均衡策略解決以上問(wèn)題。由于老鼠流在網(wǎng)絡(luò)中的占比超過(guò)90%，并且考慮到工程應(yīng)用中的可行性，本研究將網(wǎng)絡(luò)中到來(lái)的新流視為老鼠流[15]，提出路徑流表評(píng)分作為評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)源目的節(jié)點(diǎn)間的各條路徑的流表質(zhì)量，選擇評(píng)分最高的路徑作為路由路徑，以實(shí)現(xiàn)流表均衡。

該指標(biāo)綜合考慮路徑流表平均質(zhì)量和路徑瓶頸流表質(zhì)量。由于本文中選擇Fat-tree拓?fù)渥鳛榫W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，一對(duì)源目的服務(wù)器間各條路徑上交換機(jī)數(shù)一致，即流表數(shù)一致，所以路徑流表平均質(zhì)量可以由路徑流表總質(zhì)量表示。特別地，對(duì)于一個(gè)單獨(dú)的流表而言，其剩余容量越大，負(fù)載越小，流表質(zhì)量越好。然而，路徑流表總質(zhì)量不能簡(jiǎn)單地用路徑流表剩余容量之和來(lái)評(píng)價(jià)，這樣會(huì)忽略各流表間負(fù)載的差異。當(dāng)各條路徑上的流表剩余容量和均相同，每條路徑的流表負(fù)載分布可能不同(例如，2條路徑上流表負(fù)載分布為[2,3,7,8]和[4,5,5,6])。但是這種不同不能從剩余容量之和中得到反映。此外，剩余容量之和高的路徑也不一定比剩余容量之和低的路徑更優(yōu)。這是因?yàn)槁窂缴狭鞅淼呢?fù)載可能存在兩極分化，路徑上可能會(huì)有多個(gè)高負(fù)載流表，這樣的路徑是應(yīng)該避開(kāi)的。根據(jù)以上分析，本文提出路徑流表負(fù)載總增量作為路徑流表總質(zhì)量的評(píng)價(jià)指標(biāo)。

具體地，本文提出的流表負(fù)載增量函數(shù)Ti(x)是一個(gè)非線性函數(shù)，用來(lái)增大流表間的差異，如式(2)和式(3)所示。其代表當(dāng)流量到達(dá)已存儲(chǔ)流條目數(shù)為x的交換機(jī)i時(shí)，給該交換機(jī)流表帶來(lái)的負(fù)擔(dān)。其中，f(x)為流表負(fù)載評(píng)價(jià)函數(shù)。特別地，提出流表?yè)砣撝?，將流表狀態(tài)分為2種：擁塞狀態(tài)和非擁塞狀態(tài)。在式(3)中，不同的函數(shù)被用來(lái)評(píng)價(jià)不同狀態(tài)的流表。一個(gè)增長(zhǎng)率更高的函數(shù)被用來(lái)評(píng)價(jià)擁塞狀態(tài)的流表。通過(guò)這種方式，當(dāng)流量到達(dá)一個(gè)部署了擁塞狀態(tài)流表的交換機(jī)時(shí)，會(huì)產(chǎn)生很大的負(fù)載增量。

Ti(x)=f(x+1)-f(x)

(2)

其中，

β>α>2 (3)

a、b、α、β取相應(yīng)值使f(x)滿足連續(xù)、單調(diào)增，且為凸函數(shù)。Cmax為交換機(jī)流表容量，kCmax為流表?yè)砣撝怠?/p>

考慮到路徑上的瓶頸流表，綜合路徑流表負(fù)載總增量和路徑最小流表剩余容量，提出路徑流表評(píng)分計(jì)算公式，如式(4)所示：

(4)

流量將從源目的交換機(jī)間的多條備選路徑中選擇路徑流表評(píng)分最大的路徑進(jìn)行傳輸。

流表負(fù)載均衡算法偽代碼如算法1所示。

算法1 Load Balancing for Flow Table 1 while newflow do2 foreach path in paths do3 foreach sw in path do4 iftable(sw)≤kCmaxthen5 load(sw)←f1(table(sw))6 else7 load(sw)←f2(table(sw))8 end if9 if table(sw)+1≤kCmaxthen10 load2(sw)←f1(table(sw)+1)11 else12 load2(sw)←f2(table(sw)+1)13 end if14 inc(sw)←load2(sw)-load(sw)15 inctable(path)←inctable(path)+inc(sw)16 end do17 minfreetable(path)←min{Cmax-table(sw)}18 scoretable(path)←minfreetable(path)inctable(path)19 end do20 path←argmax{scoretable(path)|path∈paths}21 end while

其中，table(sw)為交換機(jī)sw中流表所存儲(chǔ)的流條目數(shù)，load(sw)和load2(sw)分別為流到達(dá)交換機(jī)sw前后該交換機(jī)中流表負(fù)載的評(píng)價(jià)值，inc(sw)為流表負(fù)載增量，min_freetable(path)為路徑path上流表的最小剩余容量，scoretable(path)為路徑流表評(píng)分。

2.2.2 鏈路負(fù)載均衡算法

鏈路負(fù)載均衡算法由大象流調(diào)度算法和分流算法組成，它們分別運(yùn)行于大象流調(diào)度模塊和分流模塊中。

鏈路負(fù)載均衡的目標(biāo)是緩解網(wǎng)絡(luò)擁塞。由數(shù)據(jù)中心網(wǎng)絡(luò)流量特點(diǎn)可知，大象流是網(wǎng)絡(luò)鏈路帶寬的主要占用者，網(wǎng)絡(luò)鏈路負(fù)載均衡與其密切相關(guān)。但其數(shù)目只占流量總數(shù)的極小部分，對(duì)交換機(jī)流表負(fù)載影響不大。所以，鏈路負(fù)載均衡算法是針對(duì)大象流而言的。

(1)大象流調(diào)度算法

文獻(xiàn)[9]為網(wǎng)絡(luò)中所有流量提供主路徑與備份路徑。受該思想啟發(fā)，并考慮到老鼠流占比大，為其成倍地下發(fā)流表會(huì)導(dǎo)致流表負(fù)擔(dān)的急劇加重，且老鼠流數(shù)據(jù)量小、持續(xù)時(shí)間短，備份路徑并不是必要的，因此本文只為大象流計(jì)算主備份路徑。主路徑用于大象流的重路由，以實(shí)現(xiàn)鏈路負(fù)載均衡；備份路徑能夠在后期網(wǎng)絡(luò)鏈路狀態(tài)不佳時(shí)，為主路徑分擔(dān)部分流量。此外，文獻(xiàn)[9]并沒(méi)有給出主路徑和備份路徑的選擇方法，而本文給出了一種詳細(xì)的選路方案。

主路徑與備份路徑的計(jì)算方法如下。類似于流表負(fù)載均衡算法中的思想，本文提出路徑鏈路評(píng)分來(lái)評(píng)價(jià)源目的節(jié)點(diǎn)間的各條路徑。其綜合考慮了路徑鏈路平均質(zhì)量和瓶頸鏈路質(zhì)量。因網(wǎng)絡(luò)拓?fù)涮攸c(diǎn)，路徑鏈路平均質(zhì)量可用路徑鏈路總質(zhì)量代替，這里路徑鏈路負(fù)載總增量作為其評(píng)價(jià)指標(biāo)。

具體地，本文提出鏈路負(fù)載增量函數(shù)Li, j(x,v)，同時(shí)考慮大象流大小以及鏈路負(fù)載情況，如式(5)所示。其代表將大小為v的大象流調(diào)度到已用帶寬為x的鏈路上，給該鏈路帶來(lái)的負(fù)擔(dān)。

Li, j(x,v)=g(x+v)-g(x)

(5)

其中，g(x)為鏈路負(fù)載評(píng)價(jià)函數(shù)，同f(x)類似，唯一不同的是分界點(diǎn)的選取。在g(x)中，分界點(diǎn)為鏈路擁塞閾值。當(dāng)鏈路已用帶寬超過(guò)該閾值，則判定該鏈路擁塞，選擇增長(zhǎng)速率更高的函數(shù)對(duì)該鏈路進(jìn)行評(píng)價(jià)。因此，當(dāng)大象流調(diào)度到擁塞鏈路上或大象流的調(diào)度導(dǎo)致調(diào)度鏈路的擁塞，都會(huì)產(chǎn)生很大的負(fù)載增量。

同時(shí)，考慮到路徑的瓶頸鏈路，路徑鏈路評(píng)分計(jì)算公式如式(6)所示：

(6)

大象流從源目的交換機(jī)間備選路徑中選擇路徑鏈路評(píng)分最高和次高的路徑分別作為主路徑和備份路徑。

大象流調(diào)度算法偽代碼如算法2所示。

算法2 Elephantflows Rerouting1 while elephantflow do2 v←speed(elephantflow)3 foreach path in paths do4 foreach link in path do5 if bw(link)≤kBmaxthen6 load(link)←g1(bw(link))7 else8 load(link)←g2(bw(link))9 end if10 if bw(link)+v≤kBmaxthen11 load2(link)←g1(bw(link)+v)12 else13 load2(link)←g2(bw(link)+v)14 end if15 inc(link)←load2(link)-load(link)16 inclink(path)←inclink(path)+inc(link)17 end do18 minfreebw(path)←min{Bmax-bw(link)}19 scorelink(path)←minfreebw(path)inclink(path)20 end do21 pathm←argmax{scorelink(path)|path∈paths}22 paths2←remove pathm from paths23 pathb←argmax{scorelink(path)|path∈paths2}24 end while

其中，bw(link)為鏈路link已用帶寬，load(link)和load2(link)分別為流量到達(dá)鏈路前后的鏈路負(fù)載評(píng)價(jià)值，inc(link)為鏈路負(fù)載增量，min_freebw(path)為路徑path上鏈路的最小剩余容量，scorelink(path)為路徑鏈路評(píng)分。

(2)分流算法

當(dāng)處于流量高峰期時(shí)，由于大量突發(fā)流量的到來(lái)，網(wǎng)絡(luò)中某些鏈路可能會(huì)處于高負(fù)載狀態(tài)，導(dǎo)致鏈路負(fù)載不均衡。針對(duì)該問(wèn)題，本文提出分流算法。

該算法首先根據(jù)控制器周期性監(jiān)測(cè)到的網(wǎng)絡(luò)信息，計(jì)算鏈路負(fù)載均衡度。當(dāng)判定網(wǎng)絡(luò)鏈路負(fù)載不均衡時(shí)，選取要分裂的象流并計(jì)算組表權(quán)重，實(shí)現(xiàn)流量在主、備份路徑間的分配。網(wǎng)絡(luò)中的脈沖流(流帶寬很大但持續(xù)時(shí)間短)可能對(duì)鏈路負(fù)載均衡度造成很大影響，導(dǎo)致不必要的分流，從而給網(wǎng)絡(luò)帶來(lái)能量消耗。因此，本文采用文獻(xiàn)[9]中方案，當(dāng)鏈路負(fù)載均衡度連續(xù)m個(gè)周期大于負(fù)載均衡閾值，則判斷此時(shí)網(wǎng)絡(luò)鏈路負(fù)載不均衡。

鏈路負(fù)載均衡度借鑒方差的概念，定義如式(7)[9]所示：

(7)

(8)

其中，Bi, j(t)為t時(shí)刻交換機(jī)i、j間鏈路的已用帶寬，Ci, j(t)為鏈路最大帶寬，ui, j(t)為鏈路帶寬利用率，uave(t)為全網(wǎng)鏈路平均帶寬利用率，N為網(wǎng)絡(luò)中鏈路總數(shù)。由于|ui, j(t)-uave(t)|在0與1之間，添加1可使δ值變化范圍更大，從而更易判斷網(wǎng)絡(luò)鏈路負(fù)載情況。

當(dāng)監(jiān)測(cè)到網(wǎng)絡(luò)鏈路負(fù)載不均衡，選擇全網(wǎng)鏈路利用率最高的鏈路上的最大的象流，并判斷該流備份路徑上是否存在擁塞鏈路。若不存在，計(jì)算組表權(quán)重，在主、備份路徑間分配流量；若存在，從該大象流的多條備選路徑中，選擇除主路徑之外路徑最小剩余帶寬最大的路徑作為新備份路徑并計(jì)算組表權(quán)重。

組表權(quán)重計(jì)算公式如下：

(9)

(10)

其中，Bmain、Bback_up分別為主路徑、備份路徑鏈路剩余帶寬最大值，v為選中分割的大象流流帶寬。

分流算法偽代碼如算法3所示。

算法3 Flow Shunting1 while link load imbalance do2 foreach link in links do3 utilization(link)←portstate(link)4 end do5 linkmax← argmax{utilization(link)|link∈links}6 flowset←elephantflow(linkmax)7 foreach flow in flowset do8 v(flow)←flowstate(flow)9 end do10flowmax←argmax{v(flow)|flow∈flowset}11path←pathbackup(flowmax)12if congestion links in path then13calculate new path14 calculate weight15else16 calculate weight17end if18end while

其中，utilization(link)為鏈路link的帶寬利用率，linkmax代表全網(wǎng)鏈路利用率最大的鏈路，flow_set為該鏈路上的大象流集合，flowmax為該集合中的最大流。

3 仿真及結(jié)果分析

3.1 仿真場(chǎng)景描述

Mininet[16]是一款可在Linux下運(yùn)行的網(wǎng)絡(luò)仿真器，能夠方便地創(chuàng)建虛擬網(wǎng)絡(luò)，本文的網(wǎng)絡(luò)拓?fù)浠贛ininet搭建。同時(shí)，選用開(kāi)源的SDN控制器Ryu[17]作為本文的集中控制器，利用iperf[18]生成網(wǎng)絡(luò)數(shù)據(jù)流。交換機(jī)選用支持OpenFlow協(xié)議的 Open vSwitch[19]。數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)溥x用k=4的Fat-tree拓?fù)洌窗?0臺(tái)交換機(jī)和16臺(tái)主機(jī)，如圖1所示。實(shí)驗(yàn)中，鏈路帶寬設(shè)置為100 Mbps，交換機(jī)流表容量設(shè)置為20。為了模擬數(shù)據(jù)中心網(wǎng)絡(luò)流量，利用隨機(jī)流量模型，各主機(jī)等概率地向網(wǎng)絡(luò)中其他交換機(jī)發(fā)送數(shù)據(jù)流。其中，大象流所占比例小于老鼠流所占比例，且總和小于等于1；大象流持續(xù)時(shí)間遠(yuǎn)遠(yuǎn)大于老鼠流持續(xù)時(shí)間。在這里假設(shè)大象流數(shù)量占20%，老鼠流占80%，且大象流持續(xù)時(shí)間設(shè)置為60 s，老鼠流設(shè)置為5 s。大象流與老鼠流的區(qū)分閾值設(shè)為鏈路帶寬的0.5%[10]，即0.5 Mbps。

3.2 仿真結(jié)果及分析

本文將所提出的JLBFTL算法與SRL+FlowFit、L2RM算法進(jìn)行對(duì)比，并從平均丟包率、平均帶寬利用率及吞吐量3個(gè)方面比較了這3種算法的網(wǎng)絡(luò)性能。由圖3、圖4可得到表1、表2中信息，從該信息中可以得知，相比于L2RM與SRL+FlowFit，本文所提JLBFTL算法平均丟包率在整個(gè)區(qū)間上平均降低了12.6%和11.6%，平均帶寬利用率平均提升了9.3%和14.7%。這是由于SRL+FlowFit只考慮了網(wǎng)絡(luò)鏈路負(fù)載均衡，而忽視了交換機(jī)流表容量有限的問(wèn)題，容易引發(fā)流表溢出，導(dǎo)致丟包；L2RM雖通過(guò)動(dòng)態(tài)調(diào)整流表空閑時(shí)間來(lái)緩解流表的溢出，但其隨機(jī)選取初始化路由，容易使鏈路發(fā)生擁塞，造成丟包和包延遲。JLBFTL同時(shí)考慮流表負(fù)載均衡與鏈路負(fù)載均衡，能夠有效緩解流表溢出和鏈路擁塞，尤其保障了數(shù)目多但攜帶數(shù)據(jù)量少的老鼠流的正常傳輸，減少了丟包和包延遲，使得JLBFTL算法的平均丟包率和平均帶寬利用率得到改善。

圖3 3種算法平均丟包率比較

圖4 3種算法平均帶寬利用率比較

表1 JLBFTL相較于對(duì)比方案的平均丟包率下降率

表2 JLBFTL相較于對(duì)比方案的平均帶寬利用率增加率

由圖5可知，在吞吐量方面，JLBFTL相較于L2RM有一定的提升。雖然L2RM和JLBFTL在路由初始化時(shí)均未考慮鏈路狀態(tài)，但JLBFTL對(duì)大象流進(jìn)行了重路由以獲得更高的鏈路帶寬。因此，L2RM在鏈路負(fù)載均衡方面效果不佳，無(wú)法保證大象流的傳輸，使其吞吐量低于JLBFTL。JLBFTL與SRL+FlowFit相比，當(dāng)網(wǎng)絡(luò)流量到達(dá)速率小于280 Mbit/min時(shí)，JLBFTL吞吐量低于SRL+FlowFit；隨著流到達(dá)速率的增長(zhǎng)，JLBFTL吞吐量最終超過(guò)了SRL+FlowFit。這是由于SRL+FlowFit在路由初始化時(shí)考慮了鏈路狀態(tài)，而JLBFTL并未考慮，在該時(shí)期JLBFTL可能引發(fā)大象流的擁塞，導(dǎo)致大象流丟包，網(wǎng)絡(luò)吞吐量降低。但隨著網(wǎng)絡(luò)流量的增多，網(wǎng)絡(luò)負(fù)載的加重，SRL+FlowFit的最大流調(diào)度方案可能導(dǎo)致新鏈路的擁塞。此時(shí)，JLBFTL算法的分流機(jī)制使得大象流的傳輸?shù)玫奖Ｕ希瑥亩雇掏铝康玫接行嵘?/p>

圖5 3種算法吞吐量比較

4 結(jié) 論

本文提出的JLBFTL算法，針對(duì)數(shù)據(jù)中心網(wǎng)絡(luò)流量特征，將流表負(fù)載均衡和鏈路負(fù)載均衡相結(jié)合?？紤]路徑上流表負(fù)載總增量與最小流表剩余容量初始化路由，實(shí)現(xiàn)流表均衡。對(duì)于監(jiān)測(cè)到的大象流，考慮路徑上鏈路負(fù)載總增量與最小鏈路剩余帶寬，將大象流調(diào)度到帶寬資源更多的路徑上，實(shí)現(xiàn)鏈路負(fù)載均衡。當(dāng)流量高峰期時(shí)，網(wǎng)絡(luò)中大量的突發(fā)流量可能導(dǎo)致部分鏈路負(fù)載過(guò)重，造成鏈路負(fù)載不均衡，此時(shí)可通過(guò)選擇合適的大象流，利用備份路徑和組表進(jìn)行有效分流實(shí)現(xiàn)鏈路快速均衡。仿真結(jié)果表明，與SRL+FlowFit、L2RM算法相比，本算法在帶寬利用率、丟包率、吞吐量方面都有一定的改善，緩解了網(wǎng)絡(luò)擁塞和流表溢出，提升了網(wǎng)絡(luò)性能。

由于本文算法在路由初始化時(shí)將所有流量都視為老鼠流進(jìn)行流表均衡，可能會(huì)導(dǎo)致大象流的擁塞。這是未來(lái)工作中需要解決的問(wèn)題。同時(shí)，基于數(shù)據(jù)中心網(wǎng)絡(luò)大小流特點(diǎn)，可以進(jìn)一步設(shè)計(jì)流表空閑超時(shí)時(shí)間以實(shí)現(xiàn)流表空間更合理的利用。