Mesh网络容错单播路由算法

Fault-tolerant unicast routing algorithm on mesh networks

基于k Mesh子网连通的概念,提出一个简单的Mesh网络容错单播路由算法.该容错单播路由算法是基于局部信息的,因为路由算法在路由的过程中,只需要知道其相邻结点的信息而无需知道其他结点出错的情况.对于给定的源结点和目的结点,当路由路径扩展到每一个k Mesh子网中时,该子网均可独立地完成算法的操作而无需考虑算法在其他k Mesh子网中的操作状态.所以,路由算法是高度分布式的.容错单播路由算法的时间复杂性是最优的.模拟结果表明,路由算法所构造的路由路径长度非常接近于2个结点之间的最优路径长度.

With the continuous increasing in network size, routing algorithm in large size networks with faults has become unavoidable. This paper proposes a novel and simple fault tolerance unicast routing algorithm based on the concept of k-submesh connectivity on mesh networks. On the one hand, the algorithm is local information based, because each node knows only its neighbors′ status and no global information of the network is required by the algorithms in the course of routing. On the other hand, for the given pair of source node and destination node, when routing path extends in each k-submesh, this k-submesh can independently finish routing operations and algorithm doesn't consider operations in other k-submesh, so the algorithm is highly distributed. The running time of the unicast routing algorithm is optimal. Simulation results show that the length of the routing path constructed by this algorithm is very close to the optimal length.