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

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

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