軟件定義數(shù)據(jù)中心網(wǎng)絡(luò)基于分支界限法的多路徑路由算法

雷田穎,林子薇,何榮希

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

1 引 言

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

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

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

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

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

2 MPA-BB算法

2.1 SDCN連通性分析

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

圖1 具有k個(gè)pod的Fat-tree拓?fù)鋱DFig.1 Fat-tree topology with k pods

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

定義1.最小網(wǎng)絡(luò)連通子集.在G0中,如果只有一個(gè)核心層交換機(jī),每一個(gè)pod中只有一個(gè)匯聚層交換機(jī),并均與該核心層交換機(jī)相連接,而且每一個(gè)匯聚層交換機(jī)又與該pod中所有邊緣層交換機(jī)相連接,則稱該網(wǎng)絡(luò)子集為最小網(wǎng)絡(luò)連通子集.由Fat-Tree拓?fù)涞奶攸c(diǎn)可知,它包含|C|個(gè)最小網(wǎng)絡(luò)子集.

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

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

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

(1)

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

(2)

其中,

(3)

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

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

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

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

2.2 算法描述

為了更好地對(duì)算法進(jìn)行描述,引入以下定義.

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

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

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

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

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

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

最后,從Gbest1中獲取任意邊緣層交換機(jī)間傳輸大流時(shí)的所有可行路徑,存放到集合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é)點(diǎn)

endif

else

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

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

ifflag==falsethen

G1.add(lac);

endif

endif

endfor

forainJa1do

ifbi

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

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;

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

對(duì)于小流,則首先應(yīng)考慮其時(shí)延性能,其次再兼顧剩余帶寬.獲取滿足小流性能要求的最佳網(wǎng)絡(luò)子集Gbest2和任意邊緣層交換機(jī)間傳輸小流的可行路徑集合Sij的過(guò)程與上述過(guò)程類似,由于小流對(duì)時(shí)延更為敏感,因此,此時(shí)先從G0中獲取滿足式(5)的子集G1,然后,再?gòu)腉1中獲取滿足式(4)的子集G2,最終從G2中找出Gbest2,并從Gbest2中獲取任意邊緣層交換機(jī)間的可行路徑集合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)絡(luò)實(shí)際狀況設(shè)定.bmin表示所有鏈路剩余帶寬的下限值,其值越大,則選路時(shí)對(duì)鏈路剩余帶寬的要求越高.dmax表示所有鏈路的最大時(shí)延,其值越小,則選路時(shí)對(duì)鏈路時(shí)延的要求越高.

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

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

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

Input:f;

Output:Rbest;

begin

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

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

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

Rbest← getBest(Bij);

else

Rbest← getBest(Sij);

endif

returnRbest;

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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