A New Heuristic for Monitoring Trail Allocation in All-Optical WDM Networks

We study the m-trail (monitoring trail) allocation problem in all-optical WDM mesh networks for achieving fast and unambiguous link failure localization. The existing ILP is not feasible for solving the problem in large-size networks. A heuristic RCA+RCS can find feasible solutions in a shorter running time, but it is a randomized algorithm. More importantly, RCA+RCS suffers from the disjoint trail problem which dramatically increases the number of required monitors in large-size networks. In this paper, we propose a new heuristic MTA (Monitoring Trail Allocation) to solve the problem. MTA avoids those issues in RCA+RCS, and achieves an efficient tradeoff between monitor cost and bandwidth cost. Compared with RCA+RCS, MTA greatly shortens the running time and achieves a much higher solution quality. We also show that MTA provides a flexible framework to enable multiple possible variations for future study.