SDN動態停滯超時時間優化算法*

劉 霞, 楊桂芹, 邵軍花, 蔣占軍

(蘭州交通大學 電子與信息工程學院,甘肅 蘭州 730070)

0 引 言

隨著互聯網時代信息的爆炸式增長，云計算、大數據的產生，傳統的網絡結構已無法滿足信息技術的要求。因此軟件定義網絡(software defined network, SDN)隨之產生[1]。

SDN作為一種新興的網絡體系結構，將控制平面與轉發平面解耦[2]，交換機將控制器下發的配置信息存儲到各自的流表中，由于交換機的流表空間資源有限，不能無限制地儲存攜帶不同配置信息的不同流表項，當數據量龐大時，數據流類型會相應增加，會導致大量數據包涌入控制器的情況出現，降低SDN的性能及效率。

Zarek A等人在實際網絡中測試分析，發現了流表項的停滯超時時間與流表資源利用率之間存在一定的關系[3]，此后，研究人員開始陸續采用改進停滯超時時間的方式來對流表進行優化。Kim T等人用AR預測算法對下個取樣周期內到達流進行預測，提出了一種動態調整流表項超時時間的方案[4]；Zhu H等人提出了一種能夠動態調整停滯超時時間的智能控制機制[5]；付應輝等人提出了FDO算法，引入了資源偏好度，對停滯超時時間的設置進行了一定的改進[6]；Zhang L等人借助排隊論提出一種有效利用交換機資源的方案[7]；唐菀等人通過對流表項工作機制的分析，提出了一種動靜態流表項轉換機制對停滯超時時間進行設置[8]。

上述方法都對SDN中的流表項超時時間進行了一定的研究，但均未考慮到根據網絡實際負載，且相應算法復雜，在達到目的的同時增加了控制器負擔。

因此，本文在前述工作的基礎上，提出了一種動態停滯超時時間優化(dynamic timeout time optimization,DTO)算法，采用一種動態參數對流表項停滯超時時間進行動態調整，以期提升流表空間資源利用率、流表匹配率，提高SDN的性能。

1 算法分析

1.1 流表項停滯超時時間原理分析

在SDN交換機中，每個流表都由多條流表項組成，每個流表項對應一個特定的流，流表項通常由六部分組成，如圖1所示。

圖1 流表結構

流表項中的匹配域內儲存著數據流的匹配信息，當新流進入流表后與各流表項的匹配域進行比對，當流表項在一定時間內無新流與之匹配時，該流表項將被清除出流表，這個設定值就稱為停滯超時時間。

不同的停滯超時時間對于流表乃至整個網絡的工作都有影響。若停滯超時時間設置過小，舊流表項會被頻繁地移出流表，導致數據包進入流表時無法匹配到對應的流表項，發送packet-in數據包給控制器，占用控制器計算資源，降低網絡性能，如圖2(a)所示；而當停滯超時時間設置過大時，流表項在流表中的占用時間過長，導致新增流表項無法進入流表，降低了交換機的流表空間利用率，如圖2(b)所示。

圖2 停滯超時時間設置示意

從上述分析可見，在流表容量一定的條件下，可將各流表項設置合適的停滯超時時間來對流表進行優化。

1.2 DTO算法分析

1.2.1 動態指數平滑法預測算法分析

若要更精確地調整流表項停滯超時時間，必須預測下一時間周期內的新增流表項數量，本文在設計DTO算法時引入預測模塊來提高設置精確度。傳統的AR預測算法計算復雜度高，對控制器性能影響較大，綜合考慮算法復雜度及預測精度，采用動態指數平滑DES法預測算法對下一時間周期內新增流表項數量進行預測。

通過對歷史數據的收集,可得每個時間周期內流表新增流表項的數量,新增流表項可將其看作是時間序列，指數平滑法正是一種針對時間序列的預測方法，因此可運用在新增流表項的預測之中。加權則遵循“厚近薄遠”的思想，即距離預測時刻越近的時間周期內的數據所占的權重越大，因此，準確地把握臨近時間周期的歷史數據，同時又不至于被異常數據影響過大，可提高預測準確度。

設{Xt}為新增流表項觀測值的序列，則一次指數平滑值的計算公式[9～11]為

Ft=αXt+(1-α)Yt-1

(1)

式中F0稱為初始平滑值，Ft為t時刻的平滑值，α為平滑系數，滿足0<α<1。而一次指數平滑模型的預測值為

(2)

為盡可能減小預測誤差，本文采用二次指數平滑法預測新增流表項數量。在一次指數平滑的基礎上再次進行指數平滑，其平滑值計算方法為[12,13]

(3)

則對時間序列建立的預測模型為

(4)

(5)

此外，為解決平滑初始值F0以及平滑參數α難以確定的缺點，引入了參數μt，對應不同時刻的觀測值序列{Xt}，有不同的取值與之對應，令

(6)

可見，μt為t的函數，且當0<α<1，t>1時，0<μt<1，滿足平滑參數的要求。當t=1時，有

(7)

則可令初始狀態值為μt=1，μt為時間序列{Xt}的動態平滑參數。因此，{Xt}序列以μt為動態平滑參數的動態指數平滑法預測模型為

(8)

取動態參數μt是為了依據不同情況得到更準確的預測值，但動態的μt依然要依賴于一個固定的α，而α的取值應根據預測誤差的平方SSE(均方差)做出變化，以均方差最小為目標建立α的優化模型，如下式

(10)

1.2.2 流表項停滯超時時間優化算法分析

以往的算法對于數據量時刻變化的網絡并不適用，為解決這一缺點，DTO算法考慮當前網絡中的實際負載，引入了動態參數，根據網絡負載變化做動態停滯超時時間優化。

從整體結構上講，流表容量可表示為Nmax=Nc+Ne，Nc為取樣周期為T時刻的實際流表項數量，Ne為取樣周期為T時刻的空余流表項數量。通過對歷史數據的分析預測到下一時刻將會進入流表的新增流表項的數量，記為y，當yNe時，說明新增流表項數量多于流表中的空余空間，此時，需要將部分流表項清除出流表，為即將到達流表的新流表項移出足夠的空間。引入動態參數對停滯超時時間進行調整如下

(11)

式中tori為流表項的初始停滯超時時間，而tmod為經過調整后的停滯超時時間。上式表示當yNe時，則需要通過參數p對初始停滯超時時間進行調整，以滿足新增流表項對流表剩余空間的需求。

1.3 DTO算法

綜合上述分析，本文所提出的DTO算法分為2個模塊，模塊1為新增流表項數量預測模塊，它為整個算法提供了數據基礎，首先收集歷史時刻的流表項數量的實測序列，而后利用動態指數平滑(DES)模型得到下一時間周期的新增流表項數量的預測值，至此模塊1的工作完成。而模塊2利用該預測值與網絡當時的負載狀況，采用動態參數對流表項停滯超時時間進行優化調整后，輸出新流表。

DTO整體算法實現過程如下：

模塊1：

1)收集歷史新增流表項數量數據；

2)DES算法計算出估計值；

模塊2：

6)若p>1，tmod=tori，否則tmod=p*tori；

7)此時各流表項的超時停滯時間為ti(i=1,2,3，…，Nc)，若ti=0，則將此流表項清除出流表，否則令ti=tmod；

8)輸出調整后的流表。

2 結果與分析

本文采用SDN常用仿真軟件Mininet搭建實驗環境，在主機上的VMware workstation中安裝Ubantu14.04LTS虛擬機，并在其中安裝Mininet和Ryu控制器。OpenFlow 交換機以及主機都用Mininet模擬實現，并用sFlow對整個網絡進行流量監控及數據分析。

實驗中指定交換機中的數據流最多有105條且呈波動狀態，交換機的流表總容量為300，流類別為990，本文將通過平均吞吐量、流表資源利用率、流表匹配率3個指標對DES算法效果進行驗證，同時與不使用流表優化算法的初始網絡、傳統AR算法的優化網絡以及FDO算法的優化網絡3種情況下的各指標進行比較。

2.1 流表匹配率分析

本文提出的DTO算法的直接效果是盡可能多地使進入流表的數據流能夠與流表項成功匹配，因此，流表匹配率的大小直接反映了優化效果。圖3(a)所示為流表匹配率的實驗結果。

隨數據流數量的增加，流表匹配率呈現先下降后穩定的狀態。開始時由于數據量以及流類別未超過流表容量，4種網絡下流表匹配率均接近100 %。隨著數據量大幅增加，初始網絡的流表匹配率急劇降低，當數據量超過5 000時，匹配率基本穩定在65 %左右；而優化后的3種網絡雖然也有下降，但幅度不大。在同樣的網絡條件下，數據量超過4 000時，AR算法與FDO算法優化網絡的流表匹配率在83 %左右浮動，DTO算法由于添加了動態調整參數，流表匹配率在86 %左右浮動，優化效果明顯。

2.2 流表資源利用率分析

流表資源利用率可以反映交換機流表空間的利用狀況，若流表資源利用率低則表示流表空間未充分使用即交換機性能低。圖3(b)為4種網絡下的流表資源利用率曲線。

從整體上看，4條曲線均為先增大后平穩的狀況。在網絡中數據量較少時，4種網絡下的流表資源均未得到充分利用。隨著數據量的增大，流表資源利用率提高；當網絡中的數據量持續增加時，4種情況下的流表資源利用率均達到了基本穩定狀態，這是由于SDN的轉發機制導致交換機在大數據量的情況下只能等待控制器配置流表項，出現了性能瓶頸。但從圖中可明顯看出優化后的三種網絡利用率遠高于未使用優化算法的初始網絡，AR算法與FDO算法的流表利用率均維持在76 %左右，而本文提出的DTO算法優化方案對流表項利用率的提升穩定在78 %左右，優于其他兩種算法。

2.3 網絡平均吞吐量分析

當數據量增大時，由于交換機處理能力的不足，會限制網絡的平均吞吐量，使其達到瓶頸。因此,本文算法對于交換機性能的提升也將會對同時提高網絡平均吞吐量。實驗結果如圖3(c)所示。

在數據流數量較小時，4種網絡的吞吐量均在增加；但隨著網絡中的數據量的逐步增大，初始網絡的吞吐量明顯到達了其瓶頸，且略有下降趨勢。而傳統AR算法的優化網絡對這一現象略有改善，但是在數據量超過8 000時也呈現出下降趨勢，這是由于AR算法雖然對交換機的性能有所改善，使得吞吐量有了短暫的提升，但是其算法的復雜度增加了控制器的負擔，當數據量不斷增加時，控制器的性能限制了其整體的網絡性能。從曲線走勢可以看出，FDO算法與本文的DTO算法優化網絡的吞吐量都在不斷提升且最終達到了穩定狀態，并未出現大幅度下降趨勢，但DTO算法的優化效果明顯強于FDO算法的優化效果，本文的DTO算法吞吐量最終達到了75 MbPs左右，而FDO算法只達到了72 MbPs，可見，在同樣的網絡狀況下，采用DTO算法進行優化的網絡吞吐量明顯高于其他三種網絡并能夠保持穩定。

圖3 仿真結果

綜合以上實驗結果，對于數據流數量大的SDN，3種優化網絡相比未優化的初始網絡對于網絡性能的提升是顯而易見的。另外，相比于傳統的AR算法和FDO算法，本文的優化算法達到了相對較高的流表匹配率、流表資源利用率以及網絡平均吞吐量，而這3個參數分別直觀地體現了算法的直接效果、交換機的性能以及整個SDN的性能，因此本文的優化算法實現了更佳的優化目的。

3 結 論

通過仿真驗證與分析可知，在同樣的網絡下，DTO算法相比于初始網絡以及其他兩種優化算法能有效地提高流表資源利用、流表項的匹配率，提升網絡的整體性能。但在設計方案時未考慮每個流表項使用頻率不同這一因素，后續將繼續改進算法，依據頻率高低，對不同的流表項做出不同的處理。