Une exploration de méthodes exactes pour une détection et un diagnostic efficaces des défaillances des réseaux

Abstract

Cet article est un résumé d’un article accepté à la conférence CPAIOR 2024. Dans les réseaux informatiques, une récupération rapide des défaillances nécessite une détection et un diagnostic rapides. À l’aide de protocoles tels que Bidirectional Forwarding Detection (BFD), il est possible de sonder l’état d’une route. Ces protocoles sont exécutés sur des nœuds spécifiques désignés comme des moniteurs réseaux. Les moniteurs sont responsables de vérifier constamment la viabilité des chemins de communication. Il est crucial de choisir soigneusement les moniteurs, car la surveillance entraîne des coûts, nécessitant un équilibre entre le nombre de moniteurs et la qualité de la surveillance. Dans ce contexte, nous explorons deux défis de surveillance issus du domaine de la tomographie booléenne des réseaux : la couverture, qui consiste à détecter les défaillances, et la 1-identifiabilité, qui nécessite également d’identifier le lien ou le nœud défaillant. Nous essayons trois approches exactes pour résoudre ce problème : un modèle de programmation linéaire en nombre entier (ILP), un modèle de programmation par contrainte (CP) et un modèle de satisfaisabilité maximale (MaxSAT). En utilisant 625 topologies de réseaux réels, nous illustrons que l’utilisation de ces méthodes exactes peut réduire le nombre de moniteurs nécessaires par rapport à l’algorithme glouton de l’état-de-l’art.

Cristel Pelsser

Critical embedded systems, Computer networking, Researcher, Professor

The focus of my research is on network operations, routing, Internet measurements, protocols and security.