Aller au contenu principal

14. Routing Table Calculation (Calcul de la table de routage)

Ce chapitre décrit le calcul de la table de routage en utilisant l'algorithme Dijkstra SPF.

14.1 Aperçu de l'algorithme Dijkstra​

Objectif​

  • Construire l'arbre du plus court chemin (SPF Tree)
  • Racine : routeur calculant
  • Poids des arêtes : coût des liens

Structures de données​

  • Liste candidats : nœuds à traiter
  • Arbre SPF : nœuds traités
  • Table routage : routes finales

14.2 Étapes de l'algorithme​

Phase 1 : Initialisation​

  • Ajouter nœud racine (soi-même) à arbre SPF
  • Distance = 0

Phase 2 : Construction arbre SPF​

TANT QUE liste candidats non vide:
    1. Sélectionner nœud V à distance minimale
    2. Ajouter V à arbre SPF
    3. Pour chaque voisin W de V:
       - Calculer distance
       - Mettre à jour liste candidats

Chemins équivalents (ECMP)​

  • Plusieurs chemins de même coût
  • Conserver tous les chemins équivalents

14.3 Phases de calcul des routes​

Routes intra-zone (Intra-Area)​

  • Générées depuis arbre SPF
  • Priorité la plus élevée

Routes inter-zones (Inter-Area)​

  • Calculées depuis LSA Type 3
  • Priorité moyenne

Routes externes (External)​

  • Calculées depuis LSA Type 5
  • Type 1 : Coût = interne + externe
  • Type 2 : Coût = externe seulement (défaut)

14.4 Priorité de sélection des routes​

  1. Routes intra-zone
  2. Routes inter-zones
  3. Routes externes Type 1
  4. Routes externes Type 2

Déclenchement du calcul​

Recalcul nécessaire quand​

  • Changement LSDB
  • Changement état interface
  • Changement état adjacence

Optimisations​

  • Calcul différé
  • SPF incrémental (iSPF)

Points techniques​

Complexité algorithmique​

  • Implémentation standard : O(N²)
  • Implémentation optimisée : O((E + N) log N)

Points d'implémentation​

  • File de priorité efficace
  • Recherche LSDB rapide
  • Traitement ECMP correct

Références (References)

Dernière mise à jour le