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

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

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

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.