不同冗余度下的网络级联失效仿真分析

， ， ，

(1.陆军勤务学院 军事物流系，重庆 401311； 2.陆军勤务学院 勤务保障实验中心，重庆 401311；3.陆军勤务学院 网管中心，重庆 401311)

0 引言

在互联网覆盖越来越广泛的今天，人们生活的方方面面已经离不开互联网。然而近年来大规模的网络级联失效事件时有发生，对互联网的整体网络性能造成了极大的破坏。互联网的健壮性、稳定性问题引起了人们的关注[1-2]。

互联网可以看作是一组相互连接的自治系统(autonomous system，AS)的集合，每个AS可以看做一个单独的可管理的网络单元[3]。为增强网络的健壮性和稳定性，新的AS加入网络时往往会与多个AS建立连接，形成具有冗余度的备份连接，这种备份接入的现象会对网络级联失效产生影响。级联失效发生时域间冗余度不同会导致网络表现出不同的特征，因此需要对不同冗余度下的多自治域网络级联失效加以分析。

广义网络[4-6]、交通网络[7-8]等是当前级联失效问题研究的主要区域，如文献[4]采用介数分析法建立了双层复杂网络的级联失效模型；文献[8]提出了利用耦合映像格子模型有效降低运输网络级联失效程度的新思路。互联网级联失效的研究主要集中在特定的路由协议下[9-11]，如文献[10]基于IRS介数构建了域间级联失效模型，文献[11]建立了针对BGP-LDos威胁的级联失效传播模型。这些研究分析了级联失效的产生、传播机理以及影响因素，对网络级联失效的防控起到了一定的理论支持作用，却鲜有涉及自治域连接方式对网络级联失效发生时的影响，且忽视了互联网用户更加关注的是级联失效对网络服务质量的影响。

基于以上因素，针对互联网的现实情况，本文从不同冗余度连接的多自治域网络拓扑入手，建立了多自治域网络级联失效模型，设立网络级联失效时的评价指标，对不同冗余度下的多自治域网络进行模拟仿真，分析不同冗余度下级联失效的制约因素以及级联失效对网络拓扑和性能造成的影响，为多自治域网络级联失效的防控提供了一定的理论依据。

1 不同冗余度下的多自治域网络的拓扑分析

1.1 多自治域网络拓扑的两个级别

多自治域网络是典型的关联网络，具有层次分布特性和节点度分布的幂律特性。层次分布是多自治域网络的现实特性，位于上层的自治域级拓扑和下层的路由器级拓扑，因采用不同的路由策略和管理方法导致两层结构不同。节点度幂律分布是复杂网络理论中多自治域网络的基本特性。

现实中多自治域网络是一个动态实体，新的网络设备加入和旧的设备删除，导致多自治域网络的拓扑结构是不断变化的。但从网络整体来看，多自治域网络仍保持着无标度特性，所以可以用无标度网络的生成算法来近似模拟多自治域网络的生成模式，用节点数目有限的无标度网络来静态表示多自治域拓扑。按照互联网拓扑结构的划分方法，多自治域网络拓扑也分为自治域级和路由器级，路由器级别的网络拓扑结构也符合幂律特性[12]，如图1所示。为了便于对数据产生过程进行仿真，路由器级拓扑中的节点表示路由器及与其相连的主机、子网等网络实体。

图1 多自治域网络拓扑划分的两个级别

1.2 不同冗余度的多自治域网络拓扑

网络设计的冗余性是指在链路失效的情况下，通过提供迂回路由来建立稳定的传输路径，这是网络规划中一个重要的设计指标。在网络规划时，电信运营商为了提高网络的健壮性，新的自治域加入网络时往往会与多个自治域建立连接，形成具有冗余度的备份连接。网络中某个自治域出现故障时，流量可以绕过发生故障的自治域，经过备份连接进行转发。

这种备份接入的现象会对多自治域网络级联失效产生影响，为了分析不同冗余度接入方式形成的网络拓扑在级联失效时对网络性能造成的差异，定义域间冗余度为建模过程中新自治域与已有网络建立连接边的条数，用β表示。

当自治域数量不多时，Waxman模型可以很好地再现其拓扑[13]。本文的自治域级拓扑参考Waxman模型来生成，路由器级拓扑参考BA无标度模型来生成。使用冗余度β来控制自治域级拓扑的接入方式。理论上网络冗余度越大则网络健壮性越好，但现实中由于受成本的约束，冗余度一般是2，即双线接入。

为了直观比较不同冗余度接入方式的多自治域网络拓扑差异，以自治域数量为9，域内路由器数量为20，总节点数为180的多自治域网络为例，绘制其在冗余度分别为1、2和3时的自治域级拓扑和路由器级拓扑，对网络进行可视化分析。其中图2表示是β=1、2、3的网络拓扑(左为自治域级拓扑，右为路由器级拓扑)，可以看出冗余度越大，自治域之间的连接越稠密。

图2 冗余度β分别为1，2，3时的网络拓扑

2 多自治域网络级联失效模型

2.1 数据包产生和消失规则

多自治域网络中节点表示的是路由器及与其相连的主机等网络实体，因此其节点同时模拟主机产生、接收数据包以及路由器转发数据包。

2.1.1 数据包产生规则

t时刻，节点vi产生m个数据包，整个网络共产生m×N个数据包，N表示多自治域网络节点数，其中占数据包总量比例θ(0≤θ≤1)的数据包随机选择本自治域外的节点作为目的节点，剩余数据包随机选择所属自治域内的其余节点作为目的节点。按照此发包规则，整个网络的发包率为m，域间流量比例为θ。

2.1.2 数据包消失规则

数据包的消失在模型中是通过对数据包的删除实现的，根据数据包删除的条件不同，本文假设两种数据包消失的情况：

1)正常情况下，数据包到达目的节点，目的节点将数据包删除。

2)传输过程中，节点的失效造成数据包的目的节点不可达，转发节点在收到目的节点不可达的消息后将该数据包删除，此操作相当于网络中的丢包处理。

2.2 多自治域网络级联失效模型

2.2.1 网络节点属性定义

结合网络中路由器的实际情况，借鉴信息流动力学的建模思想[14]，对自治域内的节点vi定义与数据传输相关的性能属性，以便对网络中数据传输过程进行仿真。

定义1:节点vi最大转发能力为Fi：

Fi=η×Biη>0

(1)

Fi表示节点vi在单位时间内能够转发的数据包数量的最大值，Bi表示节点vi在初始时刻的最短路介数[15]，η为转发能力系数，表征节点转发能力大小。

定义2:节点vi在t时刻负载为Li(t)：

(2)

Qi(t)=Li(t-1)-Fi

(3)

Li(t-1)表示节点vi在t-1时刻需转发的数据包数量；m为t时刻节点vi自身产生的数据包数量；Ri(t)表示节点vi在t时刻收到的转发数据包数量。

定义3:节点vi的容量为Ci：

Ci=α×(Di+1)α≥1

(4)

Ci表示节点vi能承受的最大负载，α为容量系数，表征节点容量大小；Di表示节点vi的度。

2.2.2 路由规则

自治域内路由采用OPSF协议，该协议寻找最小度量的路径，由网管人员来决定度量的选取，通常选用路径长度、时延等。本节选择度量为路径长度，即最短路径。多自治域网络中的负载重分配是在转发节点失效后，含有该节点的路径被删除，发包节点利用域内全局信息重新寻找最短路径，负载沿新路径进行分配。自治域间路由采用BGP协议，寻找AS-PATH最短的一条路径。

2.2.3 多自治域网络级联失效分析

Step1:网络中某些节点负载超过其容量或者被攻击而导致失效后，将无法作为转发节点继续转发数据包。

Step2:数据包根据路由规则重新选择最短路径并进行发送。

Step3:承担转发任务的部分节点的负载超过其容量后失效，导致路由变化，进而引起负载重分配。

Step4:随着节点失效、路由变化和负载重分配的过程不断重复，最终导致级联失效的发生。

Step5:当网络中剩余正常节点的负载都不超过其容量，网络形成新的稳定状态，标志着级联失效结束。

3 级联失效评价指标

3.1 网络性能指标

现实生活中用户更加关注的是网络性能的变化，为了直观有效地反映级联失效对网络性能的影响，本文采用吞吐率和平均负载两种评价指标来表征网络性能的变化。

定义5:吞吐率TP(t)：

(5)

(6)

Zi(t)表示节点vi在t时刻转发数据包的数量。吞吐率TP可以反映网络级联失效前后网络性能的变化，其值越大，说明单位时间内网络能传输更多的数据包。

定义6:网络在t时刻平均负载LA(t)：

(7)

Li(t)表示节点vi在t时刻的负载。网络平均负载的变化可以反映网络中缓存数据包队列长度的变化，平均负载值越大，说明路由器中等待发送的数据包队列越长。

3.2 网络拓扑指标

级联失效对网络拓扑也会造成一定的影响，使网络拓扑结构发生变化。本文用节点失效比例来表征级联失效在网络拓扑层面的影响。

定义7:节点失效比例G：

(8)

N’表示网络中失效节点数量，N表示全部节点数量。

4 不同冗余度下的网络级联失效模拟仿真

为符合网络实际情况且同时方便不同冗余度的网络进行对比，选择冗余度分别为1、2和3生成三个网络，编号1、2、3。为了减少其它拓扑因素对实验结果的干扰，三个网络的自治域数量、域内路由器数量、节点数都相同。根据互联网服务提供商曾经使用过的自治域划分情况，本文的自治域数量设为9，自治域内路由器数量设为20，总的节点数为180。每个网络拓扑的配置参数如表1所示。(网络拓扑图同图2)

表1 网络拓扑的配置参数

采用以上三种网络拓扑结构，经过反复调整参数，在转发、容量等参数都相同的情况下，改变发包率使网络分别处于正常状态和级联失效状态，观察两种状态下不同冗余度的网络在拓扑结构和性能方面随时间的变化过程。模型中域间流量比例按照网络规划的“80/20”规则(大部分流量在域内，小部分流量在域间)取值为0.2，在此基础上调整转发能力系数η和容量系数α，使模型可以在低发包率时正常运行，高发包率时产生级联失效且能够在较短时间内结束。经反复调整模型参数，采用如下参数可满足以上要求：转发能力系数η=5，容量系数α=6，域间流量比例θ=0.2，时间t=1 000 s(仿真时间t取值要足够大，以便级联失效能在仿真时间内结束)；在以上参数条件下，多次调整发包率进行模拟仿真，发包率m=1 Mpps时，三种网络均处于正常状态，发包率m=14 Mpps时，三种网络均发生级联失效。为了降低实验结果的随机性，每种网络在同一发包率下进行10次实验，取平均值作为实验结果。

级联失效结束后，节点失效比例不再变化，吞吐率和平均负载也保持稳定。为了衡量不同条件(如发包率不同、容量不同)下级联失效结束后，整个网络受到的影响，并减少随机因素对实验结果的影响，分别取三种评价指标最后100 s时间段内的平均值作为评价指标的最终值。

4.1 不同冗余度下发包率对级联失效的影响

多自治域网络级联失效的重要原因之一是网络负载的骤增，通过改变发包率进而改变整个网络的负载，得到发包率对级联失效的影响关系。

图3 不同β下发包率对级联失效的影响

4.2 不同冗余度下转发能力对级联失效的影响

转发速率是路由器的一个重要指标，当转发速率过小时，数据包不能及时转发，而进入转发队列排队等待，造成路由器负载变大，有可能引起路由器失效。实验中采用转发能力系数η来表征路由器的转发速率，通过改变η的大小来研究转发能力对级联失效的影响。

从图4(a)可看出:1)随着转发能力系数的增大，级联失效的规模在不断减小直至为0。2)存在转发能力系数阈值，一旦转发能力系数超过该值，网络不会产生级联失效。3)冗余度越大的网络其转发能力系数阈值越小(η3<η2<η1)。图4(b)显示了级联失效时三种冗余度网络中转发能力系数η和吞吐率TP的关系。转发能力系数η超过阈值之后，网络吞吐率TP进入平稳状态；转发能力系数η未超过阈值即网络处于级联失效时，吞吐率TP随转发能力系数变大而增加。从图4(c)显示三种不同冗余度的网络随着转发能力系数η的增加，平均负载LA有逐渐下降并趋于稳定的趋势。

图4 不同β下转发能力对级联失效的影响

4.3 不同冗余度下容量对级联失效的影响

现实中路由器处理器或接口卡和数据总线间的所能吞吐的最大数据量取决于路由器的背板带宽，背板带宽越高，处理数据的能力越强，但成本也越高，所以背板带宽不可能无限增大。实验中用节点的容量来模拟路由器的背板带宽，通过容量系数α的改变来模拟路由器背板带宽的改变。

图5(a)显示了级联失效产生后，容量系数α的改变对拓扑层面的影响。1)当容量系数较小，节点失效比例随着容量系数的增大而减小甚至变为0，说明此时制约级联失效传播的主要因素是节点容量；2)相同的容量系数下，冗余度大的网络其节点失效比例较小，说明冗余度大的网络在拓扑层面抵御级联失效的能力较强。图5(b)显示了：1)容量系数α较小时，吞吐率TP随容量系数α增大而增加；因为此时容量系数制约着级联失效的规模，α越大则失效节点越少，会有更多的节点转发数据包，进而提高了吞吐率。2)容量系数α超过阈值后，吞吐率基本保持不变，容量系数的增大不会提高整个网络的吞吐率。图5(c)显示：1)未发生级联失效，容量系数的增大不会引起平均负载的变化；2)发生级联失效，容量系数的增大会引起平均负载的增大。另外，级联失效发生时，容量系数相同的情况下，冗余度大的网络仍然具有较低的平均负载，说明冗余度大的网络性能较好。

图5 不同β下容量系数对级联失效的影响

5 结语

本文针对不同冗余度连接方式下的多自治域网络，分析了其拓扑结构，建立了级联失效模型并进行仿真分析，观察不同冗余度下发包率、转发能力和容量对级联失效的影响，仿真结果表明，随着发包率的增加，网络失效规模增大；冗余度大的网络其结构鲁棒性好，发生级联失效时网络性能较好；增大转发能力比增大节点容量可以更有效的控制级联失效的传播。

在现实网络环境中，网络规划人员可以结合多自治域网络的吞吐率和平均负载情况，选择合理的冗余度接入方式，防止网络级联失效的发生。一旦级联失效发生，网络管理人员可以根据网络性能恶化的不同方面采取针对性的补救措施。

参考文献：

[1] 黎 松,诸葛建伟,李 星.BGP安全研究[J].软件学报,2013,24(1):121-138.

[2] Li Q,Zhang X W, Zhang X,et al.Invalidating idealized BGP security proposals and countermeasures[J]. IEEE Trans on Dependable and Secure Computing,2015,12(3):298-311.

[3] Tanenbaum A S.计算机网络[M]. 潘爱民，译.4版.北京:清华大学出版社,2004:387.

[4] 沈 迪,李建华,等.一种基于介数的双层复杂网络级联失效模型[J].复杂系统与复杂性科学,2014,11(3):12-18.

[5] 袁 铭.带有层次结构的复杂网络级联失效模型[J].物理学报,2014,63(22):220501.

[6] 陈世明,邹小群,等.面向级联失效的相依网络鲁棒性研究[J].物理学报,2014,63(2):028902.

[7] 王正武,王 杰,等.控制城市道路交通网络级联失效的关闭策略[J].系统工程,2016,34(2):103-108.

[8] 尹洪英,权小锋.交通运输网络级联失效影响规律及影响范围[J].系统管理学报,2013,22(6):869-875.

[9] 邱 菡,李玉峰,等.域间路由系统的级联失效攻击及检测研究[J].中国科学：信息技术,2017,47(12):1715-1729.

[10] 陆余良,杨 斌.域间路由级联失效分析与建模[J].系统工程与电子技术,2016,38(1):172-178.

[11] 苗 甫,王振兴,等.BGP-SIS:一种域间路由系统BGP-LDoS攻击威胁传播模型[J].计算机应用研究,2017,34(12):3735-3739.

[12] Magoni D,Pansiot J J. Internet topology modeler based on map sampling[C]. Piscataway, NJ: IEEE, 2002: 1021-1027.

[13] Waxman B M.Routing of multipoint connections[J]. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622.

[14] 赵 娟, 郭 平, 邓宏钟, 等.基于信息流动力学的通信网络性能可靠性建模与分析[J].通信学报, 2011, 8(32): 159-164.

[15] Brandes, U.A faster algorithm for betweenness centrality[J].Journal of Mathematical Sociology, 2001, 25(2): 163-177.