Brevet FR2954872A1 — publié le 20110701

PROCEDE POUR ANALYSER LES DEFAILLANCES NECESSAIRES POUR RENDRE UNE COMMUNICATION IMPOSSIBLE ENTRE ELEMENTS D'UN RESEAU DE TELECOMMUNICATIONS L'invention concerne un procédé pour déterminer les défaillances éventuelles de noeuds et/ou des liens reliant les noeuds entre eux dans un réseau de télécommunications. II permet, par exemple, de déterminer le nombre d'éléments hors services conduisant à la perte de connexité entre des noeuds donnés, les combinaisons d'éléments hors service responsables de la perte de connexité, les éléments le plus souvent responsables de la perte de connexité. La percolation est un phénomène de seuil lié à la transmission d'une « information» par le biais d'un réseau de sites et de liens qui peuvent, selon leur état, transmettre ou non l'information aux sites voisins. L'étude de la percolation dans le domaine des réseaux de télécommunications permet donc de définir à partir de quel moment celui-ci devient assez sûr au niveau de son fonctionnement pour contrecarrer des pannes ou des sabotages de toutes sortes (agissant sur les noeuds et/ou les liaisons). En effet si celui-ci est conçu pour être proche du seuil de percolation, la moindre panne ou détérioration conduit à l'interruption des communications. II y donc perte de connexité du graphe reliant les noeuds entre eux, alors que si l'on est loin au dessous du seuil, il faut un nombre important de pannes ou de détérioration des noeuds et des liens pour stopper son fonctionnement. Etre proche du seuil de percolation permet de disposer d'un réseau moins cher mais rend le réseau par contre plus vulnérable en cas de défaillances. De façon générale dans des problèmes de ce type, le pourcentage de noeuds et/ou de liaisons coupés augmentant, on atteint un certain seuil où, quel que soit le nombre de relais, il devient impossible de communiquer entre deux stations éloignées. La valeur pc associée au pourcentage critique de liaisons actives nécessaires pour que deux points quelconques ou deux noeuds du réseau soient reliés, est appelée « seuil de percolation ». Interpréter ce problème de communication comme un phénomène de percolation consiste à évaluer la probabilité d'existence d'un ensemble de liens, autorisant la communication directe ou indirecte entre deux stations. La publication « networks and availability and connexity » de Philippe Loisèle et Jacques Chommeloux évoque une analyse de connexité dans l'ensemble du réseau. L'idée de la présente invention concerne un procédé qui va io permettre de déterminer le nombre de défaillances nécessaires pour empêcher la communication de paires distantes choisies, les combinaisons des éléments correspondantes et la fréquence d'apparition de chaque élément dans ces combinaisons. A partir de cette information, il sera possible de proposer une nouvelle architecture de réseau fiable au cours de son is fonctionnement. D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description d'un exemple de réalisation annexé des figures qui représentent : 20 • La figure 1, un exemple de réseau comprenant des noeuds reliés entre eux par des liens, • La figure 2, un exemple d'interface mise à la disposition d'un utilisateur pour lire le résultat du procédé selon l'invention et éventuellement prendre une décision. 25 La figure 1 schématise un réseau de communications formés par plusieurs noeuds Ni reliés entre eux au moyen de liens li qui peuvent être des liens physiques ou toute autre moyen existant. Les noeuds sont définis par : 30 - un identifiant unique, représenté par un nombre entre 0 et 999 pour les noeuds. un indicateur de bon fonctionnement, qui permet de définir si l'élément est en état de bon fonctionnement ou si au contraire celui-ci est en panne. une valeur de disponibilité au sens général, c'est à dire une valeur entre 0 et 1 qui peut représenter une disponibilité intrinsèque, une disponibilité opérationnelle, une probabilité de bon fonctionnement sur un temps donné, etc. un type (abonné ou transit). Certaines méthodes ne traitent que sur les noeuds abonnés (le calcul analytique par exemple). le réseau étant constitué d'un couche logique et d'une couche physique, il io y a donc un indicateur définissant l'appartenance à telle ou telle couche. Les liaisons entre noeuds sont définies par exemple par: un identifiant unique dont le nombre minimale est, par exemple, 1000. une disponibilité. un poids qui représente en réalité le coût technique d'une liaison. 15 un indicateur qui définit le type de la liaison (liaison physique ou logique). Pour effectuer le calcul de percolation sur des réseaux de télécommunications, le système selon l'invention comportera, par exemple, un processeur 1, une interface graphique 2 permettant l'entrée d'informations 20 ou de commandes, ainsi que l'affichage des résultats, un moyen de mémorisation ou de stockage des résultats, par exemple une mémoire, 3. La première étape après avoir pris connaissance de l'architecture initiale du réseau est de générer des défaillances dans le réseau et d'analyser son comportement face à ces défaillances. On regarde pour 25 chaque combinaison de défaillances (on place donc les éléments de la combinaison en état de panne) si les paires sélectionnées par l'utilisateur peuvent communiquer. Les combinaisons sont fonction d'un nombre de défaillances. On génère donc des combinaisons de « n » éléments défaillants parmi tous les éléments du réseau. Le procédé va commencer en générant une seule défaillance, on regarde ensuite pour toutes les applications possibles aux éléments s'il existe un élément engendrant la perte de connexité pour les paires sélectionnées. On augmente au fur et à mesure le nombre de défaillances et on génère les combinaisons en fonction de ce nombre. Dès qu'une combinaison de défaillances engendre la perte de connexité, on regarde si io pour ce nombre de défaillances il y a d'autres combinaisons d'éléments qui engendrent la perte de connexité. Les combinaisons des éléments ayant engendré une perte de connexité entre les paires sélectionnées sont stockées dans la mémoire 3. On regarde ensuite pour chaque élément le nombre de fois qu'il 15 apparaît dans les combinaisons d'éléments hors service et on construit un tableau de couples (élément, fréquence d'apparition dans les combinaisons d'éléments hors service). Ce tableau comprenant les couples (éléments identifiés (nceuds et/ou liens), nombre de défaillances) permet d'isoler les éléments les plus sensibles, c'est-à-dire ceux qui ont le plus de chance 20 d'engendrer une défaillance dans le fonctionnement du réseau. L'étude des réseaux consiste en partie à trouver les forces et les faiblesses de celui-ci. Dans ce but il est possible d'effectuer des statistiques permettant d'analyser les éléments du réseau qui provoquent le plus souvent la perte de connexité. 25 Définition de la k-connexité : Un graphe k-connexe est un graphe connexe qui reste connexe après suppression de n'importe quel sous-ensemble de k-1 sommets est dit k-connexe (ou bi-connexe quand k = 2). Le théorème de Menger indique que pour être résistant à la défaillance de k-1 noeuds, un réseau doit posséder k routes noeuds internes disjointes entre toute paire de 30 sommets. Théorème 1 :, (Menger) Un graphe est k-connexe si et seulement si pour toute paire de sommets u, v, il existe k chemins noeuds interne disjoints reliant u à v. Description des étapes mises en oeuvre dans le procédé selon l'invention calcul de percolation sans tenir compte des éléments en liaison avec les éléments de départ. Fonctions utiles : o DeterminerEnsembleATraiterSans() permet de sélectionner dans le graphe tous les éléments nécessaires au calcul. Ici les éléments de io départ ainsi que les éléments en liaisons avec les éléments de départ ne seront pas pris en compte. o CombinaisonPercolation() permet de générer des combinaisons d'éléments à partir des éléments fournis par la fonction DeterminerEnsembleATraiterSansO. La fonction 15 CombinaisonPercolation() prend en entrée un nombre de défaillances, ce nombre permettant de définir le nombre d'éléments constituant une combinaison. o CalculPercolation() permet la recherche d'un chemin entre les paires sélectionnées par l'utilisateur. Cette fonction fait appel à la fonction 20 DFS_IsRouteExisteO. o La fonction DFS_IsRouteExiste() parcourt le graphe en profondeur pour vérifier l'existence d'un chemin entre 2 noeuds du graphe. Etapes Soit un graphe g = G(N, L) correspondant à un réseau donné initialement où 25 N est le nombre de noeuds et L le nombre de liaisons. Entrée : Un Graphe g = G(N, L, p, q), tableau de paires. Sortie : seuil de percolation seuil. 1. On détermine les éléments à traiter à l'aide de la fonction DeterminerEnsembleATraiterSans(). //Initialisation des variables booléen TestVerification Réel seuilsù O Entier nbDéfaillances '1ù 1 2. tant que ( TestVérification4-- faux) a. On génère les combinaisons de nbDéfaillances éléments défaillants grâce à CombinaisonPercolation(), les éléments défaillants étant marqués à etatSimule 1--- 0 b. Pour chaque combinaison générée au fur et à mesure, chercher l'existence de routes pour toute les paires sélectionnées par l'utilisateur, avec la fonction CalculPercolation(), qui utilise DFS_IsRouteExiste() sur chaque paire pour déterminer l'existence d'une route. Si ( il n'existe aucune route valide) alors TestVérification' true Fin si //Cela correspond donc à la première combinaison générant la perte de connexité pour toutes les paires sélectionnées. nbDéfaillances aù nbDéfaillances + 1 Fin tant que . Compilation des statistiques de percolation obtenues et affichage. • Seuil de percolation • Eléments générant la perte de connexité ^ Fréquence des éléments générant la perte de connexité La figure 2 schématise un exemple d'interface qui permet à un utilisateur de paramétrer la mise en oeuvre du procédé, par exemple en sélectionnant des paires de noeuds utilisés pour les étapes précitées. D'autre part, l'utilisateur aura aussi le choix de l'élément à mettre en défaillance noeuds et/ou liens. Les étapes mises en oeuvre dans les différentes variantes de réalisation exposées précédemment sont par exemple implémentées en utilisant le langage C++ ou tout autre langage de programmation qui permet ro une manipulation des différents objets ; noeuds, liaisons, réseau. L'interface Homme machine peut être une interface avec fenêtres de saisie sous Windows, des boutons d'action, des menus déroulant, une utilisation de dispositifs de pointage. 15 Le procédé et le système selon l'invention offrent notamment les avantages suivants : • Un établissement rapide des faiblesses au point de vue connexité d'un réseau de télécommunications, face à des dégradations multiples avec la possibilité d'évoluer vers un autre' réseau plus robuste. 20 • Une mise en évidence des points d'articulation (noeuds critiques) et les isthmes (liaisons critiques). REVENDICATIONS1 - Procédé mis en oeuvre au sein d'un système comprenant au moins un processeur (1), un moyen de mémorisation des résultats (3), afin de déterminer le nombre de défaillances rendant impossible une communication entre les éléments d'un réseau de communication caractérisé en ce qu'il comporte au moins les étapes suivantes : Définir un graphe g G(N, L) correspondant à un réseau donné initialement où N est le nombre de noeuds et L le nombre de liaisons, Définir en Entrée des étapes du procédé : un Graphe représentation du réseau g = G(N, L, p, q), un tableau de paires de noeuds du réseau pour lequel on cherche à déterminer l'apparition du seuil de percolation provoquant une rupture de la connexité entre les noeuds desdites paires, Déterminer en Sortie : un seuil de percolation seuil en exécutant les étapes suivantes : 1. On détermine les éléments à traiter à l'aide de la fonction DeterminerEnsembleATraiterSansQ : on initialise les variables suivantes Une variable booléen TestVerification et on met une variable Réel seuil à 0 on met Entier nbDéfaillances à 1 2. on exécute les étapes suivantes tant que ( la variable TestVérification est à faux) : a. on génère les combinaisons de nbDéfaillances, éléments défaillants grâce à une fonctionCombinaisonPercolationO, les éléments défaillants étant marqués par une variable etatSimule mise à 0, b. pour chaque combinaison générée au fur et à mesure, chercher l'existence de routes pour toute les paires sélectionnées par 30 l'utilisateur, avec la fonction CalculPercolationO, qui utilise unefonctionDFS_IsRouteExiste() sur chaque paire pour déterminer l'existence d'une route : s'il n'existe aucune route valide alors mettre la variable TestVérification à vrai ou true, ce qui correspond à la première combinaison générant la perte de connexité pour toutes les paires sélectionnées, incrémenterla variable nbDéfaillances à nbDéfaillances + 1 3. Compiler les statistiques de percolation obtenues, stocker dans le moyen de mémorisation (3) les combinaisons des éléments dudit réseau ayant 10 engendré une perte de connexité entre les paires sélectionnées et afficher : ^ Le Seuil de percolation ^ Les Eléments générant la perte de connexité ^ La Fréquence des éléments générant la perte de connexité 15 4. déterminer les éléments du réseau qui ont le plus de chance d'engendrer une défaillance dans le fonctionnement dudit réseau, 5. modifier en conséquence l'architecture du réseau ou valider ladite architecture. 20 2 ù Procédé selon la revendication 1 caractérisé en ce que les fonctions utilisées dans les étapes sont : o DeterminerEnsembleATraiterSans() qui permet de sélectionner dans le graphe tous les éléments nécessaires au calcul. Ici les éléments de départ ainsi que les éléments en liaisons avec les éléments de départ 25 ne seront pas pris en compte, o CombinaisonPercolation( qui permet de générer des combinaisons d'éléments à partir des éléments fournis par la fonction DeterminerEnsembleATraiterSansO o La fonction CombinaisonPercolation() prend en entrée un nombre de 30 défaillances, ce nombre permet de définir le nombre d'éléments constituant une combinaison.o CalculPercolation() permet la recherche d'un chemin entre les paires sélectionnées par l'utilisateur, ladite fonction fait appel à la fonction DFS_IsRouteExiste(). o La fonction DFS_IsRouteExiste( parcourt le graphe en profondeur 5 pour vérifier l'existence d'un chemin entre 2 noeuds du graphe.