劉 釗,夏鴻斌,2
1江南大學(xué) 數(shù)字媒體學(xué)院,江蘇 無(wú)錫214122
2江南大學(xué) 江蘇省媒體設(shè)計(jì)與軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室,江蘇 無(wú)錫214122
隨著新型網(wǎng)絡(luò)技術(shù)的不斷涌現(xiàn),網(wǎng)絡(luò)流量的增長(zhǎng)也變得十分迅速,不同的網(wǎng)絡(luò)應(yīng)用對(duì)于網(wǎng)絡(luò)資源的需求也變得越來(lái)越高。傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)由于自身結(jié)構(gòu)的僵化[1]越來(lái)越不能滿足用戶和業(yè)務(wù)的需求。傳統(tǒng)網(wǎng)絡(luò)架構(gòu)將轉(zhuǎn)發(fā)平面和控制平面[2]緊密耦合在獨(dú)立的設(shè)備中,很難對(duì)網(wǎng)絡(luò)進(jìn)行全局把控,增加了部署新型網(wǎng)絡(luò)應(yīng)用的難度。下一代可編程的網(wǎng)絡(luò)架構(gòu)軟件定義網(wǎng)絡(luò)(Software-Defined Networking,SDN)[3]應(yīng)運(yùn)而生,它通過(guò)將傳統(tǒng)網(wǎng)絡(luò)中的數(shù)據(jù)平面和控制平面解耦,將網(wǎng)絡(luò)邏輯與網(wǎng)絡(luò)設(shè)備分離開來(lái),降低了網(wǎng)絡(luò)的復(fù)雜性和組網(wǎng)成本。SDN架構(gòu)以簡(jiǎn)單、可編程的方式控制網(wǎng)絡(luò),它使得分布式的數(shù)據(jù)平面由一個(gè)集中控制的平面來(lái)管理。圖1 給出了SDN網(wǎng)絡(luò)體系結(jié)構(gòu)與傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)的分層視圖。
圖1 (a) SDN架構(gòu)網(wǎng)絡(luò)體系結(jié)構(gòu)
圖1 (b) 傳統(tǒng)網(wǎng)絡(luò)體系架構(gòu)
在SDN 網(wǎng)絡(luò)體系中,控制器通過(guò)OpenFlow[4]協(xié)議中的控制信道,對(duì)其管理域內(nèi)的所有交換機(jī)進(jìn)行配置。SDN 交換機(jī)將信息保存到本地的流表中。在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的過(guò)程中,交換機(jī)根據(jù)其本地流表中的流表項(xiàng)對(duì)數(shù)據(jù)包進(jìn)行匹配,并根據(jù)該流表項(xiàng)中的動(dòng)作對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā),而未找到對(duì)應(yīng)的流表項(xiàng)的數(shù)據(jù)包將會(huì)被交換機(jī)轉(zhuǎn)發(fā)給控制器。控制器根據(jù)轉(zhuǎn)發(fā)來(lái)的數(shù)據(jù)包生成新的轉(zhuǎn)發(fā)規(guī)則并下發(fā)給交換機(jī),同時(shí)對(duì)交換機(jī)中的流表進(jìn)行更新。在實(shí)際的應(yīng)用部署中,流表一般存儲(chǔ)在交換機(jī)的三態(tài)內(nèi)容尋址存儲(chǔ)器(Ternary Content Addressable Memory,TCAM)[5]中。由于TCAM的高成本與高能耗,其所能存儲(chǔ)的流表項(xiàng)數(shù)量也是十分有限的。研究表明[6-7],在SDN 數(shù)據(jù)中心中,90%的數(shù)據(jù)流為老鼠流,而10%的大象流卻傳輸了超過(guò)90%的字節(jié),而處理這些老鼠流的流表項(xiàng)大量的占據(jù)了交換機(jī)的流表空間。由于對(duì)這些使用頻率較低的流表項(xiàng)的更新不及時(shí),導(dǎo)致了交換機(jī)中流表的匹配率不能滿足實(shí)際的需求[8],流表資源不能被充分利用。與此同時(shí),隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大,控制器也不可避免地暴露出處理能力有限的問(wèn)題[9]。流表匹配率過(guò)低以及控制器端負(fù)載過(guò)重嚴(yán)重降低了SDN系統(tǒng)的整體性能。
為了解決上述問(wèn)題,相關(guān)學(xué)者展開了很多研究。文獻(xiàn)[10]提出在SDN中部署權(quán)威交換機(jī),并將一部分流表項(xiàng)存儲(chǔ)在權(quán)威交換機(jī)中,并使其行使部分控制器的功能。當(dāng)一條新流到達(dá)普通交換機(jī)時(shí),由權(quán)威交換機(jī)直接向普通交換機(jī)添加相應(yīng)的轉(zhuǎn)發(fā)規(guī)則。這樣的設(shè)計(jì)使得原本需要在控制器處理的大部分?jǐn)?shù)據(jù)流,在權(quán)威交換機(jī)處即可得到解決,有效減輕了控制器的負(fù)擔(dān)。但是這種做法并不符合當(dāng)前OpenFlow 協(xié)議的規(guī)范,需要對(duì)當(dāng)前SDN 網(wǎng)絡(luò)模型進(jìn)行大規(guī)模修改才能實(shí)現(xiàn)。文獻(xiàn)[11]提出將流表的更新方式與排隊(duì)系統(tǒng)進(jìn)行類比,將流表模型轉(zhuǎn)化為排隊(duì)模型,并通過(guò)排隊(duì)論分析了hard_timeout對(duì)阻塞概率與流截?cái)啻螖?shù)的影響。該方法通過(guò)調(diào)整timeout 值有效提高了流表的匹配率,但對(duì)控制器造成的負(fù)擔(dān)較重。文獻(xiàn)[12]提出了一種OpenFlow 交換機(jī)流表自動(dòng)控制機(jī)制,用于解決在大數(shù)據(jù)流下交換機(jī)流表更新不及時(shí)造成的流表資源不足的問(wèn)題。但是該方案所提出的對(duì)流表項(xiàng)停滯時(shí)間的優(yōu)化處理仍然是靜態(tài)優(yōu)化,不能滿足交換機(jī)在真實(shí)網(wǎng)絡(luò)環(huán)境下的需求。文獻(xiàn)[13]和[14]提出了基于新增流表項(xiàng)數(shù)量預(yù)測(cè)并動(dòng)態(tài)調(diào)整流表中流表項(xiàng)空閑超時(shí)時(shí)間的方法。在這兩種方法中,控制器通過(guò)分析每次的新增流表項(xiàng)數(shù)量,預(yù)測(cè)下一個(gè)取樣周期內(nèi)新增加的流表項(xiàng)數(shù)量,并且根據(jù)當(dāng)前流表空間的使用情況動(dòng)態(tài)調(diào)整流表項(xiàng)超時(shí)時(shí)間。其中,文獻(xiàn)[13]使用AR 模型對(duì)下一個(gè)取樣周期內(nèi)新增的流表項(xiàng)進(jìn)行預(yù)測(cè),文獻(xiàn)[14]使用的預(yù)測(cè)算法是基于二次平均移動(dòng)的。他們的方法很好地克服了靜態(tài)優(yōu)化的缺點(diǎn),提高了流表資源的使用效率,但在調(diào)整流表項(xiàng)停滯超時(shí)時(shí)間的過(guò)程中,未能考慮每一條流表項(xiàng)自身的特點(diǎn),沒(méi)有根據(jù)每條流表項(xiàng)的使用頻率做出調(diào)整,因此具有進(jìn)一步的改進(jìn)空間。文獻(xiàn)[15]提出了一種基于LRU 的改進(jìn)型流表更新算法。他們將流表中的空閑空間作為一個(gè)緩存區(qū),用于存放過(guò)期的流表項(xiàng),并對(duì)每一條過(guò)期流表項(xiàng)進(jìn)行計(jì)時(shí)。當(dāng)有到達(dá)交換機(jī)的數(shù)據(jù)包與緩存區(qū)中過(guò)期的流表項(xiàng)相匹配時(shí),該流表項(xiàng)被重新激活。在緩存區(qū)中存在時(shí)間最長(zhǎng)的流表項(xiàng)在流表空間不足時(shí)將被優(yōu)先刪除。這種方法的優(yōu)點(diǎn)在于可以使SDN交換機(jī)盡可能多的保存使用頻率高的流表項(xiàng)。但在網(wǎng)絡(luò)高峰期時(shí),SDN交換機(jī)的流表并沒(méi)有太多空閑空間可以被用作緩存區(qū),其所能存儲(chǔ)的流表項(xiàng)太少也就失去了意義。
針對(duì)上述問(wèn)題,本文提出了一種基于ARMA 模型預(yù)測(cè)的流表更新算法。算法通過(guò)收集每個(gè)單位時(shí)間內(nèi)新增加的流表項(xiàng)數(shù)量,預(yù)測(cè)下一個(gè)時(shí)刻的新增流表項(xiàng)數(shù)量,并根據(jù)預(yù)測(cè)值提前刪除一定數(shù)量的最近一段時(shí)間內(nèi)使用頻率較低的流表項(xiàng),為即將到來(lái)的數(shù)據(jù)流預(yù)留出足夠的流表空間。算法在提高流表匹配率的同時(shí)也減少了與控制器的交互次數(shù),有效減輕了控制器的負(fù)擔(dān)。
算法框架如圖2所示。
圖2 算法框架
OpenFlow 標(biāo)準(zhǔn)協(xié)議通常采用基于先進(jìn)先出(First In First Out,F(xiàn)IFO)的、基于隨機(jī)(Random)的、基于最少使用(Least Recently Used,LRU)的、基于最不經(jīng)常使用(Least Frequently Used,LFU)的更新算法對(duì)流表資源進(jìn)行管理。在交換機(jī)流表空間不足時(shí),更新算法通過(guò)控制器主動(dòng)地向下層的交換機(jī)發(fā)送消息來(lái)刪除舊流表項(xiàng)。其中FIFO 置換算法和Random 置換算法的區(qū)別很小,在對(duì)流表進(jìn)行更新的過(guò)程中二者都有很大的隨機(jī)性。所以本文下面將對(duì)FIFO、LRU、LFU等流表更新算法進(jìn)行闡述。
基于先進(jìn)先出的(FIFO)的流表更新算法因?yàn)閷?shí)現(xiàn)過(guò)程簡(jiǎn)單,更新效率相對(duì)較高,因此經(jīng)常將該算法作為流表的更新算法。該算法的核心思想為:當(dāng)流表空間不足時(shí),總是優(yōu)先選擇在流表中存在時(shí)間最久的流表項(xiàng)進(jìn)行刪除,即最先在交換機(jī)中安裝的流表項(xiàng)將被最先刪除。交換機(jī)流表中的Duration_sec字段記錄了每條流表項(xiàng)在交換機(jī)中存在的時(shí)間,該值越長(zhǎng)說(shuō)明該流表項(xiàng)越早被安裝。實(shí)現(xiàn)FIFO算法的偽代碼描述如下。
算法1 基于先進(jìn)先出的(FIFO)置換算法FIFO_FlowEntryReplacement
輸入:數(shù)據(jù)流Flows={p0,p1,…,pn}
輸出:流表FlowTable
FIFO_FlowEntryReplacement()
{for ?pi∈Flows do
{//將當(dāng)前數(shù)據(jù)流pi的數(shù)據(jù)包封裝在Packet_in 消息中發(fā)送給控制器
Packet_in_message ←sendPacket_in(pi)
//控制器提取流表項(xiàng)信息
FlowEntry ←getFlowEntry(Packet_in_message)
//獲取交換機(jī)當(dāng)前流表
FlowTable ←getFlowTable()
If(FlowTable is not full):
//控制器發(fā)送Flow_mod消息給交換機(jī)安裝流表項(xiàng)
Flowtable.add(FlowEntry)←sendFlow_mod(FlowEntry)
else:{//尋找交換機(jī)中存在時(shí)間最長(zhǎng)流表項(xiàng)進(jìn)行刪除
deleteEntry ←findLongestFlow(Flowtable)
//控制器發(fā)送Flow_mod消息給交換機(jī)刪除流表項(xiàng)
Flowtable.delete ←sendFlow_mod(deleteEntry)
Flowtable.add(FlowEntry)←sendFlow_mod(FlowEntry)
}
//控制器向交換機(jī)發(fā)送Packet_out 消息處理Packet_in 消息中封裝的數(shù)據(jù)包
FlowTable.foward ←sendPacket_out(Packet_in_message)
}
}
return FlowTable;
}
在算法1 中,函數(shù)findLongestDuration 優(yōu)先尋找當(dāng)前流表中Duration_sec 值最大的流表項(xiàng)進(jìn)行刪除,這可能導(dǎo)致一些使用頻率較高的流表項(xiàng)被頻繁刪除,降低了流表的匹配率。此外FIFO算法在對(duì)流表進(jìn)行更新時(shí)的隨機(jī)性較大,對(duì)于數(shù)據(jù)傳輸時(shí)間不同的數(shù)據(jù)包,不能滿足其對(duì)于流表更新算法的需求。
基于近期最少使用(LRU)的流表更新算法根據(jù)近期數(shù)據(jù)流的匹配情況對(duì)當(dāng)前交換機(jī)內(nèi)的流表項(xiàng)進(jìn)行更新,更加符合真實(shí)的數(shù)據(jù)流環(huán)境。一般的LRU 算法根據(jù)每條流表項(xiàng)匹配數(shù)據(jù)包的時(shí)間,找到最長(zhǎng)時(shí)間沒(méi)有數(shù)據(jù)包與其匹配的流表項(xiàng)作為近期最少使用的流表項(xiàng),并將其優(yōu)先刪除。流表中的idle_timeout值可用于記錄每條流表項(xiàng)最后匹配數(shù)據(jù)包的時(shí)間。根據(jù)OpenFlow協(xié)議規(guī)范,每條流表項(xiàng)的idle_timeout值隨時(shí)間遞減,當(dāng)該條流表項(xiàng)有匹配的數(shù)據(jù)包到達(dá)時(shí),其對(duì)應(yīng)的idle_timeout值將被重置。對(duì)于LRU 算法而言,idle_timeout 值最小的流表項(xiàng)即為最近最長(zhǎng)時(shí)間沒(méi)有處理數(shù)據(jù)包的流表項(xiàng),應(yīng)優(yōu)先被刪除。實(shí)現(xiàn)LRU算法的偽代碼描述如下。
算法2 基于近期最少使用(LRU)置換算法LRU_FlowEntryReplacement
輸入:數(shù)據(jù)流Flows={p0,p1,…,pn}
輸出:流表Flowtable
LRU_FlowEntryReplacement()
{for ?pi∈Flows do
{//將當(dāng)前數(shù)據(jù)流pi的數(shù)據(jù)包封裝在Packet_in 消息中發(fā)送給控制器
Packet_in_message ←sendPacket_in(pi)
//控制器提取流表項(xiàng)信息
FlowEntry ←getFlowEntry(Packet_in_message)
//獲取當(dāng)前交換機(jī)的流表
FlowTable ←getFlowtable()
If(FlowTable is not full):
//控制器發(fā)送Flow_mod 消息給交換機(jī)安裝流表項(xiàng)并設(shè)置idle_timeout值
Flowtable.add(FlowEntry,idle_timeout)←sendFlow_mod(FlowEntry,idle_timeout)
else:
{//尋找當(dāng)前交換機(jī)中最少流表項(xiàng)進(jìn)行刪除
deleteEntry ←findleastUsedFlow(Flowtable)
//控制器發(fā)送Flow_mod消息給交換機(jī)刪除流表項(xiàng)
Flowtable.delete ←sendFlow_mod(deleteEntry)
Flowtable.add(FlowEntry,idle_timeout)←sendFlow_mod
(FlowEntry,idle_timeout)
}
//控制器向交換機(jī)發(fā)送Packet_out 消息處理Packet_in 消息中封裝的數(shù)據(jù)包
FlowTable.foward ←sendPacket_out(Packet_in_message)
}
}
return FlowTable;
}
在算法2中,idle_timeout值作為記錄流表項(xiàng)匹配數(shù)據(jù)包的最后時(shí)間,所以將其設(shè)置為一個(gè)相對(duì)長(zhǎng)的固定值。當(dāng)流表空間已滿時(shí),函數(shù)findLeastUsedFlow在當(dāng)前流表中尋找idle_timeout值最小的流表項(xiàng)并將其優(yōu)先刪除。LRU置換算法能夠避免FIFO算法刪除使用高頻率使用流表項(xiàng)的缺點(diǎn),但LRU 算法也會(huì)導(dǎo)致一些使用頻率較高,數(shù)據(jù)包時(shí)間間隔較長(zhǎng)的數(shù)據(jù)流的流表項(xiàng)被頻繁刪除。
基于最不經(jīng)常使用(LFU)的流表更新算法在流表空間不足時(shí),根據(jù)每條流表項(xiàng)歷史訪問(wèn)次數(shù),優(yōu)先刪除匹配數(shù)據(jù)包數(shù)量最少的流表項(xiàng)。流表中的匹配計(jì)數(shù)器可用于記錄每條流表項(xiàng)所匹配過(guò)的數(shù)據(jù)包數(shù)量。根據(jù)OpenFlow協(xié)議規(guī)范,當(dāng)流表項(xiàng)有匹配的數(shù)據(jù)包到達(dá)時(shí),其對(duì)應(yīng)的匹配計(jì)數(shù)器就會(huì)自動(dòng)加一。對(duì)于LFU 流表更新算法而言,當(dāng)前流表中匹配過(guò)數(shù)據(jù)包數(shù)量最少的流表項(xiàng)即為使用頻率最低的流表項(xiàng),應(yīng)優(yōu)先被刪除。LRU算法的偽代碼描述如下。
算法3 基于最不經(jīng)常使用的(LFU)置換算法LFU_FlowEntryReplacement
輸入:數(shù)據(jù)流Flows={p0,p1,…,pn}
輸出:流表Flowtable
LFU_FlowEntryReplacement()
{for ?pi∈Flows do
{if ??entry ∈FlowTable is matched
{//將當(dāng)前數(shù)據(jù)流pi的數(shù)據(jù)包封裝在Packet_in 消息中發(fā)送給控制器
Packet_in_message ←sendPacket_in(pi)
//控制器提取流表項(xiàng)信息
FlowEntry ←getFlowEntry(Packet_in_message)
//獲取交換機(jī)當(dāng)前流表
FlowTable ←getFlowTable()
If(FlowTable is not full):
//控制器發(fā)送Flow_mod消息給交換機(jī)安裝流表項(xiàng)
Flowtable.add(FlowEntry)←sendFlow_mod(FlowEntry)
else:{//尋找當(dāng)前流表中使用頻率最低的流表項(xiàng)進(jìn)行刪除
deleteEntry ←findLeastestCountFlow(Flowtable)
//控制器發(fā)送Flow_mod消息給交換機(jī)刪除流表項(xiàng)
Flowtable.delete ←sendFlow_mod(deleteEntry)
Flowtable.add(FlowEntry)←sendFlow_mod(FlowEntry)
}
//控制器向交換機(jī)發(fā)送Packet_out 消息處理Packet_in 消息中封裝的數(shù)據(jù)包
FlowTable.foward ←sendPacket_out(Packet_in_message)
}
}
return FlowTable;
}
在算法3 中,函數(shù)findLeastedCountFlow 在流表空間不足時(shí)尋找當(dāng)前流表中匹配計(jì)數(shù)器最小的流表項(xiàng)進(jìn)行刪除。LFU 相對(duì)于FIFO 與LRU 算法可以清除更多的使用頻率較低的流表項(xiàng)。但與FIFO 和LRU 算法相同,LFU算法只有在當(dāng)前流表空間不足時(shí)才對(duì)當(dāng)前流表資源進(jìn)行管理,不能提前為交換機(jī)留出足夠的流表空間容納新增流表項(xiàng)。
在網(wǎng)絡(luò)流量的高峰期,現(xiàn)有的一般流表更新算法不能很好的解決流表資源不足以及控制器負(fù)擔(dān)過(guò)重的問(wèn)題。為了解決上述問(wèn)題,本文提出了一種新的P-LRU流表更新算法(Promoted Least Recently Used,P-LRU)。該算法收集每個(gè)取樣周期內(nèi)新增的流表項(xiàng)數(shù)量作為歷史數(shù)據(jù),使用自回歸移動(dòng)平均模型(ARMA模型)[16]預(yù)測(cè)下一個(gè)取樣周期內(nèi)新增加的流表項(xiàng)數(shù)量。并根據(jù)當(dāng)前流表空間的使用情況動(dòng)態(tài)清除使用頻率低的流表項(xiàng)。本文算法不僅使交換機(jī)的流表?yè)碛辛俗銐虻目臻e空間容納新增流表項(xiàng),并且在增加了流表的匹配率的同時(shí),減少了交換機(jī)與控制器間交互的次數(shù),有效降低了控制器端的負(fù)擔(dān)。
自回歸移動(dòng)平均模型(ARMA 模型)是一種常見的用于短期預(yù)測(cè)的時(shí)間序列模型,由自回歸模型與移動(dòng)平均模型兩部分組成。文獻(xiàn)[17]使得ARMA 模型擁有一套完整、結(jié)構(gòu)化的建模方法,以及堅(jiān)實(shí)的理論基礎(chǔ)和統(tǒng)計(jì)學(xué)上的完善性。
4.1.1 ARMA模型表述
基于ARMA模型的新增流表項(xiàng)數(shù)量預(yù)測(cè)的基本思想為:將每個(gè)取樣周期內(nèi)增加的流表項(xiàng)數(shù)目隨著時(shí)間推移而形成一個(gè)隨機(jī)時(shí)間序列。ARMA 模型認(rèn)為序列中第t個(gè)時(shí)刻的數(shù)值不僅與前p 個(gè)時(shí)間序列的數(shù)值有關(guān),而且與前q 個(gè)進(jìn)入系統(tǒng)的隨機(jī)擾動(dòng)有關(guān),并由此來(lái)預(yù)測(cè)下一個(gè)時(shí)刻的數(shù)值。其中作為預(yù)測(cè)對(duì)象的Xt受到前P個(gè)時(shí)間序列數(shù)值的影響,其自回歸過(guò)程如下式:
式中,φ1,φ2,…,φp為自回歸系數(shù),{Xt}為新增流表項(xiàng)數(shù)量所形成的時(shí)間序列數(shù)值,et為誤差項(xiàng)。
誤差項(xiàng)在不同時(shí)期具有依存關(guān)系,其移動(dòng)平均過(guò)程如下式表示:
式中,θ1,θ2,…,θq為移動(dòng)平均系數(shù),{αt}是與{Xt}獨(dú)立共同分布的白噪聲。
由此,新增流表項(xiàng)數(shù)量預(yù)測(cè)ARMA 模型可以表述為:
將該模型記作ARMA(p,q)。其中p 為自回歸階數(shù),q 為移動(dòng)平均階數(shù)。
4.1.2 預(yù)測(cè)步驟
基于ARMA模型的新增流表項(xiàng)預(yù)測(cè)按照以下步驟進(jìn)行。
(1)數(shù)據(jù)預(yù)處理和平穩(wěn)性檢驗(yàn)
首先獲取新增流表項(xiàng)數(shù)目的時(shí)間序列,可表示為:{Xt}={X1,X2,…,Xk}然后,將現(xiàn)有的時(shí)間序列進(jìn)行零均值化處理,得到零均值化后的序列,其中為的平均值。接著,計(jì)算自相關(guān)函數(shù)與偏自相關(guān)函數(shù):
(2)建立模型,參數(shù)估計(jì)
接下來(lái),根據(jù)的偏相關(guān)函數(shù)和自相關(guān)函數(shù)確定ARMA(p,q)模型的階數(shù)p,q。由于ARMA 模型在很多領(lǐng)域的廣泛使用,已經(jīng)出現(xiàn)了很多相關(guān)的科學(xué)計(jì)算包,例如Python 的StatsModels 等。通過(guò)調(diào)用相關(guān)科學(xué)計(jì)算包中的工具函數(shù),對(duì)ARMA(p,q)模型進(jìn)行擬合,并結(jié)合最小信息準(zhǔn)則(AIC),計(jì)算不同的(p,q)組合下模型的AIC 值,選擇使得AIC 值最小的階數(shù),將其作為ARMA(p,q)模型的最佳階數(shù)。
確定最佳階數(shù)(p,q)組合的同時(shí),使用最小二乘估計(jì)法對(duì)模型中剩余未知參數(shù)進(jìn)行計(jì)算,得到t+1 時(shí)刻的新增流表項(xiàng)數(shù)量的預(yù)測(cè)關(guān)系式:
(3)進(jìn)行預(yù)測(cè)
最后,運(yùn)用預(yù)測(cè)關(guān)系式對(duì)下一取樣周期的新增流表項(xiàng)數(shù)量預(yù)測(cè),并輸出預(yù)測(cè)結(jié)果Nnew。
在交換機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)包的過(guò)程中,流表空間的大小、控制器處理信息的能力的不足是制約交換機(jī)轉(zhuǎn)發(fā)能力的瓶頸。因此在流表空間一定的情況下,流表項(xiàng)的處理就成為了關(guān)鍵。如圖3所示,流表空間由已在交換機(jī)中存在流表項(xiàng)和空閑空間構(gòu)成。每條流表項(xiàng)包含匹配域、動(dòng)作、在交換機(jī)中的存在時(shí)間、超時(shí)時(shí)間等信息。理論上流表的空閑空間必須保持一定且合適的數(shù)量才能使系統(tǒng)發(fā)揮最佳的性能。
圖3 流表空間
假設(shè)取樣周期T 時(shí)流表空間如圖3(a)所示,由此圖可知:
其中,Nmax是流表最多可以容納的流表項(xiàng)數(shù)目,Nflow是流表中已經(jīng)存在的流表項(xiàng)的數(shù)目,Nempty是流表的空閑空間。通過(guò)對(duì)近期歷史數(shù)據(jù)的分析,預(yù)測(cè)下一個(gè)取樣周期的新增流表項(xiàng)數(shù)目,如果預(yù)測(cè)值較大,表明流表可能需要應(yīng)對(duì)在下一取樣周期中產(chǎn)生大量的流表項(xiàng)的情況,此時(shí)流表應(yīng)該保留較大的空閑空間。如果預(yù)測(cè)值較小,表明在下一個(gè)取樣周期產(chǎn)生的流表項(xiàng)較少,需要的空閑空間較少,此時(shí)可以保留更多的使用高頻率的流表項(xiàng)以減少控制器與交換機(jī)之間的交互次數(shù)。假設(shè)N′flow為取樣周期T+1 時(shí)在上個(gè)周期T 時(shí)就已經(jīng)存在的流表項(xiàng),Nnew為流表中新增的流表項(xiàng),T+1 時(shí)的流表空間如圖3(b)所示。
由式(7)和式(8)可知,若Nnew>Nempty則需要清除流表中的部分已經(jīng)存在的流表項(xiàng),為下一個(gè)周期中新增的流表項(xiàng)預(yù)留空間。此時(shí)需要從當(dāng)前流表中清除的流表項(xiàng)數(shù)目:
本文算法通過(guò)調(diào)用基于ARMA模型的預(yù)測(cè)算法對(duì)收集的歷史數(shù)據(jù)進(jìn)行分析,估計(jì)下一個(gè)取樣周期內(nèi)可能新增加的流表項(xiàng)數(shù)目,并且根據(jù)當(dāng)前流表空間使用情況計(jì)算出需要清除的流表項(xiàng)數(shù)目。最后在交換機(jī)中提前清除一定數(shù)目的使用頻率較低的流表項(xiàng),使交換機(jī)流表有足夠的空間容納在下一個(gè)取樣周期內(nèi)產(chǎn)生的流表項(xiàng)。與一般的LRU算法根據(jù)處理數(shù)據(jù)包的最后時(shí)間尋找優(yōu)先刪除的流表項(xiàng)不同,函數(shù)FindLeastPacketCount在當(dāng)前流表中尋找在上一個(gè)取樣周期中處理數(shù)據(jù)包數(shù)量最少的流表項(xiàng)作為優(yōu)先刪除的流表項(xiàng)。當(dāng)新增流表項(xiàng)數(shù)量遠(yuǎn)大于預(yù)測(cè)結(jié)果時(shí),調(diào)用一般LRU 算法對(duì)部分新增流表項(xiàng)進(jìn)行置換,防止流表項(xiàng)溢出。P-LRU算法的具體偽代碼描述如下。
輸入:數(shù)據(jù)流Fl ows={p0,p1,…,pn},交換機(jī)收集到的新增流條目歷史數(shù)據(jù)集dataold
輸出:調(diào)整后的流表FlowTable
FlowEntryReplacement_PLRU()
{for ?pi∈dataFlow do
{if(intervalTime ≤T)://每T 秒清除一次使用頻率低的流表項(xiàng)
{//調(diào)用預(yù)測(cè)算法對(duì)下一個(gè)周期內(nèi)新增流條目進(jìn)行預(yù)測(cè),得到預(yù)測(cè)值
Nnew←UseARMA(dataold);
//獲取當(dāng)前交換機(jī)流表
FlowTable ←getFlowtable()
//得到當(dāng)前交換機(jī)空閑流表數(shù)目
Nempty←getFreeEntryNum(FlowTable);
//計(jì)算出要清除的流表項(xiàng)數(shù)目Ndel
Ndel=Nnew-Nempty
//清除Ndel條流表項(xiàng)
While(Ndel>0)
{
deleteEntry ←FindLeastPacketCount(Flowtable);
//控制器發(fā)送Flow_mod消息給交換機(jī)刪除流表項(xiàng)
Flowtable.delete ←sendFlow_mod(deleteEntry);
Ndel--;
}
//更新歷史數(shù)據(jù)集
dataold ←update(dataold)
}
}
//若流表溢出則調(diào)用一般LRU算法更新流表
FlowTable ←LRU_FlowEntryReplacement(pi)
}
Return FlowTable;
}
為了驗(yàn)證算法的性能,本文使用真實(shí)的數(shù)據(jù)中心流量作為測(cè)試數(shù)據(jù),該數(shù)據(jù)來(lái)源于文獻(xiàn)[7]的校園數(shù)據(jù)中心所獲得的數(shù)據(jù)集。該數(shù)據(jù)中心擁有500 臺(tái)服務(wù)器以及22 臺(tái)交換機(jī),其數(shù)據(jù)集包含了E-mail、Web 服務(wù)和音頻視頻等數(shù)據(jù)流。該數(shù)據(jù)集原本用于分析數(shù)據(jù)包和數(shù)據(jù)流的傳輸特性對(duì)于丟包率、鏈路利用率以及鏈路阻塞等方面的影響。因此使用從數(shù)據(jù)集中所選取的數(shù)據(jù)進(jìn)行實(shí)驗(yàn),能夠有效地比較本文描述的3種流表更新算法對(duì)真實(shí)SDN數(shù)據(jù)中心網(wǎng)絡(luò)的影響。
本文使用RYU 控制器和mininet 仿真平臺(tái)搭建SDN 網(wǎng)絡(luò)環(huán)境。在實(shí)驗(yàn)過(guò)程中從數(shù)據(jù)集中選取3 組數(shù)據(jù)作為實(shí)驗(yàn)測(cè)試數(shù)據(jù),每組數(shù)據(jù)數(shù)據(jù)流類別在10~40k之間,數(shù)據(jù)包個(gè)數(shù)為400 萬(wàn)到800 萬(wàn)之間。每個(gè)數(shù)據(jù)包都包含時(shí)間戳、源地址、目的地址、數(shù)據(jù)包長(zhǎng)度等信息,并且按照各個(gè)數(shù)據(jù)包上的時(shí)間戳模擬數(shù)據(jù)包的到達(dá),SDN 交換機(jī)流表空間被設(shè)置為500 條。并且為了分析不同取樣周期可能對(duì)流表更新效果產(chǎn)生的影響,P-LRU算法在三組實(shí)驗(yàn)中分別將5 s、10 s、20 s 作為取樣周期對(duì)流表進(jìn)行更新。
本文使用3個(gè)指標(biāo)即新增流表項(xiàng)預(yù)測(cè)精度、數(shù)據(jù)包匹配率、控制器與交換機(jī)間平均每秒交換的信息數(shù)量,將本文所提P-LRU 算法與上文描述的FIFO 和LRU 算法進(jìn)行了比較。
新增流表項(xiàng)預(yù)測(cè)精度的計(jì)算公式如式(10)所示:
其中是Paop為預(yù)測(cè)精度,Prec為平均相對(duì)誤差。新增流表項(xiàng)的預(yù)測(cè)精度反映了預(yù)測(cè)算法對(duì)于下一取樣周期內(nèi)新增加的流表項(xiàng)數(shù)量的預(yù)測(cè)是否準(zhǔn)確,預(yù)測(cè)精度越高說(shuō)明預(yù)測(cè)結(jié)果與實(shí)際值之間的誤差越小。
流表匹配率的公式如式(11)所示:
流表匹配率是指到達(dá)交換機(jī)的數(shù)據(jù)包,在流表中能夠直接找到與之匹配的流表項(xiàng)的數(shù)量占到達(dá)交換機(jī)的總數(shù)據(jù)包數(shù)量的比率。假設(shè)Nmatch表示到達(dá)交換機(jī)的數(shù)據(jù)包能夠直接在交換機(jī)中找到匹配的流表項(xiàng)的數(shù)量,Nall表示到達(dá)交換機(jī)總的數(shù)據(jù)包數(shù)量。流表的匹配率越高說(shuō)明流表中使用頻率高的流表項(xiàng)越多,流表資源的使用效率也就越高。
消息交換數(shù)量是指在交換機(jī)在處理數(shù)據(jù)包的過(guò)程中,交換機(jī)與控制器之間平均每秒交換的消息數(shù)量。當(dāng)數(shù)據(jù)包在流表中找不到對(duì)應(yīng)的流表項(xiàng)時(shí),交換機(jī)與控制器之間會(huì)交換PacketIn、FlowModify、PacketOut 這3 種消息。當(dāng)交換機(jī)與控制器之間交換的消息越少時(shí),算法對(duì)控制器端所造成的負(fù)擔(dān)越小,算法效率也就越高。
5.2.1 新增流表項(xiàng)預(yù)測(cè)精度
在3組實(shí)驗(yàn)中,每一個(gè)取樣周期記錄一次本周期內(nèi)新增的流表項(xiàng)數(shù)量,收集前50 個(gè)數(shù)據(jù)作為初始?xì)v史數(shù)據(jù),使用預(yù)測(cè)模型對(duì)下一個(gè)周期內(nèi)產(chǎn)生的流表項(xiàng)數(shù)量進(jìn)行預(yù)測(cè)。為了驗(yàn)證ARMA模型對(duì)于新增流表項(xiàng)數(shù)量的預(yù)測(cè)效果,本文采用文獻(xiàn)[13]所使用的AR 模型作為對(duì)比,實(shí)驗(yàn)結(jié)果如表1~3所示。
表1 實(shí)驗(yàn)組1預(yù)測(cè)精度 %
表2 實(shí)驗(yàn)組2預(yù)測(cè)精度 %
表3 實(shí)驗(yàn)組3預(yù)測(cè)精度%
分析3 組實(shí)驗(yàn)結(jié)果可知:ARMA 模型總體上比AR模型的平均誤差更小,預(yù)測(cè)精度更高。這是因?yàn)锳R模型通過(guò)時(shí)間序列歷史數(shù)據(jù)的線性組合加上白噪聲建立自回歸方程對(duì)當(dāng)前數(shù)據(jù)進(jìn)行預(yù)測(cè),并且在預(yù)測(cè)的過(guò)程中認(rèn)為歷史數(shù)據(jù)中各個(gè)時(shí)期數(shù)值的隨機(jī)波動(dòng)可以相互抵消。但是在實(shí)際過(guò)程中,交換機(jī)在每個(gè)取樣周期中新增加的流表項(xiàng)數(shù)量具有較大的隨機(jī)性,各個(gè)時(shí)期所產(chǎn)生的隨機(jī)干擾或誤差并不能相互抵消,而這些隨機(jī)波動(dòng)的累積又會(huì)對(duì)預(yù)測(cè)結(jié)果產(chǎn)生較大影響。ARMA 模型由自回歸和移動(dòng)平均兩部分組成,綜合了AR 模型與MA 模型的優(yōu)勢(shì)。自回歸過(guò)程負(fù)責(zé)量化當(dāng)前數(shù)據(jù)與歷史數(shù)據(jù)之間的關(guān)系,移動(dòng)平均過(guò)程負(fù)責(zé)解決隨機(jī)變動(dòng)項(xiàng)的求解問(wèn)題。其中,移動(dòng)平均部分對(duì)原序列有修勻和平滑的作用,可以有效的削弱原序列的隨機(jī)波動(dòng)。因此,ARMA模型對(duì)于交換機(jī)新增流表項(xiàng)數(shù)量的預(yù)測(cè)結(jié)果比AR模型具有更小的誤差方差。與此同時(shí),隨著取樣周期的縮短,新增流表項(xiàng)歷史數(shù)據(jù)之間的變化趨勢(shì)變得更加明顯,ARMA 模型的預(yù)測(cè)結(jié)果與實(shí)際結(jié)果之間的誤差變小,預(yù)測(cè)精度也就更高。
5.2.2 流表匹配率
如圖4 為3 組實(shí)驗(yàn)中流表的匹配率,其中FIFO、LRU、LFU 和P-LRU 為本文所提到的4 種流表更新算法。由圖可知,P-LRU 算法的流表匹配率明顯高于FIFO、LRU 以及LFU 算法。FIFO 算法在4 種算法中的流表匹配率最低,原因在于FIFO 算法并未對(duì)每一條流表項(xiàng)根據(jù)使用頻率進(jìn)行區(qū)分,導(dǎo)致一些使用頻率較高的流表項(xiàng)被頻繁刪除。LRU 算法則會(huì)導(dǎo)致一些數(shù)據(jù)包時(shí)間間隔較長(zhǎng)但數(shù)據(jù)包數(shù)量較多的數(shù)據(jù)流的流表項(xiàng)被優(yōu)先刪除。LFU 算法的缺點(diǎn)在于會(huì)將一些新到達(dá)交換機(jī)的流表項(xiàng)當(dāng)作使用頻率較低的表項(xiàng)優(yōu)先刪除。P-LRU 算法可以很好的避免這些問(wèn)題,算法優(yōu)先清除在上一個(gè)取樣周期內(nèi)匹配數(shù)據(jù)包數(shù)量最少的流表項(xiàng),可以使交換機(jī)保存更多的在近期使用頻率較高的流表項(xiàng),有效提高了流表的匹配率。同時(shí),P-LRU 算法的取樣周期越短,對(duì)流表的更新速度也就越快,流表匹配率也就越高。
圖4 流表匹配率
5.2.3 信息交換數(shù)量
如圖5 為交換機(jī)與控制器之間平均每秒交換的信息數(shù)量。在3組實(shí)驗(yàn)中,F(xiàn)IFO算法因?yàn)樵趯?duì)流表進(jìn)行更新的過(guò)程中缺乏靈活性,所以在交換機(jī)與控制器之間產(chǎn)生的消息數(shù)量最多,對(duì)控制器端造成的負(fù)擔(dān)最重。而P-LRU算法平均每秒在交換機(jī)與控制器之間產(chǎn)生的消息數(shù)量最少。原因在于FIFO、LRU、LFU算法只有在流表空間不足的情況下才開始對(duì)流表資源進(jìn)行管理,具有一定的滯后性。而P-LRU 算法周期性地清除流表中使用頻率較低的流表項(xiàng),可以使交換機(jī)保持更多的空閑空間以容納新增流表項(xiàng),有效減少了交換機(jī)與控制器之間的交互次數(shù)。同時(shí),P-LRU 算法的取樣周期越短,控制器所需要獲取的當(dāng)前交換機(jī)的流表信息也就越多,交換機(jī)與控制器之間所交換的信息數(shù)量也相應(yīng)增多,控制器端的負(fù)載也就變得更重。
圖5 信息交換數(shù)量
在SDN 網(wǎng)絡(luò)中,因?yàn)榱鞅淼馁Y源有限以及控制器處理能力的不足,在網(wǎng)絡(luò)高峰期,交換機(jī)的性能受到嚴(yán)重影響。針對(duì)該問(wèn)題,文中提出了一種新的流表更新算法。在本文所提流表更新算法中,通過(guò)周期性的清除交換機(jī)中使用頻率較低的流表項(xiàng),使交換機(jī)在盡可能多的保存使用頻率較高的流表項(xiàng)的同時(shí),也留出足夠的流表空間以容納新增的流表項(xiàng)。通過(guò)模擬實(shí)驗(yàn)表明,本文所提算法相對(duì)于流表更新的一般方法可以有效提高流表的匹配率,降低控制器的負(fù)擔(dān),并且取樣周期會(huì)對(duì)流表的更新效果產(chǎn)生一定的影響。盡管如此,本文還是存在一些不足,比如在清除流表項(xiàng)的過(guò)程中只考慮到了每條流表項(xiàng)在過(guò)去一段時(shí)間內(nèi)的使用情況,而沒(méi)有考慮到該流表項(xiàng)在未來(lái)一段時(shí)間內(nèi)可能再次被使用到的可能性,因此對(duì)于流表項(xiàng)本身的特點(diǎn)還需要進(jìn)行深入研究。