具有不可靠链路的通信网最佳可靠路由的确定

IDENTIFICATION OF OPTIMAL RELIABLE ROUTING IN COMMUNICATION NETWORKS WITH UNRELIABLE LINKS

研究了对给定拓扑结构的通信网在假定节点完全可靠而边存在随机破坏的情况下，通过计算点对间的路由概率确定最佳可靠路由的两种算法———邻接矩阵算法和动态路由算法－ 邻接矩阵算法通过构造网络的邻接矩阵及一些相关矩阵，利用深度优先搜索的方法找到点对间的所有路由，进而计算各路由的概率并由此确定最佳可靠路由－ 动态路由算法则给出了在链路失效后，按照最短路径原则由失效链路的起始点重新构造最佳可靠路由的方法－ 图１，参５－

Two algorithms for reliable routing identificationAdjacent Matrix Algorithm (AMA) and Dynamic Routing Algorithm (DRA) are developed in this paper. The two algorithms are based on the assumption that the communication networks have a given topology with nodes being absolutely reliable but edges being randomly failing. With the two algorithms the routing probabilities between a node pair can be computed and the optimal reliable routing be identified in the communication networks. By constructing adjacent matrix and some related matrices of the network, AMA can identify all the routings between a node pair with Depth-First Search, compute probabilities of all routings and determine which routing is the optimal reliable one. DRA reconstructs the optimal reliable routing at the starting point of the failed link according to the shortest path principle when a link has failed. 1fig., 5refs.