无向双环网络的容错路由研究

Research on fault-tolerant routing of bidirectional double-loop networks

在节点出现故障的情况下,如何保证网络节点之间的路由是一个重要的问题。将无向双环网络的节点按照最短路径访问方式映射到直角坐标系形成最优路由构图CG(N;±r,±s);基于该构图根据源节点和目的节点是否位于坐标轴上以及它们周围的故障节点数,提出故障节点封闭区和逃逸区的概念;存在故障逃逸区的情况下,源、目的节点之间仍然可以进行最优路由,针对出现故障节点封闭区而无法进行最优路由的情况下,增加等价节点形成扩展路由构图ECG(N;±r,±s),从而寻找容错路由;给出最优路由构图、扩展路由构图和容错路由的算法,并编程仿真了这些算法。

It is important to assure communication among nodes tional double-loop network to Cartesian coordinates by the CG（N; ±r,±s）. By this graph according to whether source node in networks when fault nodes occur. Assigning nodes of bidirec- minimum distance visiting mode forms an optimum graph and destination node lie in horizontal or vertical coordinate and the amount of fault nodes around them, the concepts of closing areas and escaping areas of faulty nodes are proposed. When escap- ing areas occur, there exists optimum routing paths from source node to destination node. As for the situation of there exists no optimum routing that arising from closing areas of faulty nodes, adding equivalent nodes to form an extended optimum graph ECG（N; _＋r, ＋s） to seek fault-tolerant routing. The algorithms of optimum Cartesian coordinates graph, extended Cartesian coor- dinates graph and fault-tolerant routing are proposed and simulated by programming. Key words： bidirectional double-loop networks; optimum routing graph; extended routing graph; fault-tolerance routing; closing areas of faulty nodes; escaping areas of faulty nodes