朱金奇 , 孫華志 , 黃永鑫 , 劉 明

1(天津師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,天津 300387)

2(電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,四川 成都 611731)

軟件定義網(wǎng)絡(luò)(software defined networking,簡(jiǎn)稱SDN)是一種把控制平面和數(shù)據(jù)平面分離在不同設(shè)備上實(shí)現(xiàn)的新型網(wǎng)絡(luò)架構(gòu)[1].在控制層,控制器通過在數(shù)據(jù)平面上建立路由轉(zhuǎn)發(fā)規(guī)則,對(duì)數(shù)據(jù)平面提供集中和靈活的控制,掌握全局網(wǎng)絡(luò)信息;在數(shù)據(jù)層,交換機(jī)根據(jù)轉(zhuǎn)發(fā)規(guī)則進(jìn)行數(shù)據(jù)流轉(zhuǎn)發(fā).由于網(wǎng)絡(luò)中數(shù)據(jù)流的動(dòng)態(tài)性[2]、流量負(fù)載轉(zhuǎn)移、網(wǎng)絡(luò)維護(hù)[3]等原因,數(shù)據(jù)平面的狀態(tài)需要不斷更新來(lái)避免次優(yōu)路徑可能導(dǎo)致網(wǎng)絡(luò)擁塞.這里,數(shù)據(jù)平面的狀態(tài)指決定交換機(jī)如何轉(zhuǎn)發(fā)數(shù)據(jù)包的轉(zhuǎn)發(fā)規(guī)則集合.控制器則以推送轉(zhuǎn)發(fā)規(guī)則到交換機(jī)流表的形式來(lái)響應(yīng)諸如流量強(qiáng)度變化、來(lái)自主機(jī)的新連接等事件,以達(dá)到各種網(wǎng)絡(luò)性能需求,如負(fù)載均衡和資源的高效利用.因此,路由更新(網(wǎng)絡(luò)更新)能夠極大地改善網(wǎng)絡(luò)的性能,提高網(wǎng)絡(luò)資源的利用率[4].

路由更新過程包括控制平面的路由選擇和數(shù)據(jù)平面的交換機(jī)流表更新兩部分.由于路由更新的速度決定了控制器的靈活性,因而成為眾多網(wǎng)絡(luò)應(yīng)用的重要指標(biāo).已有大多數(shù)路由更新相關(guān)研究[4,5]根據(jù)網(wǎng)絡(luò)當(dāng)前數(shù)據(jù)流狀況(如流的數(shù)量、網(wǎng)絡(luò)中流的總大小)為數(shù)據(jù)流計(jì)算新路由,接著利用各種路由更新調(diào)度算法,把數(shù)據(jù)平面從當(dāng)前路由配置更新到新配置.如文獻(xiàn)[5]把網(wǎng)絡(luò)中所有數(shù)據(jù)流分成最小數(shù)量的集合,并在每輪更新一個(gè)集合中的數(shù)據(jù)流來(lái)避免網(wǎng)絡(luò)擁塞.Jin 等人[4]則把各交換機(jī)流表更新調(diào)度操作之間的依賴關(guān)系建立一個(gè)全網(wǎng)的更新調(diào)度圖,接著動(dòng)態(tài)調(diào)度不同交換機(jī)上的更新操作,以降低路由更新延遲.然而,由于現(xiàn)有相關(guān)工作沒有關(guān)注控制平面的路由選擇對(duì)路由更新速度的影響,導(dǎo)致路由更新延遲較長(zhǎng).當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí),更新延遲增加現(xiàn)象尤為明顯.例如,在一個(gè)中等規(guī)模的數(shù)據(jù)中心網(wǎng)絡(luò)中,對(duì)于由40 個(gè)服務(wù)器組成的機(jī)架,到達(dá)交換機(jī)的流量達(dá)到75KB～100KB 流量/min[6].假設(shè)某交換機(jī)需要更新8KB 數(shù)據(jù)流的路由(僅僅是一小部分),其更新延遲取決于需要更新的總的轉(zhuǎn)發(fā)規(guī)則數(shù)量和TCAM 更新操作(插入或修改)的速度兩部分.通過對(duì)當(dāng)今商用交換機(jī)進(jìn)行測(cè)試,每個(gè)插入和修改TCAM 流表的操作大約需要5ms 和11ms[4].對(duì)于上述實(shí)例,如果插入和修改操作分別為4KB,則交換機(jī)轉(zhuǎn)發(fā)規(guī)則更新所需時(shí)間至少為60s.文獻(xiàn)[2,6]通過對(duì)不同的數(shù)據(jù)中心進(jìn)行測(cè)試,得到網(wǎng)絡(luò)中的數(shù)據(jù)流具有如下特性:1)超高80%的數(shù)據(jù)流持續(xù)時(shí)間不超過10s;2)僅有低于0.1%的數(shù)據(jù)流持續(xù)時(shí)長(zhǎng)超過200s;3)數(shù)據(jù)流中超過50%的字節(jié)持續(xù)時(shí)間低于25s.根據(jù)這些特性可知,如果全網(wǎng)路由更新所需時(shí)間過長(zhǎng),由于部分?jǐn)?shù)據(jù)流已經(jīng)終止且新的數(shù)據(jù)流產(chǎn)生,更新后的傳輸路徑可能變得無(wú)效.為此得出:實(shí)時(shí)快速的路由更新是提升SDN 性能的關(guān)鍵,是網(wǎng)絡(luò)必須的.路由更新速度快,將有助于提高網(wǎng)絡(luò)性能.然而,實(shí)時(shí)路由更新策略的設(shè)計(jì)具有如下挑戰(zhàn):1)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能動(dòng)態(tài)變化,并且網(wǎng)絡(luò)中不斷有來(lái)自主機(jī)新的傳輸請(qǐng)求,造成網(wǎng)絡(luò)中的數(shù)據(jù)流動(dòng)態(tài)變化;2)各交換機(jī)執(zhí)行更新操作的速度存在差別,另外,各交換機(jī)開始執(zhí)行更新的時(shí)間不同,這可能造成鏈路擁塞;3)滿足實(shí)時(shí)更新的需求,在更新延遲容忍值內(nèi)完成路由更新操作.

事實(shí)上,路由選擇和交換機(jī)流表調(diào)度更新均對(duì)更新延遲具有重要影響.當(dāng)控制器更新的數(shù)據(jù)流數(shù)量較多時(shí),盡管路由已經(jīng)是最佳了,更新延遲仍較大;相反地,若需要更新的數(shù)據(jù)流少,更新延遲則大為降低.也就是說,網(wǎng)絡(luò)路由更新延遲和數(shù)據(jù)流路徑優(yōu)化之間存在折中.為此,與現(xiàn)有研究不同,本文提出延遲滿足的路由選擇和調(diào)度更新策略(delay satisfied route selection and updating scheme,簡(jiǎn)稱DSRSU),同時(shí)從路徑選擇優(yōu)化和流表調(diào)度更新兩方面考慮來(lái)滿足SDN 實(shí)時(shí)路由更新的要求.路由選擇階段,只選擇部分?jǐn)?shù)據(jù)流進(jìn)行路由更新,根據(jù)鏈路剩余容量和網(wǎng)絡(luò)路由更新的延遲容忍值T0共同決定選擇哪部分?jǐn)?shù)據(jù)流進(jìn)行路徑更新,并確定這些數(shù)據(jù)流的目標(biāo)路徑.路由更新階段,首先建立全網(wǎng)更新調(diào)度圖;接著,根據(jù)更新調(diào)度圖挖掘數(shù)據(jù)流更新之間的依賴關(guān)系,從而建立更新關(guān)系圖;最后,根據(jù)更新關(guān)系圖確定交換機(jī)執(zhí)行數(shù)據(jù)流更新的先后順序,以在滿足路由更新延遲容忍值基礎(chǔ)上進(jìn)一步加快路由更新的速度.大量實(shí)驗(yàn)仿真結(jié)果表明,與現(xiàn)有的幾種路由更新策略相比,DSRSU 不僅能夠極大地降低路由更新的延遲,同時(shí)能夠?qū)崿F(xiàn)與對(duì)比策略類似的網(wǎng)絡(luò)性能.本文創(chuàng)新性如下:

?提出SDN 路由更新延遲和數(shù)據(jù)流路由優(yōu)化之間存在折中,因此僅更新部分?jǐn)?shù)據(jù)流的路由來(lái)滿足數(shù)據(jù)流實(shí)時(shí)路由更新要求的思想;

?提出路由更新過程要保證擁塞避免、丟包避免、數(shù)據(jù)包一致性和實(shí)時(shí)路由更新的要求;

?在路由選擇階段,根據(jù)鏈路剩余容量和路由更新的延遲容忍值共同決定更新數(shù)據(jù)流集,在實(shí)現(xiàn)實(shí)時(shí)路由更新的同時(shí),保證鏈路負(fù)載均衡;

?路由更新過程通過建立更新關(guān)系圖挖掘數(shù)據(jù)流更新間的依賴關(guān)系,使無(wú)依賴數(shù)據(jù)流的更新操作盡量并行執(zhí)行,以進(jìn)一步降低路由更新的延遲,保證實(shí)時(shí)路由更新.

1 相關(guān)工作

SDN 中,由于網(wǎng)絡(luò)的動(dòng)態(tài)性,控制器需要頻繁更新數(shù)據(jù)平面以提高網(wǎng)絡(luò)性能.近些年,很多研究者提出了不同的路由更新策略以實(shí)現(xiàn)各種網(wǎng)絡(luò)性能優(yōu)化目標(biāo).根據(jù)優(yōu)化目標(biāo)的不同,已有路由更新策略可以分為兩類.

?第1 類策略以路由更新過程數(shù)據(jù)包一致性保證、丟包避免、更新過程擁塞避免為主要目的.

如Wang 等人[7]對(duì)SDN 網(wǎng)絡(luò)更新可能引起的若干問題如數(shù)據(jù)包不一致、鏈路擁塞等進(jìn)行了綜述,并給出了針對(duì)各問題的幾種現(xiàn)有解決方案.在保證數(shù)據(jù)包一致性方面,文獻(xiàn)[8]介紹了一致性網(wǎng)絡(luò)更新的概念,并確定了兩個(gè)不同的一致性等級(jí):每個(gè)包和每個(gè)流.接著提出兩階段提交協(xié)議以保證數(shù)據(jù)包的一致性,每個(gè)數(shù)據(jù)包或者按照更新前的路徑傳輸,或者根據(jù)更新后的路徑在網(wǎng)絡(luò)中傳輸直到目的地.然而這種方式中,舊轉(zhuǎn)發(fā)規(guī)則的數(shù)據(jù)包處理完畢后新規(guī)則的數(shù)據(jù)包才開始處理,引起交換機(jī)的空間被占用,產(chǎn)生較高的處理成本.文獻(xiàn)[9]給出一種openflow 協(xié)議來(lái)保證路由更新過程中數(shù)據(jù)包一致性,該協(xié)議通過確保任何時(shí)間交換機(jī)上只有一組路由轉(zhuǎn)發(fā)規(guī)則集合存在來(lái)節(jié)省交換機(jī)的資源,尤其是TCAM 的空間.然而,由于該協(xié)議執(zhí)行完一組轉(zhuǎn)發(fā)規(guī)則后再開始執(zhí)行下一組轉(zhuǎn)發(fā)規(guī)則,造成路由更新速度慢.Katta 等人[10]提出一種遺傳算法來(lái)降低路由更新中對(duì)內(nèi)存的需求,保持?jǐn)?shù)據(jù)包的一致性.該算法把新的路由轉(zhuǎn)發(fā)規(guī)則分成一個(gè)個(gè)的分片,將轉(zhuǎn)發(fā)規(guī)則更新分成多輪進(jìn)行,每一輪更新一個(gè)分片.通過增加分片的數(shù)量,可以降低交換機(jī)的存儲(chǔ)開銷,但卻增加了路由更新延遲.文獻(xiàn)[11]討論了能夠?qū)崿F(xiàn)并行和穩(wěn)健轉(zhuǎn)發(fā)規(guī)則實(shí)施的分布式控制平面.作者首先引入描述數(shù)據(jù)平面和控制平面交互的形式化模型;接著,系統(tǒng)地闡述并發(fā)網(wǎng)絡(luò)轉(zhuǎn)發(fā)規(guī)則更新的一致化問題.另外,在保證擁塞避免、丟包避免等方面,文獻(xiàn)[12]認(rèn)為,路由更新應(yīng)保證鏈路不擁塞和回路避免,即數(shù)據(jù)包在網(wǎng)絡(luò)傳輸中不應(yīng)該出現(xiàn)回路.該文研究了虛擬機(jī)場(chǎng)景下的轉(zhuǎn)發(fā)規(guī)則更新算法,該算法可以確保在更新過程中擁有足夠的帶寬,同時(shí)不會(huì)影響到其他流的正常轉(zhuǎn)發(fā).Liu 等人[13]提出了異步交換機(jī)和網(wǎng)絡(luò)流量動(dòng)態(tài)變化下的擁塞避免網(wǎng)絡(luò)更新機(jī)制zUpdate,以避免更新過程中鏈路擁塞和數(shù)據(jù)包丟失.Mizrahi 等人[14]介紹了利用準(zhǔn)確時(shí)間協(xié)調(diào)網(wǎng)絡(luò)更新的方法Time4,文中定義了一組稱為流交換的更新場(chǎng)景,在這些場(chǎng)景中,Time4 具有比已有路由更新方法更低的數(shù)據(jù)包丟失率.

?第2 類策略的主要目標(biāo)是降低路由更新的延遲.

Hong 等人[5]通過分流來(lái)最大限度地減小無(wú)擁塞更新的延遲.他們把路由更新問題轉(zhuǎn)化為線性規(guī)劃問題,提出在多項(xiàng)式時(shí)間內(nèi)解決該問題,并分析了路由更新的延遲上限.文獻(xiàn)[4]描述了SDN 中快速、一致性更新的Dionysus 系統(tǒng),該系統(tǒng)把各交換機(jī)流表更新調(diào)度操作之間的依賴關(guān)系建立一個(gè)全網(wǎng)的更新調(diào)度圖;然后,為每個(gè)更新操作節(jié)點(diǎn)計(jì)算關(guān)鍵路徑長(zhǎng)度;然后,根據(jù)各更新操作節(jié)點(diǎn)關(guān)鍵路徑長(zhǎng)度值的大小動(dòng)態(tài)調(diào)度不同交換機(jī)上的路由更新操作,以降低路由更新延遲.文獻(xiàn)[15]介紹了 TIMEFLIPs 方法實(shí)現(xiàn)準(zhǔn)確的基于時(shí)間的路由更新.TIMEFLIPs 利用TCAM 條目中的時(shí)間戳區(qū)域?qū)崿F(xiàn),不僅可以用來(lái)完成Atomic Bundle 更新,而且能夠以較高的精度實(shí)現(xiàn)網(wǎng)絡(luò)更新.然而上述工作僅僅依據(jù)網(wǎng)絡(luò)當(dāng)前工作量,把網(wǎng)絡(luò)從當(dāng)前路由更新到目標(biāo)路由配置.盡管試圖提高路由更新的速度,但由于交換機(jī)基于TCMA 進(jìn)行流表更新的操作速度慢、更新數(shù)據(jù)流數(shù)量大等原因,仍可能造成路由更新的延遲較長(zhǎng).此外,Xu 等人在文獻(xiàn)[16]中首次提出了更新部分?jǐn)?shù)據(jù)流以保證路由更新延遲時(shí)間約束的思想.文中介紹了兩種算法以實(shí)現(xiàn)實(shí)時(shí)路由更新.然而他們把數(shù)據(jù)流實(shí)時(shí)路由更新問題轉(zhuǎn)化為線性規(guī)劃問題,這將導(dǎo)致所提算法更新速度慢且不適用于具有數(shù)據(jù)流數(shù)量大的大型網(wǎng)絡(luò).此外,為防止鏈路陷入擁塞,該文在為數(shù)據(jù)流分配新的路由后,并不回收原來(lái)路徑上該數(shù)據(jù)流占用的鏈路資源,造成鏈路容量的浪費(fèi)和信道利用率低下.

2 網(wǎng)絡(luò)模型和問題描述

2.1 網(wǎng)絡(luò)模型

一個(gè)典型的SDN 由兩種類型的設(shè)備組成:一臺(tái)控制器和若干臺(tái)交換機(jī).整個(gè)網(wǎng)絡(luò)的拓?fù)錇镚=(V,E).其中,V={v1,v2,…,vn}是交換機(jī)的集合,vi代表第i個(gè)交換機(jī),n=|V|;E是連接交換機(jī)之間鏈路的集合.令當(dāng)前網(wǎng)絡(luò)中所有數(shù)據(jù)流的集合為T={r1,r2,…,rm},m=|T|是數(shù)據(jù)流的總數(shù)量.假設(shè)任一數(shù)據(jù)流r從入口交換機(jī)(ingress switch)開始直到被傳輸給出口交換機(jī)(egress switch).假設(shè)當(dāng)交換機(jī)為數(shù)據(jù)流r建立流表項(xiàng)后,交換機(jī)就能統(tǒng)計(jì)流r的大小.通過收集流量統(tǒng)計(jì)信息,控制器了解數(shù)據(jù)流r的大小S(r).與已有研究類似[5,8],為簡(jiǎn)單起見,令每個(gè)流在網(wǎng)絡(luò)中只選擇一條路徑進(jìn)行數(shù)據(jù)傳輸.對(duì)于數(shù)據(jù)流r,設(shè)當(dāng)前路由為Pc(r),更新的目標(biāo)路徑為Pd(r).此外,當(dāng)數(shù)據(jù)流到達(dá)交換機(jī)時(shí),如果有匹配的流表項(xiàng)則按流表項(xiàng)進(jìn)行轉(zhuǎn)發(fā);否則,交換機(jī)把數(shù)據(jù)包頭報(bào)告給控制器,再由控制器決定此數(shù)據(jù)流的路由,并在該路徑的所有交換機(jī)上為此數(shù)據(jù)流建立流表項(xiàng).

2.2 TCAM更新時(shí)間模型

文獻(xiàn)[4]表明,若所有流表項(xiàng)具有相同優(yōu)先級(jí),則插入或修改流表項(xiàng)的延遲與需要插入或修改流表項(xiàng)的數(shù)量幾乎成線性關(guān)系.然而很多實(shí)際應(yīng)用中,大多數(shù)數(shù)據(jù)流具有不同的優(yōu)先級(jí)[17].另外,某些應(yīng)用把數(shù)據(jù)流分為微流和宏流規(guī)則方案[18],并對(duì)宏流(又稱為大象流)賦予較高優(yōu)先級(jí),對(duì)微流(老鼠流)賦予較低優(yōu)先級(jí).由于本文只選擇一些大象流進(jìn)行路由更新,我們假設(shè)這些大象流具有獨(dú)特的優(yōu)先級(jí).此時(shí),對(duì)交換機(jī)流表項(xiàng)的插入/修改操作認(rèn)為一個(gè)常數(shù)[16].令ti和tm分別表示插入和修改一個(gè)流表項(xiàng)操作所需的時(shí)間,通過對(duì)實(shí)際交換機(jī)進(jìn)行測(cè)試,得出tm≈11ms,tm>ti[4],因?yàn)樾薷牧鞅眄?xiàng)涉及插入新流表項(xiàng)和刪除舊流表項(xiàng)兩種操作.用t(s,Pc(r),Pd(r))表示為了把流r的路徑更新到目標(biāo)路徑Pd(r),對(duì)交換機(jī)s流表項(xiàng)的操作延遲.我們有:

2.3 問題描述

SDN 中,路由更新的速度通常決定了控制器的靈活性,因而成為眾多網(wǎng)絡(luò)應(yīng)用的重要指標(biāo).路由更新速度慢,意味著發(fā)生網(wǎng)絡(luò)丟包和鏈路擁塞的時(shí)間較長(zhǎng),這嚴(yán)重影響網(wǎng)絡(luò)性能.現(xiàn)有大多數(shù)路由更新方法[5,10,13]是靜態(tài)的,即提前計(jì)算好各數(shù)據(jù)流路徑更新的順序,路由更新過程中按照此順序進(jìn)行轉(zhuǎn)發(fā)規(guī)則更新.然而此方法很難適應(yīng)網(wǎng)絡(luò)中數(shù)據(jù)流的動(dòng)態(tài)變化和不同交換機(jī)執(zhí)行轉(zhuǎn)發(fā)規(guī)則更新的時(shí)間差異,造成路由更新的速度慢和更新的不一致性.由于交換機(jī)硬件上的差異、CPU 負(fù)載的不同以及控制器進(jìn)行遠(yuǎn)程過程調(diào)度RPC 的時(shí)間可變性,網(wǎng)絡(luò)中不同交換機(jī)執(zhí)行轉(zhuǎn)發(fā)規(guī)則更新的時(shí)間差異是普遍存在的.為此,某些系統(tǒng)[4,19]根據(jù)當(dāng)前工作量進(jìn)行動(dòng)態(tài)路由更新,以快速適應(yīng)網(wǎng)絡(luò)中不斷變化的數(shù)據(jù)強(qiáng)度.如文獻(xiàn)[19]提出了頻繁的網(wǎng)絡(luò)更新,以實(shí)現(xiàn)快速路由更新并獲得高效的網(wǎng)絡(luò)利用率.文獻(xiàn)[4]的Dionysus 方法根據(jù)流表更新調(diào)度操作間的依賴關(guān)系動(dòng)態(tài)調(diào)度不同交換機(jī)上的路由更新操作,加快路由更新速度.然而由于需要更新的數(shù)據(jù)量可能較大,上述路由更新的延遲仍然可能較長(zhǎng).Xu 等人[16]提出,當(dāng)需要更新的數(shù)據(jù)流總量為40KB 時(shí),利用文獻(xiàn)[4]的方法進(jìn)行路由更新的延遲接近65s.這對(duì)于許多網(wǎng)絡(luò)應(yīng)用是不能容忍的.為進(jìn)一步降低路由更新的延遲,Xu 等人提出僅更新部分?jǐn)?shù)據(jù)流以保證路由更新延遲時(shí)間的約束.文中介紹了兩種算法以保證路由更新延遲不超過設(shè)定的約束值.然而所提算法主要問題在于,首先,更新過程中為避免擁塞,為數(shù)據(jù)流分配新路徑后,并不回收原來(lái)路由上該數(shù)據(jù)流占用的鏈路資源,造成鏈路容量的嚴(yán)重浪費(fèi);其次,哪些數(shù)據(jù)流能夠并行執(zhí)行并不明確,影響路由更新的速度.

為此,本文提出延遲滿足的路由選擇和調(diào)度更新策略DSRSU,從路由選擇和路由更新調(diào)度兩方面聯(lián)合進(jìn)行優(yōu)化,爭(zhēng)取在滿足更新延遲容忍值前提下盡可能降低路由更新的延遲,保證實(shí)時(shí)路由更新.除實(shí)時(shí)路由更新的要求外,路由更新過程還需滿足以下條件.

1)鏈路擁塞避免:路由更新要合理安排數(shù)據(jù)流調(diào)度更新的執(zhí)行順序,以保證到達(dá)鏈路的總流量低于鏈路容量.如圖1 所示,設(shè)每條鏈路的容量是10 單位,且每條數(shù)據(jù)流的大小在圖中進(jìn)行了標(biāo)記.控制器想把網(wǎng)絡(luò)從圖1(a)狀態(tài)更新為圖1(b)狀態(tài).如果控制器同時(shí)發(fā)送所有更新操作命令給交換機(jī),由于不同交換機(jī)執(zhí)行更新的時(shí)間不同及快慢不同,此策略可能造成某些鏈路擁塞.比如,當(dāng)交換機(jī)s4執(zhí)行更新r2之前,s3就執(zhí)行了更新r1,那么鏈路s1s4將擁塞.

2)丟包避免:交換機(jī)在轉(zhuǎn)發(fā)數(shù)據(jù)流過程中要盡量避免丟失數(shù)據(jù)包.

3)滿足一致性:數(shù)據(jù)流或者遵循舊的路由,或者遵循新路由進(jìn)行轉(zhuǎn)發(fā),而不能根據(jù)兩者的混合進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),否則會(huì)引起數(shù)據(jù)轉(zhuǎn)發(fā)的混亂.

Fig.1 Link congestion in route update圖1 路由更新中的鏈路擁塞

在路由更新發(fā)生時(shí),為實(shí)現(xiàn)丟包避免和數(shù)據(jù)包一致性,本文采取了與文獻(xiàn)[4,8,17]類似的兩階段提交方法來(lái)更新規(guī)則:第1 階段,當(dāng)需要更新某數(shù)據(jù)流的轉(zhuǎn)發(fā)規(guī)則時(shí),只有對(duì)相應(yīng)原數(shù)據(jù)流處理完畢的交換機(jī)才能進(jìn)行轉(zhuǎn)發(fā)規(guī)則更新或刪除;第2 階段,在數(shù)據(jù)流新路徑完全建立起來(lái)之后(新路徑上所有交換機(jī)均更新完畢后),才把數(shù)據(jù)流放在新路徑上傳輸.兩階段轉(zhuǎn)發(fā)的具體細(xì)節(jié),可詳見文獻(xiàn)[4,8].對(duì)于路由更新過程中如何避免擁塞和保證實(shí)時(shí)路由更新,是本文要研究的重要內(nèi)容,具體見下文.

3 DSRSU 的實(shí)現(xiàn)

為了達(dá)到網(wǎng)絡(luò)性能優(yōu)化和路由更新延遲間的折中,DSRSU 策略力圖從路徑選擇和交換機(jī)流表調(diào)度更新兩個(gè)方面來(lái)聯(lián)合優(yōu)化,實(shí)現(xiàn)實(shí)時(shí)路由更新.通常,路由更新中更新的數(shù)據(jù)流數(shù)量越多、更新的數(shù)據(jù)總量越大,路由更新調(diào)度的效果就越好.但更新的數(shù)據(jù)流數(shù)量大會(huì)造成非常大的更新延遲,難以滿足網(wǎng)絡(luò)實(shí)時(shí)路由更新要求.為實(shí)現(xiàn)實(shí)時(shí)路由更新,DSRSU 就需要合理設(shè)計(jì)路徑選擇和分配算法,確定更新的數(shù)據(jù)流集,通過更新部分?jǐn)?shù)據(jù)流盡量達(dá)到較好的路由更新效果.DSRSU 路徑選擇對(duì)路由更新調(diào)度的影響還表現(xiàn)在路徑選擇階段選擇的數(shù)據(jù)流數(shù)量越少,路由更新完成的速度越快.因此,在保證實(shí)時(shí)路由更新和較低網(wǎng)絡(luò)負(fù)載的同時(shí),路徑選擇和分配應(yīng)盡量減小更新數(shù)據(jù)流的數(shù)量,以進(jìn)一步加快路由更新調(diào)度的速度,降低路由更新調(diào)度延遲.下面首先描述如何通過路徑選擇和分配算法確定更新數(shù)據(jù)流集;接著,在路由選擇基礎(chǔ)上設(shè)計(jì)路由更新調(diào)度策略,把更新數(shù)據(jù)流集中的數(shù)據(jù)流更新到新路由的同時(shí)進(jìn)一步降低路由更新的延遲;然后描述路由更新調(diào)度算法;最后介紹更新調(diào)度中的循環(huán)問題,并給出了處理方法.

3.1 路徑的選擇和分配

路由選擇是DSRSU 的重要組成部分,在路由選擇過程中,為了實(shí)現(xiàn)實(shí)時(shí)路由更新和鏈路負(fù)載均衡,我們同時(shí)從鏈路的剩余容量和交換機(jī)的延遲容忍值T0兩個(gè)方面選擇網(wǎng)絡(luò)中數(shù)據(jù)流T的子集TU作為更新路徑集,并為其中每個(gè)數(shù)據(jù)流選擇一條可行路徑作為目標(biāo)路由.與已有工作[5]類似,設(shè)控制器預(yù)先為T中的每個(gè)數(shù)據(jù)流計(jì)算了一個(gè)可行路徑集,并始終從中選擇一條路徑作為該數(shù)據(jù)流的目標(biāo)傳輸路徑.如數(shù)據(jù)流r的可行路徑集為Pr,我們首先把集合T中所有流按由大到小順序排列成隊(duì)列Z;然后,TU的選擇和TU中數(shù)據(jù)流的目標(biāo)路徑分配算法偽代碼見算法1.具體過程描述如下.

步驟1:從隊(duì)頭中選擇數(shù)據(jù)流r,對(duì)Pr的每條路徑p,若用p上各鏈路e剩余容量的最小值代表其可用容量,則把Pr中的路徑按照可用容量由大到小進(jìn)行排列.

步驟2:從Pr中選擇可用容量最大的路徑(設(shè)為pm),判斷若為r分配pm作為目標(biāo)路徑Pd(r)時(shí),pm的可用容量是否滿足公式(2):若滿足,說明pm的所有鏈路都能包含流r,則轉(zhuǎn)入步驟3;若不滿足,說明Pr中其余路徑的可用容量也不能包含r,則r的路徑更新失敗,此時(shí)把r從Z中移入集合TN后,繼續(xù)選擇Z頭數(shù)據(jù)流重復(fù)步驟1.

其中,c(Pm)表示路徑pm的可用容量,s(r)是流r的大小,λ為鏈路負(fù)載因子.

步驟3:若步驟2 中pm的剩余容量能夠包含數(shù)據(jù)流r,則繼續(xù)判斷pm上每個(gè)交換機(jī)的更新延遲是否不大于更新延遲容忍值T0:若成立,則分配pm為r的目標(biāo)路徑Pd(r).如pm上交換機(jī)s更新延遲的判斷公式為

其中,Ts表示交換機(jī)s的更新延遲值;t(s,Pc(r),Pd(r))為交換機(jī)s更新Pc(r)為Pd(r)需要執(zhí)行的流表項(xiàng)操作所需時(shí)間,根據(jù)公式(1)選擇相應(yīng)的值.若r的路徑更新成功,則把數(shù)據(jù)流r放入集合TU,從集合Z中刪除流r并轉(zhuǎn)入步驟4;否則,認(rèn)為pm不可用,忽略Pr中可用容量最大的路徑,轉(zhuǎn)入執(zhí)行步驟2.

步驟4:更新路徑Pd(r)上各鏈路e的剩余容量和Pd(r)上所有交換機(jī)的更新延遲.若令l(e)表示Pd(r)上鏈路e的剩余容量,Ts為Pd(r)上交換機(jī)s的更新延遲,則l(e)和Ts分別更新為

步驟5:對(duì)于當(dāng)前路徑Pc(r)的每條鏈路,回收已分配給流r的容量,更新Pc(r)上各鏈路e′的剩余容量值為

步驟6:重復(fù)步驟1 到步驟5,直到網(wǎng)絡(luò)中各交換機(jī)的更新延遲均大于T0.

算法1.TU的選擇和數(shù)據(jù)流的目標(biāo)路徑分配.

3.2 動(dòng)態(tài)路由更新調(diào)度

3.2.1 為什么需要?jiǎng)討B(tài)更新調(diào)度

根據(jù)第3.1 節(jié)確定數(shù)據(jù)流的目標(biāo)路徑后,我們需要更新交換機(jī)的流表項(xiàng),把TU中的數(shù)據(jù)流從當(dāng)前路由更新為新路由.更新過程要保證鏈路不擁塞、丟包避免、數(shù)據(jù)包一致性,并盡量降低路由更新的延遲.第3.1 節(jié)的目標(biāo)路徑分配算法給定了路徑分配的順序,如果按照此順序更新數(shù)據(jù)流的路徑,即上一數(shù)據(jù)流的路徑更新完畢后控制器再給下一數(shù)據(jù)流目標(biāo)路徑上的交換機(jī)發(fā)送更新命令進(jìn)行流表調(diào)度更新,雖然可以保證更新過程中鏈路不擁塞,但卻導(dǎo)致路由更新的速度慢.例如,如圖2 所示,設(shè)每條鏈路的容量是10 單位,數(shù)據(jù)流r1的大小為5 單位,r2大小是6 單位,r3和r4的大小分別為7 單位和4 單位.假設(shè)按第3.1 節(jié)算法的順序進(jìn)行路由更新,更新順序?yàn)楦聄3→更新r2→更新r1→更新r4.這里,更新路徑包括建立新路徑并刪除舊路徑.控制器按照該順序發(fā)送更新指令,僅當(dāng)交換機(jī)完成上一路徑更新后,控制器才發(fā)送下一路徑更新命令.但從圖2 可知,交換機(jī)完成r3的更新后,控制器可發(fā)送操作指令進(jìn)行流r2的更新,并且在完成r2的路徑更新后,流r1的更新操作和r4的更新操作可并行進(jìn)行,并不會(huì)造成鏈路擁塞.相對(duì)于目標(biāo)路徑分配算法規(guī)定的更新順序,在保證鏈路不擁塞的前提下,交換機(jī)同時(shí)進(jìn)行多個(gè)數(shù)據(jù)流的更新可進(jìn)一步降低路由更新的延遲.為此,在滿足更新延遲容忍值基礎(chǔ)上進(jìn)一步降低路由更新的延遲,我們需要研究更加高效的更新調(diào)度方法.

Fig.2 Example of route update圖2 路由更新實(shí)例

3.2.2 建立更新調(diào)度圖

為了在路由更新延遲容忍值T0內(nèi)把TU中數(shù)據(jù)流的路徑更新為目標(biāo)路徑,同時(shí)盡量降低路由更新的延遲,就需要根據(jù)網(wǎng)絡(luò)狀況動(dòng)態(tài)地調(diào)度數(shù)據(jù)流的更新操作.我們用更新調(diào)度圖反映更新之間的依賴關(guān)系,保證路徑更新過程中擁塞避免.更新調(diào)度圖有兩種類型的節(jié)點(diǎn):資源節(jié)點(diǎn)和操作節(jié)點(diǎn).資源節(jié)點(diǎn)用方框表示,方框內(nèi)的數(shù)字代表該鏈路的可用剩余容量;操作節(jié)點(diǎn)用橢圓表示,代表數(shù)據(jù)流的更新操作(這里的更新操作包括建立新路由和刪除舊路由,涉及到數(shù)據(jù)流新路徑和舊路徑上所有交換機(jī),包括建立和修改轉(zhuǎn)發(fā)規(guī)則).更新調(diào)度圖中從某資源節(jié)點(diǎn)指向某操作節(jié)點(diǎn)的有向邊代表執(zhí)行該更新操作需要該鏈路資源,邊上的數(shù)字代表所需鏈路資源的數(shù)量.此時(shí),該操作節(jié)點(diǎn)稱為此資源節(jié)點(diǎn)的子節(jié)點(diǎn).而一條從操作節(jié)點(diǎn)指向資源節(jié)點(diǎn)的有向邊表示完成該更新操作能夠釋放的鏈路資源,有向邊上的數(shù)字為釋放的鏈路資源數(shù)量.此時(shí),該操作節(jié)點(diǎn)稱為此資源節(jié)點(diǎn)的父節(jié)點(diǎn).

我們通過圖3 來(lái)說明更新調(diào)度圖的建立過程.圖3(a)的狀態(tài)為當(dāng)前路由狀態(tài),圖3(b)的狀態(tài)是目標(biāo)路由狀態(tài).設(shè)每條鏈路的容量是10 單位,各數(shù)據(jù)流的大小在圖中進(jìn)行了標(biāo)記.根據(jù)圖3 中各數(shù)據(jù)流當(dāng)前占有鏈路資源和更新各流需要鏈路資源的情況,建立更新調(diào)度圖如圖3(c)所示.以其中流r1為例,把r1的路徑更新為目標(biāo)路徑需要鏈路S1-S5這5 單位的資源;此外,r1的路徑更新為目標(biāo)路徑后能夠分別釋放鏈路S4-S5及鏈路S1-S4各5 單位的鏈路資源.根據(jù)該更新調(diào)度圖容易看出:更新r3或更新r6執(zhí)行完成后才能執(zhí)行更新r2.另外,更新r1受限于流r2或r4更新執(zhí)行完成.如果交換機(jī)并行執(zhí)行更新r3、更新r6和更新r4,在流r3或r6之一更新完成后立即執(zhí)行更新r2,并且更新r2和更新r4的任意一個(gè)執(zhí)行完后馬上執(zhí)行更新r1.此時(shí),無(wú)論網(wǎng)絡(luò)中是否有交換機(jī)執(zhí)行流表更新的速度較慢,按照該順序調(diào)度路由更新操作,相對(duì)于第3.1 節(jié)的路徑更新順序,網(wǎng)絡(luò)路由更新的延遲降低了.在滿足更新延遲容忍值前提下,為任意類型的網(wǎng)絡(luò)拓?fù)鋱?zhí)行這樣的路由更新調(diào)度,進(jìn)一步加快路由更新的速度,是下面我們工作的目標(biāo).

Fig.3 Building update scheduling graph for updating from current state to target state圖3 從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)更新調(diào)度圖的建立

3.2.3 建立更新關(guān)系圖

我們用更新關(guān)系圖反映數(shù)據(jù)流更新間的依賴關(guān)系.對(duì)更新調(diào)度圖中每個(gè)資源節(jié)點(diǎn),若該資源節(jié)點(diǎn)存在子節(jié)點(diǎn),我們就對(duì)該資源節(jié)點(diǎn)進(jìn)行分析,挖掘其父節(jié)點(diǎn)與子節(jié)點(diǎn)間的更新依賴關(guān)系;然后,再對(duì)任一數(shù)據(jù)流進(jìn)行路由更新需要的所有資源節(jié)點(diǎn)進(jìn)行綜合,最終建立網(wǎng)絡(luò)中各數(shù)據(jù)流間的更新關(guān)系.以鏈路Sa-Sb和流r為例,設(shè)更新流r的路由需要鏈路資源Sa-Sb,則流r的更新依賴關(guān)系建立過程描述如下.

步驟1.

1)若Sa-Sb的剩余容量能夠滿足其所有子節(jié)點(diǎn)所需資源(大于所有子節(jié)點(diǎn)請(qǐng)求資源的總和),說明子節(jié)點(diǎn)的更新操作無(wú)需等待該資源,則此時(shí)建立Sa-Sb的父節(jié)點(diǎn)和子節(jié)點(diǎn)的更新關(guān)系如圖4(a)所示.

2)若Sa-Sb的剩余容量不能滿足所有子節(jié)點(diǎn)的資源需求,而存在鏈路Sa-Sb的某個(gè)父節(jié)點(diǎn)釋放的資源加上鏈路Sa-Sb的剩余資源大于等于該鏈路所有子節(jié)點(diǎn)請(qǐng)求資源的總和,表明資源節(jié)點(diǎn)Sa-Sb的子節(jié)點(diǎn)需要等待Sa-Sb的這個(gè)父節(jié)點(diǎn)執(zhí)行完成,則建立數(shù)據(jù)流之間的更新關(guān)系如圖4(b)所示.

3)若鏈路Sa-Sb的剩余容量不能滿足所有子節(jié)點(diǎn)的資源需求,但Sa-Sb的多個(gè)父操作節(jié)點(diǎn)釋放的資源總和加上該鏈路的剩余資源大于等于其所有子節(jié)點(diǎn)所需此鏈路資源的總和,則首先如圖4(c)所示把這些父節(jié)點(diǎn)連接起來(lái),再引入從連接之后的任一端節(jié)點(diǎn)分別指向此資源節(jié)點(diǎn)各子操作節(jié)點(diǎn)的有向邊.

4)若鏈路Sa-Sb的剩余容量不能滿足其所有子節(jié)點(diǎn)的資源需求,但存在Sa-Sb的多個(gè)父節(jié)點(diǎn)的組合,并且每個(gè)組合釋放的資源總和加上該鏈路的剩余資源大于等于其所有子節(jié)點(diǎn)請(qǐng)求該鏈路資源的總和,則此時(shí)首先計(jì)算各組合中父節(jié)點(diǎn)的總個(gè)數(shù)與該組合中每個(gè)父節(jié)點(diǎn)需求資源節(jié)點(diǎn)個(gè)數(shù)之和,然后選擇其中和最小的組合中的父節(jié)點(diǎn),把這些父節(jié)點(diǎn)連接起來(lái)后,引入端節(jié)點(diǎn)分別指向此資源節(jié)點(diǎn)各子節(jié)點(diǎn)的有向邊.選擇上述父節(jié)點(diǎn)的組合作為資源節(jié)點(diǎn)Sa-Sb所有子操作節(jié)點(diǎn)的父節(jié)點(diǎn)是因?yàn)楹妥钚≌f明子節(jié)點(diǎn)進(jìn)行更新操作需要依賴的操作節(jié)點(diǎn)數(shù)量越少,因此子節(jié)點(diǎn)就越容易盡早實(shí)現(xiàn)路徑更新.若有多個(gè)組合的上述和相同,則查看不同組合的父節(jié)點(diǎn)個(gè)數(shù),并直接選擇父節(jié)點(diǎn)個(gè)數(shù)最少的那個(gè)組合中的父節(jié)點(diǎn)為資源節(jié)點(diǎn)Sa-Sb所有子操作節(jié)點(diǎn)的父節(jié)點(diǎn).若父節(jié)點(diǎn)的個(gè)數(shù)仍相同,則查看不同組合父節(jié)點(diǎn)之間有無(wú)依賴關(guān)系,并選擇不依賴其他組合中節(jié)點(diǎn)的組合為資源節(jié)點(diǎn)Sa-Sb所有子操作節(jié)點(diǎn)的父節(jié)點(diǎn).如圖4(d)所示,流r1,r2和r3更新完成釋放的資源總和或更新r5完成釋放的鏈路資源均能滿足更新r4和更新r6所需資源,由于等待“更新r5”只需等待一個(gè)父節(jié)點(diǎn)執(zhí)行完成即可進(jìn)行流r4和r6的更新,因此最終選擇操作節(jié)點(diǎn)“更新r5”作為節(jié)點(diǎn)“更新r4”和“更新r6”的父節(jié)點(diǎn).同理,圖4(e)中,由于更新r1、更新r2和更新r3相比更新r2、更新r3和更新r4需要依賴的節(jié)點(diǎn)數(shù)量少(設(shè)更新r4需要的資源比更新r1的多),選擇“更新r1”、“更新r2”和“更新r3”為“更新r5”和“更新r6”的父節(jié)點(diǎn),把更新r1,r2和r3連接起來(lái)后,分別引入更新r3指向更新r5和更新r6的有向邊.

Fig.4 Build the relationship between the parent operation and the child operation for a resource node圖4 建立資源節(jié)點(diǎn)的父子操作間的關(guān)系

步驟2.對(duì)更新流r需要的所有其他鏈路資源進(jìn)行步驟1,建立其父節(jié)點(diǎn)和子節(jié)點(diǎn)之間的依賴關(guān)系.

步驟3.對(duì)于數(shù)據(jù)流r,對(duì)其目標(biāo)路徑Pd(r)的每條鏈路更新關(guān)系中涉及流r的部分進(jìn)行合并,即得到流r的更新關(guān)系.如圖5 中更新r6需要3 個(gè)資源節(jié)點(diǎn),對(duì)這3 個(gè)資源節(jié)點(diǎn)分別建立更新關(guān)系如圖5(a)～圖5(c),通過圖5(a)可知,更新r6依賴更新r1和更新r3執(zhí)行完成;圖5(b)表明,更新r6依賴更新r1釋放資源;圖5(c)中,更新r6需要等待更新r3及更新r4完成.合并圖5(a)～圖5(c),得到流r6的更新關(guān)系,從此更新關(guān)系可知,更新r6需依賴更新r1、更新r3和更新r4,即操作節(jié)點(diǎn)“更新r1”“更新r3”和“更新r4”是操作節(jié)點(diǎn)“更新r6”的父節(jié)點(diǎn).

Fig.5 Example of building updater relationship for the flow圖5 為流建立更新關(guān)系示例

對(duì)網(wǎng)絡(luò)中的每個(gè)流,按上述描述依次建立更新關(guān)系,即得全網(wǎng)數(shù)據(jù)流的更新關(guān)系圖.

3.2.4 實(shí)例描述

圖6 給出了根據(jù)更新調(diào)度圖為網(wǎng)絡(luò)中所有數(shù)據(jù)流建立更新關(guān)系圖的實(shí)例.根據(jù)第3.2.3 節(jié)描述的更新關(guān)系圖建立方法,根據(jù)圖6(a)的網(wǎng)絡(luò)更新調(diào)度圖,最終為流r1～r7建立數(shù)據(jù)流之間的更新關(guān)系如圖6(b)所示.對(duì)于數(shù)據(jù)流r3,從6(a)可見,更新r3既可依賴于流r4且流r8更新完成,又可依賴于r4且r5或r8且r5更新執(zhí)行完成.利用第3.2.3 節(jié)步驟1 的描述,由于更新r5依賴于更新r8,我們最終選擇更新r4和更新r8為操作節(jié)點(diǎn)更新r3的父節(jié)點(diǎn).

Fig.6 Example of building update dependency graph based on the update scheduling graph圖6 根據(jù)更新調(diào)度圖建立更新關(guān)系圖示例

3.3 更新調(diào)度過程

為了進(jìn)行路由更新,控制器首先根據(jù)數(shù)據(jù)流的更新關(guān)系圖,為每個(gè)需要更新的數(shù)據(jù)流建立更新操作優(yōu)先級(jí).在具體更新調(diào)度過程中,控制器根據(jù)各流的優(yōu)先級(jí)高低發(fā)送更新調(diào)度指令給交換機(jī).優(yōu)先級(jí)越高,相應(yīng)數(shù)據(jù)流路由更新操作執(zhí)行就越優(yōu)先.具體來(lái)說,控制器首先給優(yōu)先級(jí)最高的數(shù)據(jù)流目標(biāo)路徑上的所有交換機(jī)發(fā)送更新指令,讓相應(yīng)交換機(jī)執(zhí)行流表更新操作.若有多個(gè)數(shù)據(jù)流的更新優(yōu)先級(jí)相同,則控制器同時(shí)向它們的目標(biāo)路徑上的交換機(jī)發(fā)送流表更新指令.只有當(dāng)上一優(yōu)先級(jí)的流路徑更新操作全部完成后,控制器才發(fā)送下一優(yōu)先級(jí)數(shù)據(jù)流的更新指令.數(shù)據(jù)流更新優(yōu)先級(jí)的確定過程如下.

首先,沒有任何父節(jié)點(diǎn)的數(shù)據(jù)流更新操作優(yōu)先級(jí)為0(最高優(yōu)先級(jí),數(shù)字越大,優(yōu)先級(jí)就越低),僅依賴于優(yōu)先級(jí)0 的數(shù)據(jù)流更新操作的優(yōu)先級(jí)設(shè)為1.若要確定操作節(jié)點(diǎn)“更新r”的優(yōu)先級(jí),首先要確定其所有父節(jié)點(diǎn)的優(yōu)先級(jí).在所有父節(jié)點(diǎn)的優(yōu)先級(jí)確定后,依次查看其父節(jié)點(diǎn)的優(yōu)先級(jí),操作節(jié)點(diǎn)“更新r”的優(yōu)先級(jí)在其優(yōu)先級(jí)最低的父節(jié)點(diǎn)的優(yōu)先級(jí)的數(shù)字基礎(chǔ)上加1.例如,對(duì)于圖6(b),“更新r2”和“更新r7”不依賴于任何更新操作,因此,“更新r2”和“更新r7”的優(yōu)先級(jí)為0.由于“更新r1”僅依賴于“更新r2”執(zhí)行完成,可以確定“更新r1”的優(yōu)先級(jí)為1.同理,“更新r6”的優(yōu)先級(jí)也為1.由于“更新r1”的優(yōu)先級(jí)為1 且“更新r1”是“更新r4”的父節(jié)點(diǎn),因此,“更新r4”的優(yōu)先級(jí)是2.同理,“更新r8”的優(yōu)先級(jí)在“更新r4”的基礎(chǔ)上加1 是3,“更新r5”的優(yōu)先級(jí)為4,“更新r3”的優(yōu)先級(jí)是4.各數(shù)據(jù)流的更新操作優(yōu)先級(jí)見圖6(b).更新調(diào)度過程的偽代碼如算法2 所示.

算法2.更新調(diào)度.

3.4 處理循環(huán)

我們發(fā)現(xiàn),有些情況下,按照第3.2.3 節(jié)所述的方法建立更新關(guān)系圖,會(huì)造成因最終的數(shù)據(jù)流更新關(guān)系圖處理不當(dāng)而存在循環(huán).若更新關(guān)系圖存在循環(huán),就無(wú)法利用第3.3 節(jié)所述的方法確定數(shù)據(jù)流更新操作的優(yōu)先級(jí).甚至有些情況下,更新關(guān)系圖中有多個(gè)循環(huán)糾纏在一起,造成問題更加復(fù)雜.如圖7 中,按照上述建立更新關(guān)系圖的方法,操作節(jié)點(diǎn)“更新r4”選擇“更新r5”作為父節(jié)點(diǎn),造成操作節(jié)點(diǎn)“更新r3”“更新r4”和“更新r5”出現(xiàn)循環(huán),引起死鎖.

對(duì)于圖7 的死鎖問題,我們可以采取如下方法解除死鎖.

對(duì)循環(huán)中的每個(gè)操作節(jié)點(diǎn),按照路徑選擇和分配的優(yōu)先順序依次查看這些節(jié)點(diǎn)是否可以選擇更新調(diào)度圖中其他節(jié)點(diǎn)作為父節(jié)點(diǎn).若成立,則查看選擇其他節(jié)點(diǎn)作為父節(jié)點(diǎn)后,循環(huán)是否解除:如果能夠解除,則死鎖問題得到解決;否則,按此方法繼續(xù)查看循環(huán)中下一操作節(jié)點(diǎn),直到循環(huán)解除為止.如圖7 所示,操作節(jié)點(diǎn)“更新r3”、“更新r4”和“更新r5”出現(xiàn)循環(huán),首先查看流r3和r5,發(fā)現(xiàn)r3和r5無(wú)其他父節(jié)點(diǎn)可以選擇,則繼續(xù)查看流r4,發(fā)現(xiàn)操作“更新r4”除選擇操作節(jié)點(diǎn)“更新r5”外,還能選擇“更新r1”和“更新r2”作為父節(jié)點(diǎn).由于“更新r1”和“更新r2”的優(yōu)先級(jí)均可確定,此時(shí)死鎖解除.

我們還發(fā)現(xiàn),在一些特殊情況下,采用上述選擇其他父節(jié)點(diǎn)的方法并不能解除死鎖.如圖8 中,若更新r2先于更新r1執(zhí)行完畢,則更新r4和更新r1之間出現(xiàn)死鎖.對(duì)于這種情況,我們采取改進(jìn)的Dionysus 方法[4]解除死鎖.具體如下.

Fig.7 cycle in the update dependency graph圖7 更新關(guān)系圖中的循環(huán)

Fig.8 A deadlock example圖8 死鎖示意

?首先,把更新關(guān)系圖中所有流的更新關(guān)系組合成一幅圖,并把組合后的圖轉(zhuǎn)換為虛擬DAG 圖.這里用到強(qiáng)連通分量(strongly connected component,簡(jiǎn)稱SCC)[20]的概念,一個(gè)SCC 被看作DAG 圖中的一個(gè)虛擬節(jié)點(diǎn).如果將每個(gè)SCC 視為圖中的虛擬節(jié)點(diǎn),那么組合后的更新關(guān)系圖就成為虛擬DAG 圖.可以通過tarjan 算法[21]尋找更新關(guān)系圖中所有的SCC.當(dāng)每個(gè)SCC 成為一個(gè)虛擬節(jié)點(diǎn)后,我們首先利用第3.3節(jié)所述方法確定虛擬DAG 圖中優(yōu)先級(jí)最高的虛擬節(jié)點(diǎn)的更新優(yōu)先級(jí).然后,對(duì)于該虛擬節(jié)點(diǎn)內(nèi)的獨(dú)立節(jié)點(diǎn),依據(jù)更新調(diào)度圖查看其中哪個(gè)節(jié)點(diǎn)可以相對(duì)最先執(zhí)行(剩余鏈路資源大于對(duì)該鏈路的請(qǐng)求資源數(shù)量),最先執(zhí)行的節(jié)點(diǎn)優(yōu)先級(jí)等于其所在虛擬節(jié)點(diǎn)的優(yōu)先級(jí),其他內(nèi)部節(jié)點(diǎn)優(yōu)先級(jí)的值在虛擬節(jié)點(diǎn)的優(yōu)先級(jí)別基礎(chǔ)上按照?qǐng)?zhí)行順序依次加1.例如,在圖8 的更新關(guān)系圖中,操作節(jié)點(diǎn)“更新r4”和“更新r1”構(gòu)成一個(gè)SCC 節(jié)點(diǎn),在確定了該SCC 的更新優(yōu)先級(jí)之后,通過分析圖8 了解到,“更新r1”可先于“更新r4”執(zhí)行(更新r1能夠獲得鏈路S1-S5的剩余資源),那么“更新r1”的優(yōu)先級(jí)等于其所在SCC 的優(yōu)先級(jí),“更新r4”優(yōu)先級(jí)的值等于該SCC 優(yōu)先級(jí)加1.

?其次,用該SCC 內(nèi)部?jī)?yōu)先級(jí)最低節(jié)點(diǎn)的優(yōu)點(diǎn)級(jí)替換該SCC 的更新優(yōu)先級(jí),繼續(xù)計(jì)算DAG 內(nèi)其他節(jié)點(diǎn)的優(yōu)先級(jí).此后,每當(dāng)獲得DAG 內(nèi)一個(gè)虛擬節(jié)點(diǎn)的優(yōu)先級(jí)后,就依據(jù)上述確定虛擬節(jié)點(diǎn)內(nèi)獨(dú)立節(jié)點(diǎn)優(yōu)先級(jí)的方法確定其所有內(nèi)部獨(dú)立節(jié)點(diǎn)的優(yōu)先級(jí);然后,用此SCC 內(nèi)部?jī)?yōu)先級(jí)最低節(jié)點(diǎn)的優(yōu)點(diǎn)級(jí)替換該SCC 的更新優(yōu)先級(jí),繼續(xù)計(jì)算DAG 內(nèi)其他節(jié)點(diǎn)的優(yōu)先級(jí),直到所有操作節(jié)點(diǎn)優(yōu)先級(jí)確定完畢.例如,按照上述確定優(yōu)先級(jí)的方法,圖8 中更新r2的優(yōu)先級(jí)在更新r4的優(yōu)先級(jí)基礎(chǔ)上加1.

此外,為了防止循環(huán)發(fā)生,當(dāng)位于SCC 內(nèi)的操作節(jié)點(diǎn)和位于此SCC 外的節(jié)點(diǎn)都請(qǐng)求同一資源時(shí),若所請(qǐng)求的資源也位于SCC 循環(huán)之內(nèi),則規(guī)定此資源優(yōu)先分配給位于該SCC 內(nèi)的操作節(jié)點(diǎn).若不能滿足,則此SCC 內(nèi)的操作節(jié)點(diǎn)只能從獨(dú)立節(jié)點(diǎn)請(qǐng)求資源.這種方法可以防止在滿足SCC 內(nèi)部操作節(jié)點(diǎn)的資源需求前,把SCC 內(nèi)的資源分配給SCC 外的節(jié)點(diǎn)引起死鎖(如更新r2).

4 性能分析

4.1 仿真環(huán)境和性能評(píng)價(jià)指標(biāo)

仿真實(shí)驗(yàn)中,我們選擇具有不同網(wǎng)絡(luò)大小的兩種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[16]:第1 種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)(拓?fù)浣Y(jié)構(gòu)a)包含20個(gè)交換機(jī)和74 條鏈路,第2 種網(wǎng)絡(luò)拓?fù)?拓?fù)浣Y(jié)構(gòu)b)包含100 個(gè)交換機(jī)以及397 條鏈路.對(duì)于兩種拓?fù)?設(shè)每條鏈路的容量均為100Mbps.文獻(xiàn)[22]表明,通常,不足20%的數(shù)據(jù)流占據(jù)了網(wǎng)絡(luò)總流量的80%.為此,仿真分析中,我們產(chǎn)生不同數(shù)量的數(shù)據(jù)流,每個(gè)流的大小服從上述2-8 分布.我們基于Mininet[23]對(duì)所提DSRSU 策略進(jìn)行性能分析,并把DSRSU 策略與GRSU 策略[16]、OSPF 機(jī)制、EMCF+DS 進(jìn)行性能對(duì)比.GRSU 是文獻(xiàn)[16]提出的針對(duì)SDN 路由更新延遲時(shí)間保證的思想.OSPF 是典型的TCP/IP 網(wǎng)絡(luò)路由選擇協(xié)議,始終選擇網(wǎng)絡(luò)中的最短路徑充當(dāng)數(shù)據(jù)流的路由且并不進(jìn)行路由更新.對(duì)于EMCF+DS 策略,眾多文獻(xiàn)提出SDN 網(wǎng)絡(luò)控制器首先利用不同的路由算法,如MCF 算法[24],根據(jù)網(wǎng)絡(luò)當(dāng)前工作量為各數(shù)據(jù)流計(jì)算目標(biāo)路由配置;然后,再利用更新調(diào)度算法,如Dionysus[4],把網(wǎng)絡(luò)從當(dāng)前路由更新為目標(biāo)路由配置.此時(shí),由于控制器需要更新所有的流,包括大象流和老鼠流,造成路由更新的延遲大[16].一種改進(jìn)的策略是只更新大象流的路由[18],表示成EMCF,并同樣利用Dionysus 方法進(jìn)行路由調(diào)度更新,這種聯(lián)合策略稱為EMCF+DS.由于本文關(guān)注于實(shí)時(shí)路由更新,我們采用以下兩個(gè)指標(biāo)來(lái)分析各路由更新調(diào)度策略的更新效率和性能.

?路由更新延遲:通過各路由更新策略,把網(wǎng)絡(luò)從當(dāng)前路由配置更新到目標(biāo)路由配置所需時(shí)長(zhǎng).

?鏈路負(fù)載率(link load ratio,簡(jiǎn)稱LLR):鏈路負(fù)載率定義為L(zhǎng)LR=max{n(e)/c(e),e∈E},其中,e代表鏈路,c(e)是鏈路e的容量,n(e)為鏈路e的流量負(fù)載.

實(shí)驗(yàn)中,設(shè)更新延遲容忍值T0的默認(rèn)值是2s,λ初始值是0.65.每個(gè)仿真執(zhí)行100 次,最后結(jié)果取每次執(zhí)行結(jié)果的平均值.

4.2 不同流的數(shù)量對(duì)更新延遲的影響

本組實(shí)驗(yàn)討論數(shù)據(jù)流數(shù)量的變化對(duì)路由更新延遲的影響.實(shí)驗(yàn)中,我們把兩種網(wǎng)絡(luò)拓?fù)渲械臄?shù)據(jù)流數(shù)量逐漸增加,得到的實(shí)驗(yàn)結(jié)果如圖9(a)和圖9(b)所示.兩幅圖均顯示,當(dāng)數(shù)據(jù)流數(shù)量增加時(shí),由于需要進(jìn)行路由更新的數(shù)據(jù)流數(shù)量變大,因此EMCF+DS 策略的路由更新延遲逐漸增加.圖9(b)表明,在規(guī)模較大的拓?fù)浣Y(jié)構(gòu)b中,當(dāng)數(shù)據(jù)流的數(shù)量增加到40KB 時(shí),使用EMCF+DS 進(jìn)行路由更新的延遲超過了19s.這表明,盡管在EMCF+DS 策略中控制器僅更新大象流,路由更新的延遲仍遠(yuǎn)遠(yuǎn)大于延遲容忍值T0.由于DSRSU 設(shè)置了路由更新延遲容忍值,令路由更新的延遲不超過該值,所以隨著網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)量變化,該策略的路由更新延遲保持T0默認(rèn)值不變.DSRSU 策略在滿足更新延遲容忍值前提下,通過路由更新調(diào)度進(jìn)一步加快了路由更新的速度,所以DSRSU 的更新延遲容忍值比GRSU 策略要低.

Fig.9 Number of flows vs.route update delay圖9 流的數(shù)量對(duì)路由更新延遲

4.3 延遲容忍值對(duì)網(wǎng)絡(luò)性能的影響

本組實(shí)驗(yàn)討論延遲容忍值的大小對(duì)網(wǎng)絡(luò)性能的影響.當(dāng)網(wǎng)絡(luò)中流總數(shù)量恒定時(shí),我們把GRSU 和DSRSU 策略的延遲容忍值分別從0 變化到4s,得到的實(shí)驗(yàn)結(jié)果如圖10 和圖11 所示.圖10 和圖11 都表明,在拓?fù)浣Y(jié)構(gòu)a和b中,DSRSU 和GRSU 的鏈路負(fù)載率均隨著路由更新延遲容忍值T0的增大而降低.這是因?yàn)?T0越大,兩種策略在延遲容忍值內(nèi)更新的數(shù)據(jù)流總數(shù)量就越大,也就越有利于實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡.由于OSPF 始終選擇網(wǎng)絡(luò)中源到目的的最短路徑為數(shù)據(jù)流的路由,并不進(jìn)行路由更新,因此當(dāng)數(shù)據(jù)流數(shù)量不變時(shí),OSPF 策略的鏈路負(fù)載率不變.當(dāng)數(shù)據(jù)流總數(shù)量增多時(shí),從圖10(a)到圖10(b)和圖11(a)到圖11(b)顯示,因?yàn)榇藭r(shí)需要更新的數(shù)據(jù)流總量多了,在T0內(nèi)能夠被更新的數(shù)據(jù)流占總數(shù)據(jù)流的比重減小,當(dāng)T0相同時(shí),DSRSU 和GRSU 策略的鏈路負(fù)載率也增大了.無(wú)論數(shù)據(jù)流數(shù)量如何變化,在同一數(shù)據(jù)流數(shù)量的前提下,兩種拓?fù)浣Y(jié)構(gòu)中,OSPF 策略的網(wǎng)絡(luò)性能始終低于其他策略(鏈路負(fù)載率最高).這主要是由于OSPF 不進(jìn)行路由更新,致使網(wǎng)絡(luò)中某些鏈路的負(fù)載率大且某些鏈路可能擁塞的原因.此外,因?yàn)镋MCF+DS 策略始終需要為網(wǎng)絡(luò)中所有大象流更新路由,完全更新這些大象流需要的時(shí)間大于4s,所以,T0的變化對(duì)EMCF+DS 策略的鏈路負(fù)載率無(wú)影響.兩幅圖中,隨著T0的變化,我們的策略開始鏈路負(fù)載率略高于GRSU;而隨著更新延遲容忍值的變大,DSRSU 鏈路負(fù)載率變得低于GRSU.原因主要在于,當(dāng)更新延遲容忍值逐漸變大時(shí),更新的數(shù)據(jù)流數(shù)量變大,我們的策略路由選擇階段在確定數(shù)據(jù)流新路徑后回收期舊路徑的資源,相對(duì)于GRSU 對(duì)舊路徑資源不回收以防止擁塞,本策略相對(duì)于GRSU 更加高效地利用鏈路資源,使得實(shí)際能夠進(jìn)行路由更新的數(shù)據(jù)流數(shù)量增多,因此更容易實(shí)現(xiàn)負(fù)載均衡.

Fig.10 Route update delay constrains vs.link load ratio in topology a圖10 拓?fù)鋋 中路由更新延遲容忍值對(duì)鏈路負(fù)載率

Fig.11 Route update delay constrains vs.link load ratio in topology b圖11 拓?fù)鋌 中路由更新延遲容忍值對(duì)鏈路負(fù)載率

圖10 顯示,當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí),相對(duì)于EMCF+DS,本文的DSRSU 策略能夠降低EMCF+DS 策略約69%的路由更新延遲,卻達(dá)到與EMCF+DS 策略相近的網(wǎng)絡(luò)性能(鏈路負(fù)載率比EMCF+DS 低2.1%).例如,當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)量是4 000 時(shí),圖9(a)表明,EMCF+DS 策略的路由更新延遲約為4.3s;而圖10(a)顯示,DSRSU 僅需要2s,就能達(dá)到與EMCF+DS 相似的網(wǎng)絡(luò)鏈路負(fù)載率.在圖11 中,當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí),我們發(fā)現(xiàn),利用DSRSU 策略進(jìn)行流路由更新,相對(duì)于EMCF+DS,能夠在降低EMCF+DS 策略約74.5%路由更新延遲的前提下,具有和EMCF+DS策略相近的鏈路負(fù)載率.

4.4 數(shù)據(jù)流總數(shù)量對(duì)網(wǎng)絡(luò)性能的影響

本組實(shí)驗(yàn)中,對(duì)于兩種不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),我們?cè)谝来卧O(shè)定路由更新延遲容忍值T0=1(s)和T0=2(s)的前提下,把網(wǎng)絡(luò)中數(shù)據(jù)流的數(shù)量逐漸增大,得到的實(shí)驗(yàn)結(jié)果如圖12 和圖13 所示.

Fig.12 Link load ratio vs.number of flows in topology a圖12 拓?fù)鋋 中流數(shù)量的變化對(duì)鏈路負(fù)載率

Fig.13 Link load ratio vs.number of flows in topology b圖13 拓?fù)鋌 中流數(shù)量的變化對(duì)鏈路負(fù)載率

圖12 和圖13 均表明,在路由更新延遲容忍值一定的情況下,4 種策略的鏈路負(fù)載率均隨著網(wǎng)絡(luò)中數(shù)據(jù)流總數(shù)量的變大呈逐漸增大的趨勢(shì),且OSPF 的鏈路負(fù)載率遠(yuǎn)高于其他3 種策略.其原因是,對(duì)于OSPF,當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)流逐漸增多時(shí),由于有更多的數(shù)據(jù)需要放在網(wǎng)絡(luò)上傳輸,網(wǎng)絡(luò)的負(fù)載逐漸加重.并且,OSPF 不進(jìn)行路由更新,因此鏈路負(fù)載率高的那些鏈路始終保持高鏈路負(fù)載率居高不下,造成OSPF 的鏈路負(fù)載率較高.對(duì)于EMCF+DS、GRSU 和DSRSU 策略,隨著數(shù)據(jù)流數(shù)量增大,實(shí)現(xiàn)路由更新的數(shù)據(jù)流數(shù)量占總數(shù)據(jù)流總量的比率降低了,路由更新的效果下降,因此鏈路負(fù)載率升高.從圖12(a)到圖12(b)以及圖13(a)到圖13(b)的變化可見,在數(shù)據(jù)流數(shù)量相同的條件下,T0=2 相對(duì)于T0=1 時(shí)GRSU 和DSRSU 策略的鏈路負(fù)載率均下降.這是因?yàn)門0增大時(shí),路由更新延遲容忍值內(nèi)可以更新更多數(shù)據(jù)流的結(jié)果.此外,圖12 和圖13 顯示,在路由更新延遲容忍值恒定不變的前提下,隨著網(wǎng)絡(luò)中數(shù)據(jù)流數(shù)量的增多,EMCF+DS、GRSU 和DSRSU 策略的網(wǎng)絡(luò)性能比較接近.當(dāng)路由更新延遲容忍值T0=2時(shí),本文DSRSU 策略的鏈路負(fù)載率略始終低于GRSU.這是因?yàn)?我們的策略不僅在路徑選擇時(shí)強(qiáng)調(diào)鏈路負(fù)載均衡,同時(shí)相對(duì)于GRSU 強(qiáng)調(diào)鏈路資源的回收,使得實(shí)際由于鏈路資源不滿足要求致使無(wú)法進(jìn)行路由更新的情況減少了.另外,具體來(lái)講,對(duì)于拓?fù)浣Y(jié)構(gòu)a,DSRSU 策略在T0=2 時(shí)就能達(dá)到與EMCF+DS 策略類似的網(wǎng)絡(luò)性能;而在拓?fù)浣Y(jié)構(gòu)a中,EMCF+DS 的更新延遲卻需要5s～8s.圖13(b)表明,本文的DSRSU 策略在T0=2 時(shí)達(dá)到與EMCF+DS 策略花費(fèi)11s～16s 的路由更新延遲類似的鏈路負(fù)載率.其主要原因在于,DSRSU 不僅在選路時(shí)考慮了鏈路負(fù)載均衡,而且通過建立更新關(guān)系圖的方式挖掘各數(shù)據(jù)流路由更新調(diào)度的順序來(lái)盡量降低路由更新延遲,使得路由更新能夠盡快完成.

4.5 鏈路負(fù)載因子對(duì)網(wǎng)絡(luò)性能的影響

本實(shí)驗(yàn)討論路徑分配中的鏈路負(fù)載因子λ對(duì)網(wǎng)絡(luò)性能的影響.在其他參數(shù)不變的情況下,把鏈路負(fù)載因子λ從0.2 逐漸變化到1,得到的實(shí)驗(yàn)結(jié)果如圖14 所示.由圖14 可見,在拓?fù)浣Y(jié)構(gòu)a和拓?fù)浣Y(jié)構(gòu)b中,當(dāng)λ很小時(shí),網(wǎng)絡(luò)鏈路負(fù)載率高.這是因?yàn)棣溯^小,導(dǎo)致數(shù)據(jù)流在路由更新的選路階段,由于鏈路負(fù)載的限制,能夠被選擇充當(dāng)新路徑的鏈路很少,造成很多數(shù)據(jù)流由于找不到滿足條件的新路由而無(wú)法完成路徑的更新.此時(shí),幾乎無(wú)法通過路由更新來(lái)降低鏈路負(fù)載率.當(dāng)λ逐漸增大時(shí),鏈路負(fù)載大為降低,因?yàn)榇藭r(shí)很多數(shù)據(jù)流能夠完成新路徑的選擇,從而路由更新可以進(jìn)行了.圖中當(dāng)λ達(dá)到0.6 時(shí),網(wǎng)絡(luò)鏈路負(fù)載率最小,而之后,隨著鏈路負(fù)載因子的增大,鏈路負(fù)載率提高.這是由于鏈路負(fù)載因子較大會(huì)導(dǎo)致某些鏈路在路由更新中負(fù)載較重的結(jié)果.

Fig.14 Link load factor vs.link load rate圖14 鏈路負(fù)載因子對(duì)鏈路負(fù)載率

5 結(jié) 論

本文研究軟件定義網(wǎng)絡(luò)中實(shí)時(shí)路由更新問題,在同時(shí)考慮TCMA 的更新速度、當(dāng)前網(wǎng)絡(luò)工作負(fù)載和各個(gè)交換機(jī)流表更新速度差異的前提下,提出延遲滿足的路由選擇和調(diào)度更新策略(delay satisfied route selection and updating scheme,簡(jiǎn)稱DSRSU),從路徑選擇和路由更新調(diào)度兩個(gè)方面聯(lián)合進(jìn)行優(yōu)化,以降低路由更新延遲,實(shí)現(xiàn)實(shí)時(shí)路由更新.大量仿真結(jié)果表明,DSRSU 策略具有高效性,能夠在保證網(wǎng)絡(luò)性能的前提下,極大地降低路由更新的延遲.