Faculté informatique et communications IC, Département de systèmes de communication, Institut de systèmes de communication ISC (Laboratoire pour les communications informatiques et leurs applications 3 LCA3)

Fault location algorithms for optical networks

Mas Machuca, Carmen ; Thiran, Patrick (Dir.)

Thèse sciences techniques Ecole polytechnique fédérale de Lausanne EPFL : 2000 ; no 2164.

Ajouter à la liste personnelle
    Summary
    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.
    Résumé
    Aujourd'hui, il n'y a pas de doute que les réseaux optiques sont la solution à l'explosion du trafic internet encore inimaginable il y a deux décennies. Les réseaux optiques offrent une grande capacité grâce, entre autres, à l'utilisation des techniques de multiplexage en longueur d'onde (Wavelength Division Multiplexing, WDM). Néanmoins, l'avantage procuré par cette augmentation de la capacité disponible doit être contre-balancé par la grande quantité d'information qui peut être perdue quand il y a une panne, car non seulement un, mais plusieurs canaux sont alors interrompus. Des mécanismes de détection et de localisation des pannes sont par conséquent nécessaires. Notre objectif est l'identification et la localisation de pannes (simples et multiples) d'éléments de la couche physique d'un réseau optique en présence de fausses alarmes et d'alarmes perdues. Après une brève description des réseaux optiques et des techniques de multiplexage, nous commençons par étudier les composants optiques et leurs pannes les plus courantes. Nous proposons une classification de tous ces éléments basée sur leur comportement en cas de panne. Cette classification procure un modèle du réseau optique à un niveau d'abstraction suffisant pour développer deux algorithmes de localisation des éléments défectueux. Les deux algorithmes tolèrent l'existence de fausses alarmes et d'alarmes perdues, et localisent des pannes simples, ou multiples. Notons que la localisation de pannes multiples, même sans fausses alarmes ou alarmes perdues, est un problème NP-complet. Le premier algorithme, que nous nommons Alarm Filtering Algorithm (AFA), est basé sur la combinaison de deux approches: directe (forward) et inverse (backward). L'approche directe donne pour chaque élément du réseau, son domaine, c'est-à-dire l'ensemble des éléments qui produiront des alarmes en cas de panne de cet élément. La seconde approche fournit l'ensemble des éléments qui sont directement liés aux alarmes reçues. Les alarmes qui sont considérées donner une information redondante sont éliminées. La combinaison des résultats donnés par les deux approches permet de localiser des pannes multiples, malgré l'existence d'un nombre fixé a priori de fausses alarmes et d'alarmes perdues. Cependant, cet algorithme ne minimise pas la complexité quand de nouvelles alarmes sont reçues. Par conséquent, un second algorithme, que l'on nomme Fault Location Algorithm (FLA), a été proposé. L'objectif du FLA est de concentrer la complexité dans une phase de pré-calcul, de telle sorte que les éléments défectueux soient localisés très rapidement dès que de nouvelles alarmes sont émises. L'algorithme FLA est basé sur la construction d'un arbre binaire ainsi que sur des propriétés de codes correcteurs non linéaires. Outre les pannes dures (ou soudaines), l'algorithme FLA a été étendu pour pouvoir également localiser pannes douces (ou progressives) qui sont causées par le vieillissement des équipements ou d'autres causes externes comme température et pression. Les deux algorithmes sont comparés sur des réseaux simulés, en prenant des topologies différentes et divers types de pannes. La comparison a été aussi faite sur base de leur complexité dans le cas le plus défavorable.