Heuristic algorithm for fault detection and path performance monitoring in meshed all-optical networks

摘要

Fault detection is critical for all-optical networks (AONs). This paper introduces the concept of monitoring cycles and proposes a mechanism for fault detection and path performance monitoring based on decomposing AONs into monitoring cycles. Two monitoring cycle finding algorithms are developed: heuristic depth first searching (HDFS) and shortest path Eulerian matching (SPEM). The two algorithms are compared in terms of wavelength overhead in nodes and links. It is shown that the proposed fault detection mechanism based on monitoring cycles is effective and cost efficient. udHeuristic depth first searching (HDFS): ud1) Given graph G(V, E) , let the cycle cover C = = = null ; number all nodes in V; and label all nodes in V and all links in E as “uncovered”; ud2) Select an uncovered link e in E, if multiple such links are available; select the uncovered link whose endpoints are also uncovered. Start DFS from e and go to that Uncovered endpoints of e if possible; if no uncovered link with uncovered endpoint is available, apply the largest/smallest rule described below; ud3) At each step of the DFS, select an uncovered link if possible. If multiple links are available, alternatively use the largest/smallest node number first rule in the iteration, e.g. if the last time we selected the node with the largest number among multiple nodes with the same priority, then this time we select the node with the smallest number; ud4) Once a link returns to the previously visited part, a cycle c can be formed and add the cycle to the cover C; label all the links and nodes in cycle c as “covered”; ud5) Repeat (2)-(4) until all links in E are “covered”. udShortest path Eulerian matching (SPEM): ud(1) For a non-Eulerian graph G (V, E), find the set V’ of odd-degree nodes; ud(2) Start from a node x∈∈∈V’ and find the shortest path to every other node, select the smallest one among them, denote as p(x, y). Add path p(x, y) to G (now some links in G are “doubled”) and remove x, y from V’ ; ud(3) Repeat (2) until V’ = = = null. Now G (V, E) is Eulerian; ud(4) Find an Eulerian cycle of the augmented G(V, E) and decompose it to a cycle cover as mentioned above. udThis paper introduced the concept of monitoring cycles and proposed a fault detection and path performance monitoring mechanism based on decomposing AONs into monitoring cycles. The heuristic depth first searching (HDFS) and shortest path Eulerian matching (SPEM) algorithms are developed for finding monitoring cycles in AONs. The two algorithms are compared with respect to the maximum and average number of wavelengths occupied by monitoring in nodes and links. The results for the 4 network examples show that the wavelength overhead is pretty low with this mechanism. Thus the proposed mechanism based on monitoring cycles is a promising fault detection method for AONs. It is also applicable to path transmission performance monitoring. The results also suggest that the SPEM algorithm is better than the HDFS algorithm in terms of the wavelength overhead.