Reroutage dans OSPF avec des chemins de secours

Le protocole de routage RIP (Routing Information Protocol) a été largement utilisé dans les réseaux IP. D'une part parce qu'il est le premier protocole de routage développé pour Internet et d'autre part parce qu'il très facile à mettre en oeuvre puisqu'il est basé sur l'algorithme de Bellman-Ford. Avec l'expansion de l'Internet, les limites du protocole RIP, telles que le diamètre du réseau qui ne doit pas dépasser 16 routeurs et le temps de convergence qui est relativement élevé, ont apparues. Le protocole OSPF (Open Shortest Path First) a été conçu plus tard au sein de l'IETF (Internet Engineering Task Force) pour substituer le protocole RIP. OSPF a permis de résoudre tous les problèmes constatés avec RIP et en particulier il a permis de réduire nettement le temps de convergence. Actuellement, ce temps de convergence est à l'ordre de la minute. Malheureusement, ce temps de convergence n'est pas tolérable pour certaines applications temps réel. Dans ce rapport, nous proposons un mécanisme complémentaire à OSPF qui permet de réduire encore plus le temps de convergence du protocole via le calcul préalable d'un chemin de secours disjoint du premier chemin utilisé pour chaque destination possible dans le réseau. L'algorithme TDSP " Two Disjoint Shortest Paths " que nous avons proposé pour calculer deux chemins disjoints en un seul passage a une complexité de O(n^2)