基于Local-map的Mesh光网络简单p圈构造法

Novel algorithm based on Local-map of finding good candidate simple p-cycles in optical Mesh network

圈构造算法是Mesh光网络中p圈法设计的前提。根据简单p圈的特点,针对圈构造算法问题,提出将原来圈上边变为跨接边的圈扩展算法。该圈扩展算法构造的圈具有保护性能优良,并且包含所有原来的圈上的点。在圈扩展算法和Local-map概念的基础上提出了基于Local-map的p圈启发式算法,该算法在Local-map中运行圈扩展算法,这样既能提高p圈的保护性能,又能使p圈位于局域范围内,保证快速恢复。对比分析Local-map和DFS两种找圈算法的实验结果,该方案构造的圈恢复速度快,容量利用率高,比较适合网状光网络中的p圈设计。

The p-Cycle is a promising approach for protecting working capacities in optical mesh networks. The first and most important problem in p-cycle network design is to find a set of the candidate p-cycles. The definition of the local-map, the basic types of p-cycle and several algorithms of finding cycles are introduced in the paper. In order to get the p-cycle whose on-cycle spans are near to each other, we construct the simple p-cycle in the local-map. The expanding algorithms perform on the cycle in the local-map to get more p-cycles with good efficiency. We present a novel heuristic algorithm of finding simple cycles based on local-map. Comparisons are made between this algorithm and the Depth-First Search （DFS） algorithm, and the result is that the local-map algorithm can find more candidate p-cycles with good efficiency in optical mesh networks.