一种基于最小路径的通信网络可靠性分析

B ased on the Shortest P ath

CHEN Jian,SUN Xiao2han,ZH ANG Ming2de

(Department o f Electronic Engneering,Southeast Univer sity,Nanjing210096,China)

Abstract:　This paper introduces background about the reliability researches in communication netw orks.On the basis of the shortest path and netw ork delay,we create a reliability evaluating m odel of communication netw ork,and analyse its re2 liability performance.We simulate a typical communication netw ork by using the m odel,obtain a range of the netw ork de2 lay for the given netw ork topology and analyse the dependence relation between the result and the reliability assessment of the communication netw ork.

K ey w ords:　C ommunication netw ork;reliability;delay;service performance

EEACC:　6150P;0170N

一种基于最小路径的通信网络可靠性分析①

陈　坚,孙小菡,张明德

(东南大学电子工程系,南京　210096)

摘要:介绍了通信网络可靠性研究的现状,然后,从网络最小路径的角度出发,在考虑网络延时的基础上,建立了可靠性评估模型,并分析了通信网络的可靠性性能。最后,通过模拟计算,得到了针对给定网络的网络延时条件的范围,以及分析了计算结果与网络可靠性评价的相关关系。

关键词:通信网;可靠性;延时;业务性能

中图分类号:T N915.02　　　文献标识码:A　　　文章编号:1005-9490(2003)04-0447-04

　　在通信业务急速膨胀的今天,通信网络的失效往往会对社会经济产生巨大的负面影响,有时甚至是毁灭性的。所以,人们对通信网络的可靠性性能十分重视,并且把它列为通信网络设计和分析必须考虑的因素之一[1]。

对于网络可靠性的这个概念,至今都没有一个统一的定义[2～4]。一般可以理解为:在人为或自然的破坏作用下,通信网络在规定条件下和规定时间内完成规定功能的能力。

通信网可靠性的研究大致可分为三个内容:1、抗毁性,即仅从网络拓扑结构考虑的网络失效,它的一般测度为粘聚度和连通度[5];2、生存性,即考虑到网络部件失效的随机失效,它的一般测度为连通概率[6,7];3、有效性,即考虑了满足网络业务性能条件下的网络可靠性,它的测度随着考察的业务的不同而不同[8,9]。

在满足一定的通信网络上层业务和网络延时要求的基础上,本文利用对网络各节点之间的最小路径的考察,给出了对整个通信网络的可靠性评价模型并进行了仿真模拟。

文中将用到的符号定义如下:

G(V,E)———以V为节点集,E为链路集的拓扑图;

L ij———v i到v j的链路长;

第26卷第4期2003年12月　　　　　　　　　

电　子　器　件

Chinese Journal of Electron Devices

Vol.26,No.4

Dec.,2003

①收稿日期:2003-06-06

作者简介:陈　坚(1979-),男,硕士研究生,主要从事光网络可靠性及保护策略,cjian@seu.edu.cn;　　　　　张明德,男,教授,博士生导师,mdzhang@seu.edu.cn.exp(-λi t)———v i的失效函数;

exp(-μij t)———e i的失效函数,此处μij=a L ij,a 为一常数;

T ij———v i到v j的网络延时;

T m———网络延时域值;

F(T ij)———路径选择因子;

r ij———v i到v j的业务量要求;

Pa ij———路径连通概率;

ε

ij———有效路径连通概率;

1　可靠性模型

　　首先,根据图论中的最短通路dijkstra算法,从拓扑图的任意一节点出发找到它到其他任意一节点的最小路径。然后,根据可靠性数学中串联系统的可靠性计算方法,利用路径中节点可靠性函数exp (-λi t)和链路可靠性函数exp(-μij t)求得每条路径

的路径连通概率Pa

ij。接着,由给定的域值条件T m[10]判断得出路径选择因子F(T ij)为

F(T)=1,T0,T(1)

可得

ε

ij

=Pa ij3F(T ij)(2)　　网络上层的业务量一般根据客户的要求给出为r ij,用业务量对有效路径连通概率进行加权[11],就可

以得到点路径可靠性测度B

i为

B i=

∑5

i=0,j=0

r ij3εij

∑5

i=0,j=0

r ij

(3)

由点路径可靠性测度B

i

,可看出在考虑网络延时情

况下,网络中每一节点相应的连通能力。

考虑到网络中每节点都有其自身的可靠性函数

描述,利用得到的点路径可靠性测度B

i

对各节点的失效函数再一次的加权,最后得到一个针对整个网络性能的综合有效性测度,记为A:

A=∑5

i=0

B i3exp(-λi t)

∑5

i=0

B′i

(4)

这里B′

i为网络延时域值T m为最大时的点路径可靠性测度。

最后,将变量t=0和域值条件T

m为无穷

(系统刚开始使用网络部件全为新,延时条件无限宽松)时的A值定义为A′=1,对所得A的结果进行归一化处理得到最终结果为

A l=

A

A′

(5)利用上述的模型就可以对整个网络的可靠性性能进行评估。

2　模拟计算与结果分析

　　给定一典型的赋权拓扑图G(V,E)(如图1),a, b,c,d,e,f分别代表地理位置不同的通信站点,网络各边的权代表网络实际距离(单位:公里)

图1　网络图示例

根据图1,给出网络关联矩阵D

ij为

D ij=

05

-7-2

506-9-

-60-6-

7--031

-9630-

2--1-0

此矩阵是以链路的长度为代价的。也可根据网络的不同要求选择不同的参量为代价。由于此模型是针对网络上层业务量负载的,所以给出的网络业务量

矩阵R

ij为一不对称矩阵

(单位:erlang),它可表示为R ij=

0110111113114112

1130113112110110

1121140115111112

1101101110115111

1131141141110112

1151121131131100

844　　　　　　　　　　　　　　　　　　　　　电子器件　　　　　　　　　　　　　　　　　　　　第26卷

按上述数据,根据已给出的可靠性模型就可对图1的网络进行计算分析。

图2给出的是域值条件为无穷,即不考虑网络延时,A l 和B i 随时间t 的变化。由计算数据可以看出B i 和A l 随t 的增大逐渐减小,符合网络可靠性随时间推移逐渐变差的实际。由于网络中节点和链路可靠性均被假设按指数分布,故从图中可看出表示网络每节点连通能力的点路径测度B i 几乎按同一曲线变化,可见给定拓扑结构网络中,各节点的连通能力的变化是相似的

。

图2　A 1和B i 随t 的变化

在测试网络性能时候,考虑到网络延时条件,不同的网络上层服务提出的延时域值条件可以是不一样的,有的服务可以容忍比较大的网络时延,而有的服务则只能容忍比较小的延时。因此必须根据给定的网络结构,给出网络能容许的延时条件的范围。

图3给出了不同时刻,网络有效性综合参数A

l

图3　A 1随T m 变化

随T m 的变化,由图可看出A l 随着时间t 的增大而减小,而随着域值T m 的增大而增大,并且增加的速率

逐渐减小。在T m 值增加到11以后,网络各方面的性能指数均已不再变化,即网络的最大延时不会超过11。

图4给出了网络路径点测度B 0随着时间t 的增大而减小,而随着域值T m 的增大而增大。此图从一个微观的角度来考察了网络中具体某点连通能力随t 和T m 的变化

。

图4　B 0随T m 变化

表1给出了t =1000h 时,网络中各点的点路径测度B i 随域值条件T m 变化。可以看出T m <6时,

网络中至少有一个节点的连通能力为0,即网络的业务传输量减少,用户需求的业务不能完成。此时可认为,此时网络性能较差。

表1　点路径测度B i 随域值条件T m 变化

T m

B 0

B 1

B 2

B 3

B 4

B 5

10000.18084300.19335920.187406000.180834

0.4162

30.390425000.5918040.1610490.416240.390425

00.5918040.3367350.56519150.5465870.210011

0.5918040.3367350.565191

60.765210.4200190.3659980.5918040.7320130.56519170.765210.5815590.3659980.5918040.7320130.74365580.765210.7754040.3659980.7561750.7320130.74365590.765210.9369390.5855840.936980.9369590.743655100.765210.9369390.7612490.936980.9369590.936979110.765210.9369390.936910.936980.9369590.93697912

0.765210.9369390.93691

0.936980.9369590.936979

　　通过以上的数据分析,我们可以看出网络的综

合性能衰减是网络内部各部件衰减的一个综合反映。根据本文中给定的拓扑结构(如图1),我们得到了能有效影响此网络结构的延时条件范围(6,11),当T m <6时,网络的可靠性性能教差,不能满足

9

44第4期　　　　　　　　　　　陈　坚,孙小菡等:一种基于最小路径的通信网络可靠性分析　　　　　　　　　　　　

m

>11时,网络的可靠性性能趋于稳定,即针对此特定的网络结构,用户所要求的延时条件对网络可靠性性能已经没有什么影响。据此可判断在具有一定业务量的网络中,对于一项具体的业务,它是否能容忍网络所产生的延时。例如,业务对延时条件要求比较苛刻,小于网络正常工作所能容忍的最小延时条件,则不能在此网络中应用这个业务,或者改善网络性能以减小网络所产生的延时。

3　结　论

　　通信网络可靠性随时间的推移逐渐变坏;同时,依据通信网络能容忍的延时域值条件,网络的可靠性功能值也不同,且条件越宽松功能值越大,即系统可靠性性能越好。此模型从最小路径的角度出发,考察了的网络中各节点与其它点的连通能力,再以此为基础综合考虑网络的可靠性性能。模型的计算深入到了网络内部,更加细致的描述了网络的性能。参考文献:

[1]　Sudhir S Dixit,Philip J Lin,Optical Netw orking:S igns of Ma2

turity[J].IEEE C ommunications,2002.2.

[2]　llyas M,Performance Evaluation of C omputer C ommunications

Netw orks[J].IEEE C ommunications,1985,33(4).

[3]　Raghavendra C S.Reliability M odeling and Analysis of C om2

puter Netw orks[J].IEEE T rans.on Reliability,1986,R-35

(2).

[4]　熊蔚明,刘有恒.关于通信网可靠性的研究进展[J].通

信学报1990,11(4).

[5]　叶明凤,姜成志,顾泽元.计算机网络可靠性的研究

[J].电脑开发与应用2001,14(7).

[6]　K ent Fitzgerald,Shahram Latifi,Pradip K.Srimani.Reliability

M odeling and Assessment of the S tar-G raph Netw orks[J].

IEEE T rans on Reliability,2002,51(1).

[7]　Jack Shaio.A Family of Alg orithms for Netw ork Reliability

Problems[J].IEEE C ommunications,ICC2002,2002,4:2167

-2173.

[8]　Lena W osinska,Lars Thylen,R oger P H olmstrom.Large2Ca2

pacity S trictly N onblocking Optical Cross-C onnects Based on Microelectrooptormechanical Systems(ME OMS)S witch Matri2 ces:Reliability Performance Analysis[J].JLT,2001,19(8). [9]　Michiaki Hayashi,K azuho Ohara,Hideaki T anaka,Masahiro

Daikoku,T om ohiro Otani,Masatoshi Suzuki.Highly Reliable Optical Bidirectional Path S witched Ring Netw orks Applicable to Photonic IP Netw orks[J].JLT,2003,21(2).

[10]　Bonaventura V,Service,Availability of C ommunication Net2

w orks[J].Proc.IEEE.NT C’80,H ouston,TX,1980,1(15.

2).

[11]　熊庆旭,刘有恒.给定拓扑结构的网络的可靠性设计

[J].通信学报1998,19(1).

33333333333333333333333333333333333333333333

(上接第446页)

波长上提供一个峰值增益,这样在多个泵浦波的共同作用下,便可得到一个具有宽平坦增益的光纤拉曼放大器。可见,利用多个波长的泵浦来拓展拉曼放大器的平坦增益带宽是一种行之有效的方法。当给出传输系统所需增益的大小以及泵浦个数时,通过调整各泵浦波输入功率的大小和泵浦波长,便可优化出满足所需的具有较宽平坦增益带宽的光纤拉曼放大器。

参考文献:

[1]　迟荣华,胡姝玲,吕可诚等.前途光明的宽带混合光纤

放大器[J].激光杂志,2001,22(4):6-8.

[2]　Shu Namiki and Y oshihiro Em ori,Ultrabroad-Band Raman

Amplifiers Pumped and G ain-Equalized by Wavelength-

Division-Multiplexed High-P ower Laser Diodes[J].IEEE Journal on Selected T opics in Quantum E lectronics,2001,7

(1):3-16.

[3]　江加和,宋子善,沈为群等.模拟褪火算法在连续变

量全局优化问题中应用[J].北京航空航天大学学报, 2001,27(5):556-559.

[4]　Min Bumki,Lee W on Jae and Namky oo,E fficient F ormula2

tion of Raman Amplifier Propagation Equations with Average P ower Analysis[J].IEEE Photonics T echnology Letter, 2000,12(11):1486-1488.

[5]　H odgkins on T G,Improved Average P ower Analysis T ech2

nique for Erbium-D oped Fiber Amplifiers[J].IEEE Photon2 ics T echnology Letter,1992,4(11):1273-1275.

[6]　Perlin Victor E,and Win ful Herbert G.Optimal Design of

Flat-G ain Wide-Band Fiber Raman Amplifiers[J].IEEE Journal of Lightwave T echnology,2002,20(2):250-254.

054　　　　　　　　　　　　　　　　　　　　　电子器件　　　　　　　　　　　　　　　　　　　　第26卷