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

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

作　　者：肖杰[1] 梁家荣[1] 洪锡清[1] 李银[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机工程》2009年第3期148-151,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60564001);教育部"新世纪优秀人才支持计划"专项基金资助项目(NCET-06-0756);广西研究生创新基金资助项目(2006105930812M21)

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

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

分 类 号：TP393.08[自动化与计算机技术—计算机应用技术]