Monitoring Trails Computation within Allowable Expected Period Specified for Transport Networks

Active network monitoring based on Boolean network tomography is a promising technique to localize link failures instantly in transport networks. However, the required set of monitoring trails must be recomputed after each link failure has occurred to handle succeeding link failures. Existing heuristic methods cannot compute the required monitoring trails in a sufficiently short time when multiple-link failures must be localized in the whole of large-scale managed networks. This paper proposes an approach for computing the required monitoring trails within an allowable expected period specified beforehand. A random walk-based analysis estimates the number of monitoring trails to be computed in the proposed approach. The estimated number of monitoring trails are computed by a lightweight method that only guarantees partial localization within restricted areas. The lightweight method is repeatedly executed until a successful set of monitoring trails achieving unambiguous localization in the entire managed networks can be obtained. This paper demonstrates that the proposed approach can compute a small number of monitoring trails for localizing all independent dual-link failures in managed networks made up of thousands of links within a given expected short period.

Automated summary

The paper proposes an approach for computing the required monitoring trails within a specified expected period, allowing for rapid localization of link failures in large-scale managed networks. Random walk-based analysis estimates the number of monitoring trails needed, and a lightweight method is used to achieve partial localization before obtaining an unambiguous set of monitoring trails for the entire network.