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

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

基于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.