Une détection des pannes plus autonome

La détection de panne, une étape critique dans le mécanisme de conver-gence

Dans les réseaux IP, les routeurs utilisent des protocoles IGP afin de construire leurs tables de routage. Chaque routeur d’un IGP à une vue complète de la topologie. Ils peuvent ainsi connaître les plus courts chemins vers n’importe quelle destination. Des métriques de routage sont utilisées pour définir le point de chaque lien. Ces métriques jouent un rôle important dans le routage des flux. Le calcul de route est effectué en exécutant un algorithme de SPF 1 tel que l’algorithme de Dijkstra. Seul le prochain saut est ensuite utilisé pour la commutation des paquets. Pour des raisons de passage à l’échelle et de rapidité de convergence, un domaine autonome est divisé en aires de routage. Les aires de routage sont organisées en étoile autour d’une aire de routage principale nommée « aire 0 »ou backbone. Les autres aires de routage sont connectées à l’aire 0 et chaque route ayant une source et une destination dans deux aires différentes doit passer par l’aire 0. Des routeurs ont des interfaces dans plusieurs aires de routage, ce sont des routeurs de bordure d’aire (ABR 2 ), alors que les routeurs en bordure de système autonome sont appelés routeur de bordure de système autonome (ASBR 3 ). Le découpage du routage en aires multiples permet de ne nécessiter que la vue complète de la topologie de l’aire. Mais la pertinence des chemins dépend de la fiabilité du graphe, et donc de la performance du mécanisme en charge de collecter les informations sur la topologie. Un des aspects critiques est la détection des modifications dans la topologie, notamment dans le cas d’une panne. Chaque routeur observe l’état de ses routeurs adjacents et diffuse des messages d’état de liens dès qu’un changement est observé (par exemple une panne ou une réparation). Lors d’un changement de topologie, les routeurs recalculent les plus courts chemins afin de connaître les prochains sauts à utiliser pour emprunter le plus court chemin. Cela permet de modifier la table de commutation (FIB 4 ) en mettant à jour les interfaces qui sont utilisées pour le transfert des paquets.
Aussi bien OSPF qu’IS-IS utilisent le protocole Hello de détection de pannes paire-à-paire. Le protocole Hello est basé sur l’envoi périodique de messages Hello de chaque routeur à l’ensemble de ses voisins. Les différents paramètres impliqués dans la configuration du protocole Hello ont une incidence sur le temps de détection d’une panne ainsi que le rétablissement d’une vue cohérente de la topologie du réseau. Pendant cette période, entre la panne et le rétablissement d’une représentation du réseau conforme à la réalité, les paquets IP transférés vers le routeur en panne sont perdus. Il est donc important de réduire cette période afin minimiser la quantité de trafic perdue. De plus, des boucles de routage peuvent apparaître pendant cette période instable et engendrer de la congestion dans le réseau. La détection d’une panne et la mise à jour du routage prend des dizaines de secondes dans les réseaux d’opérateur. Il est utile de voir précisément quels processus et quels paramètres sont impliqués et quels sont leurs incidences sur le temps de rétablissement d’une panne. Le protocole OSPF est ici pris en exemple, mais le protocole IS-IS fonctionne de manière similaire.
Quatre étapes sont nécessaires pour la restauration du routage IP. En premier, la détection de la panne, puis viens ensuite la diffusion de cette panne à tous les routeurs de l’aire de routage par l’envoi de messages LSA 5 . Une fois le LSA reçu, chaque routeur calcule ses nouveaux plus courts chemins et met à jour ses tables de routage et de commutation en conséquence. Le délai total de convergence dépend du temps pour compléter chacune de ces étapes. Mais ces étapes ne sont pas équivalentes en termes de durée, la détection des pannes étant de loin l’étape la plus longue.
La détection de pannes s’appuie sur le protocole d’échange de messages Hello. Deux routeurs sont adjacents tant qu’ils peuvent échanger des messages Hello. Le voisinage n’est plus valide lorsqu’un routeur ne reçoit plus de message Hello. Dans certain cas, le protocole de niveau inférieur permet de détecter la panne de manière plus rapide. Mais ce mécanisme n’est pas toujours disponible et ne permet pas de détecter certaines pannes au sein du routeur telles que les pannes du contrôleur ou les pannes logicielles. Chaque routeur envoi des messages Hello avec une période définie par le paramètre Hello Interval. Ce paramètre a une valeur par défaut de 30 secondes mais peut descendre jusqu’à 1 seconde. Il est en général de l’ordre de la dizaine de seconde. Les voisins qui reçoivent ces messages Hello décident de supprimer un routeur de la topologie lorsqu’ils ne reçoivent pas de message Hello de sa part pendant un intervalle défini par le paramètre Router Dead Interval. Ce paramètre est communément configuré à 3 ou 4 fois la valeur du Hello Interval. Ceci permet de garantir une certaine fiabilité dans la détection de pannes en attendant la non réception de 3 ou 4 messages Hello avant de la déclarer.
Lorsqu’un changement de topologie est détecté, l’information est ensuite diffusée aux voisins par l’envoi de LSA. Chaque routeur maintient une vue complète de l’aire OSPF dans sa LSDB 1 contenant les LSA. Chaque LSA représente un lien du réseau. Les routeurs adjacents s’échangent des messages regroupant plusieurs LSA afin de synchroniser leur LSDB. Lors d’un changement de topologie, les routeurs affectés par la panne doivent générer des LSA qui sont diffusés à tous leurs voisins. À la réception d’un nouveau LSA, les routeurs mettent à jour cette base de données, mais doivent aussi rediffuser le LSA reçu aux autres voisins. La réception d’un nouveau LSA déclenche aussi le calcul des plus courts chemins (SPF), puis la mise à jour des FIB nécessaires au transfert des paquets. Comparé à la détection de panne, les autres étapes sont presque négligeables en terme de durée puisqu’elles sont inférieures une centaine de millisecondes, avec 0,03 secondes pour le temps de diffusion des LSA tF [SG01] et 0,2 secondes pour le délai de mise à jour des tables de routage et de forwarding tU [GRcF03].
Le temps de calcul des plus courts chemins dépend du nombre de nœuds du réseau qui, selon [GRcF03], est égale à tSP = 2, 47.10−6 ∗ |N |2 + 9, 78.10−3 (Cf Eq. (2.3)) où N est l’ensemble des routeurs du réseau. Bien que des délais aient été ajoutés pour limiter le nombre de calculs de SPF, des études montrent que ces délais peuvent être supprimés [AC02].
Le temps de détection tD est actuellement l’étape la plus pénalisante dans le processus de convergence des protocoles IGP. Elle peut être bien plus rapide en utilisant les protocoles de détection des couches inférieures mais de tels dispositifs ne sont pas tout le temps disponible et ne permettent pas de détecter des pannes au niveau logiciel du routeur ou du contrôleur. Le protocole Hello utilisé dans les protocoles IGP est contrôlé par deux paramètres. Le Hello
Figure 2.1: Message Hello.
Interval et le Router Dead Interval sont présents dans le message Hello représenté dans la Fig. 2.1. Le Hello Interval définit la période d’envoi des messages et le Router Dead Interval, l’intervalle nécessaire avant de décider de la suppression d’un routeur de la topologie suite à la non réception de messages Hello. La définition du protocole Hello, telle que présentée dans les Sec. 9.5 et 10.5 de la RFC2328 [Moy98] pour le protocole OSPF, précise que ces deux paramètres doivent être similaires sur toute l’aire de routage et ne peuvent pas changer dynamiquement. Toute nouvelle valeur différente est ignorée par le protocole Hello. De plus, il n’est pas possible de définir une valeur inférieure à la seconde pour le Router Dead Interval et pour le Hello Interval. Néanmoins, la configuration du Hello Interval en dessous de la seconde a été implémentée par certains industriels tels que Cisco au sein de leurs routeurs [Sys02]. Les paramètres que nous avons décris concernent le protocole OSPF mais le protocole IS-IS fonctionne de manière tout fait similaire. Bien que le Hello Interval puisse être de seulement une seconde, les opérateurs préfèrent utiliser des valeurs supérieures, entre 3 et 10 secondes [AC02]. En fait, l’utilisation d’une fréquence élevée pour l’envoi des messages Hello engendre de fausses détections de panne, ce qui créé des oscillations dans le routage [OBOM03, BR01, SVKD00].

Problématique

Le temps de convergence des réseaux IP a une incidence directe sur la disponibilité du trafic. La réduction de ce temps de convergence est un problème qui a largement été étudié par la communauté de recherche. L’étape du processus de restauration la plus pénalisante en termes de temps est la phase de détection. Il est possible de détecter de manière extrêmement rapide une panne, de manière matérielle par l’intermédiaire des protocoles inférieurs ; mais ces mécanismes ne sont pas toujours disponibles et ne permettent pas de détecter l’ensemble des pannes. Par exemple, si une panne implique le processeur de route centrale, mais que les cartes de lignes sont toujours fonctionnelles, la détection matériel est inefficace. C’est pourquoi la détection de pannes s’appuie sur le protocole de détection de pannes Hello dont les délais de détection sont de plusieurs secondes. Ce délai correspond à une grande partie de l’interruption de service imputé au processus de convergence, ce qui en fait la cible privilégiée pour l’amélioration du mécanisme de restauration IP. Il est possible d’améliorer la rapidité de détection de pannes en accélérant la fréquence d’envoi des messages Hello.
Malheureusement, la réduction du Hello Interval pose plusieurs problèmes. La nécessité d’en-voyer et de recevoir des messages Hello après quelques millisecondes créé une charge addition-nelle non anodine pour le contrôleur principal ou le processeur de contrôle. Le temps CPU dédié au traitement des messages Hello peut devenir important et venir perturber les autres tâches effectuées par l’unité de calcul.
En effet, la limitation des tâches effectuées par le protocole de routage reste toujours valide. OSPF, en tant que protocole distribué, nécessite l’exécution par les routeurs de certaines opé-rations dans un temps limité, telles que la génération et le traitement des messages Hello. Il est donc essentiel que les routeurs ne soient pas trop chargés, sinon ils pourraient ne pas être en mesure d’assurer correctement leurs fonctions, ce qui pourrait entraîner le dérèglement du routage au niveau global . Pour éviter ce cas de figure, un grand nombre de routeurs possèdent une architecture distribuée où un processeur central exécute le protocole de routage et où le transfert des paquets est assuré par les cartes de lignes. La charge de traitement dédié au pro-tocole OSPF dépend de la taille de l’aire de routage et du nombre de voisin du routeur. Bien que les processeurs des routeurs soient plus puissants que par le passé, la taille et la complexité des domaines de routage rendent la surcharge d’un routeur possible.
De plus, plus le Hello Interval est faible, plus la chance qu’une congestion du réseau amène la perte de plusieurs messages Hello consécutifs augmente. Une telle congestion peut se mani-fester dans des éléments de réseaux intermédiaires, tels que les switchs, mais aussi au sein des routeurs au niveau des files d’attente de la carte de lignes ou des files d’attentes de la carte de contrôle, par exemple à cause de la surcharge de travail apportée par le traitement d’un nombre massif de messages Hello. Le résultat d’une fausse détection entraîne le retrait erroné d’un voi-sinage alors que celui-ci est parfaitement fonctionnel. Le LSA généré par la fausse détection amène à de nouveau calcul de route afin de ne plus emprunter le lien faussement supprimé. La fausse alarme est ensuite rapidement corrigée par l’échange des messages Hello, ce qui déclenche le rétablissement du voisinage supprimé, la diffusion d’un nouveau LSA ainsi que le re-calcul des tables de routage. En résumé, les fausses détections causent des changements temporaires dans les chemins de routage [OBOM03, BR01, SVKD00] ainsi qu’une charge de calcul supplémentaire et inutile pour les routeurs. Les changements de route fréquents avec intervalle très faible ont un sérieux impact sur la QoS du trafic car les routes temporaires peuvent introduire de mauvais délais de transmission ainsi que des pertes dues à la congestion apportée par ces changements de route fréquents. L’instabilité créée par ces fausses détections étant trop pénalisantes, les opé-rateurs préfèrent utiliser une fréquence lente d’envoi des messages Hello au détriment d’une restauration rapide. Les valeurs les plus couramment utilisées sont de l’ordre de quelques se-condes [AC02] et peuvent même atteindre plusieurs dizaines de secondes dans le cas de réseaux particulièrement instables.

Amélioration du temps de détection des pannes dans les protocoles de routage à état de lien

L’amélioration du temps de convergence est un sujet largement étudié [RMD05, FFEB05]. Parmi les améliorations proposées, la détection de pannes, qui constitue actuellement le point faible de la restauration IP, a été l’objet d’une attention toute particulière. La solution proposée est la diminution du Hello Interval jusqu’à des valeurs inférieures à la seconde [GRcF03, AYJ00] afin d’accélérer la convergence des protocoles IGP d’un ordre de grandeur. Mais, comme souligné dans la section précédente, l’accélération de la fréquence d’envoi des messages Hello peut amener des instabilités de routage. Cette instabilité, étudiée par Basu et Riecke dans « Stability issues in OSPF Routing »[BR01] a le désavantage d’empirer la situation en terme de perte de paquets et peut entraîner une réaction en chaîne qui crée alors un envoi massif de LSA paralysant tout le réseau [Wor01, Pre98, Cho99, Rea01].
En considérant ce problème, des études ont cherché à déterminer quels étaient les réglages op-timaux dans le protocole Hello, pour le Hello Interval et le Router Dead Interval. Les simulations de Basu et Riecke montrent par exemple que la réduction du Hello Interval de 500 millisecondes 250 millisecondes ne provoque pas de surcharge significative du processeur mais génère six fois plus d’oscillations de routage à cause des fausses détections. Les travaux de Chouldhury et al. [CMS01] s’attachent à évaluer le problème d’envoi massif en chaîne de LSA (LSA storm). Lors d’une ou plusieurs pannes, la génération des LSA entraîne une utilisation intensive des processeurs routeurs et la diffusion en chaîne des LSA dans tout le réseau. Cette période d’ac-tivité intense peut engendrer des ralentissements dans le réseau qui, couplés avec une fréquence d’envoi des messages Hello élevée, peut entraîner de fausses détections de panne. Ces fausses détections de panne entrainant à leur tour l’envoi de nouveaux LSA, une réaction en chaîne peut se déclencher, déréglant le routage et entrainant des pertes importantes. Malgré le fait que des études aient essayé de définir une valeur optimale pour le Hello Interval, celle-ci dépend de nombreux facteurs. Entre autre, l’étude de Goyal et al. [GRcF03] montre que la fréquence des fausses détections de panne augmente avec le niveau de congestion du réseau et avec le nombre de liens dans le réseau. Dans « On parameter settings of network keep-alive protocol for failure detection »[Qua09], l’impact d’un faible Hello Interval sur le nombre de fausses prédictions est étudié, notamment dans le cas de congestion. L’utilisation d’une fréquence d’envoi élevée n’est recommandée que dans le seul cas où le réseau ne subit pas de ralentissement tel que la conges-tion. Dans le cas contraire, une fréquence d’envoi faible doit être utilisée, ou un dispositif de suppression des oscillations de routage doit être mis en place. Pour régler ce problème d’oscil-lation de routage, plusieurs solutions ont été proposées. La majorité de ces solutions prônent l’adaptation dynamique de la fréquence d’envoi à la congestion observée dans le réseau. Dans « Improving Network Convergence Time and Network Stability of an OSPF-Routed »[SN05], cinq niveaux de Hello Interval sont prédéfinis et associés à cinq niveaux de congestion. Ainsi, lors de la détection d’un certain niveau de congestion, la fréquence d’envoi des messages Hello est immédiatement ajustée suivant les valeurs prédéfinies afin d’éviter les fausses détections. Néanmoins, cette solution considère que la sensibilité d’envoi des messages Hello à la congestion est similaire sur chaque équipement, ce qui n’est pas le cas dans les réseaux actuels possédant des routeurs très hétérogènes, de vendeur, de qualité et d’ancienneté différente. L’article « A Route Flap Suppression Mechanism Based on Dynamic Timers in OSPF Network »[WCLL08] propose une autre stratégie basée sur l’évaluation de l’instabilité du réseau. Dans le cas d’un nombre trop important de fausses détections, la fréquence d’envoi des messages Hello est pro-gressivement abaissée sur le lien, ou le routeur concerné, jusqu’à ce que l’instabilité baisse. Cette stratégie permet de conserver une fréquence élevée lorsque c’est possible et d’utiliser une détec-tion moins rapide lorsque cela engendre des oscillations de routage. Le principal défaut est que le mécanisme attend d’observer des oscillations pour entreprendre des actions, ce qui limite le problème mais ne permet pas de l’éradiquer.
Malgré les efforts fournit par la communauté pour définir la fréquence optimale d’envoi des messages Hello, les opérateurs conservent des valeurs de l’ordre de la seconde [AC02]. En effet, ces études s’appuient en majorité sur des simulations ou quelques configurations de réseau spécifiques, peu représentatives de l’étendue des réseaux opérationnels. Dans la pratique, le Hello Interval n’est jamais sous la seconde, mais plutôt autour de trois secondes [AC02], allant même jusqu’à une dizaine de secondes, en fonction des caractéristiques de chaque réseau, telles que les performances des routeurs, leur ancienneté, la taille, la charge du réseau, etc.
Un protocole spécifique pour la détection de pannes a été défini par l’IETF afin de dépasser les limites du protocole Hello intégré aux protocoles IGP. Le protocole BFD 1 [KW10] permet une détection bien plus rapide en utilisant une fréquence d’envoi de messages Hello beaucoup plus rapide. Il peut être utilisé avec les protocoles IGP tel qu’OSPF et IS-IS mais est plus adapté la détection de pannes le long d’une connexion tel qu’un LSP 2 , ou à la détection d’une panne sur un lien bien spécifique, qu’à la détection de pannes sur la topologie de routage dans son ensemble. En effet, il a été créé pour être implémenté de manière matérielle au sein des cartes de lignes afin de décharger le contrôleur du traitement intensif des messages Hello que nécessite une fréquence élevée. Néanmoins, il ne permet pas de détecter les pannes qui surviennent au niveau du contrôleur et du logiciel de routage, ce qui limite son utilité. Ses caractéristiques sont néanmoins intéressantes car elles permettent de dépasser les limitations des protocoles Hello des protocoles IGP, en autorisant des valeurs inférieures à la seconde et l’utilisation de fréquences d’envoi spécifique à chaque routeur.

Description de la proposition

Le premier dispositif proposé dans cette thèse exploite l’information de risque de panne four-nit par un module RAM pour améliorer l’efficacité de la détection de pannes et par conséquent la rapidité de la restauration IP. Le mécanisme proposé concerne uniquement le protocole Hello, et plus particulièrement la période d’envoi de ces messages, définit par le Hello Interval. Une fréquence lente d’envoi des messages est nécessaire pour la stabilité, mais une détection rapide permet de réduire sensiblement l’interruption de trafic lors d’une panne. Nous pensons donc qu’il est obligatoire de conserver une fréquence lente mais que les indicateurs annonciateurs de panne peuvent être mis à contribution par les équipements réseaux afin d’accélérer de manière auto-nome cette fréquence lorsqu’un équipement à des fortes chances de tomber en panne [VGD11]. Nous proposons de conserver un Hello Interval semblable à ce qui est utilisé aujourd’hui (supé-rieur à la seconde) la majorité du temps afin d’assurer un routage stable et lors d’une prédiction de panne, d’accélérer temporairement la fréquence d’envoi des messages Hello sur le lien risqué, ou en provenance d’un routeur ou d’une carte de lignes risqués. Cela permet d’être beaucoup plus réactif si une panne a donnée des signes avant-coureurs tout en gardant un réseau stable.

Aperçu général du principe de détection de pannes adaptatif

Dans le contexte des réseaux autonomes, la fonction d’autoréparation AFDT utilise une information de risque de panne afin d’améliorer le temps de détection des pannes. Elle a pour mission d’adapter la réactivité de la détection de pannes au risque de pannes observé afin d’amé-liorer sensiblement le temps de convergence du protocole IGP tout en maintenant une stabilité acceptable [VGD11].
Comme nous l’avons souligné, le temps de convergence des IGP est fortement couplé au temps de détection d’une panne. Le temps de détection d’une panne peut être extrêmement rapide avec l’utilisation d’une fréquence élevée d’envoi des messages Hello équivalente à un Hello Interval inférieur à la seconde. Mais la contrepartie est une surcharge inutile des liens et des routeurs, de nombreuse fausses détections de panne ce qui oblige les opérateurs à garder un Hello Interval supérieur à la seconde.
L’idée que nous proposons est d’adapter dynamiquement la valeur du Hello Interval lors-qu’une prédiction de panne est levée [VGD11]. Grâce à la prédiction de pannes effectuée au sein des RAM, un module de gestion de la fréquence des messages Hello localisé au sein du RM_DE a pour mission d’accélérer l’envoi des messages Hello par un routeur dont l’un des composants (contrôleur, carte de ligne, lien, etc.) va tomber en panne de manière imminente. De façon sy-métrique, ce module AFDT (Cf Fig. 2.2) est en charge de rétablir une valeur moins agressive de Hello Interval que l’on considère comme extrêmement stable lorsqu’aucun risque important de panne n’est détecté.