基于時間序列模型的RED算法研究

□ 文 李多佳 劉 靜 許 勇

一、引言

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

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

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

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

三、基于時間序列預測流量的RED擁塞控制算法——ARIMA_RED算法

3.1 ARIMA_RED算法原理

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

3.1.1 ARIMA模型

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

3.1.2 ARIMA模型流量預測

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

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

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

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

（4）使用建立好的ARIMA模型預測流量。

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

ARIMA模型流量預測流程圖如圖1所示。

圖1 ARIMA_RED算法流程圖

3.1.3 ARIMA_RED算法步驟

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

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

3.2 時間序列模型預測評估

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

圖2 ARIMA_RED算法偽碼

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

接著利用ARIMA模型進行建模分析，得出的結果如表2所示。

表2 ARIMA模型建模結果

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

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

圖3 時間序列模型擬合與預測

圖4 仿真實驗網(wǎng)絡拓撲結構

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

四、基于NS2的隨機早期檢測算法模型實現(xiàn)

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

本次仿真實驗所使用的網(wǎng)絡拓撲結構見圖4。

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

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

表3 實驗仿真數(shù)據(jù)表

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

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

4.2 時間序列預測算法的仿真實現(xiàn)

本次仿真實驗將所選取的實驗仿真數(shù)據(jù)應用到ARIMA模型中，對網(wǎng)絡流量進行預測，并將訓練好的數(shù)學模型應用到網(wǎng)絡傳輸拓撲結構中。

路由器在應用基于ARIMA模型的RED算法后，隊列長度產(chǎn)生了明顯的變化。源數(shù)據(jù)端發(fā)出的數(shù)據(jù)在路由節(jié)點出產(chǎn)生隊列，在基于ARIMA模型的RED算法的控制下，對流量情況做出預測，在此基礎上進行擁塞控制。可以看出隊列長度基本保持在期望值附近，比原來有了很大程度的改進。

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

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

五、結束語

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

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

主要包括以下幾方面：

（1）對擁塞控制算法基礎的研究。文章對已有的擁塞控制算法背景進行了研究,了解擁塞控制的原理，并總結了算法的評價標準。

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

（3）改進既算法并修改內(nèi)部對應的協(xié)議。在NS2軟件下進行仿真實驗得出實驗結果。

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

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