Internet路由器随机建模与收敛性分析*

周 军， 张 健， 杨顺枫

（1.西南林业大学 数理学院，昆明 650224；2.东华大学 信息科学与技术学院，上海 201620）

引 言

路由信息协议分为内部网关协议和外部网关协议：内部网关协议包含RIP 协议、OSPF 协议等；外部网关协议包含BGP 协议、SPVP 协议等[1].目前针对路由收敛问题的研究，主要集中在两个方面：一是收敛性的研究，其主要探讨路由发散的原因，以及如何才能保证路由的收敛；二是收敛时间的研究，其主要关注如何加快收敛速度，缩短收敛所需的时间[2].

针对以上两类问题，很多Internet 路由级模型被建立进行分析.例如，文献[3]通过有向图建立BGP 通讯网络模型并分析其收敛时间，根据实验注入数据和故障测量数据探讨了网络拓扑结构和策略对路由收敛速度的影响.文献[4]使用有向图对BGP 收敛过程建模，针对BGP 报文的处理和等待时间以及各种延迟对收敛时间的影响，给出了一种新的BGP 收敛时间上界.上述文献指出：AS 内部的拓扑、更新报文处理过程等对BGP 收敛的影响仍是开放性问题.文献[5]根据表征Internet 路由级拓扑规律的多项特征值，提出了面向Internet 路由级拓扑的DNLH(dynamic non-linear hierarchy)模型，并结合遗传算法优化了节点间非线性连接参数.文献[6]分析了无标度模型、启发式优化拓扑模型、IGen 模型等路由器级拓扑模型优缺点，并提出了AS 级-域内双层模型.文献[7]把各路由器中网络流量建模为无限多个到达代理的无限流，每个代理负责无限小的流量或作业，利用Lyapunov 稳定性定理，理论证明了离散时间自私路由算法收敛于Wardrop 均衡.文献[8]基于复杂网络模型提出了一种路由器级互联网拓扑演化模型，可将其用于收敛性控制等路由控制.

以上文献建立的模型都是确定性模型.事实上，路由协议在执行过程中会发生许多随机事件，这些随机因素会影响路由器的收敛.比如：路由信息在路由器之间交换时存在随机丢包情况，丢包会影响路由的收敛[9]；突然的网络攻击、断电等会导致路由器互连拓扑结构的改变，网络拓扑结构对路由收敛存在很大影响[3]；路由器连接链路存在噪声，根据Shannon 定理，噪声会影响链路状态传输速度，从而影响路由协议的收敛性和收敛速度[10].显然，建立路由随机模型并对其进行收敛性分析更贴近现实也更有意义.基于此目标，本文引入Bernoulli白序列分布、Gauss 白噪声、Markov 过程建立其随机动力系统模型，应用随机微分方程理论和随机分析方法得出其路由收敛的充分条件，结果表明：在噪声强度有限的情况下，路由设备的收敛与路由器连接拓扑的Laplace 矩阵、Markov 切换平稳分布以及网络中数据包的成功传输率息息相关.最后通过数值仿真证明了所得结论的正确性.

1 问题描述

注2零状态是误差系统（3）的平衡点.为了实现N个路由设备的收敛，接下来误差系统（3）在孤立平衡点零处的稳定性将被讨论.

为了得到路由收敛的充分条件，我们还需要如下假设及引理.

2 主要结果

根据假设1 有

同时根据cij(t)是 Bernoulli 白序列分布，存在E{cij(r(t))−qi j(r(t))}=0，有

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

根据定义(2)，系统(3)在平衡点零处是均方渐近稳定的.换句话说，N个路由设备的路由状态在假设1～3 和条件(7)下能实现均方收敛.定理得证.

注3假设3 保证了各路由器之间的连通性.在假设3 条件下，根据式(7)，路由设备的收敛性还与Markov 过程平稳分布π、噪声强度相关矩阵H、路由连接联合拓扑、相邻网络节点之间丢包率 1 −qij有关.当丢包率 1 −qij越小时，qij越大，式(7)越容易满足，各路由器的路由更容易收敛.当噪声强度相关矩阵H越小时，结论也一样.

注4在理想状态下，网络中任何相邻节点之间没有丢包、噪声和切换，这时Pun=Lun，m ink∈S{πk}=1，H=0.在联合拓扑Gun是 连通的情况下，即联合拓扑下任何两个路由器之间存在路径，这时联合拓扑Gun的 Laplace 矩阵Lun相应特征值0 =λ1≤λ2≤···≤λN，显然式(7)也成立，路由器收敛，这也与我们的经验相符.

3 数值模拟

为了验证以上结论的正确性，我们使用MATLAB 数值仿真5 个路由设备（每个设备的路由表有三个状态分量，用来代表三条路由）的收敛情况.5 个路由设备的拓扑结构将跟随Markov 链 {r(t)}在G1和G2中随机切换(图1)，其中Markov 链在空间S={1,2}取 值，它的生成函数 Γ定 义为根据遍历定理π =πP，可得π=[5/9,4/9].

图1 路由设备网络连接拓扑图Fig.1 The router connection topology

另外，让噪声强度函数为g(t,xi(t))=Rxi(t)，且图1 中各图对应的Laplace 矩阵，以及Q，R分别为

基于以上参数， mink∈S{πk}=4/9， 当HTH=0．04I5×5时满足假设1.使 用MATLAB 函 数 eig(·)求矩阵HTH−mink∈S{πk}Pun的特征值分别为−1.714 2，−0.888 4，−0.404 4，−0.270 4，−0.078 1，显然不等式(7)成立.根据定理1，5 个路由设备路由状态收敛.

根据以上参数，利用Euler-Maruyama 方法[15]得到式(4)的数值解，并使用MATLAB 数值仿真5 个路由设备的收敛情况：图2 显示2-模态的Markov 链， {r(t)}在状态空间1 和2 中随机切换，其中1 代表路由设备的拓扑结构G1， 2 代表路由设备的拓扑结构G2，用来模拟因路由器节点故障、断电或网络攻击等而造成的路由器互连拓扑结构改变.图3 显示路由设备x1～x5的 第1 个状态分量x11～x51的收敛情况，图示大约在25 ms 左右其收敛到同一状态.图4、5 分别表示路由设备x1～x5的第2，3 个状态分量收敛到同一状态.

图2 2-状态Markov 链Fig.2 The 2-state Markov chain

图3 5 个路由器路由状态第1 个分量Fig.3 The 1st element of the 5-router state

图4 5 个路由器路由状态第2 个分量Fig.4 The 2nd element of the 5-router state

图5 5 个路由器路由状态第3 个分量Fig.5 The 3rd element of the 5-router state

具体的算法步骤如下：

第一步 设置5 个路由器路由状态变量x1(0)～x5(0)初始值；

第二步 根据成功传输率矩阵Q，使用MATLAB 函数sign(fix(rand(1,length(t)/(1−qi j) )))，构建Bernoulli 白序列分布，用来模拟网络中相邻节点间传输过程中的丢包情形；

第三步 运用了独立增量性生成Brown 运动，使用MATLAB 函数

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

构建Brown 运动，使用w(k+1)−w(k)模拟网络中的Gauss 白噪声；

第四步 根据矩阵指数函数得到转移概率阵，并得到逐列累加转移概率阵，进一步模拟Markov 切换；

第五步 在第二、三、四步的基础上，根据Euler-Maruyama 方法得到式（4）的数值解；

第六步 保存结果，即可得图2～5.

4 结 论

针对噪声、丢包和互连拓扑突变环境下路由器的收敛问题，本文引入三个随机过程建立相应的随机动力系统模型并分析其收敛性.分析结果显示：在噪声强度有限的情况下，当路由连接拓扑的Laplace 矩阵、Markov 切换平稳分布以及网络中数据包的成功传输率满足一定数值关系时路由器能实现收敛.且当网络中数据包的成功率越高（网络中丢包率越小）、噪声强度越小、路由器连接拓扑切换不频繁时，路由器更容易收敛，反之也成立.本文建立的随机模型只是现实模型的简化，还有许多其他因素（比如传输时滞等）有待进一步考虑和研究.

致 谢本文作者衷心感谢西南林业大学科研启动基金（112007）和西南林业大学数理学院课程建设项目《计算机网络》对本文的资助.