一種基於二階最優模型和自適應計算的路由器主動隊列管理方法

2023-06-24 10:13:46 2

專利名稱：一種基於二階最優模型和自適應計算的路由器主動隊列管理方法
技術領域：
本發明涉及一種基於二階最優模型和自適應計算的路由器主動隊列管理方法。

背景技術：
實踐證明，在網絡中大部分業務流為響應性流的情況下，TCP端到端擁塞控制機制能夠有效地防止擁塞崩潰現象的發生。然而，在網絡擁塞的情況下，非響應性流(如UDP流)並不會降低其發送速率來響應擁塞，從而侵佔更多的網絡帶寬，造成擁塞長時間得不到解除。因此，傳統的端到端擁塞控制機制在公平性、延時和丟包率保證以及發生擁塞後恢復正常的響應性等問題上效率低下，更不用說提供網絡服務質量的支持。為解決這些問題，主動隊列管理(ActiveQueue Management，AQM)被推薦部署在網絡中間節點來增強端到端擁塞控制。
AQM的主要技術目標包括如下四個方面(1)降低路由器的分組丟失率；(2)提供高吞吐量和低延時及延時抖動；(3)增強算法魯棒性和響應性；(4)簡單、有效，擴展性好，能部署到實際網絡中。
在現有的AQM方法中，鏈路的擁塞通常通過隊列長度、業務流的輸入速率等擁塞測度來估計。(平均)隊列長度被廣泛用於RED及其變種算法。一些研究者們從理論分析和仿真實驗兩個方面對RED算法進行了性能評價。幾乎所有的研究表明RED在參數配置方面存在嚴重的缺陷。針對這些不足，Floyd和其它的研究者們在RED參數配置方面做出了很多的努力，提出了gentle-RED，ARED和SRED等算法。不幸的是，這些針對RED參數配置問題所提出來的算法本身也存在這方面的問題，而且在特定的網絡環境下仍然會出現嚴重的隊列震蕩，造成低吞吐量和高排隊延時。Hollot依據TCP動態非線性流量模型的啟發為AQM設計了PI控制器，但PI控制器的概率調節過分依賴於緩存，並存在響應性能差的缺點。


發明內容
為了解決上述技術問題，本發明提供一種基於二階最優模型和自適應計算的路由器主動隊列管理方法。本發明非常適用於網絡時變特性特點，並且響應性能好。
本發明解決上述技術問題的技術方案包括如下步驟 在路由器上建立一個自適應的比例控制器； 測量路由器的分組丟失率； 根據路由器分組丟失率計算路由器的加權平均分組丟失率； 根據路由器的加權平均分組丟失率計算路由器的分組丟棄概率，根據分組丟棄概率丟棄分組。
上述的基於二階最優模型和自適應計算的路由器主動隊列管理方法中，所述路由器的分組丟失率為 上式中l(k)為第k次的分組丟失率，它是第k次的分組丟失率等於前M個測量周期時間內被丟失的數據總量與到達的數據總量的比值；D(i)為第i個周期丟失的數據包的個數；A(i)為第i個周期到達的數據包的個數。
上述的基於二階最優模型和自適應計算的路由器主動隊列管理方法中，所述路由器的加權平均分組丟失率為 l(k)＝w*l(k-1)+(1-w)*l(k) 上式中w是加權係數。
上述的基於二階最優模型和自適應計算的路由器主動隊列管理方法，所述路由器的分組丟棄概率為 p(t)＝l(k)+γ(·)(q(t)-q0) q(t)為路由器當前的緩衝隊列長度；q0為預先設定的目標隊列長度；γ(·)為比例控制參數。
本發明的技術效果在於本發明根據當前測量到的路由器平均分組丟失率來計算激活的TCP連接數，採用簡單的比例控制器和基於二階最優控制模型的極點配置法自適應的調整分組丟棄概率，以此調整路由器主動隊列長度。本發明具有適應性強、魯棒性高、算法實現簡單的優越性能，在實現主動隊列管理時可保證較高的鏈路利用率，同時減小了排隊延時的特點。
下面結合附圖對本發明作進一步的說明。



圖1為本發明的AQM控制框圖； 圖2為本發明的流程圖； 圖3為本發明的仿真實驗拓撲圖； 圖4為本發明控制的隊列變化； 圖5為本發明中平均隊長隨TCP流數的變化； 圖6為本發明中隊列變化標準差隨TCP流數的變化； 圖7為本發明控制的隊列變化(FTP流、UDP流、HTTP流共存)。

具體實施例方式 參見圖1，圖1為實現本發明的AQM控制框圖。本發明應用二階系統最優模型為主動隊列管理(AQM，Active Queue Management)設計了一種稱為AOPC(Adaptive Optimized Proportional Controller)的隊列管理方法。圖中的控制器G1(s)指路由器中使用的AQM方法，G2(s)是受控制的TCP/AQM系統的傳遞函數，這一函數描述了控制器是如何通過改變控制量p(t)來影響q(t)的。圖1描述的控制系統是二階線性系統。AOPC周期性地測量最近M個周期內的平均分組丟失率l(k)並在每個分組到達路由器時更新分組的丟棄概率。
首先測量最近M個周期的分組丟失率l(k) k為當前的測量時間點，T為測量周期，l(k)為第k次的分組丟失率，它是第k次的分組丟失率等於前M個測量周期時間內被丟失的數據總量與到達的數據總量的比值；D(i)為第i個周期丟失的數據包的個數；A(i)為第i個周期到達的數據包的個數。
通過加權滑動平均方法計算平均的分組丟失率l(k)，計算方法如下 l(k)＝w*l(k)+(1-w)*l(k) 其中，w為加權係數。
AOPC能夠根據測量到的分組丟失率自適應地調整比例控制參數，這樣能夠解決很多AQM算法參數調節不靈活和改善對網絡流量動態變化不適應的缺點。AOPC在每個新的分組到達後採用如下方程計算分組的丟棄概率 p＝l(k)+γ(q-q0)(1) 其中，γ是根據當前網絡狀況調整的可變參數，l(k)是測量到的分組丟失率。
將測量到的分組丟失率l(k)近似地看作當前網絡狀態下穩定的分組丟棄概率p0，即l(k)≈p0。AOPC在每次測量完分組丟失率之後，基於TCP吞吐量模型來估計TCP的連接數N，進而根據二階系統最優模型來調節控制參數，使系統能夠工作在動態變化的網絡環境中，並且具有優化的性能。
AOPC通過引入分組丟失率來反應動態網絡的負載信息，通過建立控制參數與分組丟失率之間的函數關係，設計了用於AQM控制的自適應控制律。AOPC有兩個重要的組件(1)網絡負載預估器，在每次測量完分組丟失率之後估計TCP的連接數目，用於消除控制參數對網絡變量的依賴性；(2)參數優化器，基於二階系統最優模型對TCP/AOPC聯合控制系統的參數進行優化計算。下面具體描述了兩個組件的工作原理。
(1)網絡負載預估器 假設單個TCP流的端到端分組丟棄概率為p0，已有文獻建立單個TCP流吞吐量與RTT和分組丟失率之間的函數關係，用公式表示如下 Ri(t)為TCP流的往返延時，Xi為單個TCP流吞吐量。
現在來考慮一條鏈路同時被N個TCP流共享，令y＝∑xi(i＝1，...，N)為總發送速率。假設該條鏈路的服務速率(鏈路容量)為C，緩存容量足夠大能保證鏈路完全被利用。並假設總發送速率大於鏈路的服務速率，即y＞C，因此，丟棄概率p0滿足如下關係式 (1-p0)y＝C(3) 那麼，由(2)和(3)，可知 令 其中，Req為N個TCP流RTT的調和平均值。
從(4)和(5)，可以得到 由於測量到的分組丟失率可以近似地視為最近時段內穩定的分組丟棄概率，即l(k)≈p0，令則方程(6)可以改寫為 N＝ReqCf(l(k)) (7) 這裡，將f(·)稱為計算分組丟棄概率的調節因子。
方程(7)表明，要估計TCP連接數N，只需要知道N個TCP流的RTT的調和平均值Req， 而不需要知道單個TCP流的RTT。如果Req的值可以事先測量出來並且始終在某個穩定值附近緩慢地變化，那麼，可以忽略Req的時變性質而估計出TCP連接數。
(2)參數優化器 本二階系統的閉環傳遞函數為 上式中K是靜態靈敏度，τ是時間常數，ζ是阻尼係數。
阻尼係數ζ影響二階系統的輸出。工程上把ζ＜1，ζ＝1，和ζ＞1的系統分別稱為欠阻尼、臨界阻尼和過阻尼系統。ζ太大則過渡過程時間太長，不利於控制；但ζ太小則振蕩劇烈，過渡過程時間也隨之變長，同樣不利於控制。因此ζ值的選擇就很重要。通常把ζ＝0.707的情況稱為二階最優模型。對於ζ＜1，系統的階躍響應為 從控制的角度來看，當t→∞，y(t)→1時，系統的靜態誤差趨近於0。假設在比例AQM控制中總能滿足K≤1的條件(在後面將看到這個假設實際上是恆成立的)，令y(∞)＝1，那麼系統的靜態誤差ess和過渡過程時間ts(允許誤差為2％，|y(ts)-y(∞)|＝0.02y(∞))分別為 ess＝1-K(9) 系統靜態誤差反應了系統控制的精度，過渡過程時間刻畫了系統的響應速度。
據圖1所示的TCP/AQM控制系統框圖，用γ表示比例AOPC控制器的控制參數，則我們可以得到TCP/AOPC控制系統的閉環傳遞函數為 其中，靜態靈敏度K，時間常數τ，阻尼係數ζ分別為 TCP/AOPC的參數優化原理則是基於二階最優模型，通過調節控制係數γ來保證系統的阻尼係數ζ＝0.707。這種方法在控制理論裡面稱為極點配置法。
由可以得到在網絡負載預估模塊中，我們得到了激活的TCP連接數N的估計方法，將方程(7)代入上式，得到 方程(12)給出TCP/AOPC控制系統的控制律。AOPC控制參數γ的調節依賴於網絡負載預估組件測量到的平均分組丟失率。另外，儘管單個TCP流的RTT變化可能會出現很大的波動，但是從整個網絡來看，所有TCP流的調和平均值是緩慢時變的，不會出現很大的震蕩。從式(12)中可以看到調和平均值Req對控制參數γ的影響很小。例如，假設當前測量到的分組丟失率l(k)＝0.01，鏈路容量為2500分組數/秒，當Req＝0.2秒時，參數γ＝2.625(10)-4，當Req＝0.15秒時，γ＝3.5(10)-4。該例表明控制參數γ不敏感於實際網絡中RTT的擾動。
參見圖2，圖2本發明的流程圖。其具體步驟如下 步驟(1)在路由器上建立一個自適應的比例控制器，該控制器採用測量平均分組丟失率來實時調節控制器參數以適應動態變化的網絡流量。
步驟(2)初始化參數和變量。
步驟(3)判斷當前系統時刻是否達到lastTime+T，如果已到達，則執行步驟(4)，否則執行步驟(9)； 步驟(4)測量當前的分組丟失率l(k)， 步驟(5)計算平均分組丟失率l(k)，l(k)＝w*l(k)+(1-w)*l(k)； 步驟(6)計算控制器調節因子f， 步驟(7)更新控制器參數γ， 步驟(8)把lastTime賦值為當前系統時刻； 步驟(9)等待新分組的到來，如果有新的分組到達，則執行步驟(10)，否則重複執行步驟(3)； 步驟(10)執行比例控制器，獲得當前的路由器隊列長度q(t)，計算分組的丟棄概率p(t)，p(t)＝l(k)+γ(·)(q(t)-q0)； 步驟(11)以概率p(t)丟棄該分組； 步驟(12)轉到步驟(3)，重複執行步驟(3)至步驟(11)，直至結束。
我們在NS2(Network Simulator，Version 2)網絡仿真軟體上實現了AOPC主動隊列管理方法，並對它的性能進行了詳細的測試。NS2網絡仿真軟體是一種通用的多協議網絡模擬軟體，它是在網際網路上公開發布的(http://www-mash.cs.berkeley.edu/ns/)，目前已被網絡研究者們廣泛使用。採用圖3所示的拓撲結構，S1~Sn為發送結點，D1~Dn為接收結點，R1、R2為路由器，Si~R1和R2~Di的傳輸延遲均勻分布在區間[10ms，50ms]上。R1→R2的鏈路構成瓶頸，其鏈路容量為10Mbps。分組的平均大小為500位元組，目標隊列長度設為50個分組大小，瓶頸路由器的緩存大小為200個分組。
為模擬AOPC在存在突發業務情況下的響應性和穩定性，我們在突然加重負載的情況下對AOPC進行了檢驗。開始啟動100個FTP流，50秒後再次啟動100個FTP流來檢查各算法對突發業務的響應性。AOPC的隊列長度變化過程分別如圖4所示。從圖4中可以看出，在突然加重負載的情況下，AOPC能夠在很快的時間內將隊列穩定在預先設定的隊列長度附近。
為了進一步驗證和定量分析AOPC的隊列穩定性，我們在不同TCP連接數情況下，統計出AOPC的平均隊列長度和隊列變化的標準差，並和已有的REM、PID、LRED和PIP等AQM控制器進行了比較。圖5和圖6分別給出平均隊列長度和瞬時隊列長度標準差隨TCP連接數的變化圖。仿真實驗表明AOPC的性能超過了所有比較的算法，獲得了穩定的隊列長度，並且隊列抖動很小。小的隊列抖動不僅意味著低延時抖動，還可以保證高的鏈路利用率。
最後，為模擬實際網絡流量，採用四種類型的網絡流基於TCP Reno的長期FTP流和短期HTTP流，基於UDP的CBR流和服從指數分布的ON/OFF流。其中，FTP會話存活於整個仿真過程中。HTTP流生命期較短，它請求的平均時間間隔為1秒，請求的頁面大小為1000位元組。CBR流的分組大小為500位元組，發送間隔為0.08秒，其處於ON和OFF狀態的時間分別為2秒和1秒，處於ON狀態下的發送速率為64Kbps。仿真時間為100秒。隊列的變化過程如圖7所示。仿真結果表明，在存在Web流的高度動態的網絡情景下，AOPC仍能表現出優越的穩定性能。
權利要求
1.一種基於二階最優模型和自適應計算的路由器主動隊列管理方法，包括以下步驟
在路由器上建立一個自適應的比例控制器；
測量路由器的分組丟失率；
根據路由器分組丟失率計算路由器的加權平均分組丟失率；
根據路由器的加權平均分組丟失率計算路由器的分組丟棄概率，根據分組丟棄概率丟棄分組。
2.根據權利要求1所述的基於二階最優模型和自適應計算的路由器主動隊列管理方法，所述路由器的分組丟失率為
上式中l(k)為第k次的分組丟失率，它是第k次的分組丟失率等於前M個測量周期時間內被丟失的數據總量與到達的數據總量的比值；D(i)為第i個周期丟失的數據包的個數；A(i)為第i個周期到達的數據包的個數。
3.根據權利要求2所述的基於二階最優模型和自適應計算的路由器主動隊列管理方法，所述路由器的加權平均分組丟失率為
上式中w是加權係數。
4.根據權利要求1所述的基於二階最優模型和自適應計算的路由器主動隊列管理方法，所述路由器的分組丟棄概率為
上式中q(t)為路由器當前的緩衝隊列長度；q0為預先設定的目標隊列長度；γ(·)為比例控制參數。
全文摘要
本發明公開了一種基於二階最優模型和自適應計算的路由器主動隊列管理方法，包括以下步驟在路由器上建立一個自適應的比例控制器；測量路由器的分組丟失率；根據路由器分組丟失率計算路由器的加權平均分組丟失率；根據路由器的加權平均分組丟失率計算路由器的分組丟棄概率，根據分組丟棄概率丟棄分組。本發明具有適應性強、魯棒性高、算法實現簡單的優越性能，在實現主動隊列管理時可保證較高的鏈路利用率，同時減小了排隊延時。
文檔編號H04L12/56GK101175031SQ200710034960
公開日2008年5月7日 申請日期2007年5月21日 優先權日2007年5月21日
發明者王建新, 亮 榮 申請人:中南大學