Fault location algorithms for optical networks
Today, there is no doubt that optical networks are the solution to the explosion of Internet traffic that two decades ago we only dreamed about. They offer high capacity with the use of Wavelength Division Multiplexing (WDM) techniques among others. However, this increase of available capacity can be betrayed by the high quantity of information that can be lost when a failure occurs because not only one, but several channels will then be interrupted. Efficient fault detection and location mechanisms are therefore needed. Our challenge is to identify and locate failures (single or multiple) at the physical layer of an optical network in the presence of some lost and/or false alarms. After briefly introducing optical networks and the multiplexing techniques that can be used, we study the most common components and their most usual failures. We propose a classification of all the network components based on their behaviour when failures occur. This classification gives an abstract model of the optical network, which is appropriate for developing algorithms to locate faulty elements. Two algorithms that solve the fault location problem are proposed. Both algorithms cope with existence of false and missing alarms when locating single and multiple failures. The problem of locating multiple failures already in the absence of false or missing alarms, has been shown to be NP-complete. The first algorithm, which is called Alarm Filtering Algorithm (AFA) is based on the combination of two approaches: forward and backward. The forward approach returns for each network element, their domain, which is the set of network elements that will send an alarm when the considered element fails. The backward approach returns the set of elements that are directly related to the received alarms. In this approach, the alarms that are considered to provide redundant information, are discarded. The combination of the results given by both approaches allows the location of multiple failures, given an allowed number of false and missing alarms. However, this algorithm does not minimize the complexity when new alarms are received. Hence, a second algorithm, which is called Fault Location Algorithm (FLA), is proposed. The FLA concentrates the complexity in ,a pre-computation phase, so that when new alarms are received, the result of the algorithm is rapidly displayed. The FLA algorithm is based on the construction of a binary tree that realizes a non linear error correcting code. The FLA has also been extended to locate soft failures in addition to hard failures. Hard failures are unexpected failures, whereas soft failures are progressive failures due to equipment aging, misalignments or external factors such as temperature or pressure. Both algorithms are compared on some simulated networks using different network topologies and failure cases. The comparison has also be done on the basis of their worst case complexity. Some conclusions indication with which settings each algorithm perform the best, were obtained.
Faculté informatique et communications
Institut de systèmes de communication
Laboratoire pour les communications informatiques et leurs applications 3
Jury: Polina Bayvel, Wolfgang Denzel, Rachid Guerraoui, Jean-Yves Le Boudec, André Schiper
Public defense: 2000-5-26
Record created on 2005-03-16, modified on 2016-08-08