一种新的点对点路由算法容错性概率分析

胡清桂

(内江师范学院 现代教育技术中心,四川 内江 641112)

随着网络技术的飞速发展，网络规模不断扩大，网络容错性能变得愈加重要.为了避开故障节点，找到最佳路由，许多研究者都对网络容错模型进行了深入的研究，最早由Lass和Ni提出了拐弯模型(TurnModel)，之后Hadas等提出一种基于原点(Origin-Based)的路由策略，还有Chien和Kim提出的平面路由策略，以及王晶等[1]提出的最小连通分量模型.

为了提高网络容错能力，本文提出了一种新的点对点路由策略，对该算法的容错性能进行了概率分析，结果表明新路由算法可以提高网络的容错能力，具有较好的应用基础.

1 点对点路由协议

路由器的基本作用就是确定最佳路径和转发数据，为了提高路由器工作效率，本文提出一种新的点对点路由协议.首先，路由器创建一个缓存表，保存内部主机访问的外部网址、访问时间，以便其它内部主机访问相同外部网址时，可以直接访问该内部主机.对于路由器需要创建的缓存表，需要以下几项内容：

<内部主机IP地址，目的地IP地址，访问文件及其路径，访问时间>.

接下来，当有其它主机要访问外部网址时，路由器先查看缓存表中是否已经有主机曾访问相同的目的网址，如果有主机曾访问相同的目的网址时，把数据包转发至该主机，让它直接访问内部主机，访问成功则结束，如果访问失败，再采用传统路由算法，确定最佳路径，最后转发数据包，访问外部目的网址.

在一个局域网内，用户众多，很多时候用户会访问相同的外网地址，甚至需求可能也是相同的，这种情况下，很多访问都可以在局域网内部实现，路由器工作效率会得到提高，相应地，整个网络的容错能力也会得到提高.同时也应认识到，虽然前后2个内部主机访问的是同一个外部网址，但由于用户身份、访问时间、访问目的等可能并不相同，它们期望得到的返回信息也不一定会相同，这时，由前一个主机来响应处理后一个主机的访问请求，很可能是失败的.如果大部分对同一外部网址的访问请求所期望得到的信息都不相同，这种情况下，本文所提出算法就不能显著减少内外网络之间通信量，这一点需要进一步分析讨论.

路由器增加点对点协议，虽然可以缓解出口压力，但需要自己创建缓存表，保存内部主机的访问地址，显然，这也会耗费一定的内存资源，由访问同一外部网址的前一个主机来响应处理后一个主机的请求，这需要在主机上运行额外的程序并占用相应的存储空间来保存从外部网络得到的信息，由于请求的种类有很多，需要保存的信息也可能有很多，这就需要有选择地保存信息，采用何种方法选择，这也需要进一步研究.但总体来看，对局域网而言，出口带宽往往是网络瓶颈，增加新的点对点路由协议后，路由器耗费本身的内存资源，由此节约了网络资源，本文认为是值得的.

2 网络容错性概率计算的相关概念及定义

我们把一个局域网看作是一个节点，以校园局域网为例，它内部可能有数万台主机，它有自己的路由器，但在这里我们仅仅把它看作是一个节点.我们用Mm×n表示规模为m×n的网络.

对于一个网络Mm×n，可以划分为多个子网，不同的划分方法可以得到不同的子网，这里规定子网k-Mesh的定义[2]：k-Mesh由2个整数b和d决定，b

网络中k-Mesh连通子网的定义：每一个k-Mesh子网中每一边上的正常节点数大于故障节点数，并且每个子网中的所有正确节点构成一个连通图，则称之为k-Mesh连通子网.

假定每个节点具有独立随机出错概率，并服从指数分布，指数分布的定义是：若连续随机变量ξ的概率密度为[3]

λ为常数，且λ>0，则称ξ服从指数分布，记ξ～e(λ)，

所以ξ的分布函数为：

时间t不可能为负，节点出错的概率p服从运行时间的指数分布，所以p=1-e-λt.

对于网络中k-Mesh子网，我们有如下引理：设每个结点具有独立的出错概率p，则Mk×k是k-Mesh连通子网的概率为[4]：

(1)

式中Nk,i(0≤i≤k2)是指从Mk×k中去掉i个结点后,Mk×k的每一边中正常节点超过一半且构成连通图的方法个数.

3 案例分析与讨论

为了简便，讨论M3×3是3-Mesh连通子网的概率.现在的问题是删去i个节点后，网络仍保持连通且每边至少有2个正常的方法个数N3,i，当没有故障节点时,N3,0=1，只有1个故障节点时,N3,1=9；有2个故障节点时,M3×3仍保持连通且每边上至少有2个正常节点的方法个数N3,2=20，这种情况，只要这2个错误节点不是正好在同一条边上即可[5].由M3×3是3-Mesh连通子网定义，故障节点数为3的情况不讨论.

对于故障节点数大于3的情况，可以验证，N3,4=N3,5=…=N3,9=0.

证明以4个故障节点数为例，对于一个M3×3的3-Mesh网，一共有9个节点，可以看作是3条横线和3条竖线相交，考察其中的3条横线，因为有4个故障节点，所以，至少有1条横线上存在2个故障节点，也就是说，一定会出现某一条边上存在2个故障节点的情况，即不存在任何一种方法使网络仍保持连通且每边至少有2个正常节点，问题得证[5].

将上面得出的N3,i代入(2)式，即得出网络M3×3是3-Mesh连通子网的概率为

所以M3×3是3-Mesh连通子网的概率为

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.

现在讨论M3×3采用新的路由协议后，从不连通改变为连通的概率.这里主要分析网络中出现了2个故障节点的情况，从前面的讨论得知，网络M3×3中出现2个故障节点导致不连通，那么一定是这2个故障节点正好在同一条连线上.从前面的讨论还得知，对于一个特定的故障节点，它出现故障有2类情况，假定2类故障各占50%的概率，第1类情况是不可能恢复正常的，对于第2类情况，一个节点内部主机存储有访问内容，并且能让外界成功访问的概率假定为p0=e-3λt，也就是说，这类故障不影响连通性的概率是p0=e-3λt，进一步，对于这一个特定的故障节点来说，它能转变为正常节点的概率是p1=0.5×p0=0.5e-3λt，这样，它不能转变为正常节点的概率是

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

Mesh网络M3×3中有2个故障节点，不管其中哪一个故障节点转变为正常节点，M3×3都可以从不连通改变为连通，2个故障节点都转变为正常节点，则M3×3也从不连通改变为连通，只有2个故障节点都没有转变为正常节点这种情况下，M3×3才会依然不连通.根据概率算法，2个故障节点都没有转变为正常节点的概率是[6]

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

进一步，某时刻t，网络M3×3连通的概率为Pr[C(M3×3)]，它不连通的概率则为1-Pr[C(M3×3)]，它不连通，同时2个故障节点又没恢复的的概率为

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网络M3×3采用新协议后，连通的概率则为

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)]表明采用新协议后，网络M3×3连通概率只可能得到提高，不可能降低.

需要说明的是，上面仅仅讨论了网络M3×3中出现2个故障节点导致不连通，采用新协议后，它的连通概率得到提高的情况，网络M3×3中出现4个甚至更多个故障节点导致不连通时，即使采用新协议，网络M3×3从不连通改变为连通的概率也很微小，可以忽略不计，这里就不作进一步的分析了.

最后，大致对比一下采用新的路由算法和不采用新路由算法2种情况下，Mesh网络M3×3是3-Mesh连通子网的概率.没有采用新路由算法时，M3×3是3-Mesh连通子网的概率是

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网络M3×3是3-Mesh连通子网的概率为

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.

对于不同质量的网络设备组建的网络，是不同的，根据可靠性手册和相关资料[6-7]，这里取λ=3.5×10-6，根据上面的函数式，可以得到M3×3是3-Mesh连通子网的概率随时间变化的大致曲线，如图1所示.

图1的2条曲线中，实线是采用本文点对点路由算法的3-Mesh连通子网的概率，虚线是没有采用本文算法的3-Mesh连通子网的概率，从图1中可以看出，采用新的点对点路由算法，可以提高M3×3是3-Mesh连通子网的概率，从而可以提高网络容错能力.需要说明的是，这个图精度不是太高，但它已经可以表明新的点对点路由算法可以提高网络连通概率.

4 结语

为了提高路由器工作效率，本文提出了一种点对点路由算法，经过M3×3容错性分析表明，此算法可以增大网络连通概率，相应地可以使网络容错能力得到提高.当然，本文只是一个初略的讨论，在实际网络中，情况要复杂很多.但可以肯定的是，如果网络中采用新的路由算法，不但网络容错能力可以得到提高，而且可以减小网络流量，减轻网络压力，可见，本文提出的新算法是有很大实际意义的，但要真正实现这一新的协议，还有许多具体问题需要解决，比如，当内部多个主机都有相同的资源时，路由器应采用何种算法确定访问对象，还有本文点对点路由算法如何与原有的路由器兼容等等.

参考文献:

[1] 王晶,王高才,黄亿海.节点随机出错概率下的Mesh网络容错性分析[J]. 小型微型计算机系统. 2010,31(5):888-891.

[2] 王高才,陈建,陈松乔，等. Mesh网络路由算法容错性的概率分析[J]. 计算机学报. 2004, 27(3)：319-327.

[3] 李鹏,兰巨龙. 一种新型的可重构路由交换通用平台[J]. 计算机应用研究，2009，26(6)：2016-2019.

[4] 李黎,管晓宏,蔡忠闽，等.可重构网络系统的模型及体系结构[J].小型微型计算机系统，2009,30(4):637-641.

[5] 江海峰,钱建生,孙彦景.WSN中基于能量代价的能量优化路由算法[J]. 计算机科学, 2012, 39(1)：73-76.

[6] 刘有耀,韩俊刚.一种星簇双环片上网络拓扑结构[J].西安电子科技大学学报, 2009, 36(6)：1063-1069.

[7] 方效林,高宏,熊蜀光. 无线传感器网络高可靠低维护地理路由协议[J]. 通信学报, 2012, 33(5)：30-35.