基于非線性主動隊列管理的網(wǎng)絡(luò)輸出反饋控制

基于非線性主動隊列管理的網(wǎng)絡(luò)輸出反饋控制

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