一種新的點(diǎn)對點(diǎn)路由算法容錯(cuò)性概率分析

胡清桂

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

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

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

1 點(diǎn)對點(diǎn)路由協(xié)議

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

3 案例分析與討論

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

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

證明以4個(gè)故障節(jié)點(diǎn)數(shù)為例，對于一個(gè)M3×3的3-Mesh網(wǎng)，一共有9個(gè)節(jié)點(diǎn)，可以看作是3條橫線和3條豎線相交，考察其中的3條橫線，因?yàn)橛?個(gè)故障節(jié)點(diǎn)，所以，至少有1條橫線上存在2個(gè)故障節(jié)點(diǎn)，也就是說，一定會(huì)出現(xiàn)某一條邊上存在2個(gè)故障節(jié)點(diǎn)的情況，即不存在任何一種方法使網(wǎng)絡(luò)仍保持連通且每邊至少有2個(gè)正常節(jié)點(diǎn)，問題得證[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個(gè)故障節(jié)點(diǎn)的情況，從前面的討論得知，網(wǎng)絡(luò)M3×3中出現(xiàn)2個(gè)故障節(jié)點(diǎn)導(dǎo)致不連通，那么一定是這2個(gè)故障節(jié)點(diǎn)正好在同一條連線上.從前面的討論還得知，對于一個(gè)特定的故障節(jié)點(diǎn)，它出現(xiàn)故障有2類情況，假定2類故障各占50%的概率，第1類情況是不可能恢復(fù)正常的，對于第2類情況，一個(gè)節(jié)點(diǎn)內(nèi)部主機(jī)存儲(chǔ)有訪問內(nèi)容，并且能讓外界成功訪問的概率假定為p0=e-3λt，也就是說，這類故障不影響連通性的概率是p0=e-3λt，進(jìn)一步，對于這一個(gè)特定的故障節(jié)點(diǎn)來說，它能轉(zhuǎn)變?yōu)檎９?jié)點(diǎn)的概率是p1=0.5×p0=0.5e-3λt，這樣，它不能轉(zhuǎn)變?yōu)檎９?jié)點(diǎn)的概率是

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

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

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

進(jìn)一步，某時(shí)刻t，網(wǎng)絡(luò)M3×3連通的概率為Pr[C(M3×3)]，它不連通的概率則為1-Pr[C(M3×3)]，它不連通，同時(shí)2個(gè)故障節(jié)點(diǎn)又沒恢復(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采用新路由算法后，在某時(shí)刻t依然不連通的概率，這樣，在時(shí)刻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個(gè)故障節(jié)點(diǎn)導(dǎo)致不連通，采用新協(xié)議后，它的連通概率得到提高的情況，網(wǎng)絡(luò)M3×3中出現(xiàn)4個(gè)甚至更多個(gè)故障節(jié)點(diǎn)導(dǎo)致不連通時(shí)，即使采用新協(xié)議，網(wǎng)絡(luò)M3×3從不連通改變?yōu)檫B通的概率也很微小，可以忽略不計(jì)，這里就不作進(jìn)一步的分析了.

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

采用新的點(diǎn)對點(diǎn)路由算法后，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)的概率隨時(shí)間變化的大致曲線，如圖1所示.

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

4 結(jié)語

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

參考文獻(xiàn):

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

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

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

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

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

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

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