SDN動(dòng)態(tài)停滯超時(shí)時(shí)間優(yōu)化算法*

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

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

0 引 言

隨著互聯(lián)網(wǎng)時(shí)代信息的爆炸式增長(zhǎng)，云計(jì)算、大數(shù)據(jù)的產(chǎn)生，傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)已無(wú)法滿足信息技術(shù)的要求。因此軟件定義網(wǎng)絡(luò)(software defined network, SDN)隨之產(chǎn)生[1]。

SDN作為一種新興的網(wǎng)絡(luò)體系結(jié)構(gòu)，將控制平面與轉(zhuǎn)發(fā)平面解耦[2]，交換機(jī)將控制器下發(fā)的配置信息存儲(chǔ)到各自的流表中，由于交換機(jī)的流表空間資源有限，不能無(wú)限制地儲(chǔ)存攜帶不同配置信息的不同流表項(xiàng)，當(dāng)數(shù)據(jù)量龐大時(shí)，數(shù)據(jù)流類型會(huì)相應(yīng)增加，會(huì)導(dǎo)致大量數(shù)據(jù)包涌入控制器的情況出現(xiàn)，降低SDN的性能及效率。

Zarek A等人在實(shí)際網(wǎng)絡(luò)中測(cè)試分析，發(fā)現(xiàn)了流表項(xiàng)的停滯超時(shí)時(shí)間與流表資源利用率之間存在一定的關(guān)系[3]，此后，研究人員開始陸續(xù)采用改進(jìn)停滯超時(shí)時(shí)間的方式來(lái)對(duì)流表進(jìn)行優(yōu)化。Kim T等人用AR預(yù)測(cè)算法對(duì)下個(gè)取樣周期內(nèi)到達(dá)流進(jìn)行預(yù)測(cè)，提出了一種動(dòng)態(tài)調(diào)整流表項(xiàng)超時(shí)時(shí)間的方案[4]；Zhu H等人提出了一種能夠動(dòng)態(tài)調(diào)整停滯超時(shí)時(shí)間的智能控制機(jī)制[5]；付應(yīng)輝等人提出了FDO算法，引入了資源偏好度，對(duì)停滯超時(shí)時(shí)間的設(shè)置進(jìn)行了一定的改進(jìn)[6]；Zhang L等人借助排隊(duì)論提出一種有效利用交換機(jī)資源的方案[7]；唐菀等人通過對(duì)流表項(xiàng)工作機(jī)制的分析，提出了一種動(dòng)靜態(tài)流表項(xiàng)轉(zhuǎn)換機(jī)制對(duì)停滯超時(shí)時(shí)間進(jìn)行設(shè)置[8]。

上述方法都對(duì)SDN中的流表項(xiàng)超時(shí)時(shí)間進(jìn)行了一定的研究，但均未考慮到根據(jù)網(wǎng)絡(luò)實(shí)際負(fù)載，且相應(yīng)算法復(fù)雜，在達(dá)到目的的同時(shí)增加了控制器負(fù)擔(dān)。

因此，本文在前述工作的基礎(chǔ)上，提出了一種動(dòng)態(tài)停滯超時(shí)時(shí)間優(yōu)化(dynamic timeout time optimization,DTO)算法，采用一種動(dòng)態(tài)參數(shù)對(duì)流表項(xiàng)停滯超時(shí)時(shí)間進(jìn)行動(dòng)態(tài)調(diào)整，以期提升流表空間資源利用率、流表匹配率，提高SDN的性能。

1 算法分析

1.1 流表項(xiàng)停滯超時(shí)時(shí)間原理分析

在SDN交換機(jī)中，每個(gè)流表都由多條流表項(xiàng)組成，每個(gè)流表項(xiàng)對(duì)應(yīng)一個(gè)特定的流，流表項(xiàng)通常由六部分組成，如圖1所示。

圖1 流表結(jié)構(gòu)

流表項(xiàng)中的匹配域內(nèi)儲(chǔ)存著數(shù)據(jù)流的匹配信息，當(dāng)新流進(jìn)入流表后與各流表項(xiàng)的匹配域進(jìn)行比對(duì)，當(dāng)流表項(xiàng)在一定時(shí)間內(nèi)無(wú)新流與之匹配時(shí)，該流表項(xiàng)將被清除出流表，這個(gè)設(shè)定值就稱為停滯超時(shí)時(shí)間。

不同的停滯超時(shí)時(shí)間對(duì)于流表乃至整個(gè)網(wǎng)絡(luò)的工作都有影響。若停滯超時(shí)時(shí)間設(shè)置過小，舊流表項(xiàng)會(huì)被頻繁地移出流表，導(dǎo)致數(shù)據(jù)包進(jìn)入流表時(shí)無(wú)法匹配到對(duì)應(yīng)的流表項(xiàng)，發(fā)送packet-in數(shù)據(jù)包給控制器，占用控制器計(jì)算資源，降低網(wǎng)絡(luò)性能，如圖2(a)所示；而當(dāng)停滯超時(shí)時(shí)間設(shè)置過大時(shí)，流表項(xiàng)在流表中的占用時(shí)間過長(zhǎng)，導(dǎo)致新增流表項(xiàng)無(wú)法進(jìn)入流表，降低了交換機(jī)的流表空間利用率，如圖2(b)所示。

圖2 停滯超時(shí)時(shí)間設(shè)置示意

從上述分析可見，在流表容量一定的條件下，可將各流表項(xiàng)設(shè)置合適的停滯超時(shí)時(shí)間來(lái)對(duì)流表進(jìn)行優(yōu)化。

1.2 DTO算法分析

1.2.1 動(dòng)態(tài)指數(shù)平滑法預(yù)測(cè)算法分析

若要更精確地調(diào)整流表項(xiàng)停滯超時(shí)時(shí)間，必須預(yù)測(cè)下一時(shí)間周期內(nèi)的新增流表項(xiàng)數(shù)量，本文在設(shè)計(jì)DTO算法時(shí)引入預(yù)測(cè)模塊來(lái)提高設(shè)置精確度。傳統(tǒng)的AR預(yù)測(cè)算法計(jì)算復(fù)雜度高，對(duì)控制器性能影響較大，綜合考慮算法復(fù)雜度及預(yù)測(cè)精度，采用動(dòng)態(tài)指數(shù)平滑DES法預(yù)測(cè)算法對(duì)下一時(shí)間周期內(nèi)新增流表項(xiàng)數(shù)量進(jìn)行預(yù)測(cè)。

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

設(shè){Xt}為新增流表項(xiàng)觀測(cè)值的序列，則一次指數(shù)平滑值的計(jì)算公式[9～11]為

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

(1)

式中F0稱為初始平滑值，F(xiàn)t為t時(shí)刻的平滑值，α為平滑系數(shù)，滿足0<α<1。而一次指數(shù)平滑模型的預(yù)測(cè)值為

(2)

為盡可能減小預(yù)測(cè)誤差，本文采用二次指數(shù)平滑法預(yù)測(cè)新增流表項(xiàng)數(shù)量。在一次指數(shù)平滑的基礎(chǔ)上再次進(jìn)行指數(shù)平滑，其平滑值計(jì)算方法為[12,13]

(3)

則對(duì)時(shí)間序列建立的預(yù)測(cè)模型為

(4)

(5)

此外，為解決平滑初始值F0以及平滑參數(shù)α難以確定的缺點(diǎn)，引入了參數(shù)μt，對(duì)應(yīng)不同時(shí)刻的觀測(cè)值序列{Xt}，有不同的取值與之對(duì)應(yīng)，令

(6)

可見，μt為t的函數(shù)，且當(dāng)0<α<1，t>1時(shí)，0<μt<1，滿足平滑參數(shù)的要求。當(dāng)t=1時(shí)，有

(7)

則可令初始狀態(tài)值為μt=1，μt為時(shí)間序列{Xt}的動(dòng)態(tài)平滑參數(shù)。因此，{Xt}序列以μt為動(dòng)態(tài)平滑參數(shù)的動(dòng)態(tài)指數(shù)平滑法預(yù)測(cè)模型為

(8)

取動(dòng)態(tài)參數(shù)μt是為了依據(jù)不同情況得到更準(zhǔn)確的預(yù)測(cè)值，但動(dòng)態(tài)的μt依然要依賴于一個(gè)固定的α，而α的取值應(yīng)根據(jù)預(yù)測(cè)誤差的平方SSE(均方差)做出變化，以均方差最小為目標(biāo)建立α的優(yōu)化模型，如下式

(10)

1.2.2 流表項(xiàng)停滯超時(shí)時(shí)間優(yōu)化算法分析

以往的算法對(duì)于數(shù)據(jù)量時(shí)刻變化的網(wǎng)絡(luò)并不適用，為解決這一缺點(diǎn)，DTO算法考慮當(dāng)前網(wǎng)絡(luò)中的實(shí)際負(fù)載，引入了動(dòng)態(tài)參數(shù)，根據(jù)網(wǎng)絡(luò)負(fù)載變化做動(dòng)態(tài)停滯超時(shí)時(shí)間優(yōu)化。

從整體結(jié)構(gòu)上講，流表容量可表示為Nmax=Nc+Ne，Nc為取樣周期為T時(shí)刻的實(shí)際流表項(xiàng)數(shù)量，Ne為取樣周期為T時(shí)刻的空余流表項(xiàng)數(shù)量。通過對(duì)歷史數(shù)據(jù)的分析預(yù)測(cè)到下一時(shí)刻將會(huì)進(jìn)入流表的新增流表項(xiàng)的數(shù)量，記為y，當(dāng)yNe時(shí)，說(shuō)明新增流表項(xiàng)數(shù)量多于流表中的空余空間，此時(shí)，需要將部分流表項(xiàng)清除出流表，為即將到達(dá)流表的新流表項(xiàng)移出足夠的空間。引入動(dòng)態(tài)參數(shù)對(duì)停滯超時(shí)時(shí)間進(jìn)行調(diào)整如下

(11)

式中tori為流表項(xiàng)的初始停滯超時(shí)時(shí)間，而tmod為經(jīng)過調(diào)整后的停滯超時(shí)時(shí)間。上式表示當(dāng)yNe時(shí)，則需要通過參數(shù)p對(duì)初始停滯超時(shí)時(shí)間進(jìn)行調(diào)整，以滿足新增流表項(xiàng)對(duì)流表剩余空間的需求。

1.3 DTO算法

綜合上述分析，本文所提出的DTO算法分為2個(gè)模塊，模塊1為新增流表項(xiàng)數(shù)量預(yù)測(cè)模塊，它為整個(gè)算法提供了數(shù)據(jù)基礎(chǔ)，首先收集歷史時(shí)刻的流表項(xiàng)數(shù)量的實(shí)測(cè)序列，而后利用動(dòng)態(tài)指數(shù)平滑(DES)模型得到下一時(shí)間周期的新增流表項(xiàng)數(shù)量的預(yù)測(cè)值，至此模塊1的工作完成。而模塊2利用該預(yù)測(cè)值與網(wǎng)絡(luò)當(dāng)時(shí)的負(fù)載狀況，采用動(dòng)態(tài)參數(shù)對(duì)流表項(xiàng)停滯超時(shí)時(shí)間進(jìn)行優(yōu)化調(diào)整后，輸出新流表。

DTO整體算法實(shí)現(xiàn)過程如下：

模塊1：

1)收集歷史新增流表項(xiàng)數(shù)量數(shù)據(jù)；

2)DES算法計(jì)算出估計(jì)值；

模塊2：

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

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

8)輸出調(diào)整后的流表。

2 結(jié)果與分析

本文采用SDN常用仿真軟件Mininet搭建實(shí)驗(yàn)環(huán)境，在主機(jī)上的VMware workstation中安裝Ubantu14.04LTS虛擬機(jī)，并在其中安裝Mininet和Ryu控制器。OpenFlow 交換機(jī)以及主機(jī)都用Mininet模擬實(shí)現(xiàn)，并用sFlow對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行流量監(jiān)控及數(shù)據(jù)分析。

實(shí)驗(yàn)中指定交換機(jī)中的數(shù)據(jù)流最多有105條且呈波動(dòng)狀態(tài)，交換機(jī)的流表總?cè)萘繛?00，流類別為990，本文將通過平均吞吐量、流表資源利用率、流表匹配率3個(gè)指標(biāo)對(duì)DES算法效果進(jìn)行驗(yàn)證，同時(shí)與不使用流表優(yōu)化算法的初始網(wǎng)絡(luò)、傳統(tǒng)AR算法的優(yōu)化網(wǎng)絡(luò)以及FDO算法的優(yōu)化網(wǎng)絡(luò)3種情況下的各指標(biāo)進(jìn)行比較。

2.1 流表匹配率分析

本文提出的DTO算法的直接效果是盡可能多地使進(jìn)入流表的數(shù)據(jù)流能夠與流表項(xiàng)成功匹配，因此，流表匹配率的大小直接反映了優(yōu)化效果。圖3(a)所示為流表匹配率的實(shí)驗(yàn)結(jié)果。

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

2.2 流表資源利用率分析

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

從整體上看，4條曲線均為先增大后平穩(wěn)的狀況。在網(wǎng)絡(luò)中數(shù)據(jù)量較少時(shí)，4種網(wǎng)絡(luò)下的流表資源均未得到充分利用。隨著數(shù)據(jù)量的增大，流表資源利用率提高；當(dāng)網(wǎng)絡(luò)中的數(shù)據(jù)量持續(xù)增加時(shí)，4種情況下的流表資源利用率均達(dá)到了基本穩(wěn)定狀態(tài)，這是由于SDN的轉(zhuǎn)發(fā)機(jī)制導(dǎo)致交換機(jī)在大數(shù)據(jù)量的情況下只能等待控制器配置流表項(xiàng)，出現(xiàn)了性能瓶頸。但從圖中可明顯看出優(yōu)化后的三種網(wǎng)絡(luò)利用率遠(yuǎn)高于未使用優(yōu)化算法的初始網(wǎng)絡(luò)，AR算法與FDO算法的流表利用率均維持在76 %左右，而本文提出的DTO算法優(yōu)化方案對(duì)流表項(xiàng)利用率的提升穩(wěn)定在78 %左右，優(yōu)于其他兩種算法。

2.3 網(wǎng)絡(luò)平均吞吐量分析

當(dāng)數(shù)據(jù)量增大時(shí)，由于交換機(jī)處理能力的不足，會(huì)限制網(wǎng)絡(luò)的平均吞吐量，使其達(dá)到瓶頸。因此,本文算法對(duì)于交換機(jī)性能的提升也將會(huì)對(duì)同時(shí)提高網(wǎng)絡(luò)平均吞吐量。實(shí)驗(yàn)結(jié)果如圖3(c)所示。

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

圖3 仿真結(jié)果

綜合以上實(shí)驗(yàn)結(jié)果，對(duì)于數(shù)據(jù)流數(shù)量大的SDN，3種優(yōu)化網(wǎng)絡(luò)相比未優(yōu)化的初始網(wǎng)絡(luò)對(duì)于網(wǎng)絡(luò)性能的提升是顯而易見的。另外，相比于傳統(tǒng)的AR算法和FDO算法，本文的優(yōu)化算法達(dá)到了相對(duì)較高的流表匹配率、流表資源利用率以及網(wǎng)絡(luò)平均吞吐量，而這3個(gè)參數(shù)分別直觀地體現(xiàn)了算法的直接效果、交換機(jī)的性能以及整個(gè)SDN的性能，因此本文的優(yōu)化算法實(shí)現(xiàn)了更佳的優(yōu)化目的。

3 結(jié) 論

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