基于Holt 雙參數(shù)指數(shù)平滑法的SDN 交換機(jī)流表超時(shí)優(yōu)化策略*

王宣立，黃道穎*，張安琳，董 帥，劉江豪

（1.鄭州輕工業(yè)大學(xué)計(jì)算機(jī)與通信工程學(xué)院，鄭州 450000；2.鄭州輕工業(yè)大學(xué)工程訓(xùn)練中心，鄭州 450000）

0 引言

軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）［1］作為一種集中控制的網(wǎng)絡(luò)架構(gòu)，它將控制與轉(zhuǎn)發(fā)分離，將所有的控制功能交給控制器，可以讓用戶在控制器上根據(jù)不同功能的應(yīng)用程序進(jìn)行軟件編程，因此，其特別適用于計(jì)算機(jī)軍用網(wǎng)絡(luò)未來架構(gòu)。通過在軍用網(wǎng)絡(luò)中實(shí)現(xiàn)SDN 控制器的功能，達(dá)到對網(wǎng)絡(luò)節(jié)點(diǎn)全方位的掌控，能更好地適應(yīng)戰(zhàn)場變化，滿足現(xiàn)代體系作戰(zhàn)網(wǎng)絡(luò)中對各聯(lián)網(wǎng)平臺的高效受控傳輸要求。目前SDN 主要使用OpenFlow 作為控制器與交換機(jī)之間的標(biāo)準(zhǔn)交互協(xié)議，在SDN 中，“流”被定義為具有一系列相同特征的數(shù)據(jù)包集合，如具有相同的目的MAC 地址、目的IP 地址等，而“流”的轉(zhuǎn)發(fā)則依靠OpenFlow 交換機(jī)中的流表來完成。為了實(shí)現(xiàn)對流不同粒度的匹配，OpenFlow 允許流表項(xiàng)匹配域中存在任意（ANY）字段，這使得OpenFlow 交換機(jī)采用三態(tài)內(nèi)容尋址存儲器（Ternary Content Addressable Memory，TCAM）來保存控制器下發(fā)的流表項(xiàng)，但TCAM 是一種昂貴且功耗高的存儲設(shè)備，且隨著OpenFlow 的發(fā)展，每條流表項(xiàng)的匹配字段達(dá)到15 個(gè)元組、356 位，這使得目前大部分的OpenFlow交換機(jī)僅能支持10 K～40 K 條流表規(guī)則，而這一數(shù)量遠(yuǎn)遠(yuǎn)小于網(wǎng)絡(luò)正常工作所需要的數(shù)量［2］，且在網(wǎng)絡(luò)流量高峰時(shí)期，大量的數(shù)據(jù)包導(dǎo)致流表項(xiàng)的突發(fā)性增多，使TCAM 內(nèi)存不足的問題更加突顯，這將導(dǎo)致嚴(yán)重的丟包和網(wǎng)絡(luò)延遲問題。OpenFlow 面臨著嚴(yán)重的流表容量受限的問題，所以流表優(yōu)化就成了一個(gè)研究熱點(diǎn)。

當(dāng)前OpenFlow 空間流表優(yōu)化主要有3 種方式:1）基于流表資源復(fù)用的優(yōu)化方式，計(jì)算流表項(xiàng)間的關(guān)聯(lián)度，將具有相同匹配域的流表項(xiàng)進(jìn)行壓縮，增加流表空間中的可用流表項(xiàng)數(shù)量［3-4］，但壓縮算法會影響對流細(xì)粒度的管理，且壓縮算法較為復(fù)雜，會占用大量控制器計(jì)算資源；2）基于多級流表的優(yōu)化方式，OpenFlow1.1 版本提出了多級流表的流表結(jié)構(gòu)，多級流表技術(shù)擴(kuò)大了存儲空間，但仍可以通過優(yōu)化流表之間的映射關(guān)系，提高資源使用效率［5-6］；3）基于流表超時(shí)時(shí)間的方式，每條流表項(xiàng)在被下發(fā)時(shí)，會被配置匹配域、計(jì)數(shù)器、超時(shí)時(shí)間等信息，通過調(diào)整流表超時(shí)時(shí)間，實(shí)現(xiàn)無效流表項(xiàng)的清除與有效流表項(xiàng)安裝的動態(tài)平衡，實(shí)現(xiàn)對TCAM 的充分使用。相較前兩種方式，基于流表超時(shí)時(shí)間的優(yōu)化方式，更具有可操作性和擴(kuò)展性，現(xiàn)有的研究成果仍有可供改進(jìn)之處，所以本文通過對流表超時(shí)時(shí)間進(jìn)行優(yōu)化，實(shí)現(xiàn)對數(shù)據(jù)平面轉(zhuǎn)發(fā)能力的優(yōu)化。

現(xiàn)有基于流表超時(shí)時(shí)間優(yōu)化方式中，文獻(xiàn)［7］通過分析OpenFlow 的流表超時(shí)機(jī)制，計(jì)算流表項(xiàng)的空閑資源代價(jià)，提出了一種動態(tài)流表項(xiàng)和靜態(tài)流表項(xiàng)相互轉(zhuǎn)化的機(jī)制，提高了控制器和交換機(jī)的流表資源利用率，但該方法未考慮實(shí)際的網(wǎng)絡(luò)負(fù)載情況；文獻(xiàn)［8］在控制器中添加緩存模塊，使用基于歷史信息的算法來預(yù)測合適的有效時(shí)間，并結(jié)合流表負(fù)載情況，避免流表空間溢出；文獻(xiàn)［9］采用統(tǒng)計(jì)分析新增流表項(xiàng)的數(shù)量，使用了二次指數(shù)平滑法預(yù)測下一個(gè)取樣周期的流表增量趨勢，動態(tài)調(diào)整流表中流表項(xiàng)的超時(shí)時(shí)間，以達(dá)到提高流表空間利用率的目的，但沒有考慮特定流表項(xiàng)的使用頻率問題，容易清除一些重要的流表項(xiàng)；文獻(xiàn)［10］采用ARMA 模型對交換機(jī)中的流表項(xiàng)進(jìn)行預(yù)測，并通過改進(jìn)現(xiàn)有的LRU 算法，提升了交換機(jī)中有效流表的數(shù)量，但ARMA 算法較為復(fù)雜，相較于其他的算法占用更多的控制器資源；文獻(xiàn)［11］結(jié)合控制器資源、OpenFlow交換機(jī)資源以及鏈路負(fù)載情況等信息，通過代價(jià)函數(shù)調(diào)整流表項(xiàng)的超時(shí)時(shí)間，但該方法需綜合多項(xiàng)信息，計(jì)算較為復(fù)雜，且在收集控制器信息時(shí)會產(chǎn)生大量的交互信息，會占用部分安全通道的資源。

本文通過Holt 雙參數(shù)指數(shù)平滑法的改進(jìn)算法，預(yù)測OpenFlow 交換機(jī)中流表數(shù)目的變化情況，以調(diào)整流表項(xiàng)超時(shí)時(shí)間的方式，實(shí)現(xiàn)交換機(jī)TCAM 的有效利用，且該算法相較于二次指數(shù)平滑法以及ARMA 算法具有實(shí)現(xiàn)簡單、計(jì)算量少以及控制器資源占用較少的特點(diǎn)，在調(diào)整流表超時(shí)時(shí)間的過程中，無需頻繁地與控制器進(jìn)行交互。

1 基于Holt 雙參數(shù)指數(shù)平滑法的流表超時(shí)更新策略

1.1 OpenFlow 流表更新機(jī)制

當(dāng)一條新的數(shù)據(jù)流到達(dá)交換機(jī)中，若無可以匹配的流表項(xiàng)，則由控制器通過Packet-in 消息將數(shù)據(jù)包的包頭信息封裝后上傳給控制器，由控制器計(jì)算轉(zhuǎn)發(fā)路徑并通過Flow-Mod 消息下發(fā)給交換機(jī)，從而實(shí)現(xiàn)數(shù)據(jù)包的轉(zhuǎn)發(fā)。

OpenFlow 的流表更新機(jī)制為控制器在下發(fā)流表項(xiàng)時(shí)會配置流表項(xiàng)的失效時(shí)間來清除流表，流表項(xiàng)的失效時(shí)間有Hard-timeout 和Idle-timeout 兩個(gè)參數(shù)，前者表示經(jīng)過該段時(shí)間后將流表項(xiàng)從流表中刪除；后者表示在該時(shí)間內(nèi)若無數(shù)據(jù)流匹配，則清除該條流表項(xiàng)，若匹配成功，則延長該流表的失效時(shí)間。設(shè)置Hard-timeout 的方式將超時(shí)時(shí)間設(shè)為一個(gè)固定值，這會導(dǎo)致某些使用頻率較高的流表項(xiàng)在達(dá)到超時(shí)時(shí)間后被刪除，從而觸發(fā)Packet-in 消息，請求再次下發(fā)流表項(xiàng)，從而增加控制器的負(fù)擔(dān)。所以，控制器通常為流表項(xiàng)配置Idle-timeout，這樣使用率較高的流表項(xiàng)就不會被刪除。當(dāng)流表空間滿載時(shí)，控制器會通過FIFO 算法和LRU 算法清除流表項(xiàng)，這兩種算法實(shí)現(xiàn)簡單，但都是基于局部特性，且有很大的隨機(jī)性，容易刪除一些重要的流表項(xiàng)，從而導(dǎo)致控制器需要重新計(jì)算新流的路徑，進(jìn)而導(dǎo)致占用控制器的資源。

本文通過采集OpenFlow 交換機(jī)流表項(xiàng)新增數(shù)目，預(yù)測接下來一個(gè)或多個(gè)周期內(nèi)流表空間的新增流表項(xiàng)數(shù)目，將流表項(xiàng)新增數(shù)目的預(yù)測轉(zhuǎn)為一個(gè)時(shí)間序列預(yù)測問題，通過適用于時(shí)間序列預(yù)測的算法，調(diào)整流表超時(shí)時(shí)間，達(dá)到提高OpenFlow 交換機(jī)利用率的效果。

1.2 預(yù)測方法分析

指數(shù)平滑法是一種簡單易用的預(yù)測方法，在各種基于時(shí)態(tài)的時(shí)間序列預(yù)測場景中有著廣泛的應(yīng)用，它以時(shí)間序列的歷史數(shù)據(jù)為參考，通過對時(shí)間序列的歷史值賦予不同的權(quán)重，對時(shí)間序列未來的趨勢進(jìn)行預(yù)測。在應(yīng)用中，若是對時(shí)間序列進(jìn)行長期預(yù)測，通常會對權(quán)重值賦予較小的值，這樣可以獲得較好的平滑效果，但若要能夠?qū)r(shí)間序列發(fā)生波動時(shí)進(jìn)行及時(shí)響應(yīng)，則采用“重近輕遠(yuǎn)”的思想，對距離預(yù)測值較近的觀察值賦予較大的權(quán)重，距離預(yù)測值較遠(yuǎn)的觀察值權(quán)重會較小。

T 為預(yù)測期數(shù)，T 越大，預(yù)測的期數(shù)越多。

二次指數(shù)平滑值是建立在一次指數(shù)平滑值基礎(chǔ)上的，將一次指數(shù)平滑公式遞推后可得到如下的展開式:

引入自適應(yīng)平滑參數(shù)后，Holt 雙參數(shù)指數(shù)平滑法在保留了指數(shù)平滑法“重近輕遠(yuǎn)”思想的同時(shí)，解決了指數(shù)平滑法初值難以確定、平滑參數(shù)無法自適應(yīng)調(diào)整的問題，且無需對時(shí)間序列進(jìn)行二次平滑，充分使用時(shí)間序列自身的信息，相較于二次指數(shù)平滑法，Holt 雙參數(shù)指數(shù)平滑法更適用于時(shí)間序列的預(yù)測。

1.3 基于Holt 雙參數(shù)指數(shù)平滑法的流表超時(shí)更新策略

OpenFlow 交換機(jī)流表空間大小可用流表項(xiàng)的數(shù)量反應(yīng)，總的流表空間由已存在的流表項(xiàng)和剩余流表空間組成，它們之間的關(guān)系可用下式表示:

其中，Nmax表示總的流表空間，Nactive表示當(dāng)前流表空間中存活的流表項(xiàng)數(shù)量，Nempty表示空余空間可容納流表項(xiàng)數(shù)量。

本文的主要目的是為了解決網(wǎng)絡(luò)流量高峰時(shí)期固定流表超時(shí)時(shí)間機(jī)制下無效流表項(xiàng)占用大量流表空間的問題，通過新增流表項(xiàng)數(shù)量的變化，反映網(wǎng)絡(luò)流量高峰時(shí)期網(wǎng)絡(luò)流量的變化。

綜上所述，給出基于Holt 雙參數(shù)指數(shù)平滑法的流表超時(shí)時(shí)間更新策略的流程圖，如圖1 所示。本流表超時(shí)時(shí)間更新策略周期性地采集交換機(jī)流表項(xiàng)新增數(shù)目構(gòu)建時(shí)間序列X，使用Holt 雙參數(shù)指數(shù)平滑法預(yù)測下一個(gè)周期的新增流表項(xiàng)數(shù)量，倘若剩余流表空間可以滿足預(yù)測新增流表項(xiàng)的需要，則不對現(xiàn)有流表項(xiàng)的超時(shí)時(shí)間進(jìn)行調(diào)整；但若剩余流表空間不能夠滿足新增流表項(xiàng)的需要，則選取足夠數(shù)目的、流表項(xiàng)Idle-age 最大的流表項(xiàng)對其進(jìn)行超時(shí)時(shí)間的調(diào)整，調(diào)整后若不能使無效流表項(xiàng)的刪除與新增流表項(xiàng)達(dá)到動態(tài)平衡，則繼續(xù)構(gòu)建流表新增數(shù)目的時(shí)間序列，預(yù)測新增流表項(xiàng)與交換機(jī)流表空間的需求關(guān)系，調(diào)整流表項(xiàng)的超時(shí)時(shí)間。

根據(jù)流程圖，給出基于Holt 雙參數(shù)指數(shù)平滑法的流表超時(shí)時(shí)間更新策略的偽代碼如下所示:

圖1 基于Holt 雙參數(shù)指數(shù)平滑法的流表超時(shí)更新策略流程圖

本文提出的流表超時(shí)時(shí)間更新策略，將Open-Flow 交換機(jī)負(fù)載狀態(tài)的變化轉(zhuǎn)化為時(shí)間序列預(yù)測問題，根據(jù)預(yù)測結(jié)果調(diào)整流表超時(shí)時(shí)間，以實(shí)現(xiàn)交換機(jī)有限流表空間的高效利用。相較于直接刪除流表項(xiàng)或?qū)λ械牧鞅眄?xiàng)進(jìn)行超時(shí)時(shí)間調(diào)整的方法，本文借鑒LRU 算法的思想，通過流表項(xiàng)的統(tǒng)計(jì)信息Idle-age，找出未到達(dá)流表超時(shí)時(shí)間的、最久未匹配過的流表項(xiàng)，對其進(jìn)行調(diào)整，減少了OpenFlow 交換機(jī)的流表空間震蕩，也在一定程度上減少OpenFlow交換機(jī)請求流表項(xiàng)下發(fā)消息的數(shù)目。

2 實(shí)驗(yàn)與仿真分析

為驗(yàn)證本文的算法，本文通過R 語言搭建模型，數(shù)據(jù)集選擇真實(shí)的網(wǎng)絡(luò)數(shù)據(jù)流，從中隨機(jī)選取5 000 類數(shù)據(jù)流，交換機(jī)的流表容量被設(shè)置為500條，每秒到達(dá)交換機(jī)中的數(shù)據(jù)流的最大數(shù)量為500條，控制器的性能設(shè)置為30 個(gè)/s，緩存10 組。

本文將從流表空間利用率、流表適配率和數(shù)據(jù)轉(zhuǎn)發(fā)成功率3 個(gè)方面檢驗(yàn)本機(jī)制效果，并與文獻(xiàn)［9］提出的二次指數(shù)平滑法（以下用SESM 表示）以及原有的機(jī)制（以下用Fixed 表示）進(jìn)行對比。

圖2 反映隨著數(shù)據(jù)流流速改變交換機(jī)中活動流表項(xiàng)的數(shù)目，原有的方法會造成超過1/3 的空間得不到有效利用，本文提出的方法及基于二次指數(shù)平滑法的流表超時(shí)時(shí)間動態(tài)調(diào)整方法，都可以使交換機(jī)的內(nèi)存空間得到充分使用。并且由于本文通過讀取Idle-age 對部分流表項(xiàng)進(jìn)行調(diào)整，使更多的流獲得更久的存活時(shí)間，從而保證足夠數(shù)量的流表項(xiàng)用于保證數(shù)據(jù)包的轉(zhuǎn)發(fā)。

圖2 不同數(shù)據(jù)流速率下3 種機(jī)制的流表空間利用率

流表適配率反映數(shù)據(jù)流與交換機(jī)中存在的流表匹配成功的概率。從圖3 可以看出，因?yàn)樵谧铋_始的時(shí)候，控制器根據(jù)交換機(jī)上傳的Packet-in 消息計(jì)算完轉(zhuǎn)發(fā)路徑后下發(fā)流表項(xiàng)給控制器，這時(shí)大多數(shù)流表項(xiàng)都可以得到匹配，所以3 種方法都有較好的適配效果，但隨著數(shù)據(jù)流速率的增大，固定Idle-timeout 超時(shí)機(jī)制因?yàn)闊o效流表項(xiàng)占用了部分空間，導(dǎo)致了新的有效流表項(xiàng)無法安裝，從而影響了匹配效果。本方法和SESM 方法都可以通過動態(tài)調(diào)整流表項(xiàng)超時(shí)時(shí)間的方式調(diào)整流表項(xiàng)的生存時(shí)間，獲得了較好的適配效果。但從圖中可以看到本方法的表現(xiàn)更好。

圖3 不同數(shù)據(jù)流速率下3 種機(jī)制的流表適配率

圖4 表示3 種機(jī)制在不同數(shù)據(jù)流速率下的數(shù)據(jù)轉(zhuǎn)發(fā)成功率。從曲線可知，在最初交換機(jī)流表空間未滿時(shí)，大多數(shù)數(shù)據(jù)包都可以得到順利轉(zhuǎn)發(fā)，但隨著時(shí)間的推移，3 種方法轉(zhuǎn)發(fā)成功率都有下降，原有的機(jī)制在網(wǎng)絡(luò)流量高并發(fā)時(shí)因無法及時(shí)安裝新的流表項(xiàng)，導(dǎo)致了丟包現(xiàn)象的產(chǎn)生，降低了轉(zhuǎn)發(fā)成功率。本文提出的方法相較于基于二次指數(shù)平滑法的流表超時(shí)時(shí)間，更能對流量的變化作出及時(shí)響應(yīng)，從而獲得了更好的效果。

圖4 不同數(shù)據(jù)流速率下3 種機(jī)制的數(shù)據(jù)包轉(zhuǎn)發(fā)成功率

3 結(jié)論

針對控制器設(shè)定固定值作為流表項(xiàng)的停滯超時(shí)時(shí)間造成交換機(jī)流表空間資源浪費(fèi)及影響網(wǎng)絡(luò)性能的問題，本文通過引入自適應(yīng)權(quán)重參數(shù)的Holt雙參數(shù)指數(shù)平滑法預(yù)測下一個(gè)周期流表項(xiàng)新增數(shù)量，根據(jù)交換機(jī)負(fù)載情況調(diào)整現(xiàn)有流表項(xiàng)的存活時(shí)間，提高了流表項(xiàng)的適配率和數(shù)據(jù)包的轉(zhuǎn)發(fā)效率，使交換機(jī)的資源得到更加充分的利用。但本方法并未對流表項(xiàng)進(jìn)行分類，有些業(yè)務(wù)的數(shù)據(jù)流可能存在較大的數(shù)據(jù)包時(shí)間間隔，這可能會導(dǎo)致其被頻繁刪除，從而影響該類業(yè)務(wù)的服務(wù)質(zhì)量，因此，本方法還存在可改進(jìn)之處。