一種新的點對點路由算法容錯性概率分析

胡清桂

(內(nèi)江師范學(xué)院 現(xiàn)代教育技術(shù)中心,四川 內(nèi)江 641112)

隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)規(guī)模不斷擴大，網(wǎng)絡(luò)容錯性能變得愈加重要.為了避開故障節(jié)點，找到最佳路由，許多研究者都對網(wǎng)絡(luò)容錯模型進行了深入的研究，最早由Lass和Ni提出了拐彎模型(TurnModel)，之后Hadas等提出一種基于原點(Origin-Based)的路由策略，還有Chien和Kim提出的平面路由策略，以及王晶等[1]提出的最小連通分量模型.

為了提高網(wǎng)絡(luò)容錯能力，本文提出了一種新的點對點路由策略，對該算法的容錯性能進行了概率分析，結(jié)果表明新路由算法可以提高網(wǎng)絡(luò)的容錯能力，具有較好的應(yīng)用基礎(chǔ).

1 點對點路由協(xié)議

路由器的基本作用就是確定最佳路徑和轉(zhuǎn)發(fā)數(shù)據(jù)，為了提高路由器工作效率，本文提出一種新的點對點路由協(xié)議.首先，路由器創(chuàng)建一個緩存表，保存內(nèi)部主機訪問的外部網(wǎng)址、訪問時間，以便其它內(nèi)部主機訪問相同外部網(wǎng)址時，可以直接訪問該內(nèi)部主機.對于路由器需要創(chuàng)建的緩存表，需要以下幾項內(nèi)容：

<內(nèi)部主機IP地址，目的地IP地址，訪問文件及其路徑，訪問時間>.

接下來，當(dāng)有其它主機要訪問外部網(wǎng)址時，路由器先查看緩存表中是否已經(jīng)有主機曾訪問相同的目的網(wǎng)址，如果有主機曾訪問相同的目的網(wǎng)址時，把數(shù)據(jù)包轉(zhuǎn)發(fā)至該主機，讓它直接訪問內(nèi)部主機，訪問成功則結(jié)束，如果訪問失敗，再采用傳統(tǒng)路由算法，確定最佳路徑，最后轉(zhuǎn)發(fā)數(shù)據(jù)包，訪問外部目的網(wǎng)址.

在一個局域網(wǎng)內(nèi)，用戶眾多，很多時候用戶會訪問相同的外網(wǎng)地址，甚至需求可能也是相同的，這種情況下，很多訪問都可以在局域網(wǎng)內(nèi)部實現(xiàn)，路由器工作效率會得到提高，相應(yīng)地，整個網(wǎng)絡(luò)的容錯能力也會得到提高.同時也應(yīng)認識到，雖然前后2個內(nèi)部主機訪問的是同一個外部網(wǎng)址，但由于用戶身份、訪問時間、訪問目的等可能并不相同，它們期望得到的返回信息也不一定會相同，這時，由前一個主機來響應(yīng)處理后一個主機的訪問請求，很可能是失敗的.如果大部分對同一外部網(wǎng)址的訪問請求所期望得到的信息都不相同，這種情況下，本文所提出算法就不能顯著減少內(nèi)外網(wǎng)絡(luò)之間通信量，這一點需要進一步分析討論.

路由器增加點對點協(xié)議，雖然可以緩解出口壓力，但需要自己創(chuàng)建緩存表，保存內(nèi)部主機的訪問地址，顯然，這也會耗費一定的內(nèi)存資源，由訪問同一外部網(wǎng)址的前一個主機來響應(yīng)處理后一個主機的請求，這需要在主機上運行額外的程序并占用相應(yīng)的存儲空間來保存從外部網(wǎng)絡(luò)得到的信息，由于請求的種類有很多，需要保存的信息也可能有很多，這就需要有選擇地保存信息，采用何種方法選擇，這也需要進一步研究.但總體來看，對局域網(wǎng)而言，出口帶寬往往是網(wǎng)絡(luò)瓶頸，增加新的點對點路由協(xié)議后，路由器耗費本身的內(nèi)存資源，由此節(jié)約了網(wǎng)絡(luò)資源，本文認為是值得的.

2 網(wǎng)絡(luò)容錯性概率計算的相關(guān)概念及定義

我們把一個局域網(wǎng)看作是一個節(jié)點，以校園局域網(wǎng)為例，它內(nèi)部可能有數(shù)萬臺主機，它有自己的路由器，但在這里我們僅僅把它看作是一個節(jié)點.我們用Mm×n表示規(guī)模為m×n的網(wǎng)絡(luò).

對于一個網(wǎng)絡(luò)Mm×n，可以劃分為多個子網(wǎng)，不同的劃分方法可以得到不同的子網(wǎng)，這里規(guī)定子網(wǎng)k-Mesh的定義[2]：k-Mesh由2個整數(shù)b和d決定，b

網(wǎng)絡(luò)中k-Mesh連通子網(wǎng)的定義：每一個k-Mesh子網(wǎng)中每一邊上的正常節(jié)點數(shù)大于故障節(jié)點數(shù)，并且每個子網(wǎng)中的所有正確節(jié)點構(gòu)成一個連通圖，則稱之為k-Mesh連通子網(wǎng).

假定每個節(jié)點具有獨立隨機出錯概率，并服從指數(shù)分布，指數(shù)分布的定義是：若連續(xù)隨機變量ξ的概率密度為[3]

λ為常數(shù)，且λ>0，則稱ξ服從指數(shù)分布，記ξ～e(λ)，

所以ξ的分布函數(shù)為：

時間t不可能為負，節(jié)點出錯的概率p服從運行時間的指數(shù)分布，所以p=1-e-λt.

對于網(wǎng)絡(luò)中k-Mesh子網(wǎng)，我們有如下引理：設(shè)每個結(jié)點具有獨立的出錯概率p，則Mk×k是k-Mesh連通子網(wǎng)的概率為[4]：

(1)

式中Nk,i(0≤i≤k2)是指從Mk×k中去掉i個結(jié)點后,Mk×k的每一邊中正常節(jié)點超過一半且構(gòu)成連通圖的方法個數(shù).

3 案例分析與討論

為了簡便，討論M3×3是3-Mesh連通子網(wǎng)的概率.現(xiàn)在的問題是刪去i個節(jié)點后，網(wǎng)絡(luò)仍保持連通且每邊至少有2個正常的方法個數(shù)N3,i，當(dāng)沒有故障節(jié)點時,N3,0=1，只有1個故障節(jié)點時,N3,1=9；有2個故障節(jié)點時,M3×3仍保持連通且每邊上至少有2個正常節(jié)點的方法個數(shù)N3,2=20，這種情況，只要這2個錯誤節(jié)點不是正好在同一條邊上即可[5].由M3×3是3-Mesh連通子網(wǎng)定義，故障節(jié)點數(shù)為3的情況不討論.

對于故障節(jié)點數(shù)大于3的情況，可以驗證，N3,4=N3,5=…=N3,9=0.

證明以4個故障節(jié)點數(shù)為例，對于一個M3×3的3-Mesh網(wǎng)，一共有9個節(jié)點，可以看作是3條橫線和3條豎線相交，考察其中的3條橫線，因為有4個故障節(jié)點，所以，至少有1條橫線上存在2個故障節(jié)點，也就是說，一定會出現(xiàn)某一條邊上存在2個故障節(jié)點的情況，即不存在任何一種方法使網(wǎng)絡(luò)仍保持連通且每邊至少有2個正常節(jié)點，問題得證[5].

將上面得出的N3,i代入(2)式，即得出網(wǎng)絡(luò)M3×3是3-Mesh連通子網(wǎng)的概率為

所以M3×3是3-Mesh連通子網(wǎng)的概率為

Pr[C(M3×3)]=(1-(1-e-λt))9+9(1-(1-e-λt)8(1-e-λt)+20(1-(1-e-λt))7·

(1-e-λt)2.

現(xiàn)在討論M3×3采用新的路由協(xié)議后，從不連通改變?yōu)檫B通的概率.這里主要分析網(wǎng)絡(luò)中出現(xiàn)了2個故障節(jié)點的情況，從前面的討論得知，網(wǎng)絡(luò)M3×3中出現(xiàn)2個故障節(jié)點導(dǎo)致不連通，那么一定是這2個故障節(jié)點正好在同一條連線上.從前面的討論還得知，對于一個特定的故障節(jié)點，它出現(xiàn)故障有2類情況，假定2類故障各占50%的概率，第1類情況是不可能恢復(fù)正常的，對于第2類情況，一個節(jié)點內(nèi)部主機存儲有訪問內(nèi)容，并且能讓外界成功訪問的概率假定為p0=e-3λt，也就是說，這類故障不影響連通性的概率是p0=e-3λt，進一步，對于這一個特定的故障節(jié)點來說，它能轉(zhuǎn)變?yōu)檎９?jié)點的概率是p1=0.5×p0=0.5e-3λt，這樣，它不能轉(zhuǎn)變?yōu)檎９?jié)點的概率是

p2=1-p1=1-0.5e-3λt.

Mesh網(wǎng)絡(luò)M3×3中有2個故障節(jié)點，不管其中哪一個故障節(jié)點轉(zhuǎn)變?yōu)檎９?jié)點，M3×3都可以從不連通改變?yōu)檫B通，2個故障節(jié)點都轉(zhuǎn)變?yōu)檎９?jié)點，則M3×3也從不連通改變?yōu)檫B通，只有2個故障節(jié)點都沒有轉(zhuǎn)變?yōu)檎９?jié)點這種情況下，M3×3才會依然不連通.根據(jù)概率算法，2個故障節(jié)點都沒有轉(zhuǎn)變?yōu)檎９?jié)點的概率是[6]

p3=p2×p2=(1-0.5e-3λt)2.

進一步，某時刻t，網(wǎng)絡(luò)M3×3連通的概率為Pr[C(M3×3)]，它不連通的概率則為1-Pr[C(M3×3)]，它不連通，同時2個故障節(jié)點又沒恢復(fù)的的概率為

P1r[C(M3×3)]=(1-Pr[C(M3×3)])×p3=

(1-Pr[C(M3×3)])×(1-0.5e-3λt)2.

上面P1r[C(M3×3)]就是M3×3采用新路由算法后，在某時刻t依然不連通的概率，這樣，在時刻t網(wǎng)絡(luò)M3×3采用新協(xié)議后，連通的概率則為

P2r[C(M3×3)]=1-P1r[C(M3×3)] =
1-(1-Pr[C(M3×3)])×(1-0.5e-3λt)2.

下面證明P2r[C(M3×3)]>Pr[C(M3×3)].

證明

P2r[C(M3×3)]=1-P1r[C(M3×3)]=
1-(1-Pr[C(M3×3)])(1-0.5e-3λt)2> 1-(1-Pr[C(M3×3)])×1=Pr[C(M3×3)]).

P2r[C(M3×3)]>Pr[C(M3×3)]表明采用新協(xié)議后，網(wǎng)絡(luò)M3×3連通概率只可能得到提高，不可能降低.

需要說明的是，上面僅僅討論了網(wǎng)絡(luò)M3×3中出現(xiàn)2個故障節(jié)點導(dǎo)致不連通，采用新協(xié)議后，它的連通概率得到提高的情況，網(wǎng)絡(luò)M3×3中出現(xiàn)4個甚至更多個故障節(jié)點導(dǎo)致不連通時，即使采用新協(xié)議，網(wǎng)絡(luò)M3×3從不連通改變?yōu)檫B通的概率也很微小，可以忽略不計，這里就不作進一步的分析了.

最后，大致對比一下采用新的路由算法和不采用新路由算法2種情況下，Mesh網(wǎng)絡(luò)M3×3是3-Mesh連通子網(wǎng)的概率.沒有采用新路由算法時，M3×3是3-Mesh連通子網(wǎng)的概率是

Pr[C(M3×3)]=(1-(1-e-λt))9+9(1-(1-e-λt)8(1-e-λt)+20(1-(1-e-λt))7(1-e-λt)2.

采用新的點對點路由算法后，Mesh網(wǎng)絡(luò)M3×3是3-Mesh連通子網(wǎng)的概率為

P2r[C(M3×3)]=1-(1-Pr[C(M3×3)])×(1-0.5e-3λt)2=1-(1-[(1-(1-e-λt))9+9(1-(1-e-λt)8(1-e-λt)+20(1-(1-e-λt))7(1-e-λt)2])×(1-0.5e-3λt)2.

對于不同質(zhì)量的網(wǎng)絡(luò)設(shè)備組建的網(wǎng)絡(luò)，是不同的，根據(jù)可靠性手冊和相關(guān)資料[6-7]，這里取λ=3.5×10-6，根據(jù)上面的函數(shù)式，可以得到M3×3是3-Mesh連通子網(wǎng)的概率隨時間變化的大致曲線，如圖1所示.

圖1的2條曲線中，實線是采用本文點對點路由算法的3-Mesh連通子網(wǎng)的概率，虛線是沒有采用本文算法的3-Mesh連通子網(wǎng)的概率，從圖1中可以看出，采用新的點對點路由算法，可以提高M3×3是3-Mesh連通子網(wǎng)的概率，從而可以提高網(wǎng)絡(luò)容錯能力.需要說明的是，這個圖精度不是太高，但它已經(jīng)可以表明新的點對點路由算法可以提高網(wǎng)絡(luò)連通概率.

4 結(jié)語

為了提高路由器工作效率，本文提出了一種點對點路由算法，經(jīng)過M3×3容錯性分析表明，此算法可以增大網(wǎng)絡(luò)連通概率，相應(yīng)地可以使網(wǎng)絡(luò)容錯能力得到提高.當(dāng)然，本文只是一個初略的討論，在實際網(wǎng)絡(luò)中，情況要復(fù)雜很多.但可以肯定的是，如果網(wǎng)絡(luò)中采用新的路由算法，不但網(wǎng)絡(luò)容錯能力可以得到提高，而且可以減小網(wǎng)絡(luò)流量，減輕網(wǎng)絡(luò)壓力，可見，本文提出的新算法是有很大實際意義的，但要真正實現(xiàn)這一新的協(xié)議，還有許多具體問題需要解決，比如，當(dāng)內(nèi)部多個主機都有相同的資源時，路由器應(yīng)采用何種算法確定訪問對象，還有本文點對點路由算法如何與原有的路由器兼容等等.

參考文獻:

[1] 王晶,王高才,黃億海.節(jié)點隨機出錯概率下的Mesh網(wǎng)絡(luò)容錯性分析[J]. 小型微型計算機系統(tǒng). 2010,31(5):888-891.

[2] 王高才,陳建,陳松喬，等. Mesh網(wǎng)絡(luò)路由算法容錯性的概率分析[J]. 計算機學(xué)報. 2004, 27(3)：319-327.

[3] 李鵬,蘭巨龍. 一種新型的可重構(gòu)路由交換通用平臺[J]. 計算機應(yīng)用研究，2009，26(6)：2016-2019.

[4] 李黎,管曉宏,蔡忠閩，等.可重構(gòu)網(wǎng)絡(luò)系統(tǒng)的模型及體系結(jié)構(gòu)[J].小型微型計算機系統(tǒng)，2009,30(4):637-641.

[5] 江海峰,錢建生,孫彥景.WSN中基于能量代價的能量優(yōu)化路由算法[J]. 計算機科學(xué), 2012, 39(1)：73-76.

[6] 劉有耀,韓俊剛.一種星簇雙環(huán)片上網(wǎng)絡(luò)拓撲結(jié)構(gòu)[J].西安電子科技大學(xué)學(xué)報, 2009, 36(6)：1063-1069.

[7] 方效林,高宏,熊蜀光. 無線傳感器網(wǎng)絡(luò)高可靠低維護地理路由協(xié)議[J]. 通信學(xué)報, 2012, 33(5)：30-35.