A heuristic computation method for monitoring trails terminated at specified nodes

Detecting degraded signal quality solely at the terminal points of monitoring trails is a promising approach for reducing the fault management cost in networks. However, this approach requires that monitoring trails are routed so that all failures can be localized by using route information for the monitoring trails where degraded signal quality is detected. Thus, this paper proposes a novel heuristic method to compute the least number of monitoring trails required to localize all link failures in an arbitrary failure scenario. The proposed method can compute the monitoring trails terminating at the particular nodes to which monitors can be connected. This paper verifies the effectiveness of the proposed method by comparison with the global optimization method and an existing heuristic method. Using the proposed method, an accurate estimate of the least number of monitoring trails and their routes can be computed quickly, even for practical large-scale networks.