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

doi:10.3778/j.issn.1002-8331.2009.14.031

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (14): 103-106.DOI: 10.3778/j.issn.1002-8331.2009.14.031

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

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

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

收稿日期:2008-03-12 修回日期:2008-05-15 出版日期:2009-05-11 发布日期:2009-05-11
通讯作者: 李银

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

摘要/Abstract

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

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

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

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

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.

[1]	孟芸，胡欣，代亮，余雷. 干扰车载网络中增强连通性的资源分配算法[J]. 计算机工程与应用, 2019, 55(7): 9-15.
[2]	严亚伟，周雁舟，惠文涛. 模型检测在完整性形式化验证中的应用研究[J]. 计算机工程与应用, 2017, 53(4): 59-63.
[3]	冯慧芳，王瑞. 衰落信道下车载自组织网络连通性分析[J]. 计算机工程与应用, 2016, 52(18): 133-138.
[4]	袁浩1，滕奇志1，卿粼波1，吴运强2. 三维模型两点连通概率函数的快速计算[J]. 计算机工程与应用, 2015, 51(3): 181-185.
[5]	张国珍. 单向k-元n-立方体网络[J]. 计算机工程与应用, 2015, 51(20): 1-4.
[6]	李兰英，易春焕，孙建达，李伟嘉. 基于单位元的无线传感器网络密钥管理方案[J]. 计算机工程与应用, 2015, 51(2): 94-98.
[7]	赵富强，张烁，何丽，邢恩军. 基于代数连通性的复杂网络割边模型研究[J]. 计算机工程与应用, 2014, 50(11): 135-138.
[8]	豆秋丽，梁家荣，王新阳，曹入辉. 节点随机出错概率下的E-2DMesh网络容错性研究[J]. 计算机工程与应用, 2012, 48(32): 76-79.
[9]	米波1，曹建秋1，段书凯2，王勇1. 无线传感器网络密钥管理问题综述[J]. 计算机工程与应用, 2011, 47(13): 77-82.
[10]	梁锦叶¹，梁家荣². 交换超立方体网络容错路由研究[J]. 计算机工程与应用, 2010, 46(32): 24-28.
[11]	刘胜辉¹，周野². 对ICE穿越Symmetric NAT技术的改进[J]. 计算机工程与应用, 2010, 46(3): 109-111.
[12]	花仁杰，梁家荣，彭芳艳，翁毅. 星形网络的容错并行路由研究及概率分析[J]. 计算机工程与应用, 2010, 46(14): 106-108.
[13]	陈刚¹,王国军¹,过敏意². 基于安全连通性检测的随机密钥预分配方案[J]. 计算机工程与应用, 2009, 45(6): 109-112.
[14]	夏勇兴,程明,王博亮. 医学图像中微细管道结构的表面绘制算法[J]. 计算机工程与应用, 2009, 45(4): 196-197.
[15]	闫宇琦¹,高太平^1,2. 交叉立方体互联网络的容错性研究[J]. 计算机工程与应用, 2009, 45(11): 95-96.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics