基于ARMA模型預(yù)測(cè)的交換機(jī)流表更新算法

劉 釗，夏鴻斌，2

1江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫214122

2江南大學(xué) 江蘇省媒體設(shè)計(jì)與軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122

1 引言

隨著新型網(wǎng)絡(luò)技術(shù)的不斷涌現(xiàn)，網(wǎng)絡(luò)流量的增長(zhǎng)也變得十分迅速，不同的網(wǎng)絡(luò)應(yīng)用對(duì)于網(wǎng)絡(luò)資源的需求也變得越來越高。傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)由于自身結(jié)構(gòu)的僵化[1]越來越不能滿足用戶和業(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)而生，它通過將傳統(tǒng)網(wǎng)絡(luò)中的數(shù)據(jù)平面和控制平面解耦，將網(wǎng)絡(luò)邏輯與網(wǎng)絡(luò)設(shè)備分離開來，降低了網(wǎng)絡(luò)的復(fù)雜性和組網(wǎng)成本。SDN架構(gòu)以簡(jiǎn)單、可編程的方式控制網(wǎng)絡(luò)，它使得分布式的數(shù)據(jù)平面由一個(gè)集中控制的平面來管理。圖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ò)體系中，控制器通過OpenFlow[4]協(xié)議中的控制信道，對(duì)其管理域內(nèi)的所有交換機(jī)進(jìn)行配置。SDN 交換機(jī)將信息保存到本地的流表中。在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的過程中，交換機(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ā)來的數(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%的大象流卻傳輸了超過90%的字節(jié)，而處理這些老鼠流的流表項(xiàng)大量的占據(jù)了交換機(jī)的流表空間。由于對(duì)這些使用頻率較低的流表項(xiàng)的更新不及時(shí)，導(dǎo)致了交換機(jī)中流表的匹配率不能滿足實(shí)際的需求[8]，流表資源不能被充分利用。與此同時(shí)，隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，控制器也不可避免地暴露出處理能力有限的問題[9]。流表匹配率過低以及控制器端負(fù)載過重嚴(yán)重降低了SDN系統(tǒng)的整體性能。

2 相關(guā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ì)模型，并通過排隊(duì)論分析了hard_timeout對(duì)阻塞概率與流截?cái)啻螖?shù)的影響。該方法通過調(diào)整timeout 值有效提高了流表的匹配率，但對(duì)控制器造成的負(fù)擔(dān)較重。文獻(xiàn)[12]提出了一種OpenFlow 交換機(jī)流表自動(dòng)控制機(jī)制，用于解決在大數(shù)據(jù)流下交換機(jī)流表更新不及時(shí)造成的流表資源不足的問題。但是該方案所提出的對(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í)間的方法。在這兩種方法中，控制器通過分析每次的新增流表項(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í)間的過程中，未能考慮每一條流表項(xiàng)自身的特點(diǎn)，沒有根據(jù)每條流表項(xiàng)的使用頻率做出調(diào)整，因此具有進(jìn)一步的改進(jìn)空間。文獻(xiàn)[15]提出了一種基于LRU 的改進(jìn)型流表更新算法。他們將流表中的空閑空間作為一個(gè)緩存區(qū)，用于存放過期的流表項(xiàng)，并對(duì)每一條過期流表項(xiàng)進(jìn)行計(jì)時(shí)。當(dāng)有到達(dá)交換機(jī)的數(shù)據(jù)包與緩存區(qū)中過期的流表項(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ī)的流表并沒有太多空閑空間可以被用作緩存區(qū)，其所能存儲(chǔ)的流表項(xiàng)太少也就失去了意義。

針對(duì)上述問題，本文提出了一種基于ARMA 模型預(yù)測(cè)的流表更新算法。算法通過收集每個(gè)單位時(shí)間內(nèi)新增加的流表項(xiàng)數(shù)量，預(yù)測(cè)下一個(gè)時(shí)刻的新增流表項(xiàng)數(shù)量，并根據(jù)預(yù)測(cè)值提前刪除一定數(shù)量的最近一段時(shí)間內(nèi)使用頻率較低的流表項(xiàng)，為即將到來的數(shù)據(jù)流預(yù)留出足夠的流表空間。算法在提高流表匹配率的同時(shí)也減少了與控制器的交互次數(shù)，有效減輕了控制器的負(fù)擔(dān)。

算法框架如圖2所示。

圖2 算法框架

3 流表更新的一般方法

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í)，更新算法通過控制器主動(dòng)地向下層的交換機(jī)發(fā)送消息來刪除舊流表項(xiàng)。其中FIFO 置換算法和Random 置換算法的區(qū)別很小，在對(duì)流表進(jìn)行更新的過程中二者都有很大的隨機(jī)性。所以本文下面將對(duì)FIFO、LRU、LFU等流表更新算法進(jìn)行闡述。

3.1 基于先進(jìn)先出的置換算法

基于先進(jìn)先出的（FIFO）的流表更新算法因?yàn)閷?shí)現(xiàn)過程簡(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)說明該流表項(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ì)于流表更新算法的需求。

3.2 基于近期最少使用的置換算法

基于近期最少使用（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í)間沒有數(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í)間沒有處理數(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)被頻繁刪除。

3.3 基于最不經(jīng)常使用的置換算法

基于最不經(jīng)常使用（LFU）的流表更新算法在流表空間不足時(shí)，根據(jù)每條流表項(xiàng)歷史訪問次數(shù)，優(yōu)先刪除匹配數(shù)據(jù)包數(shù)量最少的流表項(xiàng)。流表中的匹配計(jì)數(shù)器可用于記錄每條流表項(xiàng)所匹配過的數(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)前流表中匹配過數(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)。

4 基于ARMA模型預(yù)測(cè)的流表更新算法

在網(wǎng)絡(luò)流量的高峰期，現(xiàn)有的一般流表更新算法不能很好的解決流表資源不足以及控制器負(fù)擔(dā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ī)的流表擁有了足夠的空閑空間容納新增流表項(xiàng)，并且在增加了流表的匹配率的同時(shí)，減少了交換機(jī)與控制器間交互的次數(shù)，有效降低了控制器端的負(fù)擔(dān)。

4.1 基于ARMA模型的數(shù)據(jù)分析

自回歸移動(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)，并由此來預(yù)測(cè)下一個(gè)時(shí)刻的數(shù)值。其中作為預(yù)測(cè)對(duì)象的Xt受到前P個(gè)時(shí)間序列數(shù)值的影響，其自回歸過程如下式：

式中，φ1,φ2,…,φp為自回歸系數(shù)，{Xt}為新增流表項(xiàng)數(shù)量所形成的時(shí)間序列數(shù)值，et為誤差項(xiàng)。

誤差項(xiàng)在不同時(shí)期具有依存關(guān)系，其移動(dòng)平均過程如下式表示：

式中，θ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ì)

接下來，根據(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 等。通過調(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。

4.2 清除流表項(xiàng)數(shù)目分析

在交換機(jī)轉(zhuǎn)發(fā)數(shù)據(jù)包的過程中，流表空間的大小、控制器處理信息的能力的不足是制約交換機(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是流表的空閑空間。通過對(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ù)目：

4.3 流表優(yōu)化算法（P-LRU）

本文算法通過調(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；

}

5 模擬實(shí)驗(yàn)

為了驗(yàn)證算法的性能，本文使用真實(shí)的數(shù)據(jù)中心流量作為測(cè)試數(shù)據(jù)，該數(shù)據(jù)來源于文獻(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)過程中從數(shù)據(jù)集中選取3 組數(shù)據(jù)作為實(shí)驗(yàn)測(cè)試數(shù)據(jù)，每組數(shù)據(jù)數(shù)據(jù)流類別在10～40k之間，數(shù)據(jù)包個(gè)數(shù)為400 萬到800 萬之間。每個(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)行更新。

5.1 性能指標(biāo)

本文使用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è)精度越高說明預(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ù)量。流表的匹配率越高說明流表中使用頻率高的流表項(xiàng)越多，流表資源的使用效率也就越高。

消息交換數(shù)量是指在交換機(jī)在處理數(shù)據(jù)包的過程中，交換機(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 實(shí)驗(yàn)結(jié)果

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模型通過時(shí)間序列歷史數(shù)據(jù)的線性組合加上白噪聲建立自回歸方程對(duì)當(dāng)前數(shù)據(jù)進(jìn)行預(yù)測(cè)，并且在預(yù)測(cè)的過程中認(rèn)為歷史數(shù)據(jù)中各個(gè)時(shí)期數(shù)值的隨機(jī)波動(dòng)可以相互抵消。但是在實(shí)際過程中，交換機(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ì)。自回歸過程負(fù)責(zé)量化當(dāng)前數(shù)據(jù)與歷史數(shù)據(jù)之間的關(guān)系，移動(dòng)平均過程負(fù)責(zé)解決隨機(jī)變動(dòng)項(xiàng)的求解問題。其中，移動(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 算法可以很好的避免這些問題，算法優(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)行更新的過程中缺乏靈活性，所以在交換機(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ù)量

6 結(jié)束語

在SDN 網(wǎng)絡(luò)中，因?yàn)榱鞅淼馁Y源有限以及控制器處理能力的不足，在網(wǎng)絡(luò)高峰期，交換機(jī)的性能受到嚴(yán)重影響。針對(duì)該問題，文中提出了一種新的流表更新算法。在本文所提流表更新算法中，通過周期性的清除交換機(jī)中使用頻率較低的流表項(xiàng)，使交換機(jī)在盡可能多的保存使用頻率較高的流表項(xiàng)的同時(shí)，也留出足夠的流表空間以容納新增的流表項(xiàng)。通過模擬實(shí)驗(yàn)表明，本文所提算法相對(duì)于流表更新的一般方法可以有效提高流表的匹配率，降低控制器的負(fù)擔(dān)，并且取樣周期會(huì)對(duì)流表的更新效果產(chǎn)生一定的影響。盡管如此，本文還是存在一些不足，比如在清除流表項(xiàng)的過程中只考慮到了每條流表項(xiàng)在過去一段時(shí)間內(nèi)的使用情況，而沒有考慮到該流表項(xiàng)在未來一段時(shí)間內(nèi)可能再次被使用到的可能性，因此對(duì)于流表項(xiàng)本身的特點(diǎn)還需要進(jìn)行深入研究。