摘要： 网络运营商为用户提供的光纤接入主干网大多以环型网络的方式提供服务，然而目前对于大规模、环数众多、连接方式多样化的复杂多环网络缺乏性能优良的路由算法。为解决传统环网结构网络延迟高和传输效率低的问题，提出一种针对复杂多环网络拓扑的路由改进算法，将多环网络中的复杂路由问题转化为单环网中的简单路由问题。在此基础上，通过设计源溯节点还原以及路径还原算法，将单一环网改进为增强环网网络结构，使同一环内通信节点间的路径还原为完整最短路径，并从理论上证明该算法得到的最优路径是无差错的。实验结果表明，相比于现有的优化Dijkstra算法，该算法的搜索空间比提升约13%，具有更好的改进效果，且算法运行时间缩短79%，更适合复杂多环网络的路由计算。

关键词: 多环网络, 路由, 最优路径, 增强环网, 拓扑

Abstract: Most of the optical access backbone networks provided by network operators provide services in the form of ring network.At present, there is a lack of high-performance routing algorithms with good performance for large-scale complex multi-ring networks with a large number of rings and diverse connection modes.In order to solve the problem of high network delay and low transmission efficiency of traditional ring network structure, an improved routing algorithm for complex multi ring network topology is proposed.The complex routing problem in multi ring network is transformed into a simple routing problem in single ring network.The algorithm of source tracing node restoration and path restoration is designed.The single ring network is improved to an enhanced ring network structure, and the path between communication nodes in the same ring is restored to the complete shortest path.It is proved theoretically that the optimal path obtained by the algorithm is error free.The experimental results show that compared with the existing optimized Dijkstra algorithm, the SearchSpace ratio of the algorithm is improved by about 13%, the improvement effect has been significantly improved, and the running time of the algorithm is shortened by 79%.The proposed algorithm is more suitable for routing calculation of complex multi-ring network.

Key words: multi-ring network, routing, optimal path, enhanced ring network, topology

中图分类号: 

• TP391