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

• 网络、通信、安全 • 上一篇    下一篇

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

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

  1. 广西大学 计算机与电子信息学院,南宁 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   

  1. 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

摘要: 基于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