基于复杂网络理论的计算机网络可靠性研究*

陈 江，丁洪伟，赵淑芳，林凤仙

(1.昆明南方地球物理技术开发有限公司，昆明 650051；2.云南大学 信息学院，昆明 650091)

随着计算机网络的快速发展，以计算机网络为基础的互联网促进了全球信息技术的又一次革命，推进了经济社会各领域的相互渗透融合，产生了许多新产品、新业务、新模式，世界各国都在大力发展互联网战略[1]。但与之而来的网络震荡、结构快速更新，给计算机网络的可靠性带来了巨大挑战。由于计算机网络不可靠因素造成的计算机网络故障事件给用户带来了巨大的经济损失，同时也给人们的生活带来了极大的不便，甚至造成严重的社会事件，使得越来越多的专家学者关注计算机网络可靠性的研究。

关于网络可靠度的精确计算问题早在1980年就由Ball证明是一个NP难题[2]。当前关于计算机网络可靠性评估的方法主要有：基于网络结构连通性的网络可靠性评估[3-5]；基于网络业务及性能的网络可靠性评估[6-7]；基于网络性能指标的网络综合可靠性评估[8-9]。计算机网络具有结构复杂、业务不断进化、链路连接存在多样性、中间设备随时间不断变化等特征，是复杂网络的典型代表。针对以上3种方法均不能完整地对计算机网络整体特性进行描述，根据计算机网络复杂特性选取复杂网络理论对计算机网络的可靠性进行研究分析。

首先给出了计算机网络的复杂网络特性指标，然后应用复杂网络理论构建了加权有向的网络模型，接下来通过计算信息转发过程中的节点度、紧密值及网络效率，进行计算机网络可靠性分析，最后通过对所给算例进行分析指出其可靠性管理能力及优化方向。

1 计算机网络复杂网络特性指标

计算机网络可靠性一般均采用抗毁性、生存性、有效性等指标来进行评估，对此，结合计算机网络运行实际，参考复杂网络小世界效应(Small-world Effect)和无标度特征(Scale-free Property)，选取的计算机网络可靠性评价指标主要有[10]：

(1) 节点的度及度分布。若节点i和节点j之间的连边表示为eij，则可将网络中节点i的度ki用公式定义为

若用N(k)表示网络中度数为k的节点数目，用N表示构成复杂网络的节点总数，则二者的比值即为网络中任一节点其度为k的概率P(k)，因此，可用函数P(k)描述一个复杂网络的度分布，即：

此外，若对复杂网络中的所有节点度求平均值，可得到平均度的表示式为

(2) 紧密度指标。指标用于表示节点跟相关节点连接关系的紧密程度，即中间节点数量，体现了节点信息传输能力。其指标值为相应节点跟网络中其他节点之间距离之和的倒数。则节点x的紧密度指标可以定义如式(1)所示。

(1)

其中，dxy为节点x到节点y之间的最短距离。

(3) 介数指标。指标反映网络节点在信息传输过程中的影响能力。利用介数指标反映节点的重要程度记为Bl，则介数指标可以定义如式(2)所示。

(2)

其中，nij为节点vl与vj之间的最短路径数，nij(l)为节点vl与vj之间的最短路径经过节点vl的条数。

(4) 网络效率。一个网络中，全局网络效率为全部节点之间效率的均值，用E表示，则有网络效率值如式(3)所示。

(3)

2 计算机网络加权有向网络模型的构建

为有效研究计算机网络信息传输过程的可靠性，根据复杂网络理论，将信息传输经过的核心设备作为复杂网络的节点，相邻设备之间的传输链路作为复杂网络的边，节点设备及链路的可靠度作为边的权重值，从而构建基于信息传输的计算机网络加权有向网络模型。

2.1 有向网络模型构建

根据计算机网络无权有向网络模型G(V，E)中各个节点连接关系，可以得到有向网络模型所对应的网络邻接矩阵A，邻接矩阵A中元素Cij值定义如下：

图1所示为计算机网络有向网络模型，根据图1可得到计算机网络的有向网络模型的邻接矩阵，如式(4)所示。

图1 计算机网络有向网络模型示意图Fig.1 Diagram of directed network model of computer network

(4)

在计算机网络中，不同设备及链路的使用寿命、稳定性、抗过载能力等存在较大差异，为准确评估整个网络的可靠性，在有向网络模型的基础上，通过引入设备及链路的可靠性指标构建计算机网络的有向加权网络模型进行可靠性评估。

2.2 权值的选取及计算

2.2.1 节点可靠度

计算机网络中设备及连接链路的可靠性特征量主要有设备可靠度R(t)、故障率λ(t)和平均无故障时间tMTBF(即平均寿命)。假设故障率λ为常数，设备可靠性概率分布服从指数分布，则有

假设设备故障仅跟设备可靠性设计有关，即设备设计寿命相关，结合可靠性分布的指数特点，构建基于设备状态的可靠性模型[12-13]，即

λ=Ke-CS

若可靠性分布服从指数分布有

(5)

其中，S为设备的状态评分，采用专家评分原则，满分为100分；K为比例系数，C为曲率系数，采用基于全寿命状态模型对参数进行求解。假定求解模型样本数据为单一设备全寿命周期的所有状态信息，参数求解过程如下：

(1) 定义设备理想使用寿命T0为

T0=e100C/K=1/λ0

其中，λ0为根据样本数据统计的故障率，是一个常数，即T0为一个已知值。

(2) 定义状态S下设备的理想状态寿命为

T(S)=eCS/K

(6)

(3) 由设备理想状态寿命与理想使用寿命相比得

T(S)/T0=eC(S-100)

(7)

(8)

也是可得未知参数C，将C代入式(5)可得

K=e100C/T0

(9)

2.2.2 链路可靠度

计算机网络传输链路介质主要以光缆为主，即链路的可靠度为节点设备之间光缆的可靠度。选取光缆可靠度评估指标为光缆平均使用时间，指标的影响因素主要有外部因素及内部因素，可由式(9)计算得到。

(10)

其中，ts为光纤预期平均使用时间；tp为光纤复绕筛选时施力时间，一般为1 s；Fs为光纤断裂概率；Np为光纤复绕筛选时1 km断裂次数；L为计算平均使用时间时光纤的总长；εp为光纤复绕筛选应力；εs为光纤服务期间所受应力；n为光纤静态疲劳参数；m为光纤韦伯尔分布曲线斜率。

根据YD/T769-2003中规定，光缆的寿命应不小于25年，则对实际状态下链路的可靠度进行归一化为

Rei=ts/25

(11)

2.2.3 等效权值及计算

计算机网络中，节点设备与链路采用串联方式连接起来，因此单节点及相连链路等效单元符合串联系统可靠性模型，则单节点及链路组合单元的等效可靠度计算如下：

设Rvi为(i=1，2，…，n)为第i个节点的可靠度，Rei=ts/25为(i=1，2，…，n)以Rvi为源节点的第i条链路的可靠度，则其等效单元li的可靠度为

Ri=Rvi×Rei

(12)

其中，Ri为第i个单元的可靠度。

3 实例分析

采用2.1节介绍的加权有向网络模型的构建方法，选取某企业核心网为例，根据信息转发方向构建节点11个、边20条的有向网络模型，如图2所示。

根据2.2节，采用全寿命状态模型计算路由器个体状态可靠性模型参数K及C的值。一般网络产品设计平均无故障运行时间(MTBF)为5×104h以上，选取样本路由器在全寿命周期运行过程中共发生3次故障，其中第3年发生1次，第5年发生2次，根据3次故障得到3个统计样本。对路由器状态采用专家评分法进行打分，其状态评分见表1。

图2 某企业核心网有向网络模型示意图Fig.2 Diagram of directed network model of a enterprise core network

表1 某路由器全寿命周期状态评分表Table 1 The state examination table of router Total-Life-Cycle

注：*表示故障状态，表中未列时间为理想状态(S为100分).

根据某企业统计的同一批次设备可靠性数据，经统计，某年因人员操作不当、电力系统不稳定、运维管理不良等原因造成网络中间设备232台共发生故障17次，所以有故障率λ0=7.33×10-2次/台，即T0=13.64。由式(6)-式(9)得，C=0.050 5，K=11.44，则设备的状态可靠性为

λ(S)=11.44×e-0.050 5 S

(13)

根据式(13)计算得到各个节点设备的可靠指标如表2所示。

根据式(11)、式(12)测算算例中计算机网络各链路的可靠度，经测算，排除外部因素，算例拓扑链路均大于YD/T769-2003规定的平均可用时间25 a，即可靠度均为1。则等效权值如表3所示。

表2 计算机网络各节点的可靠性指标Table 2 The reliability index of computer network nodes

表3 计算机网络等效单元的可靠度Table 3 The reliability of computer network equivalent element

根据表2所示各节点可靠性指标，构建算例计算机网络的加权有向网络模型，得到算例有向网络模型的邻接矩阵。

由图3可知，计算机网络加权有向网络模型中度大部分分布在4～5之间，占总数的54.5%；度值较低的节点数占45.5%，表明网络中孤立节点较多，整个网络连通性不强；节点5、6的度值最大，即当前结构中节点5、6为加权有向网络模型的关键节点，其失效时整个网络结构受影响较大，应加大对这些节点的保护，否则可能导致全网连通性失效。在图4中，节点5的紧密值最大，也就是说节点5通过网络对其他节点施加影响的能力最大。通过以上分析，节点5是整个有向网络的关键节点。

图3 计算机网络有向网络模型各节点度值Fig.3 Degree of nodes of directed network model of computer network

图4 计算机网络有向网络模型各节点紧密值Fig.4 Clustering coefficient of nodes of directed network model of computer network

如表4所示，计算机网络中所有节点的可靠指标分别提升15%、30%、45%、60%、75%及100%，计算机网络结构加权有向网络模型的网络效率值均会随之上升，而且当各个节点的可靠指标增大幅度越大，计算机网络结构加权有向网络模型网络效率值增幅就越大，说明提高节点的可靠指标可以提高计算机网络结构的可靠性，与计算机网络信息转发实际状况相符。

表4 计算机网络各等效单元可靠度指标变化全局网络效率值比较表Table 4 The statement of network efficiency for the variation of reliability index of computer network equivalent element

通过整体提高节点的可靠性可以验证整体节点可靠性对计算机网络结构可靠性的影响，结合实际分别对各节提高15%、30%的可靠度，如图5所示。通过与正常情况对比分析，发现不同节点的可靠指标分别提高时，其对计算机网络加权有向网络模型的网络效率值幅度增长贡献存在较大差异。其中，节点3、节点5和节点6的可靠指标使得计算机网络结构的加权有向网络模型的网络效率值有较大幅度的提升，即节点3、节点5和节点6是计算机网络结构中的关键节点。

图5各节点可靠指标提高后计算机网络加权有向网络模型网络效率变化曲线
Fig.5Networkefficiencyfordirectednetworkmodelofcomputernetworkwithexpandednodereliability

4 结 论

通过构建计算网络加权有向网络模型对可靠性进行分析，得结论：

(1) 在信息转发过程中，算例中节点5、6的度值最大，即节点5、6失效时网络影响最大；节点5的紧密值最大，其影响能力也最大；各个节点的度值较低，整个网络的连通性较差。

(2) 通过整体提高及分别对各节点提高可靠度对比分析，节点5为计算机网络的关键节点，计算机网络信息转发过程网络可靠性较差，网络可靠性由少数关键节点决定。

(3) 通过各节点可靠度变化对网络效率影响的对比分析，反映了各节点在计算机网络信息传输过程的不同作用；此外，各节点度值的高低与其对网络效率的影响不一致。

(4) 针对当前网络，可以采用增加中间节点、提高各节点之间的连通性及信息流负载分担等方式优化网络，提高整网可靠性。