Research On P-cycle Heuristic Algorithm In Mesh Optical Network

The survival of the network research is a hot spot because of the rapid development of the Internet.P-cycle combines the advantages of recovery speed of ring-like network and the high use of mesh network resource.P-cycle technology is divided into two parts: construction and configuration.There are two types of P-cycles,encircle-node type P-cycles and link-type P-cycles.The depth-first search algorithm(DFS)is usually not a simple cycle when constructing a cycle for a central node.If the expansion is based on this,the standard AE is not high,which means the quality of P-cycles are low.Therefor,an improved DFS construction algorithm is proposed,which shrinks the encircle-node type P-cycles into simple cycles,and in the process of expansion,choosing the span with the highest AE after expansion.The result shows that the AE of improved algorithm is higher than the traditional algorithm.In the link-type P-cycles,the number of cycles generated by Grow algorithm is large,and the Grow algorithm chooses the first one to expand which may lead to low AE.So,a cycles combining algorithm is proposed,which combines the set of cycles SLA,cycles SP-Add and improved Grow with one common span.After the merger,the higher AE is added to the alternative P cycles,the lower is adopted.The result shows the number of P cycles after the merger is significantly reduced,and the AE is higher than the traditional Grow algorithm.When the construction of P-cycles is finished,we need to spare capacity allocation.For the CIDA algorithm,the Grow algorithm is used to construct the P-cycle.Not all P-cycles are selected into the candidate P-cycles,which may lose the candidate cycles with good performance.In this paper,method based on K-shortest path construction is used to construct a large number of alternative P-cycles,and it is priority to select configured P-cycle with large CE.if the CE is the same,then choosing the P-cycles with more straddling spans,and if it still the same,choosing the minimized waste spare capacity cycles.Protection gap ratio and protection overhead ratio are proposed to illustrate the quality of the new algorithm.The results show that the new capacity allocation algorithm can achieve a 4.5% redundancy in the large-scale network with the optimal solution.The redundancy is better than CIDA with 6.1% and the operation time is less than 1.6seconds,besides,using less resources provide 100% protection.