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

（1.鄭州輕工業(yè)大學計算機與通信工程學院，鄭州 450000；2.鄭州輕工業(yè)大學工程訓練中心，鄭州 450000）

0 引言

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

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

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

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

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

1.1 OpenFlow 流表更新機制

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

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

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

1.2 預(yù)測方法分析

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

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

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

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

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

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

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

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

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

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

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

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

2 實驗與仿真分析

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

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

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

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

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

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

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

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

3 結(jié)論

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