作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2009, Vol. 35 ›› Issue (3): 148-151. doi: 10.3969/j.issn.1000-3428.2009.03.051

• 网络与通信 • 上一篇    下一篇

基于子网的E-2DMesh网络容错单播路由算法

肖 杰,梁家荣,洪锡清,李 银   

  1. (广西大学计算机与电子信息学院,南宁 530004)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-02-05 发布日期:2009-02-05

Subnet-based Fault Tolerant Unicast Routing Algorithm on E-2DMesh Networks

XIAO Jie, LIANG Jia-rong, HONG Xi-qing, LI Yin   

  1. (College of Computer and Electronic Information, Guangxi University, Nanning 530004)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-02-05 Published:2009-02-05

摘要: 基于k-E-2DMesh子网连通概念和局部信息,提出分布式E-2DMesh网络容错单播路由算法。对算法容错性进行概率分析,假设每个节点具有独立的出错概率,推导出路由算法成功返回由正确节点组成路径的概率。推理结果表明,对于规模较大的E-2DMesh网络,当k值为3而节点出错概率小于0.03%时,该算法找到正确节点所组成路径的概率大于等于99%。其具有线性时间复杂性,构造的路由路径长度接近2点间最优路径长度。

关键词: k-E-2DMesh子网, 容错单播路由, 局部连通性, 概率分析

Abstract: This paper proposes a distributed fault tolerance unicast routing algorithm based on the concept of k-E-2DMesh subnet and local information. It applies probabilistic analysis on the fault tolerance of this algorithm. Supposing each node has an independent failure probability, it is able to derive the probability that the routing algorithm successfully returns a fault-free routing path. Discursion result show that when the value of k is 3, the routing algorithm succeed in finding a fault-free routing path with probability at least 99% as long as the node failure probability is bounded by 0.03%. This algorithm runs in liner time, and its length constructed by the algorithm is close to the optimal length between 2 nodes.

Key words: k-E-2DMesh subnet, fault tolerant unicast routing, local connectivity, probability analysis

中图分类号: