基于時(shí)間序列模型的RED算法研究

□ 文 李多佳 劉 靜 許 勇

一、引言

RED算法曾是一種有效的網(wǎng)絡(luò)擁塞控制算法，其主要思想是通過(guò)路由器輸出端的隊(duì)列長(zhǎng)度控制發(fā)送端的數(shù)據(jù)。算法操作簡(jiǎn)單易實(shí)現(xiàn)，但同時(shí)也存在著參數(shù)難以確定、難以有效處理突增的網(wǎng)絡(luò)流量以及公平性等問(wèn)題。隨著網(wǎng)絡(luò)信息量的爆炸式增長(zhǎng)，現(xiàn)行RED算法已經(jīng)無(wú)法有效解決網(wǎng)絡(luò)流量過(guò)分飽和的現(xiàn)狀，也無(wú)法保證網(wǎng)絡(luò)的服務(wù)質(zhì)量。很多學(xué)者針對(duì)RED算法的缺陷展開(kāi)了優(yōu)化，基于數(shù)學(xué)方法提出了對(duì)丟包率的改進(jìn)公式，降低了參數(shù)的敏感性，避免了概率突變的問(wèn)題。本文基于時(shí)間序列模型對(duì)RED算法展開(kāi)研究，首先建立時(shí)間序列模型，對(duì)已收集的網(wǎng)絡(luò)流量數(shù)據(jù)進(jìn)行歸一化處理；對(duì)歸一化處理后的樣本進(jìn)行訓(xùn)練直至達(dá)到精度要求，得到科學(xué)的模型參數(shù)；再設(shè)置預(yù)測(cè)值，計(jì)算出預(yù)測(cè)流量的平均隊(duì)列長(zhǎng)度。在此基礎(chǔ)上，結(jié)合RED算法，得到合理的數(shù)據(jù)包丟包概率，動(dòng)態(tài)調(diào)整平均隊(duì)列長(zhǎng)度，控制網(wǎng)絡(luò)中的數(shù)據(jù)包傳送。

二、國(guó)內(nèi)外研究現(xiàn)狀

RED算法由Sally Floyd和Van Jacobson首次提出，通過(guò)隨機(jī)選擇分組進(jìn)行丟棄或標(biāo)記，在隊(duì)列溢出之前降低數(shù)據(jù)的發(fā)送速率，以緩解網(wǎng)絡(luò)擁塞。后來(lái)，一些學(xué)者提出了各種改進(jìn)的RED算法來(lái)提高網(wǎng)絡(luò)性能。其中包括運(yùn)用非線性公式增強(qiáng)算法中丟包概率的計(jì)算，用平滑的概率曲線替代振蕩的概率曲線，借鑒Sigmoid函數(shù)的特性，在參數(shù)設(shè)定上降低了難度，避免了丟包概率突變的發(fā)生；基于流量預(yù)測(cè)的改進(jìn)RED算法，利用人工神經(jīng)網(wǎng)絡(luò)模型進(jìn)行流量預(yù)測(cè)，同時(shí)綜合模擬退火和粒子群算法進(jìn)行改進(jìn)，進(jìn)一步完善RED算法；Adaptive RED(ARED)算法，運(yùn)用統(tǒng)計(jì)復(fù)用的方法，通過(guò)檢查平均隊(duì)列長(zhǎng)度來(lái)調(diào)整發(fā)送窗口大??；DyRED算法，使用一個(gè)動(dòng)態(tài)的最大閾值來(lái)控制路由器緩沖區(qū)在溢出之前的早期階段的擁塞，進(jìn)一步減少丟包，提高吞吐量；基于自適應(yīng)動(dòng)態(tài)調(diào)整的RED算法，利用S型升半哥西分布函數(shù)對(duì)丟包率函數(shù)進(jìn)行非線性處理，利用目標(biāo)隊(duì)長(zhǎng)的范圍和平均隊(duì)列長(zhǎng)度的關(guān)系引入?yún)?shù)自適應(yīng)調(diào)整策略對(duì)最大丟包率進(jìn)行改進(jìn)；建立基于一維離散時(shí)間的路由器網(wǎng)絡(luò)擁塞控制非線性模型，通過(guò)對(duì)數(shù)據(jù)包丟包概率的參數(shù)進(jìn)行控制，解決了參數(shù)的低維混沌問(wèn)題，提高了算法的穩(wěn)定性；QARED算法的改進(jìn)，通過(guò)改變丟包概率計(jì)算函數(shù)，進(jìn)一步提高了算法的自適應(yīng)性、穩(wěn)定性，降低網(wǎng)絡(luò)丟包率；利用頻時(shí)交替半解析法（HB-AFT)，研究了延遲非光滑網(wǎng)絡(luò)TCP-RED擁塞控制系統(tǒng)周期解的近似解析表達(dá)式，提出了具有時(shí)滯的非光滑動(dòng)力系統(tǒng)周期解的精確近似解析表達(dá)式；Smart-RED算法，使用平均場(chǎng)模型，解決了突發(fā)UDP流量或TCP連接時(shí)可能出現(xiàn)的問(wèn)題，保持了較低的隊(duì)列大小和合理的帶寬利用率，緩解了網(wǎng)絡(luò)擁塞。

目前已有的改進(jìn)RED算法在實(shí)際應(yīng)用上仍存在著參數(shù)難以選定、隊(duì)列長(zhǎng)度震蕩不定等問(wèn)題，本文在RED算法的基礎(chǔ)上，考慮到網(wǎng)絡(luò)流量具有自相似性、長(zhǎng)相關(guān)性、周期性、混沌性等特征，提出了一種基于時(shí)間序列模型預(yù)測(cè)流量的RED擁塞控制算法（ARIMA_RED），采用統(tǒng)計(jì)、數(shù)學(xué)等方法結(jié)合實(shí)際情況確定RED算法的參數(shù)，處理網(wǎng)絡(luò)流量突增問(wèn)題，在緩解網(wǎng)絡(luò)擁塞中具有一定效果。

三、基于時(shí)間序列預(yù)測(cè)流量的RED擁塞控制算法——ARIMA_RED算法

3.1 ARIMA_RED算法原理

本文通過(guò)建立ARIMA模型來(lái)對(duì)流量值進(jìn)行預(yù)測(cè)，歸一化處理網(wǎng)絡(luò)流量訓(xùn)練集數(shù)據(jù)，首先計(jì)算出瞬時(shí)隊(duì)列長(zhǎng)度與平均隊(duì)列長(zhǎng)度，再以平均隊(duì)列長(zhǎng)度作為RED算法的輸入?yún)?shù)來(lái)動(dòng)態(tài)控制丟包率，控制網(wǎng)絡(luò)中的數(shù)據(jù)包傳送。

3.1.1 ARIMA模型

ARIMA模型是時(shí)間序列中的一個(gè)重要模型，基本思想是把需要進(jìn)行預(yù)測(cè)的序列看成為隨機(jī)序列，在此基礎(chǔ)上不斷計(jì)算并尋找最適合描述數(shù)學(xué)模型。當(dāng)建模成功后，將已有的數(shù)據(jù)作為歷史輸入，經(jīng)過(guò)模型計(jì)算輸出預(yù)測(cè)值。

3.1.2 ARIMA模型流量預(yù)測(cè)

在使用ARIMA模型預(yù)測(cè)網(wǎng)絡(luò)流量前，首先要對(duì)抓取的網(wǎng)絡(luò)流量數(shù)據(jù)集進(jìn)行數(shù)據(jù)預(yù)處理，將預(yù)處理后的數(shù)據(jù)通過(guò)ARIMA模型進(jìn)行檢驗(yàn)，以此來(lái)判斷模型是否具有數(shù)學(xué)意義。具體步驟如下：

（1）檢測(cè)序列的平穩(wěn)性。以ADF單位根檢驗(yàn)網(wǎng)絡(luò)流量預(yù)測(cè)模型的散點(diǎn)圖、自相關(guān)函數(shù)、偏相關(guān)函數(shù)圖的方差、趨勢(shì)。

（2）平穩(wěn)化處理。網(wǎng)絡(luò)流量具有突發(fā)性、實(shí)時(shí)性，所以網(wǎng)絡(luò)流量的時(shí)間序列模型基本為非平穩(wěn)模型，存在變化的趨勢(shì)，此時(shí)，需要通過(guò)差分處理來(lái)處理數(shù)據(jù)。當(dāng)網(wǎng)絡(luò)流量存在異方差時(shí)，必須通過(guò)技術(shù)手段處理數(shù)據(jù)。當(dāng)處理后的數(shù)據(jù)具有自相關(guān)函數(shù)值和偏差時(shí)，說(shuō)明經(jīng)過(guò)處理的數(shù)據(jù)序列已為平穩(wěn)序列，可以作為模型的輸入數(shù)據(jù)。

（3）建立模型，通過(guò)估計(jì)參數(shù)來(lái)判斷模型的建立是否具有數(shù)學(xué)意義。本文通過(guò)wireshark軟件抓取的流量經(jīng)過(guò)時(shí)間序列分析得出其偏相關(guān)函數(shù)與自相關(guān)函數(shù)在函數(shù)圖上均為拖尾，故本文選取ARIMA模型來(lái)處理數(shù)據(jù)。

（4）使用建立好的ARIMA模型預(yù)測(cè)流量。

（5）將預(yù)測(cè)出的瞬時(shí)流量值作為ARIMA_RED算法的輸入?yún)?shù)，代入ARIMA_RED算法的計(jì)算公式，經(jīng)過(guò)計(jì)算得出路由節(jié)點(diǎn)的丟包率p。

ARIMA模型流量預(yù)測(cè)流程圖如圖1所示。

圖1 ARIMA_RED算法流程圖

3.1.3 ARIMA_RED算法步驟

ARIMA_RED算法偽碼描述如圖2所示。

其中參數(shù)q為當(dāng)前隊(duì)列的長(zhǎng)度；time為時(shí)間；q_time表示隊(duì)列最初空閑時(shí)間；m路由器在空閑狀態(tài)下發(fā)送的最小報(bào)文數(shù)；f(t)為t的線性函數(shù)；count是自從最后一個(gè)數(shù)據(jù)包被丟棄以來(lái)已收到的數(shù)據(jù)包數(shù)；timeseries( )為時(shí)間序列模型數(shù)據(jù)處理； A RIMA( )為預(yù)測(cè)算法。

3.2 時(shí)間序列模型預(yù)測(cè)評(píng)估

本文利用wireshark軟件抓取了一定時(shí)間內(nèi)某網(wǎng)絡(luò)的數(shù)據(jù)包個(gè)數(shù)以及出現(xiàn)錯(cuò)誤的情況，作為ARIMA模型的輸入?yún)?shù)，數(shù)據(jù)集如表1所示（數(shù)據(jù)集過(guò)長(zhǎng)，此處只選取前十列）。

圖2 ARIMA_RED算法偽碼

表1 部分時(shí)間序列模型數(shù)據(jù)集

接著利用ARIMA模型進(jìn)行建模分析，得出的結(jié)果如表2所示。

表2 ARIMA模型建模結(jié)果

針對(duì)表2的數(shù)據(jù)，在數(shù)學(xué)意義上結(jié)合AIC信息準(zhǔn)則，軟件自動(dòng)對(duì)多個(gè)潛在備選模型進(jìn)行建模和對(duì)比選擇，最終找出最優(yōu)模型為：MA(2)，其模型公式為：

從Q統(tǒng)計(jì)量結(jié)果看，Q6的p值大于0.1，則在0.1的顯著性水平下不能拒絕原假設(shè)，模型的殘差是白噪聲，模型基本滿足要求。

圖3 時(shí)間序列模型擬合與預(yù)測(cè)

圖4 仿真實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

時(shí)間序列模型擬合與預(yù)測(cè)結(jié)果如圖3所示。從中可以看出，時(shí)間序列模型可以較好的模擬網(wǎng)絡(luò)流量的特性，預(yù)測(cè)的數(shù)據(jù)基本在可信區(qū)間內(nèi)。

四、基于NS2的隨機(jī)早期檢測(cè)算法模型實(shí)現(xiàn)

本文使用NS2對(duì)網(wǎng)絡(luò)模型進(jìn)行仿真實(shí)驗(yàn)，NS2是一種面向?qū)ο蟮木W(wǎng)絡(luò)仿真器。在模擬實(shí)驗(yàn)中，模擬了多個(gè)用戶以在一定范圍內(nèi)將數(shù)據(jù)包隨機(jī)發(fā)送到路由器，并在路由器上設(shè)置了路由節(jié)點(diǎn)以處理數(shù)據(jù)包的傳輸帶寬。通過(guò)擁塞控制算法對(duì)隊(duì)列進(jìn)行擁塞管理，故本文以擁塞隊(duì)列的長(zhǎng)度作為算法優(yōu)劣的評(píng)價(jià)指標(biāo)。

本次仿真實(shí)驗(yàn)所使用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)見(jiàn)圖4。

4.1 RED算法的仿真實(shí)現(xiàn)

在網(wǎng)絡(luò)的傳輸過(guò)程中，當(dāng)網(wǎng)絡(luò)中傳輸分組的數(shù)目所需資源大于由于路由節(jié)點(diǎn)的存儲(chǔ)資時(shí)，隊(duì)列的累積便會(huì)造成網(wǎng)絡(luò)擁塞。而路由器處的隊(duì)列長(zhǎng)度則能很好的反應(yīng)網(wǎng)絡(luò)擁塞情況以及擁塞管理情況。

表3 實(shí)驗(yàn)仿真數(shù)據(jù)表

首先對(duì)RED算法進(jìn)行仿真實(shí)驗(yàn)，所選取的實(shí)驗(yàn)仿真數(shù)據(jù)見(jiàn)表3。

RED算法偽碼在前文中已經(jīng)提到，本文在將其改進(jìn)后應(yīng)用到NS2軟件中，在仿真數(shù)據(jù)下的平均隊(duì)列長(zhǎng)度如圖5中RED曲線所示。當(dāng)平均隊(duì)列長(zhǎng)度小于最小閾值長(zhǎng)度時(shí)，路由節(jié)點(diǎn)的狀態(tài)正常，數(shù)據(jù)包根據(jù)調(diào)度算法進(jìn)行排隊(duì)。當(dāng)平均隊(duì)列長(zhǎng)度在最小閾值和最大閾值之間時(shí)，路由節(jié)點(diǎn)將以一定概率p丟棄數(shù)據(jù)包；當(dāng)平均隊(duì)列長(zhǎng)度超過(guò)最大閾值時(shí)，路由節(jié)點(diǎn)將丟棄所有流量數(shù)據(jù)包?？梢钥闯?，RED算法在一定條件下可以緩解網(wǎng)絡(luò)擁塞，但由于缺少預(yù)測(cè)網(wǎng)絡(luò)流量這一步驟，導(dǎo)致多個(gè)擁塞和丟包事件。

4.2 時(shí)間序列預(yù)測(cè)算法的仿真實(shí)現(xiàn)

本次仿真實(shí)驗(yàn)將所選取的實(shí)驗(yàn)仿真數(shù)據(jù)應(yīng)用到ARIMA模型中，對(duì)網(wǎng)絡(luò)流量進(jìn)行預(yù)測(cè)，并將訓(xùn)練好的數(shù)學(xué)模型應(yīng)用到網(wǎng)絡(luò)傳輸拓?fù)浣Y(jié)構(gòu)中。

路由器在應(yīng)用基于ARIMA模型的RED算法后，隊(duì)列長(zhǎng)度產(chǎn)生了明顯的變化。源數(shù)據(jù)端發(fā)出的數(shù)據(jù)在路由節(jié)點(diǎn)出產(chǎn)生隊(duì)列，在基于ARIMA模型的RED算法的控制下，對(duì)流量情況做出預(yù)測(cè)，在此基礎(chǔ)上進(jìn)行擁塞控制?？梢钥闯鲫?duì)列長(zhǎng)度基本保持在期望值附近，比原來(lái)有了很大程度的改進(jìn)。

本文還從吞吐量角度對(duì)兩種算法進(jìn)行比較，如圖6所示，2種算法都有著較高的吞吐量。隨著時(shí)間的增加，曲線逐漸減小并穩(wěn)定下來(lái)。相比于傳統(tǒng)的RED算法，基于ARIMA模型的改進(jìn)RED算法具有更高的吞吐量。吞吐量越高，網(wǎng)絡(luò)流暢性更佳，網(wǎng)絡(luò)的性能也就更優(yōu)越。

圖6 RED算法與基于ARIMA模型的改進(jìn)RED算法的平均吞吐量比較

五、結(jié)束語(yǔ)

本文主要從性能優(yōu)化的角度來(lái)改進(jìn)已有的RED算法來(lái)避免網(wǎng)絡(luò)擁塞并及時(shí)緩解擁塞，同時(shí)優(yōu)化網(wǎng)絡(luò)性能，提高網(wǎng)絡(luò)服務(wù)質(zhì)量。

實(shí)驗(yàn)仿真了50個(gè)源端對(duì)路由節(jié)點(diǎn)發(fā)送數(shù)據(jù)，同時(shí)使用時(shí)間序列模型對(duì)隨機(jī)早期算法進(jìn)行改進(jìn)，通過(guò)預(yù)測(cè)瞬時(shí)流量值提前對(duì)丟包率做出調(diào)整，提升了其對(duì)于復(fù)雜網(wǎng)絡(luò)環(huán)境的適應(yīng)能力。

主要包括以下幾方面：

（1）對(duì)擁塞控制算法基礎(chǔ)的研究。文章對(duì)已有的擁塞控制算法背景進(jìn)行了研究,了解擁塞控制的原理，并總結(jié)了算法的評(píng)價(jià)標(biāo)準(zhǔn)。

（2）將時(shí)間序列算法應(yīng)用到流量預(yù)測(cè)中,通過(guò)抓取已有的網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行建模計(jì)算，為算法中提供參數(shù)。

（3）改進(jìn)既算法并修改內(nèi)部對(duì)應(yīng)的協(xié)議。在NS2軟件下進(jìn)行仿真實(shí)驗(yàn)得出實(shí)驗(yàn)結(jié)果。

通過(guò)NS2仿真圖可以明顯看出，經(jīng)過(guò)改進(jìn)后的RED算法在應(yīng)用時(shí)，平均隊(duì)列長(zhǎng)度得到了顯著的提升，說(shuō)明基于時(shí)間序列的RED算法對(duì)網(wǎng)絡(luò)流量的利用率更高；同時(shí)，經(jīng)過(guò)改進(jìn)后的RED算法的平均吞吐量也明顯優(yōu)于改進(jìn)前，說(shuō)明改進(jìn)后的RED算法傳輸數(shù)據(jù)的速率更高。

改進(jìn)之后的新算法側(cè)重于對(duì)突發(fā)數(shù)據(jù)流的處理，因而不能很好的控制隊(duì)列長(zhǎng)度達(dá)到穩(wěn)定值，從仿真圖中也可看出，改進(jìn)前后的RED算法在達(dá)到平穩(wěn)狀態(tài)所需要的時(shí)間基本相同。因而，下一步的工作中將改進(jìn)該擁塞控制算法，同時(shí)評(píng)估對(duì)比相關(guān)RED優(yōu)化算法進(jìn)行試驗(yàn)，進(jìn)一步發(fā)現(xiàn)新的問(wèn)題并完善。■