Design of fault tolerant routing algorithm and probabilistic analysis on Torus networks

doi:10.3778/j.issn.1002-8331.2009.14.031

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (14): 103-106.DOI: 10.3778/j.issn.1002-8331.2009.14.031

• 网络、通信、安全 • Previous Articles Next Articles

Design of fault tolerant routing algorithm and probabilistic analysis on Torus networks

LI Yin,LIANG Jia-rong,XU Shuang,XIAO Jie

College of Computer，Electronics and Information，Guangxi University，Nanning 530004，China

Received:2008-03-12 Revised:2008-05-15 Online:2009-05-11 Published:2009-05-11
Contact: LI Yin

Torus网络中容错路由算法的设计与概率分析

李银,梁家荣,徐霜,肖杰

广西大学计算机与电子信息学院，南宁 530004

通讯作者: 李银

Abstract

Abstract: In the paper，a simple fault-tolerant routing algorithm is presented based on the concept of k-subtorus.Under the assumption that each node has an independent failure probability，it is able to compute the probability of the fault-free routing path which found by the routing algorithm.For the Torus network which has more than hundreds of thousands nodes，it is at least 99% the probability that a fault-free routing path can be found by the routing algorithm presented in the paper，which runs in linear time.

Key words: Torus networks, fault tolerant routing algorithm, connectivity, probabilistic analysis

摘要： 基于k-Torus子网的概念提出了一个简单的Torus网络容错路由算法。假设结点出错相互独立，计算出路由算法成功路由的概率。对于几十万个结点以上的Torus网络，提出的路由算法构造通路的概率可达99%，且所提出的路由算法具有线性的特点。

关键词: Torus网络, 容错路由算法, 连通性, 概率分析

LI Yin,LIANG Jia-rong,XU Shuang,XIAO Jie. Design of fault tolerant routing algorithm and probabilistic analysis on Torus networks[J]. Computer Engineering and Applications, 2009, 45(14): 103-106.

李银,梁家荣,徐霜,肖杰. Torus网络中容错路由算法的设计与概率分析[J]. 计算机工程与应用, 2009, 45(14): 103-106.

[1]	MENG Yun, HU Xin, DAI Liang, YU Lei. Connectivity Improvement Resource Allocation Algorithm in Interference Vehicular Networks [J]. Computer Engineering and Applications, 2019, 55(7): 9-15.
[2]	ZHANG Wenli, LIN Shangwei, LI Yihai, GUO Huiling. Diagnosability of Unidirectional k-Ary n-Cubes Under PMC Model [J]. Computer Engineering and Applications, 2019, 55(4): 62-65.
[3]	PENG Shuo1，2, LUO Chao1, WANG Bo1，2, XIAO Zhifang1. Research on g-Good-Neighbor Conditional Diagnosability of Exchanged Crossed Cube [J]. Computer Engineering and Applications, 2019, 55(13): 51-58.
[4]	WANG Hongshen, ZHANG Xiangyu, DOU Yongkun, WANG Yurong. Edge connectivity evaluation algorithm for performance of edge detectors [J]. Computer Engineering and Applications, 2018, 54(16): 192-196.
[5]	GAO Peixian1，2, WEI Lixian1，2, LIU Jia1，2, LIU Mingming1，2. Image steganalysis based on densely connected convolutional networks [J]. Computer Engineering and Applications, 2018, 54(15): 74-77.
[6]	ZHANG Guozhen. Sufficient conditions for networks to be maximally restricted edge-connected [J]. Computer Engineering and Applications, 2017, 53(8): 19-22.
[7]	ZHOU Houqing1，XU Youzhuan2. Algebraic connectivity of trees based on network topology [J]. Computer Engineering and Applications, 2017, 53(3): 106-109.
[8]	FENG Huifang, WANG Rui. Connectivity analysis for vehicular ad hoc networks in fading channels [J]. Computer Engineering and Applications, 2016, 52(18): 133-138.
[9]	XU Xiuzhen, ZENG Qi. Efficient decomposition algorithm for evaluating connectivity reliability of logistics transportation networks [J]. Computer Engineering and Applications, 2016, 52(17): 24-28.
[10]	WAN Jiqing, CHEN Yuehui, KANG Li. Algebraic connectivity of intersectant bicycle graphs [J]. Computer Engineering and Applications, 2016, 52(16): 41-45.
[11]	ZHANG Weiqi, WEI Chunya, BIAN Genqing. Study on networking algorithm and connectivity of wireless sensor networks [J]. Computer Engineering and Applications, 2016, 52(11): 108-111.
[12]	ZHANG Jiewu1，2, ZHANG Huilin1，2, LI Lunqing1，2. Segmentation of RMB serial number with removing noise and pollution [J]. Computer Engineering and Applications, 2015, 51(7): 179-183.
[13]	FAN Yongsheng1, LI Changhua1, LI Zhijie1, YAO Peng2. Classification method of building information modeling [J]. Computer Engineering and Applications, 2015, 51(4): 148-153.
[14]	YUAN Hao1, TENG Qizhi1, QING Linbo1, WU Yunqiang2. Fast calculation method for connected probability of two points in 3D model [J]. Computer Engineering and Applications, 2015, 51(3): 181-185.
[15]	LIU Lijun. Routing algorithm in wireless sensor network based on optimal connectivity power [J]. Computer Engineering and Applications, 2015, 51(22): 119-123.

Design of fault tolerant routing algorithm and probabilistic analysis on Torus networks

Torus网络中容错路由算法的设计与概率分析

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics