Monitoring Trail Allocation in all-optical networks with the Random Next Hop Policy

The concept of monitoring trail (m-trail) provides a striking mechanism for fast and unambiguous link failure localization in all-optical networks. To achieve fast m-trail design in large-size networks, two efficient heuristics RCA+RCS and MTA are proposed against the optimal ILP (Integer Linear Program) model. However, RCA+RCS suffers from the disjoint trail problem which increases the required number of m-trails, and MTA always finds a deterministic solution which may not be good enough due to the limited solution space. In this paper, we propose a new heuristic RNH-MTA (Monitoring Trail Allocation with the Random Next Hop policy) to solve those issues. Similar to MTA, RNH-MTA ensures a valid optical structure of each m-trail and sequentially adds necessary m-trails to the solution, and thus is free of the disjoint trail problem. By replacing the deterministic searching in MTA using the Random Next Hop policy, RNH-MTA sets up a probabilistic model in extending each m-trail. This not only enlarges the solution space and increases the solution diversity, but also enables a controllable tradeoff between the solution quality and the running time of the algorithm. Our numerical results show the advantages of RNH-MTA over both RCA+RCS and MTA.