基于非線性主動隊列管理的網絡輸出反饋控制

隨著網絡規模的擴大和網絡服務質量的要求的提高，網絡過載的預防和控制已成為一個重要的研究主題。路由器中的主動隊列管理(Activequeuemanagement,AQM)機制可以通過提前檢測擁塞來提高網絡的吞吐量,同時有效地控制緩存隊列的長度,從而為要求時延保證的Internet業務提供一種良好的保障機制,是作用在網絡中間節點上的一種有效的擁塞控制策略。由于網絡擁塞控制模型可以看作是1個反饋控制系統,所以從控制理論的角度來研究網絡擁塞控制可以取得有效的控制性能,例如參考文獻對現有經典的AQM算法的魯棒穩定性、公平性等性能進行了分析,從而改進了一些經典算法,同時一些基于現代控制理論的新的AQM算法也相繼被提出。KSFC算法基于魯棒控制理論,利用線性矩陣不等式(Linearmatrixinequality,LMI)方法設計了AQM系統的狀態反饋控制率,但是由于這類算法要獲取TCP窗口值,因此其實用性受到很大限制;α-robustAQM簡化了系統控制率,但是在變時滯條件下的控制性能較差;參考文獻根據基于規則的預測控制理論(Rule-basedpredictivecontrol,RBPC)設計了一類新的AQM算法,用來穩定瓶頸路由器中的隊列擾動。然而這些新的AQM算法均基于簡單的線性控制,是在小信號線性化的基礎上設計的,所以存在局部穩定性的問題。參考文獻設計了一種具有全局穩定性的非線性擁塞控制模型,但是其僅針對單鏈路和單TCP源,具有一定的局限性;參考文獻設計了一種非線性輸出反饋控制算法(Nonlinearoutputfeedbackcontrol,NOFC),可以使瓶頸路由器的隊列長度穩定在期望值,但是把往返時間(Roundtriptime,RTT)設為固定值,與實際的網絡情況不相符合。因為RTT可以表示為隊列長度的函數,本文根據這一條件設計了基于變化RTT的網絡模型,通過反步設計法設計了非線性AQM算法。由于在實際網絡中,路由器無法得到TCP窗口值,為了使設計的非線性AQM算法僅與隊列長度相關,提出了TCP窗口值的觀測器設計,并證明了當丟包率的取值范圍為0～1時,TCP窗口觀測值收斂到實際值。ns仿真表明,本文設計的基于反步設計法的非線性主動隊列管理算法(NonlinearAQMalgorithm-backsteppingtechnique,NAQM-bt)在變化的網絡環境下具有較好的魯棒穩定性,并保證了網絡具有較高的吞吐量和較低的丟包率。1多線程窗口大小估計Misra等人于2000年基于流體理論提出的網絡模型,描述了瓶頸路由器和TCP窗口的動態特性,在忽略超時重傳機制下,可用非線性微分方程組(1)來描述˙W(t)=1R(t)-W2(t)2R(t)p(t)˙q(t)=-C+ΝR(t)W(t)(1)式中:狀態變量W(t)和q(t)分別為平均TCP窗口大小和平均隊列長度,控制輸入p(t)為數據包的標注概率,R(t)、C和N分別是RTT、鏈路容量和TCP連接數。在實際網絡環境下N應該是時間t的函數,為了計算簡便,設為已知的常數。設Tp是整個網絡的傳輸延遲,則R(t)可以表示為R(t)=q(t)/C+Tp,代入方程組(1)得˙W(t)=Cq(t)+ΤpC-CW2(t)2(q(t)+ΤpC)p(t)˙q(t)=ΝCq(t)+ΤpCW(t)-C(2)設ˉq=1/(q+ΤpC),代入方程組(2)得˙W=Cˉq-(C/2)W2ˉqp(t)˙ˉq=-ΝCWˉq3+Cˉq2(3)由于在實際路由器中,無法得到TCP窗口的大小,所以設計開環觀測器的動態方程如下˙?W=Cˉq-(C/2)?W2ˉqp(t)(4)式中:?W是TCP窗口大小觀測值,定義ε=W-?W為實際窗口值和觀測值之間的估計誤差。假設1存在常量t0>0以及正常量T0和α,使得?t≥t0,丟包率p(t)滿足1Τ0∫tt+T0p(s)ds≥α(5)假設2limsupt→∞p(t)<ˉpˉp∈(0,1)根據網絡的物理特性,對于丟包率p(t)做出了上述的2個假設。假設1意味著在一定長的時間間隔T0里,路由器緩存中標注或丟棄的數據包總數應該達到一定的數量級。因為在TCP網絡中,發送端以線形增加的方式發送數據包,一定長時間內過多數據包的積累必然會造成網絡擁塞。在擁塞控制中,并不希望由于過多的數據包丟棄造成鏈路利用率偏低,假設2意味著當系統趨于穩定時丟包率p(t)穩定在某一個小于1的值附近。引理1假設丟包率p(t)滿足假設2,則TCP窗口大小觀測值滿足liminft→∞?W(t)>0。證明由假設2可以得到,對于足夠大的t?˙?W≥Cˉq-(C/2)?W2ˉqˉp。考慮微分方程˙y1=Cˉq-(C/2)y21ˉqˉp有1個穩定平衡點√2/ˉp>0,根據比較引理,有liminft→∞?W(t)>0。定理1如果p(t)∈[0,1]滿足假設1和假設2,則窗口大小估計誤差ε漸近收斂到0。證明因為ε=W-?W?所以˙ε=˙W-˙?W=(C/2)(?W2-W2)ˉq?p(t)=-(C/2)(W+?W)ˉq?p?ε(6)解微分方程(6)得ε(t)=ε(t0)e-C/2∫t0t(W(s)+W^(s))?qˉ(s)?p(s)ds(7)式中:t0>0為一個足夠大的常量。對任意t>t0,有t=t0+kΤ0+Τ??其中T0的定義與假設1相同,k為自然數,Τ0≥Τ?≥0,代入∫t0tp(s)ds得∫t0tp(s)ds=∫t0t0+kΤ0+Τ?p(s)ds=∫t0t0+T0p(s)ds+∫t0+Τ0t0+2Τ0p(s)ds+…+∫t0+(k-1)Τ0t0+kΤ0p(s)ds+∫t0+kΤ0t0+kΤ0+Τ?≥p(s)dskαT0+∫t0+kΤ0t0+kΤ0+Τ?p(s)ds≥kαT0(8)式(8)中第1個不等式由不等式(5)推導,第2個不等式是由于p(t)是非負的。由于W(t)是實際的TCP窗口值,所以W(t)≥0,?t≥0;同理qˉ(t)≥0,?t≥0,且擁塞控制的目標是使路由器中的隊列長度維持在1個理想值附近,所以liminft→∞qˉ(t)>0。根據引理1得(W(t)+W^(t))qˉ(t)≥W^(t)?qˉ(t)≥liminft→∞W^(t)?liminft→∞qˉ(t)>0(9)根據不等式(8)和(9)有∫t0t(W(s)+W^(s))?qˉ(s)?p(s)ds≥βkαΤ0≥βα(t-t0-Τ0)(10)式中:β=liminft→∞W^(t)?liminft→∞qˉ(t)。將不等式(10)代入式(7)得ε(t)≤ε(t0)eCβΤ02?e-C2β(t-t0)(11)在圖1中,取W(0)=10,W^(0)=0.1,標注概率p(t)=0.1sint+0.1滿足假設1和假設2,如圖1所示,窗口大小估計誤差ε(t)漸近收斂到0。2控制體系的設計與分析2.1計算模型與控制函數由于窗口大小估計誤差ε漸近收斂到0,考慮如下系統狀態方程W^˙=Cqˉ-(C/2)W^2qˉp(t)qˉ˙=-ΝCW^qˉ3+Cqˉ2(12)通過變換得x1=-ΝCW^qˉ3+Cqˉ2x2=qˉ(13)改變狀態方程組(12),則x1、x2滿足xˉ1=-ΝC2qˉ4+ΝC22W^2qˉ4u(t)+3Ν2C2W^2qˉ5-5ΝC2W^qˉ4+2C2qˉ3xˉ2=x1(14)顯然當u=2(qˉ4-3ΝW^2qˉ5+5W^qˉ4-2Νqˉ3+1ΝC2v)/(W^2qˉ4)時,可以得到1組線性的系統狀態方程組x˙1=vx˙2=x1(15)下文通過反步設計法設計控制率v,使得隊列長度q收斂到一個期望的理想長度q*。隊列長度q收斂于q*,相當于x2收斂于x2=1/(q*+TpC)。基于這個目標,取z2=x2-x*2,設函數V(z2)=z22/2,則V˙(z2)=z2x˙2=z2x1(16)首先考慮標量系統x˙2=x1,把x1看作是輸入,設計反饋控制x1=φ(z2),以穩定原點z2=0。取x1=φ(z2)=-k1z2,k1>0,代入式(16)得V˙(z2)=z2x1=-k1z22≤0為運用反步法,應用變量代換z1=x1-φ(z2)=x1+k1z2,系統的形式轉化為z˙1=v-k12z2z˙2=-k1z2(17)取Vc(z)=z12/2+z22/2作為復合Lyapunov函數,得V˙c=z1(v-k12z2)-k1z22(18)取v=k12z2-k2z1,k1>0,k2>0,代入式(18)得V˙c=-k2z12-k1z22≤0。所以u(t)=2(qˉ4-3ΝW^2qˉ5+5W^qˉ4-2/Νqˉ3+(k12z2-k2z1)/(ΝC2))/(W^2qˉ4)(19)式中:k1、k2>0,z2=qˉ-qˉ*,z1=-ΝCW^qˉ3+Cqˉ2+k1z2。顯然控制率u(t)即丟包率p(t)。根據定理1對丟包率p(t)的限制條件,有以下對控制參數k1,k2的限制條件{0≤qˉmin4-3ΝW^2qˉmin5+5W^qˉmin4-2Νqˉmin3+k2CW^qˉmin3-k2ΝCqˉmin2+k1(k1-k2)ΝC2(qˉmin-qˉ*)≤W^2qˉmin420≤qˉmax4-3ΝW^2qˉmax5+5W^qˉmax4-2Νqˉmax3+k2CW^qˉmax3-k2ΝCqˉmax2+k1(k1-k2)ΝC2(qˉmax-qˉ*)≤W^2qˉmax42(20)式中:qˉmax=1/(ΤpC),qˉmin=1/(qmax+ΤpC),qmax是路由器緩存的最大容量。2.2種參考文獻的計算當丟包率p(t)如表達式(19)所示時,z1、z2收斂于原點。根據上文有z1=x1+k1z2=-ΝCWqˉ3+Cqˉ2+k1(qˉ-qˉ*),所以W收斂于1/(Νqˉ*)=(q*+ΤpC)/Ν,又因為往返時間r=q/C+Tp,所以W收斂于r*C/N,r*=q*/C+Tp,即TCP端發送數據的速率與其往返時間r成正比。參考文獻提出了一種擁塞算法公平性的判斷依據。定義1設有n個數據源發送端,其數據發送量分別為(x1,x2,…,xn),定義公平系數為f(x1,x2,?,xn)=(∑i=1nxi)2/(n∑i=1nxi2)并把f(x1,x2,…,xn)稱之為Jain公平系數。f(x1,x2,…,xn)的值在0到1之間,越大的Jain公平系數值代表了各數據流之間的公平性越好。下文根據Jain公平系數的定義研究本文算法的公平性,設有n個數據源發送端,其往返時延分別為ri,i=1,2,…,n。在時間T內發送的數據源分別為(x1,x2,…,xn),為了計算簡便,設T=m1r1=m2r2=…=mnrn,顯然有xi=(T/ri)Wi,又因為W收斂于r*iC/N,所以在一段較長的時間內近似的有xi=TC/N,有f(x1,x2,…,xn)=(∑i=1nΤC/Ν)2n∑i=1n(ΤC/Ν)2=1顯然本文算法具有較好的公平性。3仿真實驗與結果分析網絡試驗采用網絡仿真軟件ns-2,網絡拓撲結構如圖2所示。圖2中,si(i=1～N)為TCP應用發送端,N=30,其分組長度為500byte,sd為UDP應用發送端,其速率為0.5Mbps。結點nn1和nn2之間為瓶頸鏈路,其帶寬C=2500packet/s,即10Mbps。任意兩結點之間的傳播延時都為1.25ms,則Tp=0.01s。各個隊列緩存均為800packet,即qmax=800packet,期望的隊列長度q*=200packet。仿真實驗的采樣頻率為160Hz。在瓶頸鏈路采用本文的NAQM-bt算法,其他鏈路的隊列管理算法均采用尾丟棄(Droptail)算法。根據不等式組(20),取k1=1.15,k2=166.7。下面驗證NAQM-bt控制算法的魯棒穩定性。圖3(a)為初始網絡參數下瓶頸路由器中的隊列長度曲線;在圖3(b)中,在數據發送端加入1個UDP/CBR源作為噪聲干擾,發送帶寬為0.5Mb,在80s時開始發送數據,在240s時停止發送數據;在圖3(c)中Tp由0.01s變為0.1s;在圖3(d)中,在實驗進行到80s時,有15個新的FTP源加入開始發送數據,在180s的時候這15個FTP源停止發送數據并離去。由圖3可知,當網絡參數發生一些變化時,輸出反饋控制依然能得到較好的控制效果,這說明NAQM-bt算法具有較好的魯棒性,能適應一定網絡環境的變化。下面對本文的NAQM-bt算法以及KSFC算法、RBPC算法和NOFC算法的性能進行比較。圖4給出了在相同網絡環境下,這4種算法在瓶頸路由器中的隊列曲線對比。圖5、圖6分別是這4種算法在不同傳播延時下的鏈路利用率和丟包率。顯然,本文的NAQM-bt和RBPC能夠較好地抑制路由器中的隊列擾動,但是RBPC算法犧牲了一定的鏈路利用率,而本文的NAQM-bt算法保證了較好的網絡性能(鏈路利用率和丟包率)。下文驗證NAQM-bt控制算法的魯棒穩定性。表1為在不同參數條件下本文NAQM-bt算法的性能。顯然,對于滿足不等式組(20)的參數k1和k2,NAQM-bt算法都維持了較好的網絡性能,具有較高的魯棒