Internet路由器隨機(jī)建模與收斂性分析*

周 軍， 張 健， 楊順楓

（1.西南林業(yè)大學(xué) 數(shù)理學(xué)院，昆明 650224；2.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620）

引 言

路由信息協(xié)議分為內(nèi)部網(wǎng)關(guān)協(xié)議和外部網(wǎng)關(guān)協(xié)議：內(nèi)部網(wǎng)關(guān)協(xié)議包含RIP 協(xié)議、OSPF 協(xié)議等；外部網(wǎng)關(guān)協(xié)議包含BGP 協(xié)議、SPVP 協(xié)議等[1].目前針對(duì)路由收斂問題的研究，主要集中在兩個(gè)方面：一是收斂性的研究，其主要探討路由發(fā)散的原因，以及如何才能保證路由的收斂；二是收斂時(shí)間的研究，其主要關(guān)注如何加快收斂速度，縮短收斂所需的時(shí)間[2].

針對(duì)以上兩類問題，很多Internet 路由級(jí)模型被建立進(jìn)行分析.例如，文獻(xiàn)[3]通過有向圖建立BGP 通訊網(wǎng)絡(luò)模型并分析其收斂時(shí)間，根據(jù)實(shí)驗(yàn)注入數(shù)據(jù)和故障測(cè)量數(shù)據(jù)探討了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和策略對(duì)路由收斂速度的影響.文獻(xiàn)[4]使用有向圖對(duì)BGP 收斂過程建模，針對(duì)BGP 報(bào)文的處理和等待時(shí)間以及各種延遲對(duì)收斂時(shí)間的影響，給出了一種新的BGP 收斂時(shí)間上界.上述文獻(xiàn)指出：AS 內(nèi)部的拓?fù)洹⒏聢?bào)文處理過程等對(duì)BGP 收斂的影響仍是開放性問題.文獻(xiàn)[5]根據(jù)表征Internet 路由級(jí)拓?fù)湟?guī)律的多項(xiàng)特征值，提出了面向Internet 路由級(jí)拓?fù)涞腄NLH(dynamic non-linear hierarchy)模型，并結(jié)合遺傳算法優(yōu)化了節(jié)點(diǎn)間非線性連接參數(shù).文獻(xiàn)[6]分析了無標(biāo)度模型、啟發(fā)式優(yōu)化拓?fù)淠Ｐ?、IGen 模型等路由器級(jí)拓?fù)淠Ｐ蛢?yōu)缺點(diǎn)，并提出了AS 級(jí)-域內(nèi)雙層模型.文獻(xiàn)[7]把各路由器中網(wǎng)絡(luò)流量建模為無限多個(gè)到達(dá)代理的無限流，每個(gè)代理負(fù)責(zé)無限小的流量或作業(yè)，利用Lyapunov 穩(wěn)定性定理，理論證明了離散時(shí)間自私路由算法收斂于Wardrop 均衡.文獻(xiàn)[8]基于復(fù)雜網(wǎng)絡(luò)模型提出了一種路由器級(jí)互聯(lián)網(wǎng)拓?fù)溲莼Ｐ?，可將其用于收斂性控制等路由控?

以上文獻(xiàn)建立的模型都是確定性模型.事實(shí)上，路由協(xié)議在執(zhí)行過程中會(huì)發(fā)生許多隨機(jī)事件，這些隨機(jī)因素會(huì)影響路由器的收斂.比如：路由信息在路由器之間交換時(shí)存在隨機(jī)丟包情況，丟包會(huì)影響路由的收斂[9]；突然的網(wǎng)絡(luò)攻擊、斷電等會(huì)導(dǎo)致路由器互連拓?fù)浣Y(jié)構(gòu)的改變，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)路由收斂存在很大影響[3]；路由器連接鏈路存在噪聲，根據(jù)Shannon 定理，噪聲會(huì)影響鏈路狀態(tài)傳輸速度，從而影響路由協(xié)議的收斂性和收斂速度[10].顯然，建立路由隨機(jī)模型并對(duì)其進(jìn)行收斂性分析更貼近現(xiàn)實(shí)也更有意義.基于此目標(biāo)，本文引入Bernoulli白序列分布、Gauss 白噪聲、Markov 過程建立其隨機(jī)動(dòng)力系統(tǒng)模型，應(yīng)用隨機(jī)微分方程理論和隨機(jī)分析方法得出其路由收斂的充分條件，結(jié)果表明：在噪聲強(qiáng)度有限的情況下，路由設(shè)備的收斂與路由器連接拓?fù)涞腖aplace 矩陣、Markov 切換平穩(wěn)分布以及網(wǎng)絡(luò)中數(shù)據(jù)包的成功傳輸率息息相關(guān).最后通過數(shù)值仿真證明了所得結(jié)論的正確性.

1 問題描述

注2零狀態(tài)是誤差系統(tǒng)（3）的平衡點(diǎn).為了實(shí)現(xiàn)N個(gè)路由設(shè)備的收斂，接下來誤差系統(tǒng)（3）在孤立平衡點(diǎn)零處的穩(wěn)定性將被討論.

為了得到路由收斂的充分條件，我們還需要如下假設(shè)及引理.

2 主要結(jié)果

根據(jù)假設(shè)1 有

同時(shí)根據(jù)cij(t)是 Bernoulli 白序列分布，存在E{cij(r(t))?qi j(r(t))}=0，有

將式(10)、(11)代入式(9)可得

根據(jù)定義(2)，系統(tǒng)(3)在平衡點(diǎn)零處是均方漸近穩(wěn)定的.換句話說，N個(gè)路由設(shè)備的路由狀態(tài)在假設(shè)1～3 和條件(7)下能實(shí)現(xiàn)均方收斂.定理得證.

注3假設(shè)3 保證了各路由器之間的連通性.在假設(shè)3 條件下，根據(jù)式(7)，路由設(shè)備的收斂性還與Markov 過程平穩(wěn)分布π、噪聲強(qiáng)度相關(guān)矩陣H、路由連接聯(lián)合拓?fù)?、相鄰網(wǎng)絡(luò)節(jié)點(diǎn)之間丟包率 1 ?qij有關(guān).當(dāng)丟包率 1 ?qij越小時(shí)，qij越大，式(7)越容易滿足，各路由器的路由更容易收斂.當(dāng)噪聲強(qiáng)度相關(guān)矩陣H越小時(shí)，結(jié)論也一樣.

注4在理想狀態(tài)下，網(wǎng)絡(luò)中任何相鄰節(jié)點(diǎn)之間沒有丟包、噪聲和切換，這時(shí)Pun=Lun，m ink∈S{πk}=1，H=0.在聯(lián)合拓?fù)銰un是 連通的情況下，即聯(lián)合拓?fù)湎氯魏蝺蓚€(gè)路由器之間存在路徑，這時(shí)聯(lián)合拓?fù)銰un的 Laplace 矩陣Lun相應(yīng)特征值0 =λ1≤λ2≤···≤λN，顯然式(7)也成立，路由器收斂，這也與我們的經(jīng)驗(yàn)相符.

3 數(shù)值模擬

為了驗(yàn)證以上結(jié)論的正確性，我們使用MATLAB 數(shù)值仿真5 個(gè)路由設(shè)備（每個(gè)設(shè)備的路由表有三個(gè)狀態(tài)分量，用來代表三條路由）的收斂情況.5 個(gè)路由設(shè)備的拓?fù)浣Y(jié)構(gòu)將跟隨Markov 鏈 {r(t)}在G1和G2中隨機(jī)切換(圖1)，其中Markov 鏈在空間S={1,2}取 值，它的生成函數(shù) Γ定 義為根據(jù)遍歷定理π =πP，可得π=[5/9,4/9].

圖1 路由設(shè)備網(wǎng)絡(luò)連接拓?fù)鋱DFig.1 The router connection topology

另外，讓噪聲強(qiáng)度函數(shù)為g(t,xi(t))=Rxi(t)，且圖1 中各圖對(duì)應(yīng)的Laplace 矩陣，以及Q，R分別為

基于以上參數(shù)， mink∈S{πk}=4/9， 當(dāng)HTH=0．04I5×5時(shí)滿足假設(shè)1.使 用MATLAB 函 數(shù) eig(·)求矩陣HTH?mink∈S{πk}Pun的特征值分別為?1.714 2，?0.888 4，?0.404 4，?0.270 4，?0.078 1，顯然不等式(7)成立.根據(jù)定理1，5 個(gè)路由設(shè)備路由狀態(tài)收斂.

根據(jù)以上參數(shù)，利用Euler-Maruyama 方法[15]得到式(4)的數(shù)值解，并使用MATLAB 數(shù)值仿真5 個(gè)路由設(shè)備的收斂情況：圖2 顯示2-模態(tài)的Markov 鏈， {r(t)}在狀態(tài)空間1 和2 中隨機(jī)切換，其中1 代表路由設(shè)備的拓?fù)浣Y(jié)構(gòu)G1， 2 代表路由設(shè)備的拓?fù)浣Y(jié)構(gòu)G2，用來模擬因路由器節(jié)點(diǎn)故障、斷電或網(wǎng)絡(luò)攻擊等而造成的路由器互連拓?fù)浣Y(jié)構(gòu)改變.圖3 顯示路由設(shè)備x1～x5的 第1 個(gè)狀態(tài)分量x11～x51的收斂情況，圖示大約在25 ms 左右其收斂到同一狀態(tài).圖4、5 分別表示路由設(shè)備x1～x5的第2，3 個(gè)狀態(tài)分量收斂到同一狀態(tài).

圖2 2-狀態(tài)Markov 鏈Fig.2 The 2-state Markov chain

圖3 5 個(gè)路由器路由狀態(tài)第1 個(gè)分量Fig.3 The 1st element of the 5-router state

圖4 5 個(gè)路由器路由狀態(tài)第2 個(gè)分量Fig.4 The 2nd element of the 5-router state

圖5 5 個(gè)路由器路由狀態(tài)第3 個(gè)分量Fig.5 The 3rd element of the 5-router state

具體的算法步驟如下：

第一步 設(shè)置5 個(gè)路由器路由狀態(tài)變量x1(0)～x5(0)初始值；

第二步 根據(jù)成功傳輸率矩陣Q，使用MATLAB 函數(shù)sign(fix(rand(1,length(t)/(1?qi j) )))，構(gòu)建Bernoulli 白序列分布，用來模擬網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)間傳輸過程中的丟包情形；

第三步 運(yùn)用了獨(dú)立增量性生成Brown 運(yùn)動(dòng)，使用MATLAB 函數(shù)

W=cumsum(sqrt(dt)*0.2*randn(1,length(t)))

構(gòu)建Brown 運(yùn)動(dòng)，使用w(k+1)?w(k)模擬網(wǎng)絡(luò)中的Gauss 白噪聲；

第四步 根據(jù)矩陣指數(shù)函數(shù)得到轉(zhuǎn)移概率陣，并得到逐列累加轉(zhuǎn)移概率陣，進(jìn)一步模擬Markov 切換；

第五步 在第二、三、四步的基礎(chǔ)上，根據(jù)Euler-Maruyama 方法得到式（4）的數(shù)值解；

第六步 保存結(jié)果，即可得圖2～5.

4 結(jié) 論

針對(duì)噪聲、丟包和互連拓?fù)渫蛔儹h(huán)境下路由器的收斂問題，本文引入三個(gè)隨機(jī)過程建立相應(yīng)的隨機(jī)動(dòng)力系統(tǒng)模型并分析其收斂性.分析結(jié)果顯示：在噪聲強(qiáng)度有限的情況下，當(dāng)路由連接拓?fù)涞腖aplace 矩陣、Markov 切換平穩(wěn)分布以及網(wǎng)絡(luò)中數(shù)據(jù)包的成功傳輸率滿足一定數(shù)值關(guān)系時(shí)路由器能實(shí)現(xiàn)收斂.且當(dāng)網(wǎng)絡(luò)中數(shù)據(jù)包的成功率越高（網(wǎng)絡(luò)中丟包率越?。⒃肼晱?qiáng)度越小、路由器連接拓?fù)淝袚Q不頻繁時(shí)，路由器更容易收斂，反之也成立.本文建立的隨機(jī)模型只是現(xiàn)實(shí)模型的簡(jiǎn)化，還有許多其他因素（比如傳輸時(shí)滯等）有待進(jìn)一步考慮和研究.

致 謝本文作者衷心感謝西南林業(yè)大學(xué)科研啟動(dòng)基金（112007）和西南林業(yè)大學(xué)數(shù)理學(xué)院課程建設(shè)項(xiàng)目《計(jì)算機(jī)網(wǎng)絡(luò)》對(duì)本文的資助.