馬曉航,廖靈霞,李 智,2,秦 斌,趙涵捷
(1.桂林電子科技大學(xué)電子工程與自動化學(xué)院,廣西桂林 541004;2.桂林航天工業(yè)學(xué)院電子信息和自動化學(xué)院,廣西桂林 541004;3.臺灣東華大學(xué)電機(jī)工程系,臺灣花蓮 974301;4.桂林航天工業(yè)學(xué)院信息中心,廣西桂林 541004)
(?通信作者電子郵箱liaolx@guat.edu.cn)
近年來,互聯(lián)網(wǎng)技術(shù)的快速發(fā)展導(dǎo)致用戶數(shù)量激增,網(wǎng)絡(luò)環(huán)境日益復(fù)雜,合理地利用網(wǎng)絡(luò)資源成為保證網(wǎng)絡(luò)性能的關(guān)鍵;但傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)將控制功能和轉(zhuǎn)發(fā)功能緊密耦合,缺乏統(tǒng)一的標(biāo)準(zhǔn)構(gòu)建全局網(wǎng)絡(luò)視圖,導(dǎo)致網(wǎng)絡(luò)性能的管理和資源的優(yōu)化困難。軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)的出現(xiàn)為解決這一問題提供了新的思路[1]。
SDN 是斯坦福大學(xué)Cleanslate 研究組提出的一種新型網(wǎng)絡(luò)結(jié)構(gòu)[2]。如圖1所示,SDN由應(yīng)用層、控制層和數(shù)據(jù)層組成,實現(xiàn)了控制與轉(zhuǎn)發(fā)功能的分離??刂茖油ㄟ^南向接口(OpenFlow 協(xié)議[3])構(gòu)建的控制通道與數(shù)據(jù)層交互,為數(shù)據(jù)層的OpenFlow 交換機(jī)創(chuàng)建和更新轉(zhuǎn)發(fā)規(guī)則(流表項)。SDN 通過控制層的控制器實現(xiàn)了全網(wǎng)視圖的維護(hù)和資源調(diào)度[4]。
圖1 SDN架構(gòu)Fig.1 SDN architecture
SDN 交換機(jī)本身沒有控制功能,當(dāng)新數(shù)據(jù)流到達(dá)交換機(jī)時,交換機(jī)沒有轉(zhuǎn)發(fā)規(guī)則指導(dǎo)該流的轉(zhuǎn)發(fā),所以,交換機(jī)會將該流的數(shù)據(jù)包封裝成Packet-in指令通過控制通道轉(zhuǎn)發(fā)到控制器,由控制器創(chuàng)建流表項并封裝成Packet-out 下發(fā)到交換機(jī);交換機(jī)再根據(jù)下發(fā)的流表項完成轉(zhuǎn)發(fā),并將流表項保存到流表中指導(dǎo)該流后續(xù)包的轉(zhuǎn)發(fā)。
SDN 流表項的創(chuàng)建特點(diǎn)決定了流表項的配置和管理是SDN性能和資源管理優(yōu)化的關(guān)鍵。流表項的超時時間決定了流表資源的利用率和網(wǎng)絡(luò)的轉(zhuǎn)發(fā)延時。由于存儲SDN 流表的三元內(nèi)容可尋址存儲器(Ternary Content-Addressable Memories,TCAM)耗電量大、價格昂貴,SDN 交換機(jī)的TCAM容量有限。為了提高TCAM 的利用率,SDN 流表項在流表中設(shè)置有生存時間,稱為超時時間。OpenFlow 協(xié)議定義了兩種流表項超時方式:硬超時(hard-timeout)和空閑超時(idletimeout),并通過控制器對超時進(jìn)行配置。給定一個超時時間,硬超時和空閑超時分別比較流表項在流表的存在時間和空閑時間,當(dāng)超過設(shè)定值時,流表項失效[5-6]。較短的超時時間能及時刪除不用的流表項,減小交換機(jī)內(nèi)存的消耗,但會使控制器和交換機(jī)頻繁交互,消耗大量控制帶寬,增大網(wǎng)絡(luò)的轉(zhuǎn)發(fā)延時,降低網(wǎng)絡(luò)的整體性能;較長的超時時間減少了控制器和交換機(jī)的交互,降低了數(shù)據(jù)包的轉(zhuǎn)發(fā)延時,但可能導(dǎo)致完成轉(zhuǎn)發(fā)使命的流表項滯留,占用交換機(jī)的內(nèi)存,甚至導(dǎo)致流表溢出。提升流表容量能在一定程度上緩解此問題,但交換機(jī)內(nèi)存價格昂貴,提升空間有限[7],因此,優(yōu)化超時時間對SDN 性能和資源優(yōu)化有著重要意義。
當(dāng)前SDN 控制器一般將流表項設(shè)置為固定的空閑超時,很容易造成資源的浪費(fèi),甚至影響網(wǎng)絡(luò)性能,改進(jìn)方法是對超時時間進(jìn)行動態(tài)調(diào)節(jié)。調(diào)節(jié)方法大致可分為兩類:一類是基于預(yù)測算法的動態(tài)調(diào)節(jié);另一類基于網(wǎng)絡(luò)實時信息的動態(tài)調(diào)節(jié)。
文獻(xiàn)[8]通過AR 算法預(yù)測每條流數(shù)據(jù)包的到達(dá)時間;文獻(xiàn)[9]通過二次移動平均算法預(yù)測下個周期增加的流表項數(shù)目;文獻(xiàn)[10]采用指數(shù)平滑法預(yù)測下一周期中可能新增的流表項數(shù)量。上述方法通過統(tǒng)計分析采樣周期內(nèi)的數(shù)據(jù),預(yù)測下一周期可能出現(xiàn)的狀況,及時調(diào)節(jié)流表項的超時時間,預(yù)留足夠的流表空間,減少交換機(jī)和控制器之間的交互,降低了控制通道負(fù)載。文獻(xiàn)[11]通過收集數(shù)據(jù)流的信息對數(shù)據(jù)流進(jìn)行分類,對不同的類型的數(shù)據(jù)流分配不同的超時時間;文獻(xiàn)[12]提出一種IHTA 超時算法,該算法基于數(shù)據(jù)包的到達(dá)時間,為不同的數(shù)據(jù)流設(shè)置不同超時時間;文獻(xiàn)[13]引入資源偏好度,根據(jù)當(dāng)前網(wǎng)絡(luò)資源的占用率安排超時時間;文獻(xiàn)[14]通過獲取流表項匹配次數(shù)和生存時間動態(tài)調(diào)節(jié)超時時間。上述方法主要通過對網(wǎng)絡(luò)資源使用的監(jiān)測,實現(xiàn)對超時時間的調(diào)節(jié),雖然對SDN 性能在一定程度上進(jìn)行了優(yōu)化,但是預(yù)測算法大多比較復(fù)雜,實現(xiàn)難度較高,而基于網(wǎng)絡(luò)實時信息的動態(tài)調(diào)節(jié)則需要對網(wǎng)絡(luò)的實時監(jiān)控,加大了控制器開銷。并且,上述研究只考慮了流表資源和控制通道帶寬占用率的優(yōu)化,未引入其它影響SDN性能的關(guān)鍵指標(biāo),如大象流的偵測精度。
大象流是數(shù)據(jù)中心中只占數(shù)據(jù)流量總數(shù)10%卻消耗90%帶寬的數(shù)據(jù)流,其余的流稱為老鼠流。當(dāng)多個大象流共享相同的鏈路時,會造成網(wǎng)絡(luò)擁堵[15]。及時偵測大象流,為大象流分配合理的路徑,能避免擁塞、降低網(wǎng)絡(luò)能耗[16]。大象流的偵測精度是SDN性能的重要指標(biāo)之一[17-18]。
當(dāng)前的研究通常采用基于數(shù)據(jù)流統(tǒng)計的偵測方案。文獻(xiàn)[19]通過控制器輪詢保存在交換機(jī)流表項的數(shù)據(jù)流統(tǒng)計信息,當(dāng)某條數(shù)據(jù)流統(tǒng)計的數(shù)據(jù)量超過設(shè)定閾值時,將該數(shù)據(jù)流判定為大象流;但由于統(tǒng)計信息數(shù)據(jù)量大,將統(tǒng)計信息從交換機(jī)傳輸?shù)娇刂破飨拇罅康目刂仆ǖ缼挕N墨I(xiàn)[20]中基于改進(jìn)的OpenFlow 協(xié)議提出DevoFlow 模型,通過監(jiān)視交換機(jī)的數(shù)據(jù)偵測大象流;但該方法需要特定的硬件設(shè)備支持,難以普及,且頻繁的交換機(jī)與控制器交互占用大量的控制通道帶寬。文獻(xiàn)[21]使用LightGBM 算法識別大象流,引入了聚焦損失函數(shù),并使用多個門限將流劃分多個類別;但統(tǒng)計數(shù)據(jù)精度要求高,可能增加交換機(jī)和控制器額外通信。
本文考慮通過交換機(jī)轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包識別大象流,提出一種動態(tài)混合超時的SDN 三目標(biāo)聯(lián)立優(yōu)化方案,創(chuàng)新性地采用超時方式和超時時間的雙維度動態(tài)調(diào)節(jié),實現(xiàn)對大象流偵測精度、流表項存活數(shù)和控制通道帶寬占用率三目標(biāo)優(yōu)化,綜合提升SDN性能。本文的主要工作如下:
1)針對大象流偵測精度、流表項存活數(shù)和控制通道帶寬占用率三個優(yōu)化目標(biāo)建立了優(yōu)化模型,使用NSGA-Ⅱ算法求解Pareto前沿(Pareto Frontiers)。
2)設(shè)計了兩種超時時間的動態(tài)調(diào)節(jié)方法,對比靜態(tài)超時并分析性能,在此基礎(chǔ)上結(jié)合硬超時和空閑超時的特點(diǎn),提出了混合超時。
3)評估了混合超時下靜態(tài)和兩種動態(tài)調(diào)節(jié)的敏感性,使用貝葉斯多目標(biāo)優(yōu)化算法和補(bǔ)充特定點(diǎn)的方法提高Pareto Frontiers 的質(zhì)量,目前貝葉斯多目標(biāo)優(yōu)化求解尚未被用于求解SDN性能優(yōu)化問題。
本文考慮一個帶內(nèi)的SDN 系統(tǒng),通過動態(tài)調(diào)節(jié)流表項的超時方式和超時時間大小對大象流的偵測精度、控制通道帶寬的占用率和交換機(jī)內(nèi)存消耗進(jìn)行三目標(biāo)聯(lián)立優(yōu)化??紤]帶內(nèi)SDN 系統(tǒng)是因為帶內(nèi)系統(tǒng)的控制信息和業(yè)務(wù)信息共享相同的鏈路,控制通道的帶寬消耗增大會降低數(shù)據(jù)傳輸?shù)目捎脦?,引發(fā)網(wǎng)絡(luò)擁堵。表1為本文優(yōu)化模型所使用的參數(shù)。
表1 優(yōu)化模型參數(shù)描述Tab.1 Optimization model parameter description
大象流偵測精度可由精確率Acc(Accuracy)和召回率Rec(Recall)表示。精確率是正確偵測的大象流數(shù)占偵測為大象流數(shù)的比例,召回率是正確偵測大象流數(shù)占實際大象流數(shù)的比例。由于大象流是造成網(wǎng)絡(luò)擁堵的主要原因,識別出更多的大象流至關(guān)重要,即召回率優(yōu)先于精確率。本文將大象流偵測遺漏R作為大象流偵測精度衡量指標(biāo),則:
其中:FN是標(biāo)記為大象流而預(yù)測為老鼠流的流數(shù),可表示為,即給定一個數(shù)據(jù)流fi,當(dāng)其為大象流(標(biāo)記flagfi=1)但偵測結(jié)果G(Pi)=0 時,r的值為1,否則為0。Pi為數(shù)據(jù)流fi轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)量,包括第一個數(shù)據(jù)包(數(shù)據(jù)流的第一個數(shù)據(jù)包必須被轉(zhuǎn)發(fā))和后續(xù)被轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包大小,可表示為式(2)。
其中:lij表示數(shù)據(jù)流fi的第j個數(shù)據(jù)包的大??;aij表示該第j個數(shù)據(jù)包是否被轉(zhuǎn)發(fā),可表示為式(3)。
其中:ti_update表示數(shù)據(jù)流fi的流表項更新時間,受超時方式的影響,當(dāng)超時方式為硬超時時,ti_update的值為tik,數(shù)據(jù)流上一個被轉(zhuǎn)發(fā)到控制器的包的時間戳;超時方式為空閑超時時,ti_update的值為ti(j-1)。ti(j-1)_effective表示包pij到達(dá)交換機(jī)時,數(shù)據(jù)流fi流表項的超時時間,流表項超時時間在數(shù)據(jù)包pij通過之后更新。由于轉(zhuǎn)發(fā)的數(shù)據(jù)包需要使用OpenFlow 協(xié)議進(jìn)行封裝,實際計算中,lij大小要額外增加32 B(Packet-in 消息指定)。周期內(nèi)所通過的數(shù)據(jù)總量為P,是數(shù)據(jù)流fi所轉(zhuǎn)發(fā)的數(shù)據(jù)量Pi之和。
本文采用桂林航天工業(yè)學(xué)院數(shù)據(jù)中心實時抓捕的流量數(shù)據(jù)為數(shù)據(jù)集,總時長約345 s,包含571 009條數(shù)據(jù)流,7 974 581個數(shù)據(jù)包。其中,數(shù)據(jù)總量超過10 KB 持續(xù)時間超過1 s 的數(shù)據(jù)流標(biāo)記為大象流[22]。通過分析,該數(shù)據(jù)集約8.51%的大象流數(shù)據(jù)包數(shù)小于10,97.02%的老鼠流數(shù)據(jù)包數(shù)小于10,85.03%的老鼠流數(shù)據(jù)包數(shù)小于5。因此本文通過多次測試,將大象流的偵測模型確定為轉(zhuǎn)發(fā)數(shù)據(jù)量超過2 KB,轉(zhuǎn)發(fā)的包數(shù)超過5 個的數(shù)據(jù)流。該模型在超時時間為0.2 s 時對大象流偵測硬超時有約85%的精確率和90%的召回率,空閑超時有約78%的精確率和80%的召回率。由此可見,當(dāng)使用轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包偵測大象流時,流表項的超時方式和超時大小對大象流的偵測的精確率和召回率影響很大。
控制通道帶寬占用率bu是控制通道傳輸鏈路上實際消耗的帶寬與總帶寬之比。讓bwt表示單位時間控制通道通過的數(shù)據(jù)量均值,bc為控制通道最大帶寬設(shè)為125 MB,則:
由于流表內(nèi)存所使用的TCAM 資源昂貴,減少流表項的存活數(shù)可以降低TCAM 的消耗。流表項溢出問題對網(wǎng)絡(luò)性能影響極大,因此本文將偵測周期內(nèi)流表項的最大存活數(shù)作為交換機(jī)內(nèi)存消耗的衡量指標(biāo)。給定大象流偵測周期為T,T內(nèi)流表項的存活數(shù)目為E,參數(shù)Ei為數(shù)據(jù)流fi的流表項在t時刻存活情況,0 表示流表項已超時,1 表示流表項有效,則流表項的存活數(shù)為∑fi∈FEi,而Ei有:
綜上所述,本優(yōu)化問題可模型化為:
即通過調(diào)節(jié)流表項超時時間tij_effective,最小化大象流偵測遺漏、控制通道帶寬消耗和交換機(jī)內(nèi)存消耗,提高帶內(nèi)SDN 系統(tǒng)的綜合性能。通過式(1)、(3)可得,超時時間tij_effective越小,目標(biāo)R越??;通過式(3)、(4)可得,超時時間tij_effective越大,目標(biāo)bu越??;通過式(5)可得,超時時間tij_effective越小,目標(biāo)E越小。因此,三個優(yōu)化目標(biāo)之間相互沖突。
本文通過統(tǒng)計捕獲數(shù)據(jù)流信息得到,52 089 條大象流和452 140 條老鼠流的數(shù)據(jù)包平均時間間隔在0~10 s,分別占大象流總數(shù)的91%和老鼠流總數(shù)的88%,因此本文將超時時間的數(shù)值限制在(0,10),并采用NSGA-Ⅱ算法求解該優(yōu)化問題的近似Pareto Frontiers。
當(dāng)超時時間在0~10 s 內(nèi)以極小的步長變化時,優(yōu)化問題的解空間非常大,遍歷算法耗時長,因此,本文采用NSGA-Ⅱ算法對優(yōu)化問題進(jìn)行近似求解。NSGA-Ⅱ使用帶精英策略遺傳,擁有復(fù)雜性低、運(yùn)行速度快等優(yōu)點(diǎn)[23]。
使用NSGA-Ⅱ算法求解主要包括以下幾個步驟:首先確定種群規(guī)模并隨機(jī)產(chǎn)生初始父群;然后對初代父群的個體按非支配關(guān)系排序,再通過選擇、交叉、變異等遺傳算子,生成子代種群,混合父群和子群生成新的種群,對種群中個體按非支配關(guān)系排序,并按個體支配數(shù)分級;最后根據(jù)分級排序結(jié)果順序選擇,生成新一代父群;重復(fù)上述操作直到達(dá)到最大迭代次數(shù)[24-25]。
本文將超時時間作為染色體,每一個染色體即為一個種群個體,設(shè)置初值種群規(guī)模為30,即NSGA-Ⅱ在約束范圍內(nèi)隨機(jī)生成30個超時時間,如0.942 198 s等。本文讓交叉算子以隨機(jī)方式選擇均值或均差方式生成新染色體,再以隨機(jī)方式賦予某個個體新的數(shù)值的方式產(chǎn)生變異。NSGA-Ⅱ在每次迭代中將超時時間以染色體的形式輸入,計算在給定超時時間下優(yōu)化目標(biāo)的目標(biāo)值,并在目標(biāo)空間坐標(biāo)系中用點(diǎn)表示。NSGA-Ⅱ?qū)δ繕?biāo)空間的多點(diǎn)進(jìn)行擁擠度計算后完成非支配排序,最后生成Pareto Frontiers[26],流程如圖2所示。
圖2 NSGA-Ⅱ求解優(yōu)化問題的流程Fig.2 NSGA-Ⅱflowchart to solve optimization problem
NSGA-Ⅱ算法在求解優(yōu)化目標(biāo)的Pareto Frontiers 有很大的隨機(jī)性,可能導(dǎo)致對解空間的探索不夠,生成的Pareto Frontiers 質(zhì)量較差,部分Pareto Frontiers 較短。雖然該問題能通過增加種群規(guī)模和迭代次數(shù)改善,但這種改善非常有限,且需要耗費(fèi)大量時間。針對此問題,本文通過求解特定超時時間和采用貝葉斯多目標(biāo)優(yōu)化算法的方法對Pareto Frontiers 進(jìn)行完善。本文使用文獻(xiàn)[27]中的貝葉斯多目標(biāo)優(yōu)化的最新程序。貝葉斯多目標(biāo)優(yōu)化算法基于目標(biāo)函數(shù)建模的思想,通過貝葉斯網(wǎng)絡(luò)概率模型反映可行解的分布。與NSGA-Ⅱ算法相比,貝葉斯優(yōu)化算法能更快更好地逼近Pareto Frontiers[28]。
求解過程中,流表項有靜態(tài)和動態(tài)兩種調(diào)節(jié)方式:靜態(tài)調(diào)節(jié)是指流表項的超時時間大小設(shè)定后不再變化,即在流的持續(xù)時間內(nèi)不對超時時間大小做調(diào)整;動態(tài)調(diào)節(jié)則是超時時間的大小會在流持續(xù)時間的不同階段動態(tài)調(diào)整。
靜態(tài)調(diào)節(jié)是當(dāng)前運(yùn)用最廣泛的超時時間設(shè)置方式,該方式通過控制器為交換機(jī)的所有流表項配置統(tǒng)一的超時方式和時間,配置完成后不作調(diào)整。這種調(diào)節(jié)方式簡單,但是缺乏靈活性,不能合理地配置資源。本文通過NSGA-Ⅱ算法,得到靜態(tài)調(diào)節(jié)下兩種超時方式的Pareto Frontiers,如圖3。
圖3(a)顯示了采用硬超時和空閑超時對大象流偵測遺漏和帶寬占用率的Pareto Frontiers。盡管兩個Pareto Frontiers 交叉在一起也可以看到硬超時在局部更靠近原點(diǎn),所以硬超時方式會優(yōu)于空閑超時方式。圖3(b)中空閑超時方式生成的Pareto Frontiers 比硬超時方式生成的靠近原點(diǎn),說明在降低流表項存活數(shù)和控制通道帶寬消耗上空閑超時優(yōu)于硬超時。
圖3 靜態(tài)調(diào)節(jié)下兩種超時方式的Pareto FrontiersFig.3 Pareto Frontiers of two timeout methods under static adjustment
動態(tài)調(diào)節(jié)指在流持續(xù)時間內(nèi)動態(tài)調(diào)節(jié)超時時間的大小。該策略基于大象流持續(xù)時間長、老鼠流持續(xù)時間短的基本思想,一般在數(shù)據(jù)流到達(dá)前期設(shè)置一個較短的超時時間,增加轉(zhuǎn)發(fā)的控制器的數(shù)據(jù)包,提升大象流的偵測精度;在偵測出該數(shù)據(jù)流為大象流后,調(diào)整為較長超時時間,降低帶寬的占用率,同時也要盡可能地減少流表項的存活數(shù),避免流表溢出情況的發(fā)生。
對于偵測出大象流后超時時間的動態(tài)調(diào)節(jié),本文設(shè)計了兩種調(diào)節(jié)方法:方差均值(ave_sig)法和翻倍(multiple)法。
方差均值法是在偵測出該數(shù)據(jù)流為大象流前,對數(shù)據(jù)包時間戳統(tǒng)計,計算數(shù)據(jù)包間隔時間的均值和方差;在偵測出大象流后,將超時時間調(diào)整為均值與方差之和。用NSGA-Ⅱ求解該調(diào)節(jié)方式下優(yōu)化目標(biāo)的Pareto Frontiers,并與靜態(tài)調(diào)節(jié)方式對比,得到圖4。
圖4 方差均值動態(tài)超時調(diào)節(jié)方式下硬超時與空閑超時Pareto FrontiersFig.4 Pareto Frontiers of hard-timeout and idle-timeout under ave_sig dynamic timeout adjustment method
當(dāng)采用硬超時,圖4(a)中的動態(tài)超時的Pareto Frontiers與靜態(tài)調(diào)節(jié)交錯,在優(yōu)化目標(biāo)側(cè)重于大象流偵測時優(yōu)于靜態(tài)調(diào)節(jié);圖4(b)中動態(tài)調(diào)節(jié)的效果甚至比靜態(tài)調(diào)節(jié)要更差。但采用空閑超時,圖4(a)和(b)中針對兩個優(yōu)化目標(biāo)的Pareto Frontiers 都有了明顯的改善。由于均值與方差之和在正態(tài)分布圖中可表示大概率發(fā)生事件,即設(shè)置的超時時間大概率大于數(shù)據(jù)流包的達(dá)到時間間隔,因此,采用空閑超時能降低流表項存活的概率,減少了控制通道帶寬占用;但硬超時沒有此效果,甚至還會因為時間設(shè)置不合理,既增加了控制通道帶寬占用,也未能降低流表項的存活數(shù)。
翻倍法是在偵測出某條數(shù)據(jù)流為大象流后,每當(dāng)數(shù)據(jù)包到達(dá)控制器,則將該數(shù)據(jù)流流表項的超時時間調(diào)節(jié)為原來的倍數(shù),本文設(shè)置為1.2倍,得到圖5。
圖5 翻倍動態(tài)超時調(diào)節(jié)方式下硬超時與空閑超時的Pareto FrontiersFig.5 Pareto Frontiers of hard-timeout and idle-timeout under multiple dynamic timeout adjustment method
通過對比圖5(b)中的Pareto Frontiers 可以看到,針對降低流表項存活數(shù)和控制通道帶寬占用這兩個優(yōu)化目標(biāo),空閑超時的效果要強(qiáng)于硬超時;但針對大象流偵測和控制通道占用的優(yōu)化上,硬超時要略強(qiáng)于空閑超時,如圖5(a)所示??傮w而言,翻倍法對三個優(yōu)化目標(biāo)的Pareto Frontiers都有明顯的改善,其原因在于翻倍法在偵測出大象流后,對超時時間進(jìn)行延長,所以能在不影響低大象流的偵測精度的前提下相對延長流表項的存活時間,減少控制通道帶寬的消耗;而且因為倍數(shù)較小,對周期內(nèi)的最大存活數(shù)增加較小。
本文嘗試將超時時間調(diào)節(jié)更高的倍數(shù),但提升效果不明顯,在增加到2 倍后,Pareto Frontiers 基本無變化,且增加較多的有效時間會導(dǎo)致流表溢出,因此不建議調(diào)節(jié)過高倍數(shù)。
對比上述靜態(tài)和動態(tài)調(diào)節(jié)方式下兩種超時方式的效果,空閑超時方式的優(yōu)化效果總體上要強(qiáng)于硬超時,但靜態(tài)調(diào)節(jié)和翻倍動態(tài)調(diào)節(jié)中針對大象流偵測遺漏和帶寬占用率的優(yōu)化中,硬超時方式的優(yōu)化效果要略強(qiáng)于空閑超時。這是因為硬超時方式可以相對增加流表項的失效次數(shù),增大轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包,從而提高大象流的偵測精度,同時也能減少一定的交換機(jī)內(nèi)存;而空閑超時方式相對延長了流表項的存活時間,降低轉(zhuǎn)發(fā)次數(shù),減少帶寬使用的同時不利于大象流的偵測精度。
本文針對兩種超時方式對三個優(yōu)化目標(biāo)產(chǎn)生的不同影響,結(jié)合二者的特性,提出了一種混合超時方式(mixedtimeout)。
混合超時方式是將默認(rèn)超時狀態(tài)設(shè)為硬超時,增加轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包,提升大象流偵測精度,減少流表項存活數(shù)。若該數(shù)據(jù)流被偵測為大象流,則調(diào)節(jié)超時方式為空閑超時,相對延長流表項存活時間,降低控制通道帶寬占用率。該超時方式的超時時間調(diào)節(jié)也分為靜態(tài)調(diào)節(jié)和動態(tài)調(diào)節(jié)。
通過上文對動態(tài)調(diào)節(jié)和靜態(tài)的對比分析,動態(tài)調(diào)節(jié)的效果要優(yōu)于靜態(tài)調(diào)節(jié),因此本文提出將動態(tài)調(diào)節(jié)與混合超時結(jié)合,對流表項的超時方式和超時時間進(jìn)行雙維度動態(tài)調(diào)節(jié)。在數(shù)據(jù)流前期,為硬超時設(shè)置更短的超時時間,盡可能增加流表項的超時和轉(zhuǎn)發(fā)到控制器的數(shù)據(jù)包;偵測出大象流后,調(diào)整為空閑超時,并適當(dāng)?shù)匮娱L超時時間,降低控制通道帶寬和流表項的存活數(shù)。
沿用上述實測的數(shù)據(jù)集,采用Python 語言編寫仿真程序?qū)?shù)據(jù)集進(jìn)行回放仿真。本文將先分析靜態(tài)混合超時的效果,再對比靜態(tài)混合與動態(tài)混合超時,最后對比動態(tài)混合超時與另兩種超時方式動態(tài)調(diào)節(jié)的效果。
圖6為靜態(tài)調(diào)節(jié)下三種超時方式的效果對比。圖6(a)中混合超時對大象流的偵測精度和控制通道帶寬占用的優(yōu)化效果要明顯優(yōu)于其他兩種方式;圖6(b)中混合超時對交換機(jī)流表項存活數(shù)與控制通道帶寬占用的優(yōu)化優(yōu)于硬超時,但基本與空閑超時相同。
圖6 靜態(tài)調(diào)節(jié)下三種超時方式的Pareto FrontiersFig.6 Pareto Frontiers of three timeout methods under static adjustment
圖7 為靜態(tài)混合超時和動態(tài)混合超時下兩種超時時間調(diào)節(jié)方式的對比。通過圖7 對比,采用翻倍法的動態(tài)混合超時的效果在三目標(biāo)優(yōu)化中都要優(yōu)于靜態(tài)混合超時,而采用方差均值法也僅在優(yōu)化目標(biāo)側(cè)重于控制通道帶寬占用率時,優(yōu)化效果遜色于靜態(tài)混合超時。
圖7 動態(tài)混合超時與靜態(tài)混合超時的Pareto FrontiersFig.7 Pareto Frontiers of dynamic mixed timeout and static mixed timeout
圖8 顯示了采用方差均值調(diào)節(jié)法下三種超時方式的Pareto Frontiers。圖8(a)中,空閑超時的優(yōu)化效果要略優(yōu)于混合,但混合超時在優(yōu)化目標(biāo)側(cè)重大象流偵測遺漏時有優(yōu)于空閑超時的趨勢;圖8(b)中混合超時與空閑超時的優(yōu)化效果基本相同。
圖8 方差均值動態(tài)超時調(diào)節(jié)方式下三種超時方式的Pareto FrontiersFig.8 Pareto Frontiers of three timeout methods under ave_sig dynamic timeout adjustment method
圖9 顯示了采用翻倍調(diào)節(jié)法下三種超時方式的Pareto Frontiers。其中,混合超時在圖9(a)中優(yōu)于硬超時和空閑超時,在圖9(b)中,混合超時的優(yōu)化效果優(yōu)于硬超時,與空閑超時效果幾乎相同。所以,混合超時的綜合優(yōu)化效果要優(yōu)于另外兩種超時方式。
圖9 翻倍動態(tài)超時調(diào)節(jié)方式下三種超時方式的Pareto FrontiersFig.9 Pareto Frontiers of three timeout methods under multiple dynamic timeout adjustment method
綜上,動態(tài)混合超時通過對流表項的超時時間和超時方式進(jìn)行雙維度動態(tài)調(diào)節(jié),有效提高了大象流的偵測精度,降低了控制通道帶寬的占用率和交換機(jī)的內(nèi)存,避免了因流表項存活數(shù)過多而出現(xiàn)溢出的情況。動態(tài)混合超時的雙維度調(diào)節(jié)方式對優(yōu)化網(wǎng)絡(luò)性能有顯著提升。
本節(jié)以給定初值下不同優(yōu)化目標(biāo)值為基準(zhǔn),測試了混合超時調(diào)節(jié)方式下不同時間段的超時時間初值增加一倍時優(yōu)化目標(biāo)的變化率,如圖10 中0.000 01 s 的變化率表示優(yōu)化目標(biāo)初值為0.000 01 s 和初值為0.000 02 s 的比值,分析了不同優(yōu)化目標(biāo)在不同階段對超時時間初值的敏感性,結(jié)果如圖10。
1)大象流偵測遺漏的敏感性:由于混合超時將數(shù)據(jù)流的初始超時設(shè)置為硬超時,當(dāng)識別該流為大象流時,調(diào)節(jié)超時方式為空閑超時,并動態(tài)調(diào)節(jié)超時時間,即偵測精度只與超時時間初值有關(guān),因此圖中靜態(tài)、方差均值和翻倍法的變化率完全相同。由圖10 可知,當(dāng)初始時間較小時,偵測遺漏的敏感性很低,變化率趨于不變,但超出0.004 s 后明顯上升,并在0.1 s附近敏感性最高。
2)帶寬占用率的敏感性:從圖10 可知,帶寬占用率的敏感性對超時時間初值變化的敏感性不高,方差均值和翻倍法的敏感性幾乎相同,即使初值超過4 s,變化率也能保持在0.9左右。而靜態(tài)調(diào)節(jié)的敏感性相對較高初值超過4 s,變化率達(dá)到了0.7。
圖10 混合超時敏感性分析Fig.10 Mixed timeout sensitivity analysis
3)流表項存活數(shù)的敏感性:流表項的存活數(shù)受初值的變化影響較高,翻倍法和靜態(tài)調(diào)節(jié)在初值超過0.004 s 時,變化率都有明顯的上升,初值超過4 s 后,變化率維持在1.4 左右。方差均值法雖然在初值小于0.4 s 時的敏感性不高,但超過0.4 s 后,變化率顯著增加,在初值4 s 時超過了翻倍法和靜態(tài)調(diào)節(jié)。
本文通過貝葉斯多目標(biāo)優(yōu)化求解三目標(biāo)聯(lián)立優(yōu)化問題的Pareto Frontiers,并將得到的解集與原解集混合,再混合特定超時時間初始值下的解,并對新的解集進(jìn)行了篩選,生成了新的Pareto Frontiers。圖11 顯示了翻倍法下的動態(tài)混合超時的解集完善情況,圖中●表示靜態(tài)的混合超時,▲和◆分別表示采用方差均值法和翻倍法的動態(tài)混合超時,形狀相同的空心圖形分別表示貝葉斯多目標(biāo)優(yōu)化得到的解集,和×分別表示特定點(diǎn)補(bǔ)充的靜態(tài)、方差均值法和翻倍法的圖形。
圖11 動態(tài)混合超時與靜態(tài)混合超時的Pareto Frontiers(優(yōu)化后)Fig.11 Pareto Frontiers of dynamic mixed timeout and static mixed timeout(after improvement)
混合貝葉斯和特定點(diǎn)后的Pareto Frontiers 更長且更靠近原點(diǎn),質(zhì)量得到很大的改進(jìn)。進(jìn)一步說明,動態(tài)混合調(diào)節(jié)方式,特別是采用翻倍法的動態(tài)混合調(diào)節(jié)法對優(yōu)化目標(biāo)最為有效,也驗證了貝葉斯和特定點(diǎn)的補(bǔ)充對Pareto Frontiers的有非常好的改善效果。
NSGA-Ⅱ在一次迭代中的步驟包括非支配排序、擁擠度計算和排序,對應(yīng)最壞情況的復(fù)雜度分別是O(MN2)、O(MNlogN)和O(NlogN),因此NSGA-Ⅱ算法的總體復(fù)雜度由非支配排序主導(dǎo)為O(MN2),其中:M為目標(biāo)函數(shù)個數(shù),N為種群規(guī)模[29],本文將N設(shè)為30;貝葉斯多目標(biāo)優(yōu)化算法與NSGA-Ⅱ相似,每次迭代通過貝葉斯網(wǎng)絡(luò)、擁擠度計算和非支配排序求解下一代種群,算法的復(fù)雜度由非支配排序主導(dǎo)為O(MN2),本文將貝葉斯多目標(biāo)優(yōu)化的種群規(guī)模設(shè)置30[27];計算特定點(diǎn)的算法,僅需要將超時時間代入依次求解,計算復(fù)雜度為O(MN),本文在0.001 s 到10 s 范圍內(nèi)生成了15 個特定點(diǎn),即N為15,因此對優(yōu)化目標(biāo)求解的整體復(fù)雜度為O(MN2),M為目標(biāo)函數(shù)個數(shù),N為種群規(guī)模。綜上,使用貝葉斯多目標(biāo)優(yōu)化算法和指定特定點(diǎn)對NSGA-Ⅱ算法得到的Pareto Frontiers改進(jìn)的方式?jīng)]有增加求解的復(fù)雜度。
由于本優(yōu)化問題的三個優(yōu)化目標(biāo)之間相互沖突,本文僅分析了三個優(yōu)化目標(biāo)之間的影響,以及如何調(diào)節(jié)流表項超時時間達(dá)到對三個優(yōu)化目標(biāo)的同時優(yōu)化。具體如何設(shè)置流表項的超時時間大小,需要在今后的研究中根據(jù)不同的場景進(jìn)行討論。
本文根據(jù)SDN 的三個性能指標(biāo),建立了數(shù)學(xué)模型,提出了通過動態(tài)調(diào)節(jié)流表項的超時方式和超時時間大小對大象流的偵測精度、控制通道帶寬的占用率和交換機(jī)內(nèi)存消耗進(jìn)行三目標(biāo)聯(lián)立優(yōu)化問題。對比流表項現(xiàn)有的兩種超時方式的特點(diǎn),提出了一種混合超時方式,并與動態(tài)調(diào)節(jié)超時時間大小相結(jié)合,雙維度動態(tài)調(diào)節(jié)流表項。本文設(shè)計了兩種動態(tài)調(diào)節(jié)方案,通過NSGA-Ⅱ算法進(jìn)行問題的求解,并針對Pareto Frontiers 質(zhì)量不高的問題,通過貝葉斯多目標(biāo)優(yōu)化算法和補(bǔ)充特定點(diǎn),改進(jìn)了Pareto Frontiers。結(jié)果表明動態(tài)混合超時能有效改善大象流偵測精度、控制通道帶寬占用和交換機(jī)內(nèi)存消耗的問題。
但是本文實驗所使用識別大象流的模型相對簡單,精度上有很大的提升空間;流表項的超時時間調(diào)節(jié)方法也相對簡單,缺乏對數(shù)據(jù)流本身特性的針對性;對優(yōu)化目標(biāo)求得解集的精度和分布也有待改善。下一步工作中,將對多目標(biāo)求解方法進(jìn)行相應(yīng)研究,著手提高大象流識別模型的精度,使其能適應(yīng)多變的網(wǎng)絡(luò)環(huán)境,然后分析對比多種數(shù)據(jù)流的特性,設(shè)計新的超時時間調(diào)節(jié)方案。