趙夢亞,龍昭華,蔣貴全,王 奇,秦曉煥
(1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶400065;2.北京航空航天大學(xué) 軟件學(xué)院,北京100191)
軟件定義網(wǎng)絡(luò) (software defined network,SDN)[1]已經(jīng)成為未來網(wǎng)絡(luò)研究的熱點(diǎn),尤其在數(shù)據(jù)中心的應(yīng)用中,網(wǎng)絡(luò)集中控制的優(yōu)點(diǎn)能夠保證網(wǎng)絡(luò)中流量調(diào)度策略的動態(tài)性與靈活性,這是當(dāng)前傳統(tǒng)網(wǎng)絡(luò)架構(gòu)所不具備的。然而,數(shù)據(jù)根據(jù)目的地址通過最短路徑傳輸,大流量可能會導(dǎo)致最短鏈路或網(wǎng)絡(luò)接口的擁塞,與此同時(shí),與最短路徑相比的次最短路徑可能空閑,造成整體性能下降與網(wǎng)絡(luò)資源的浪費(fèi),最終導(dǎo)致網(wǎng)絡(luò)的整體服務(wù)質(zhì)量下降[2]。針對此問題,本文提出了一種提高網(wǎng)絡(luò)資源利用率的路由算法,通過源節(jié)點(diǎn)與目的節(jié)點(diǎn)計(jì)算出多條路徑,并根據(jù)各個(gè)路徑帶寬利用率對其進(jìn)行選擇,達(dá)到充分利用網(wǎng)絡(luò)資源,提升網(wǎng)絡(luò)整體性能的目的,借助OpenFlow 實(shí)驗(yàn)平臺,對該路由策略進(jìn)行實(shí)現(xiàn)并驗(yàn)證其可行性。
現(xiàn)有的OpenFlow 控制器系統(tǒng)如Floodlight[3]、NOX[4]等均能夠提供用于完成數(shù)據(jù)幀轉(zhuǎn)發(fā)的模塊,為OpenFlow交換機(jī)網(wǎng)絡(luò)提供一種基本的簡單策略數(shù)據(jù)轉(zhuǎn)發(fā),這樣的路由策略會導(dǎo)致一個(gè)嚴(yán)重的問題,總體網(wǎng)絡(luò)資源占用率并不高的情況下,大量的流進(jìn)入某條鏈路導(dǎo)致負(fù)載過大,最終導(dǎo)致網(wǎng)絡(luò)擁塞而造成數(shù)據(jù)幀的丟失。針對這些問題,提出使用等價(jià)多路徑技術(shù)與OpenFlow 中流相結(jié)合方法,設(shè)計(jì)出針對流的多路徑分配策略。
本文采用了支持OpenFlow[5,6]協(xié)議的網(wǎng)絡(luò)架構(gòu),主要對Floodlight中現(xiàn)有的單最短路徑和數(shù)據(jù)轉(zhuǎn)發(fā)控制進(jìn)行擴(kuò)展,轉(zhuǎn)發(fā)控制是根據(jù)多路徑的路徑帶寬利用率選優(yōu)進(jìn)行控制轉(zhuǎn)發(fā),從而實(shí)現(xiàn)網(wǎng)絡(luò)的多鏈路負(fù)載均衡傳 輸[7,8]。
由于OpenFlow 交換機(jī)對控制器提供統(tǒng)一的接口和數(shù)據(jù)轉(zhuǎn)發(fā)功能,控制器對OpenFlow 流表的轉(zhuǎn)發(fā)進(jìn)行統(tǒng)一控制。基于在現(xiàn)有控制器中的數(shù)據(jù)轉(zhuǎn)發(fā)策略模塊基礎(chǔ)上,提出了適合OpenFlow 網(wǎng)絡(luò)的多路徑路由解決策略。該策略的采用Floodlight控制器進(jìn)行集中控制,控制器能夠獲取整個(gè)OpenFlow 交換機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),當(dāng)新流接入Open-Flow 交換機(jī)時(shí),需要計(jì)算出源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的多條等價(jià)可用路徑,再根據(jù)統(tǒng)計(jì)出的已占用的網(wǎng)絡(luò)資源,綜合各路徑的狀況,將流合理的分配出傳輸路徑。為達(dá)到以上目標(biāo),本文提出的設(shè)計(jì)框架如圖1所示。
圖1 設(shè)計(jì)框架
在OpenFlow 網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)行擴(kuò)展,其中多路徑路由模塊是依據(jù)控制器掌握的OpenFlow 網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù)和根據(jù)網(wǎng)絡(luò)鏈路帶寬利用率為流尋找并分配合理路徑,并向交換機(jī)下發(fā)對應(yīng)流量分發(fā)組的OpenFlow 流表。收集網(wǎng)絡(luò)鏈路信息是統(tǒng)計(jì)交換機(jī)流量信息。并計(jì)算出K最短路徑各個(gè)路徑的鏈路帶寬利用率,為選擇合理的路徑提供數(shù)據(jù)支持。
多路徑路由模塊是整體網(wǎng)絡(luò)的核心,實(shí)現(xiàn)對源節(jié)點(diǎn)和目的節(jié)點(diǎn)間多路徑路由選擇。當(dāng)外部數(shù)據(jù)包第一次進(jìn)入OpenFlow 交換機(jī)網(wǎng)絡(luò)時(shí),將該數(shù)據(jù)包與流表中的流表項(xiàng)進(jìn)行匹配,由于流表中沒有與該數(shù)據(jù)包相匹配的流表項(xiàng),因此將該數(shù)據(jù)包的第一個(gè)數(shù)據(jù)幀通過OpenFlow 協(xié)議數(shù)據(jù)單元包裝發(fā)送至控制器??刂破鹘?jīng)過以下幾步完成對該數(shù)據(jù)流的處理:
(1)解析數(shù)據(jù)包的源地址、目的地址;
(2)根據(jù)源地址和目的地址查找數(shù)據(jù)包需要經(jīng)過的第一個(gè)交換機(jī)和最后一個(gè)交換機(jī);
(3)根據(jù)網(wǎng)絡(luò)拓?fù)?、鏈路花費(fèi)計(jì)算出第一個(gè)交換機(jī)和最后一個(gè)交換機(jī)間的多條可用路徑;
(4)根據(jù)各個(gè)路徑的帶寬利用率選擇最合適的路徑供該數(shù)據(jù)流使用;
(5)創(chuàng)建流規(guī)則并告知沿途所有交換機(jī)對于該數(shù)據(jù)流的處理。
網(wǎng)絡(luò)流量采集和網(wǎng)絡(luò)流量統(tǒng)計(jì)是采用sFlow 技術(shù)對整個(gè)OpenFlow 交換機(jī)網(wǎng)絡(luò)進(jìn)行流量監(jiān)控。使用sFlow 技術(shù)代替控制器的輪詢收集交換機(jī)的統(tǒng)計(jì)信息。這樣大大節(jié)約了網(wǎng)絡(luò)資源的消耗。sFlow[9]是由InMon公司提出的一種基于 “統(tǒng)計(jì)采樣方式”的高速交換網(wǎng)絡(luò)流量監(jiān)控技術(shù),通過周期性采樣來獲取網(wǎng)絡(luò)流量信息。然后把采樣包發(fā)送至流量分析器進(jìn)一步分析和處理。讓用戶實(shí)時(shí)的掌握網(wǎng)絡(luò)傳輸流的性能和狀況。sFlow 的網(wǎng)絡(luò)流量監(jiān)測實(shí)現(xiàn)由兩個(gè)部分構(gòu)成:sFlow 代理和sFlow 數(shù)據(jù)收集器。sFlow 代理對流經(jīng)過交換機(jī)的數(shù)據(jù)包進(jìn)行采樣處理成sFlow 數(shù)據(jù)報(bào),發(fā)送至指定的sFlow 數(shù)據(jù)收集器,sFlow 數(shù)據(jù)收集器可以接收一個(gè)或多個(gè)sFlow 代理發(fā)來的數(shù)據(jù)并進(jìn)行分析處理。網(wǎng)絡(luò)流量統(tǒng)計(jì)的功能:
(1)從OpenFlow 交換機(jī)網(wǎng)絡(luò)中按照一定的時(shí)間間隔獲取網(wǎng)絡(luò)各鏈路的工作狀態(tài);
(2)將獲取的鏈路信息轉(zhuǎn)為控制器可讀格式;
(3)為多路徑路由提供數(shù)據(jù)支持。
本文的實(shí)驗(yàn)設(shè)計(jì)分為網(wǎng)絡(luò)流量統(tǒng)計(jì)和多路徑路徑兩個(gè)功能模塊,其中多路徑路徑是實(shí)驗(yàn)設(shè)計(jì)的核心,決定了整個(gè)OpenFlow網(wǎng)絡(luò)中流的流向,在運(yùn)行過程調(diào)用網(wǎng)絡(luò)流量統(tǒng)計(jì)模塊提供的統(tǒng)計(jì)數(shù)據(jù)。本文將對兩個(gè)模塊的實(shí)現(xiàn)進(jìn)行描述。
網(wǎng)絡(luò)流量統(tǒng)計(jì)模塊主要反映OpenFlow 交換機(jī)網(wǎng)絡(luò)的動態(tài)信息,是為了解決多路徑路由在計(jì)算出多條路徑后,從中選擇合適的路徑提供流使用。sFlow 代理是收集網(wǎng)絡(luò)接口的信息,sFlow 數(shù)據(jù)收集器統(tǒng)計(jì)各sFlow 代理發(fā)送的信息。sFlow 代理通過開源項(xiàng)目Host sFlow[10]來實(shí)現(xiàn)一種簡單的部署方式,安裝Host sFlow 后,在配置文件中定義sFlow 收集器的地址,通過啟動hsflowd服務(wù)后即可周期性地向sFlow 收集器發(fā)送網(wǎng)絡(luò)接口信息??刂破魇腔贗n-Mon公司開發(fā)的sFlow-RT[11]收集器軟件,并提供RESTAPI接口,以JSON 格式提供數(shù)據(jù),根據(jù)收集的網(wǎng)絡(luò)接口數(shù)據(jù),計(jì)算出每個(gè)網(wǎng)絡(luò)接口利用率。接口已用帶寬測量如式 (1)所示
對于交換機(jī)節(jié)點(diǎn)i與交換機(jī)節(jié)點(diǎn)j 間的鏈路li,j帶寬利用率如式 (2)所示
路徑P 的帶寬利用率W(P)為組成該路徑的各個(gè)鏈路帶寬利用率的最大值
網(wǎng)絡(luò)流量統(tǒng)計(jì)的數(shù)據(jù)為多路徑路由選擇路徑提供了依據(jù),是整個(gè)系統(tǒng)的重要組成部分。
實(shí)時(shí)帶寬利用率η(t)定義為網(wǎng)絡(luò)中已經(jīng)使用的鏈路帶寬占網(wǎng)絡(luò)總鏈路帶寬的比例,Maxload表示為每一條鏈路上的最大帶寬,如式 (4)所示。根據(jù)η(t)數(shù)值的變化實(shí)時(shí)顯示當(dāng)前網(wǎng)絡(luò)的利用率
多路徑路由模塊是實(shí)現(xiàn)名為K 最短路徑算法的多路徑轉(zhuǎn)發(fā)核心模塊,該算法是基于MPS[12,13]的K 最短路徑算法,在求解無回路最短路徑算法時(shí),先對其進(jìn)行權(quán)重轉(zhuǎn)換,其次根據(jù)權(quán)重來選擇從源節(jié)點(diǎn)到目的節(jié)點(diǎn)中所有鏈路花費(fèi)最小的路徑。該算法的特點(diǎn)是利用一個(gè)候選路徑集合X 來尋找K 條無回路最短路徑,算法從計(jì)算最短路徑生成樹開始,當(dāng)找到最小的偏差時(shí),每條弧的權(quán)重被替換為相應(yīng)減少的權(quán)重,并只允許最優(yōu)的弧 (簡化權(quán)重最小的?。?。由于X 為堆 (數(shù)據(jù)結(jié)構(gòu)),可以快速計(jì)算出簡化權(quán)重最小的路徑。根據(jù)簡化權(quán)重對其具有相同尾結(jié)點(diǎn)的弧進(jìn)行排序。使用該方法可以減少運(yùn)算的次數(shù),加快尋找偏離邊的速度,效率相對較高,該算法的時(shí)間復(fù)雜度是O(MlgN+KN),算法在最差情況下的時(shí)間復(fù)雜度大約是O(NMlgN+KN),其中N 為交換機(jī)的個(gè)數(shù),M 為交換機(jī)網(wǎng)絡(luò)的鏈路數(shù)。核心算法的偽代碼如圖2所示。
根據(jù)多路徑路由的算法得到從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的K 條最短路徑,計(jì)算出K 條路徑上的每條鏈路帶寬剩余容量,一條路徑上的剩余帶寬容量由屬于這條路徑的所有鏈路的最小剩余帶寬容量決定。因此,控制器需要維護(hù)交換機(jī)網(wǎng)絡(luò)中所有鏈路的剩余容量。流均衡算法每次為一條流選擇某條路徑之后,需要修改這條路徑上所有鏈路的剩余容量,即這條路徑上所有鏈路的剩余容量都要減去該流的帶寬需求,從而保證路徑選擇對網(wǎng)絡(luò)中鏈路的剩余帶寬容量的影響被及時(shí)更新[14]。流均衡算法描述:
(1)網(wǎng)絡(luò)流量統(tǒng)計(jì)模塊計(jì)算出所有鏈路帶寬利用率。
(2)選擇X 中每條最短路徑中鏈路的帶寬利用率最大的作為本路徑的帶寬利用率。
(3)檢查K 條路徑的可用帶寬是否滿足所需帶寬要求,若是,執(zhí)行下一步,若不是刪除不滿足的路徑,再次計(jì)算最短路徑達(dá)到K 條路徑。
(4)選擇帶寬利用率最小的路徑分配給新流。
本文的所有實(shí)驗(yàn)都是部署在Mininet 2.0[15,16]開發(fā)環(huán)境中,控制器采用了基于Java的控制器Floodlight。根據(jù)實(shí)際網(wǎng)絡(luò)部署模擬出相似的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),并對拓?fù)洳呗赃M(jìn)行對多路徑的路由的設(shè)計(jì)進(jìn)行驗(yàn)證。為了使實(shí)驗(yàn)過程和效果具有較好的穩(wěn)定性和對比性,我們對鏈路的基準(zhǔn)參數(shù)進(jìn)行了配置,將鏈路帶寬限定為10 Mbps。控制器中使用鏈路上數(shù)值作為鏈路的花費(fèi)。多路徑數(shù)量設(shè)定為5。本文設(shè)計(jì)了網(wǎng)絡(luò)拓?fù)淙鐖D3所示。每個(gè)交換機(jī)均連接一個(gè)主機(jī)節(jié)點(diǎn)。
網(wǎng)絡(luò)性能測試工具的發(fā)送端程序運(yùn)行在主機(jī)節(jié)點(diǎn)Host1和Host11上,Host1對應(yīng)的接收端Host6、Host9、Host12、Host13,Host11 對 應(yīng) 的 接 收 端 為Host2、Host5、Host7、Host8。兩個(gè)發(fā)送端端按照每2s間隔以5Mbs的速率向相應(yīng)的4個(gè)接收端程序各發(fā)送一條數(shù)據(jù)流,流中字節(jié)均為2000字節(jié),流的長度為60s,網(wǎng)絡(luò)流量采集時(shí)間間隔為5s。
本課題實(shí)現(xiàn)了最短多路徑路由設(shè)計(jì)的根據(jù)網(wǎng)絡(luò)帶寬利用率進(jìn)行選擇路徑的算法,并與Floodlight控制器原有的最短路徑算法作對比,并在實(shí)驗(yàn)中測量了帶寬利用率和吞吐率作對比分析。針對每種路由策略,分別進(jìn)行了3次實(shí)驗(yàn)并記錄以保證實(shí)驗(yàn)的準(zhǔn)確性。
圖2 算法偽代碼
圖3 實(shí)驗(yàn)拓?fù)?/p>
最短路策略僅采用鏈路花費(fèi)最小作為選路依據(jù),并且選擇標(biāo)號最小的一條路徑作為流的轉(zhuǎn)發(fā)。最短路策略選路結(jié)果見表1。
從路徑分配表可以看出,流傳輸路徑大部分集中在S1-S2,S2-S3,S3-S4,S11-S4這4 條鏈路上。而剩余鏈路則是在空閑狀態(tài)。從而造成網(wǎng)絡(luò)資源的利用率較低。
3次實(shí)驗(yàn)中,K 最短路由策略為每條流分配的路徑見表2。
從表2可以看出,Host1發(fā)出的流在3次實(shí)驗(yàn)中分配了相同的路徑,Host11發(fā)出的流到Host2路徑中有兩個(gè)S11-S4-S6-S2和S11-S4-S3-S2,作為等價(jià)路徑且路徑跳數(shù)一樣,控制器選擇其中一條路徑作為流轉(zhuǎn)發(fā)規(guī)則下放至交換機(jī)。
表1 最短路策略路徑分配
表2 K 最短路徑策略路徑分配
經(jīng)過上述3次實(shí)驗(yàn),結(jié)合最短路策略和K 最短路由策略所分配的路徑,我們以Host12作為接受端來測量對比分析Host1發(fā)送數(shù)據(jù)的時(shí)延。
圖4是在數(shù)量流傳輸過程中,時(shí)延是數(shù)據(jù)從Host1發(fā)出開始到Host12返回的ACK 包所經(jīng)歷的時(shí)間,在剛開始時(shí)由于要尋找路徑時(shí)延的花費(fèi)比較大隨后時(shí)延趨于穩(wěn)定,在45s時(shí)刻大量的數(shù)據(jù)流注入OpenFlow 網(wǎng)絡(luò),基于最短路徑的策略不可避免的出現(xiàn)了擁塞,流傳輸?shù)牟环€(wěn)定以及丟包會導(dǎo)致時(shí)延增大,基于K 最短路徑策略在能夠?qū)⒘髁烤峙浣o路徑,時(shí)延在那一時(shí)刻之后趨近平穩(wěn)。
圖4 最短路策略和K 最短路由策略時(shí)延對比
圖5可以看出,在開始階段K 最短路徑路由策略比最短路徑策略的帶寬利用率高,原因從路徑分配表就可以看出,前期由于流量的平穩(wěn)傳輸,帶寬利用率趨近平穩(wěn),但在45s時(shí)刻大量的數(shù)據(jù)流注入OpenFlow 網(wǎng)絡(luò),基于最短路徑策略的流傳輸集中的4條鏈路出現(xiàn)了大量的丟包,網(wǎng)絡(luò)的帶寬利用率沒有發(fā)生明顯的變化,基于K 最短路徑策略通過流均衡算法對流量均衡分配給K 條路徑,網(wǎng)絡(luò)帶寬利用率較大提高,同時(shí)網(wǎng)絡(luò)吞吐量也得到提高。
圖5 最短路策略和K 最短路由策略帶寬利用率對比
本文提出了一種參照路徑帶寬利用率的K 最短路徑策略,基于Floodlight集中控制交換機(jī)的思想對該策略進(jìn)行實(shí)現(xiàn)。設(shè)計(jì)基于Floodlight控制器的多路徑路由策略,充分利用控制器全局可見、集中控制特點(diǎn),通過統(tǒng)計(jì)網(wǎng)絡(luò)流量并分析網(wǎng)絡(luò)鏈路狀態(tài)來均衡鏈路負(fù)載、創(chuàng)建轉(zhuǎn)發(fā)策略,提高網(wǎng)絡(luò)服務(wù)性能。并通過基于Mininet的實(shí)驗(yàn)平臺搭建仿真平臺,對比了控制器原有的最短路徑路由和參照網(wǎng)絡(luò)狀態(tài)的多路徑路由在網(wǎng)絡(luò)拓?fù)涞男Ч?。通過實(shí)驗(yàn)驗(yàn)證,參照路徑帶寬利用率的K 最短多路徑策略能夠提高網(wǎng)絡(luò)資源的整體利用率,從而提高網(wǎng)絡(luò)的整體性能。
[1]ZUO Qingyun,CHEN Ming,ZHAO Guangsong,et al.OpenFlow-based SDN technologies [J].Journal of Software,2013,24 (5):1078-1097 (in Chinese). [左青云,陳鳴,趙廣松,等.基于Open Flow 的SDN 技術(shù)研究 [J].軟件學(xué)報(bào),2013,24 (5):1078-1097.]
[2]ZHANG Jin.Design and implementation of resources allocation in Openflow network [D].Beijing:Beijing University of Posts and Telecommunications,2013:10-22 (in Chinese). [張瑾.OpenFlow 網(wǎng)絡(luò)中資源分配的研究與實(shí)現(xiàn) [D].北京:北京郵電大學(xué),2013:10-22.]
[3]Floodlight.[EB/OL].[2014-06-20].http://www.projectfloodlight.org/floodlight/.
[4]NOX.[EB/OL].[2014-04-12].http://www.noxrepo.org/.
[5]McKeown N,Anderson T,Balakrishnan H,et al.Open-Flow:Enabling innovation in campus networks [J].ACM SIGCOMM Computer Communication Review,2008,38 (2):69-74.
[6]OpenFlow Switch Specication Version 1.3.1[EB/OL].https://www.opennetworking.org/sdn-resources/onf-specifications,2012.
[7]LIU Chunjia.Design and implementation of an OpenFlow-based link load balancing mechanism [D].Beijing:University of Chinese Academy of Sciance,2013:31-40 (in Chinese). [劉 春佳.一種基于OpernFlow 的鏈路負(fù)載均衡機(jī)制的設(shè)計(jì)與實(shí)現(xiàn)[D].北京:中國科學(xué)院大學(xué),2013:31-40.]
[8]YANG Xiaoqin,ZHANG Lifang,CAO Qinghuang,et al.Routing algorithm based on link bandwidth utilization rate[J].Journal of Computer Applications,2012,32 (9):2422-2425(in Chinese).[楊曉琴,章麗芳,曹慶皇,等.基于鏈路帶寬利用率的路由選擇算法 [J].計(jì)算機(jī)應(yīng)用,2012,32 (9):2422-2425.]
[9]Schmidt RdO,Sadre R,Sperotto A,et al.Lightweight Link dimensioning using sFlow sampling [C]//Proceedings of the 9th International Conference on Network and Services Management,2013.
[10]Host sFlow [EB/OL]. [2014-07-10].http://sourceforge.net/projects/host-sflow/.
[11]sFlow RT [EB/OL].[2014-09-27].http://www.inmon.com/products/sFlow-RT.php.
[12]Yinglin SNJ.K constrained shortest paths problem [J].China Management Studies,2009,1:3.
[13]MAO Shaowu,ZHANG Huanguo,HUANG Chongchao,et al.A new fault-tolerance mechanism in communications based on K shortest path algorithm [J].Journal of Wuhan University,2013,59 (6):534-538 (in Chinese).[毛少武,張煥國,黃崇超,等.改進(jìn)的K 最短路徑算法在通信網(wǎng)絡(luò)中的應(yīng)用 [J].武漢大學(xué)學(xué)報(bào),2013,59 (6):534-538.]
[14]LONG Hui.Research on the OpenFlow-based load-balancing routing in distributed networks[D].Shanghai:Shanghai Jiao Tong University,2013:43-47 (in Chinese). [龍慧.基于OpenFlow 的分布式網(wǎng)絡(luò)中負(fù)載均衡路由的研究 [D].上海:上海交通大學(xué),2013:43-47.]
[15]Mininet.[EB/OL].[2014-02-15].http://mininet.org/.
[16]Bob Lantz BH,Nick McKeown.A network in a laptop:Rapid prototyping for software-defined networks [C]//Proceedings of the 9th ACM SIGCOMM Workshop on Hot Topics in Networks.ACM,2010.