雷田穎,林子薇,何榮希

(大連海事大學 信息科學技術(shù)學院,遼寧 大連 116026) E-mail:cndlmu@sina.com

1 引 言

數(shù)據(jù)中心是云計算的支撐平臺,而數(shù)據(jù)中心網(wǎng)絡(Data Center Network,DCN)是連接數(shù)據(jù)中心大規(guī)模服務器進行大型計算的橋梁[1].DCN通常采用Fat-tree等具有“富連接”特點的拓撲,通過使用數(shù)量充裕的網(wǎng)絡資源以提供可靠的轉(zhuǎn)發(fā)服務[2].但傳統(tǒng)的分布式控制,存在管理困難、資源利用率低等問題.基于OpenFlow的軟件定義網(wǎng)絡(Software Defined Network,SDN)是一種新型的網(wǎng)絡架構(gòu),可實現(xiàn)數(shù)據(jù)層與控制層的解耦合,通過集中式控制器可獲取全網(wǎng)狀態(tài)信息,便于實現(xiàn)網(wǎng)絡資源管理和網(wǎng)絡流量分配等[3,4].因此,將SDN與DCN相結(jié)合的軟件定義數(shù)據(jù)中心網(wǎng)絡(Software-defined Data Center Network),可以更好地實現(xiàn)網(wǎng)絡集中管理和流量優(yōu)化等[5],已引起業(yè)界的極大關(guān)注.

SDCN中采用傳統(tǒng)單路徑算法分配路徑,易造成數(shù)據(jù)過度集中,導致網(wǎng)絡擁堵.因此,已有文獻[6-10]提出多種多路徑路由算法.文獻[6]提出ECMP(Equal-Cost Multi-Path)算法,通過哈希運算和模運算計算轉(zhuǎn)發(fā)路徑,將數(shù)據(jù)流分散到不同路徑傳輸,可在一定程度減少單路徑算法導致的擁塞發(fā)生.但是,由于未考慮網(wǎng)絡實時狀態(tài),可能將數(shù)據(jù)流分配到剩余帶寬較少鏈路,仍易導致鏈路擁塞.文獻[7]提出基于網(wǎng)絡狀態(tài)的OFMT(OpenFlow based Multipath Transmission)算法,通過周期性輪詢和動態(tài)調(diào)度策略,可在一定程度避免鏈路出現(xiàn)擁塞和提高網(wǎng)絡資源利用率.

文獻[11]研究發(fā)現(xiàn),DCN中的數(shù)據(jù)流可分為大象流(大流)和老鼠流(小流),其中大流所占比例約為10%,對吞吐量性能要求較高,而小流占據(jù)全部流量的絕大部分比例,對鏈路時延性能要求更高.然而,上述算法都未區(qū)分大、小流,忽視了其傳輸性能要求的差異性.為此,文獻[8]和文獻[9]提出SHR(Software-defined Hybrid Routing)算法和SCR(SDN-Based Classified Routing)算法,依據(jù)流截止時間以及等待隊列長度為大流選路,而對小流則依據(jù)帶寬計算概率隨機選路.兩種算法為大、小流提供不同選路策略,有利于滿足其不同的傳輸性能需求.但是,算法的鏈路利用率不高.文獻[10]提出MLF(Multi-path Routing on Link real-time status and Flow characteristics)算法,利用鏈路剩余帶寬和哈希運算為大流選路,對小流則選擇剩余帶寬最大的路徑.該算法可在一定程度上彌補文獻[8,9]算法的不足.但是,僅依據(jù)鏈路剩余帶寬為時延敏感的小流選路,很可能所選路徑時延較大,導致小流傳輸時延性能不理想.

總的說來,上述算法[6-10]有一些不區(qū)分數(shù)據(jù)流大小及其對傳輸性能要求的差異性,對所有數(shù)據(jù)流采用相同選路策略,而有些則只片面強調(diào)大流的吞吐量指標、小流的時延指標.事實上,對于大流而言,選擇剩余帶寬較大路徑對于提高吞吐量固然重要,但其時延性能也不容忽視.為大流選路時,如果適當考慮時延因素,選擇時延較小路徑,可以使其更快完成傳輸,從而使后續(xù)到達大流具有更多可用帶寬資源,有利于提高其吞吐量.相應地,對于小流而言,不僅要關(guān)注其時延性能,滿足其時延敏感特性,也應酌情考慮路徑剩余帶寬情況,盡可能選擇剩余帶寬較大路徑,達到更為理想的負載均衡效果.另外,DCN是一個連接數(shù)萬級、十萬級甚至百萬級的大規(guī)模服務器群,規(guī)模巨大,因此,如何減少路由算法的時間復雜度也是設(shè)計時應該考慮的一個重要因素.分支限界法[12]是一種全局求解算法,基于靈活的回溯機制,可在局部無解時回到更高層次以調(diào)整搜索范圍,通過一定規(guī)則擴展子節(jié)點,并訪問盡可能少的節(jié)點,因此,有利于減少尋找可行解或者最優(yōu)解的次數(shù).本文將分支界限法的思想引入SDCN多路徑路由算法中,首先利用分支限界法的思想從原網(wǎng)絡獲取一個網(wǎng)絡子集,然后在該子集為數(shù)據(jù)流選擇合適路徑.由于該子集所包含節(jié)點和鏈路數(shù)遠小于原網(wǎng)絡,因此,可以減少算法為每一個數(shù)據(jù)流選路的求解次數(shù),有利于降低算法的時間復雜度.

本文利用SDN控制器掌控全網(wǎng)狀態(tài)信息的優(yōu)勢,綜合考慮大、小流對傳輸性能的不同要求,針對SDCN提出一種基于分支界限法的多路徑路由算法(Multiple path routing algorithm based on branch and bound,MPA-BB).首先,利用分支限界法思想獲取鏈路剩余帶寬盡可能大、鏈路時延盡可能小的網(wǎng)絡子集.為了保證子集中任意服務器間均可通信,提出最小網(wǎng)絡連通子集概念,并給出SDCN連通條件.然后,依據(jù)大、小流各自的性能要求,提出瓶頸時延、瓶頸帶寬等概念,在此基礎(chǔ)上在網(wǎng)絡子集中為大、小流利用不同策略選擇合適路徑.最后,通過Mininet和Floodlight進行仿真測試,仿真結(jié)果表明:與文獻中已有算法相比,MPA-BB算法具有更低的分組端到端時延、更高的網(wǎng)絡吞吐量和平均鏈路利用率.

2 MPA-BB算法

2.1 SDCN連通性分析

基于Fat-Tree拓撲的SDCN由交換機、服務器以及連接它們的雙向鏈路構(gòu)成.由于服務器是數(shù)據(jù)流的源和目的節(jié)點,而服務器直接與邊緣層交換機相連.為了保證數(shù)據(jù)正常通信,服務器與邊緣層交換機之間必須一直處于連接狀態(tài),即可行網(wǎng)絡子集中必須包含所有邊緣層交換機和服務器,且處于連接狀態(tài).進而,要保證可行網(wǎng)絡子集中所有服務器間均連通,必須保證與源服務器直接相連的邊緣層交換機和與目的服務器直接相連的邊緣層交換機之間均連通.為此,將SDCN中由交換機及其連接鏈路構(gòu)成的網(wǎng)絡子集記為初始網(wǎng)絡G0=(N,L).G0從上至下可分為核心層、匯聚層和邊緣層,其中N=C∪A∪E,表示所有交換機構(gòu)成的節(jié)點集合,交換機數(shù)為|N|.C、A、E分別為核心層、匯聚層和邊緣層交換機的集合,C∩A=C∩E=A∩E=Φ,各個集合包含交換機數(shù)分別為|C|、|A|、|E|.L表示連接各個交換機節(jié)點的雙向鏈路(邊)的集合,鏈路數(shù)為|L|.如果兩個節(jié)點之間存在雙向邊,則稱兩節(jié)點已連接;否則,則表示其未連接.Fat-Tree拓撲將匯聚層交換機和邊緣層交換機分為若干集合,每一個集合稱為一個pod(point of delivery)[2].對于有k個pod的Fat-Tree拓撲,G0中|N|=(5k2/4),|C|=(k/2)2,|A|=k2/2,|E|=k2/2,|L|=k3/2,服務器k3/4個,任意兩個邊緣層交換機間共有k2/4條可行路徑,如圖1所示.圖中,邊緣層、匯聚層、核心層交換機依次編號1到k2/2、k2/2+1到k2和k2+1到5k2/4.每個pod含有k個交換機(匯聚層和邊緣層交換機各k/2個).將核心層交換機依次排列,每k/2個交換機為一組,共k/2組,每一組連接不同pod中同一位置的匯聚層交換機.用a[i][j](1≤i,j≤5k2/4)表示網(wǎng)絡中第i個交換機與第j個交換機的連接情況.如果i和j相連(即連通),其值為1;否則,其值為0.

圖1 具有k個pod的Fat-tree拓撲圖Fig.1 Fat-tree topology with k pods

MPA-BB算法的目的是綜合考慮鏈路時延和剩余帶寬因素,獲取符合大、小流傳輸特性的最佳路徑.為了降低算法復雜度,首先利用分支限界法思想從G0中獲取一個網(wǎng)絡子集,進而在該子集中為數(shù)據(jù)流選擇可行路徑.在利用分支限界法選擇網(wǎng)絡子集時,必須要保證網(wǎng)絡中所有服務器對間均能正常通信(即保證SDCN全連通).在描述SDCN全連通條件前,引入以下定義.

定義1.最小網(wǎng)絡連通子集.在G0中,如果只有一個核心層交換機,每一個pod中只有一個匯聚層交換機,并均與該核心層交換機相連接,而且每一個匯聚層交換機又與該pod中所有邊緣層交換機相連接,則稱該網(wǎng)絡子集為最小網(wǎng)絡連通子集.由Fat-Tree拓撲的特點可知,它包含|C|個最小網(wǎng)絡子集.

由最小網(wǎng)絡連通子集的定義可知,要保證全網(wǎng)邊緣層交換機全部連通,只需要保證利用分支界限法獲取的最佳網(wǎng)絡子集中至少包含一個最小網(wǎng)絡連通子集即可.

定理1.為了保證SDCN中邊緣層交換機全連通,必須同時滿足以下兩個條件:

條件1.存在j∈{k2+1,k2+2,…, 5k2/4},使得式(1)成立.

(1)

條件2.對于任意的n∈{0,1,2,…,k-1},使得式(2)成立.

(2)

其中,

(3)

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

證明:根據(jù)核心層交換機與匯聚層交換機的連接特點和數(shù)據(jù)流的轉(zhuǎn)發(fā)特點可知,條件1要求至少存在一個核心層交換機與其所有連接的匯聚層交換機均處于工作狀態(tài),即保證核心層與匯聚層連通.

根據(jù)匯聚層交換機與邊緣層交換機的連接特點可知,條件2要求條件1中所有滿足要求的核心層交換機中,至少有一個核心層交換機連接的所有匯聚層交換機分別與本pod中所有邊緣層交換機連接,即保證podi(1≤i≤k)內(nèi)部邊緣層交換機全連通.

因此,當且僅當同時滿足條件1和條件2時,處于工作狀態(tài)的網(wǎng)絡子集至少包含一個最小網(wǎng)絡連通子集,因此可保證SDCN中邊緣層交換機連通,即保證了SDCN中服務器連通,也就是保證了SDCN連通.

2.2 算法描述

為了更好地對算法進行描述,引入以下定義.

定義2.瓶頸時延.構(gòu)成路徑r的鏈路集合為L′={l1,l2,…,lj},鏈路li的時延為di,則dr=max{di},li∈L′稱為r的瓶頸時延.

定義3.瓶頸帶寬.構(gòu)成路徑r的鏈路集合為L′={l1,l2,…,lj},鏈路li的剩余帶寬為bi,則br=min{bi},li∈L′稱為r的瓶頸帶寬.

MPA-BB算法首先利用分支限界法思想獲取一個保證SDCN連通的網(wǎng)絡子集,然后根據(jù)網(wǎng)絡狀態(tài)信息和大小流各自的性能要求為其提供不同的選路策略.分支限界法的主要思想是以最小代價優(yōu)先方式搜索問題的解空間樹,每一個活節(jié)點只有一次機會成為擴展節(jié)點.活節(jié)點一旦成為擴展節(jié)點,就一次性產(chǎn)生其所有子節(jié)點.將這些子節(jié)點中導致不可行解或?qū)е路亲顑?yōu)解的子節(jié)點舍棄,其余子節(jié)點加入活節(jié)點表.此后從活節(jié)點表中取下一個節(jié)點成為擴展節(jié)點,并重復上述節(jié)點擴展過程,直到找到所需解或活節(jié)點表為空[12].

MPA-BB主要由拓撲管理模塊(Topology Management,TM)、連通性判斷模塊(Connection Judgement,CJ)、路由管理模塊(Routing Management,RM)和流表下發(fā)模塊(Flow Distribution,FD)組成,整體架構(gòu)如圖2所示.

圖2 算法總體架構(gòu)Fig.2 Overall architecture of the algorithm

TM模塊是MPA-BB算法的基礎(chǔ)模塊,首先對整個SDCN進行感知,獲取核心層、匯聚層、邊緣層交換機的連接方式和網(wǎng)絡中每條鏈路的時延信息,并利用sflow軟件*sflow [OL].[2017-07-06].http://www.sflow.org/獲取每條鏈路的剩余帶寬信息.然后,考慮到SDCN中數(shù)據(jù)流存在大流和小流之分,因此根據(jù)獲取到的信息,利用分支限界法思想分別獲取滿足大流和小流性能需求的最佳網(wǎng)絡子集Gbest1和Gbest2,并將Gbest1和Gbest2中任意兩個邊緣層交換機i和j(1≤i,j≤k2/2)之間所有可行路徑分別存放到集合Bij和Sij,以供RM模塊使用.這樣當有數(shù)據(jù)流需要控制器為其選路時,RM模塊只需判斷該數(shù)據(jù)流為大流還是小流(1～100KB為小流,大于100KB為大流[11]),即可根據(jù)該數(shù)據(jù)流的源和目的節(jié)點從相應的集合Bij或者Sij中依據(jù)對應的選路策略選擇一條最佳路徑.

由于大流對吞吐量要求較高,因此首先考慮鏈路剩余帶寬的影響.此時,可通過分支限界法從G0中獲取滿足式(4)要求的網(wǎng)絡子集G1.具體過程為:初始化G1=G0,將所有核心層交換機節(jié)點存放到活節(jié)點集合Jc1中,從該集合依次取出每一個核心層交換機節(jié)點.以該節(jié)點為根節(jié)點,相連的匯聚層交換機節(jié)點為末節(jié)點,查看二者之間鏈路的剩余帶寬是否滿足式(4).如果滿足,則將該末節(jié)點存放到活節(jié)點集合Ja1中;否則,從G1中刪除該鏈路,更新G1.值得注意的是,每一次將匯聚層節(jié)點放入集合Ja1時,需要判斷集合中是否已經(jīng)含有該節(jié)點.只有當集合中沒有該節(jié)點時才將此節(jié)點放入集合.當Jc1為空時,從Ja1中依次取出每一個匯聚層交換機節(jié)點,以該節(jié)點為根節(jié)點,相連的邊緣層交換機為末節(jié)點,查看二者之間鏈路的剩余帶寬是否滿足式(4).如果滿足,由于邊緣層交換機節(jié)點為網(wǎng)絡的最底層節(jié)點,已無子節(jié)點,所以回到匯聚層交換機節(jié)點,繼續(xù)查看其他鏈路;否則,從G1中刪除該鏈路,更新G1.當Ja1為空時,此時的G1即為G0中滿足式(4)條件的網(wǎng)絡子集.

對于大流而言,考慮到如果適當選擇時延較小路徑,可以使其更快完成傳輸,也有利于網(wǎng)絡吞吐量的提高.因此,繼續(xù)考慮鏈路時延的影響,通過分支限界法從G1中獲取滿足式(5)的網(wǎng)絡子集G2,將G2記為大流的最佳網(wǎng)絡子集Gbest1.具體過程與獲取G1的過程類似,即初始化G2=G1,首先以每一個核心層交換機為根節(jié)點,從G2中獲取滿足式(5)要求的所有匯聚層交換機節(jié)點并存放到集合Ja2中,同時刪除不滿足要求的連接核心層和匯聚層交換機的鏈路,更新G2.然后以Ja2中每一個節(jié)點為根節(jié)點,刪除所有不滿足式(5)要求的連接匯聚層和邊緣層交換機的鏈路,更新G2,此時G2即為Gbest1.

最后,從Gbest1中獲取任意邊緣層交換機間傳輸大流時的所有可行路徑,存放到集合Bij(1≤i,j≤k2/2).獲取Gbest1和Bij的偽代碼如下:

Input:G0;

Output:Bij;

begin

G1←G0;

forcinJc1do

ifbi≥bminthen

ifJa1.contains(a)==falsethen

Ja1.add(a); //a是c所連接的匯聚層節(jié)點

endif

else

deletelacfromG1;//lac為a和c相連的鏈路

flag=CJ(G1);//CJ函數(shù)用于判斷鏈路是否可刪除

ifflag==falsethen

G1.add(lac);

endif

endif

endfor

forainJa1do

ifbi

deletelfromG1;//l為a和邊緣層交換機相連的鏈路

endif

flag=CJ(G1);

ifflag==falsethen

G1.add(l);

endif

endfor

G2←G1;

forcinJc2do

ifdi≤dmaxthen

ifJa2.contains(a)==falsethen

Ja2.add(a);

endif

else

deletelacfromG2;

flag=CJ(G2);

ifflag==falsethen

G2.add(lac);

endif

endif

endfor

forainJa2do

ifdi>dmaxthen

deletelfromG2;

endif

flag=CJ(G2);

ifflag==falsethen

G2.add(l);

endif

endfor

Gbest←G2;

Bij=getRoutes(Gbest);

returnBij;

值得注意的是,在分支限界法的過程中一旦要刪除某條鏈路,則需利用CJ模塊判斷剩余網(wǎng)絡資源所構(gòu)成子集是否滿足定理1給出的SDCN連通條件.因此,當網(wǎng)絡中的鏈路均不滿足式(4)和(5)時,則Gbest1是以Core中最后一個節(jié)點為根節(jié)點的最小網(wǎng)絡連通子集.由于本模塊處于SDN集中控制器中,而控制器每隔一定時間T將會重新感知整個網(wǎng)絡,因此,本模塊每隔T重新調(diào)用一次.

對于小流,則首先應考慮其時延性能,其次再兼顧剩余帶寬.獲取滿足小流性能要求的最佳網(wǎng)絡子集Gbest2和任意邊緣層交換機間傳輸小流的可行路徑集合Sij的過程與上述過程類似,由于小流對時延更為敏感,因此,此時先從G0中獲取滿足式(5)的子集G1,然后,再從G1中獲取滿足式(4)的子集G2,最終從G2中找出Gbest2,并從Gbest2中獲取任意邊緣層交換機間的可行路徑集合Sij.

bi≥bmin

(4)

di≤dmax

(5)

其中,bmin(min{bi}≤bmin≤max{bi},li∈L)和dmax(min{di}≤dmax≤max{di},li∈L)均為常數(shù),可根據(jù)網(wǎng)絡實際狀況設(shè)定.bmin表示所有鏈路剩余帶寬的下限值,其值越大,則選路時對鏈路剩余帶寬的要求越高.dmax表示所有鏈路的最大時延,其值越小,則選路時對鏈路時延的要求越高.

2Floodlight Editor, Floodlight Manual [OL].[2017-07-03], http://www.projectfloodlight.org.

CJ模塊主要用于對網(wǎng)絡連通性進行判斷,即利用定理1的條件判斷所有服務器是否能正常通信.當滿足SDCN全連通條件時,本模塊返回True,否則返回False.

RM模塊主要為數(shù)據(jù)流f選取最佳路徑,偽代碼如下:

Input:f;

Output:Rbest;

begin

i← getSource(f); //獲取數(shù)據(jù)流的f的源節(jié)點

j← getDes(f); //獲取數(shù)據(jù)流的f的目的節(jié)點

ifsize(f)>ωthen//ω為大小流的分界值

Rbest← getBest(Bij);

else

Rbest← getBest(Sij);

endif

returnRbest;

當數(shù)據(jù)流f需控制器為其選路時,獲取對應的源、目的邊緣層交換機節(jié)點i和j,并判斷其為大流還是小流(1～100KB為小流,大于100KB為大流[11]):

1)如果為大流,則利用sflow獲取Bij中所有路徑的實時瓶頸帶寬,然后選擇瓶頸帶寬最大的路徑為最佳路徑Rbest,供FD模塊使用.

2)如果為小流,則從Sij所有路徑中選擇瓶頸時延最小的路徑為最佳路徑Rbest,供FD模塊使用.

現(xiàn)對控制器為每一條數(shù)據(jù)流選路過程的復雜度進行分析.假設(shè)Bij或者Sij中含有f(1≤f≤k2/4)條可行路徑,因此,需要進行f-1次比較以獲取性能最佳路徑,時間復雜度為O(f).最壞情況是G0為最佳網(wǎng)絡子集,此時Bij或者Sij中存在k2/4條可行路徑,此時,時間復雜度為O(k2/4).

FD模塊根據(jù)Rbest生成流表信息,并告知相應的交換機如何對數(shù)據(jù)流進行傳輸.

3 仿真實驗與性能分析

采用Mininet[13]仿真軟件搭建SDCN,采用Floodlight2作為集中控制器,對本文所提出的MPA-BB算法進行仿真評測,并與OFMT算法[7]和MLF算法[10]進行對比.仿真拓撲采用k=4的Fat-Tree拓撲,包含16個主機、20個交換機和32條鏈路.仿真中,每條鏈路的時延在1到10ms之間隨機產(chǎn)生,鏈路帶寬為1Gbps,dmax=5ms,bmin=500Mbps.仿真中T=5s,利用ping技術(shù)和Iperf軟件產(chǎn)生數(shù)據(jù)流量.隨機選取10對服務器分別作為數(shù)據(jù)流的源和目的服務器.根據(jù)Benson等人的研究成果[11],假設(shè)90%的流大小為1～100KB(即小流),10%的流大小大于100KB(即大流),都服從均勻分布.小流持續(xù)時間為2秒,大流持續(xù)時間為10秒.在不同發(fā)送速率下對算法進行仿真比較,仿真評測指標為分組端到端時延、網(wǎng)絡吞吐量和平均鏈路利用率.每種發(fā)送速率都進行10次實驗,取10次的平均值作為仿真結(jié)果,如圖3-圖5所示.

圖3表示不同發(fā)送速率下各算法的分組端到端時延情況.從圖中可以看出:隨著發(fā)送速率增大,各個算法的時延均呈上升趨勢.但是,MPA-BB算法最低,OFMT算法最高,而MLF位于二者之間.主要原因在于:網(wǎng)絡帶寬一定時,隨著發(fā)送速率的增加,網(wǎng)絡負載隨之增加,網(wǎng)絡中會出現(xiàn)一定程度的擁堵,因此各個算法的時延均會有所增加.由于MPA-BB算法在選路過程中充分考慮鏈路時延和剩余帶寬的影響,優(yōu)先嘗試刪除時延較大和剩余帶寬較小的鏈路以獲取網(wǎng)絡子集,因此,所選路徑包含高時延和低剩余帶寬的鏈路較少.另外,MPA-BB算法選路時,對大流選取瓶頸剩余帶寬較大路徑,對小流優(yōu)先獲取瓶頸時延較小路徑,可以最大限度地避免選取路徑剩余帶寬不足或者時延較大而導致大量數(shù)據(jù)等待,所以分組端到端時延性能優(yōu)于其他兩種算法.由于OFMT算法未區(qū)分對待大小流,未充分利用網(wǎng)絡狀態(tài)信息選路,因此,分組端到端時延性能較差.雖然MLF算法考慮了大、小流的差異性,對大流考慮鏈路剩余帶寬因素影響,但是采取哈希運算為其選路,可能導致數(shù)據(jù)集中在某些鏈路,因此,容易導致大流分組端到端時延不理想.而對小流則直接選取剩余帶寬較大的路徑,所選路徑時延可能較大,因此,會影響小流的時延性能,所以整體上MLF算法的分組端到端時延位于MPA-BB和OFMT之間.

圖3 分組端到端時延Fig.3 End to end delay of packets

圖4 網(wǎng)絡吞吐量Fig.4 Network throughput

圖5 平均鏈路利用率Fig.5 Average link utilization

圖4給出了不同發(fā)送速率下各算法的網(wǎng)絡吞吐量對比情況.從圖中可以看出:當發(fā)送速率較小時(低于500Mbps),各算法的吞吐量性能相差不大.但是,隨著發(fā)送速率逐漸增大,各算法的吞吐量均有不同程度上升,而且差距逐漸明顯(MPA-BB最大、MLF次之、OFMT最低).當發(fā)送速率達到500Mbps時,網(wǎng)絡吞吐量達到最大值.繼續(xù)增加發(fā)送速率,由于網(wǎng)絡出現(xiàn)擁塞,吞吐量逐漸下降,并趨于穩(wěn)定.由于MPA-BB算法綜合考慮了鏈路時延和鏈路剩余帶寬對數(shù)據(jù)流的影響,盡可能選取負載輕、時延小的路徑轉(zhuǎn)發(fā)數(shù)據(jù)流,因此其吞吐量性能優(yōu)于其他兩種算法.

圖5對比了不同發(fā)送速率下各算法的平均鏈路利用率性能.從圖中可以看出:當發(fā)送速率較小時(低于400Mbps),由于網(wǎng)絡負載較輕,三種算法的鏈路利用率較低,而且相差不大.但是,隨著數(shù)據(jù)發(fā)送速率逐漸增大,網(wǎng)絡負載逐漸增加,三種算法的利用率均有不同程度上升,而且差距逐漸明顯(MPA-BB最大、MLF次之、OFMT最低).當發(fā)送速率較大時(高于500Mbps),網(wǎng)絡負載較重,各鏈路已用帶寬較大,因此鏈路利用率均較高.由于MPA-BB算法充分考慮了鏈路剩余帶寬對數(shù)據(jù)流的影響,盡可能選取負載輕的路徑轉(zhuǎn)發(fā)數(shù)據(jù)流,當網(wǎng)絡負載較高時,可以將數(shù)據(jù)流分配到其他已用帶寬較小的鏈路上傳遞數(shù)據(jù),有利于接納更多大流,因此平均鏈路利用率高于其他兩種算法.

4 結(jié)束語

本文針對SDCN中數(shù)據(jù)流的特點,提出一種基于分支界限法的多路徑路由算法(MPA-BB),該算法針對大、小流不同的網(wǎng)絡性能需求,綜合考慮時延和剩余帶寬兩種因素的影響,為大、小流采用不同的選路策略選擇合適的路徑.最后,通過Mininet和Floodlight進行仿真評測,結(jié)果表明:與文獻中已有算法相比,MPA-BB算法在傳輸數(shù)據(jù)包過程中具有更低的分組端到端時延、更高的網(wǎng)絡吞吐量和平均鏈路利用率.考慮到基于Fat-Tree拓撲的DCN會增加網(wǎng)絡能耗,不利于實現(xiàn)綠色節(jié)能,因此,下一步將對節(jié)能路由進行研究.