[1]姜禹,胡爱群,潘婷婷.基于链路重要性的分布式网络可靠性评价方法[J].东南大学学报(自然科学版),2008,38(4):547-552.[doi:10.3969/j.issn.1001-0505.2008.04.001]
 Jiang Yu,Hu Aiqun,Pan Tingting.Evaluation method for distributed network reliability based on link importance[J].Journal of Southeast University (Natural Science Edition),2008,38(4):547-552.[doi:10.3969/j.issn.1001-0505.2008.04.001]
点击复制

基于链路重要性的分布式网络可靠性评价方法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
38
期数:
2008年第4期
页码:
547-552
栏目:
信息与通信工程
出版日期:
2008-07-20

文章信息/Info

Title:
Evaluation method for distributed network reliability based on link importance
作者:
姜禹 胡爱群 潘婷婷
东南大学信息科学与工程学院,南京 210096
Author(s):
Jiang Yu Hu Aiqun Pan Tingting
School of Information Science and Engineering, Southeast University, Nanjing 210096, China
关键词:
分布式网络 分布式可靠性 文件生成树
Keywords:
distributed network distributed reliability file spanning tree
分类号:
TN913.02
DOI:
10.3969/j.issn.1001-0505.2008.04.001
摘要:
为了快速有效地评估分布式网络可靠性,针对目前最有效的HRFST算法在搜索最小文件生成树过程中存在的3个问题,提出了一种基于链路重要性的分布式网络可靠性评价方法.该算法以链路重要性为最小文件生成树的首要搜索依据,提高了干路被选中的概率.将改进的网络化简方法用于搜索的每一步,使图更为简化,并消除了对不含文件生成树的子图搜索.分析和实验结果表明,在得到正确可靠性结果的基础上,该算法减少了子图产生数量和分析可靠性的实际执行时间,性能优于其他算法.
Abstract:
In order to estimate the distributed network reliability in a fast and efficient way, focusing on three problems of the most effective HRFST algorithm in searching process of minimal file spanning tree, an evaluation algorithm for distributed network reliability based on the importance of link is proposed. The algorithm takes the link importance as the main rule for the minimal file spanning tree searching to increase the probability of choosing the network backbone. The improved network reduction methods are introduced during each searching step to make the graph simpler and the algorithm eliminates the need to search for the subgraghs which have no file spanning trees. The analysis and experimental results show that, based on the correct reliability results, the algorithm reduces both the number of generated subgraghs and the actual execution time. Therefore, its performance is better than those of other conventional algorithms.

参考文献/References:

[1] Gebre B,Ramirez-Marquez J.Element substitution algorithm for general two-terminal network reliability analyses [J]. IIE Transactions,2007,39(3):265-275.
[2] Satitsatian S,Kapur K.An algorithm for lower reliability bounds of multistate two-terminal networks [J].IEEE Transactions on Reliability,2006,55(2):199-206.
[3] Hardy G,Lucet C,Limnios N.K-terminal network reliability measures with binary decision diagrams [J].IEEE Transactions on Reliability,2007, 56(3):506-515.
[4] Younes A,Girgis M.A tool for computing computer network reliability [J]. International Journal of Computer Mathematics,2005,82(12):1455-1465.
[5] Hui K,Bean N,Kraetzl M,et al.The cross-entropy method for network reliability estimation [J].Annals of Operations Research,2005,134(1):101-118.
[6] Kumar V,Hariri S,Raghavendra C.Distributed program reliability analysis [J].IEEE Transactions on Software Engineering,1986,12(1):42-50.
[7] Raghavendra C,Kumar V,Hariri S.Reliability analysis in distributed systems [J]. IEEE Trans on Computer,1988,37(3):352-358.
[8] Kumar A,Rai S,Agarwal D.Reliability evaluation algorithm for distributed systems [C] //Proc IEEE INFOCOM 88.New Orleans,1988:851-860.
[9] Kumar A,Rai S,Agarwal D.On computer communication network reliability under program execution constraints [J].IEEE Journal of Selected Areas in Communications,1988,6(8):1393-1400.
[10] Chen D,Huang T H.Reliability analysis of distributed systems based on a fast reliability algorithm [J].IEEE Transactions on Parallel and Distributed Systems,1992,3(2):139-154.
[11] Chen D,Chen R S,Huang T H.A heuristic approach to generating file spanning trees for reliability analysis of distributed computing systems [J]. Computers Math Applic,1997,34(10):115-131.
[12] 陈勇,胡爱群,蔡天佑,等.通信网中链路重要性的评价方法[J].电子学报,2003,31(4):573-575.
  Chen Yong,Hu Aiqun,Cai Tianyou,et al.Evaluation method for link importance in communication networks [J]. Acta Electronica Sinica,2003,31(4):573-575.(in Chinese)
[13] Lin M,Chen D.The computational complexity of the reliability problem on distributed systems [J].Information Processing Letters,1997,64(3):143-147.
[14] Kumar A,Agrawal D.A generalized algorithm for evaluating distributed-program reliability [J].IEEE Trans on Reliability,1993,42(3):416-426.

备注/Memo

备注/Memo:
作者简介: 姜禹(1981—),男,博士生; 胡爱群(联系人),男,博士,教授,博士生导师,aqhu@seu.edu.cn.
基金项目: 国家高技术研究发展计划(863计划)资助项目(2006AA01Z218,2007AA01Z432)、国家242信息安全计划资助项目(2006A07).
引文格式: 姜禹,胡爱群,潘婷婷.基于链路重要性的分布式网络可靠性评价方法[J].东南大学学报:自然科学版,2008,38(4):547-552.
更新日期/Last Update: 2008-07-20