2. The Link-state Database: Organization and Calculations (Base de données à état de lien : Organisation et calculs)
Ce chapitre décrit la structure organisationnelle de la base de données à état de lien OSPF et comment utiliser cette base de données pour calculer la table de routage.
Aperçu du chapitre (Chapter Overview)
Ce chapitre couvre les sujets principaux suivants :
- Méthodes de représentation des routeurs et réseaux
- Construction de l'arbre de chemin le plus court
- Utilisation des informations de routage externe
- Implémentation du multichemin à coût égal
2.1 Representation of Routers and Networks (Représentation des routeurs et réseaux)
Concepts fondamentaux (Core Concepts)
Représentation par graphe (Graph Representation)
- Le système autonome est modélisé comme un graphe orienté (AS modeled as directed graph)
- Sommets (Vertices) : routeurs et réseaux
- Arêtes (Edges) : interfaces de routeur
- Coût (Cost) : poids de chaque arête
Représentation du routeur (Router Representation)
- ID de routeur : identifiant unique 32 bits
- Liste d'interfaces : interfaces connectées aux réseaux
- Relations de voisinage : connexions avec routeurs adjacents
- État des liens : informations d'état de chaque interface
Types de réseau (Network Types)
| Type de réseau | Anglais | Caractéristiques | Exemples |
|---|---|---|---|
| Point à point | Point-to-Point | Connecte deux routeurs | Ligne T1, PPP |
| Diffusion | Broadcast | Multi-accès, support de diffusion | Ethernet, Token Ring |
| NBMA | Non-Broadcast Multi-Access | Multi-accès, pas de diffusion | Frame Relay, X.25 |
| Point à multipoint | Point-to-MultiPoint | Traité comme ensemble de liens point à point | Frame Relay maillé partiel |
2.1.1 Representation of Non-broadcast Networks (Représentation des réseaux non-diffusion)
Caractéristiques des réseaux NBMA (NBMA Network Characteristics)
- Pas de support pour diffusion ou multicast de couche liaison
- Configuration manuelle des voisins requise
- Nécessite l'élection d'un routeur désigné (DR) et d'un routeur désigné de secours (BDR)
- Doit avoir une connectivité maillée complète ou utiliser le mode point à multipoint
Exigences de configuration (Configuration Requirements)
- Configuration de la liste de voisins
- Paramétrage de la priorité DR
- Intervalles Hello et Dead
- Intervalle de sondage (Poll Interval)
2.1.2 An Example Link-state Database (Exemple de base de données à état de lien)
Cette section illustre la structure et le contenu de la base de données à état de lien à travers un exemple concret.
Topologie réseau exemple (Example Network Topology)
- Plusieurs routeurs interconnectés
- Différents types de réseaux
- Division en zones
- Liens virtuels
Types de LSA (LSA Types)
| Type LSA | Nom | Description | Portée d'inondation |
|---|---|---|---|
| Type 1 | Router-LSA | État des liens du routeur | Dans la zone |
| Type 2 | Network-LSA | État des liens du réseau | Dans la zone |
| Type 3 | Summary-LSA (réseau) | Routes réseau inter-zones | Zone unique |
| Type 4 | Summary-LSA (ASBR) | Routes ASBR | Zone unique |
| Type 5 | AS-external-LSA | Routes externes | AS entier |
2.2 The Shortest-path Tree (Arbre de chemin le plus court)
Algorithme de Dijkstra (Dijkstra's Algorithm)
Étapes de l'algorithme (Algorithm Steps)
- Initialisation : se définir comme nœud racine
- Liste de candidats : maintenir une liste de sommets à traiter
- Sélectionner le sommet de coût minimal
- Mettre à jour les coûts des voisins
- Répéter jusqu'à ce que tous les sommets soient traités
Calcul du coût (Cost Calculation)
- Coût d'interface : basé sur la bande passante ou configuration manuelle
- Coût du chemin : somme de tous les coûts d'interface le long du chemin
- Formule de coût par défaut :
Coût = Bande passante de référence / Bande passante de l'interface
Construction de l'arbre (Tree Construction)
- Nœud racine : le routeur effectuant le calcul
- Nœuds internes : routeurs et réseaux dans l'AS
- Nœuds feuilles : routes externes (AS-external-LSA)
Termes clés (Key Terms)
| Terme | Anglais | Définition |
|---|---|---|
| Arbre SPF | SPF Tree | Arbre de chemin le plus court avec le routeur comme racine |
| Liste de candidats | Candidate List | Sommets en attente d'ajout à l'arbre |
| Nœud parent | Parent | Nœud prédécesseur dans l'arbre |
| Distance | Distance | Coût de la racine au nœud |
| Prochain saut | Next Hop | Premier routeur pour atteindre la destination |
2.3 Use of External Routing Information (Utilisation des informations de routage externe)
Types de routes externes (External Route Types)
Route externe Type 1 (Type 1 External)
- Coût = coût interne + coût externe
- Métrique comparable
- Applicable aux IGP au sein du même AS
Route externe Type 2 (Type 2 External)
- Coût = coût externe (coût interne uniquement pour départager)
- Métrique non comparable
- Applicable aux EGP de différents AS
- Type par défaut OSPF
ASBR (Autonomous System Boundary Router)
Rôle de l'ASBR (ASBR Role)
- Introduit des routes externes dans OSPF
- Génère des AS-external-LSA
- Peut être n'importe quel routeur OSPF
- Annoncé via Type 4 Summary-LSA
Redistribution de routes (Route Redistribution)
- Importer des routes d'autres protocoles
- Définir le type de route externe
- Configurer le tag de route (Route Tag)
- Définir l'adresse de transfert (Forwarding Address)
2.4 Equal-cost Multipath (Multichemin à coût égal)
Concept ECMP (ECMP Concept)
Principes de base (Basic Principles)
- Plusieurs chemins équivalents vers la même destination
- Coûts de chemin identiques
- Trafic réparti entre plusieurs chemins
- Amélioration de l'utilisation de la bande passante et de la redondance
Méthodes d'implémentation (Implementation Methods)
| Méthode | Description | Avantages | Inconvénients |
|---|---|---|---|
| Round-robin par paquet | Per-packet round-robin | Simple | Peut causer du désordre |
| Distribution par flux | Per-flow distribution | Maintient l'ordre | Nécessite identification de flux |
| Basé sur hash | Hash-based | Efficace, déterministe | Peut être déséquilibré |
Paramètres de configuration (Configuration Parameters)
- Nombre maximum de chemins : nombre maximal de chemins ECMP supportés par le système
- Algorithme d'équilibrage de charge : sélection de la méthode de distribution du trafic
- Seuil de coût : plage de différence de coût autorisée
Entrées de table de routage (Routing Table Entries)
Représentation multichemin (Multipath Representation)
- Préfixe de destination unique
- Interfaces de prochain saut multiples
- Coût de route identique
- Type de route identique
Résumé technique (Technical Summary)
Structures de données clés (Key Data Structures)
- Base de données à état de lien (LSDB) : stocke tous les LSA
- Arbre SPF : structure d'arbre de chemin le plus court
- Table de routage : table de transfert finale
- Table de voisins : informations sur les routeurs adjacents
Algorithmes importants (Important Algorithms)
- Dijkstra SPF : calcul du chemin le plus court
- Inondation LSA : distribution des informations d'état de lien
- Calcul de route : génération de table de routage à partir de l'arbre SPF
- Sélection ECMP : équilibrage de charge multichemin
Considérations de performance (Performance Considerations)
- Complexité du calcul SPF : O(N log N)
- Taille de la base de données : impact sur l'utilisation de la mémoire
- Temps de convergence : du changement de topologie à la mise à jour des routes
- Évolutivité : division en zones pour les grands réseaux
Références (References)
- Texte complet : RFC 2328 Section 2
- Algorithme de Dijkstra : E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs"
Note : Ce document est basé sur la spécification officielle RFC 2328. Pour les détails techniques complets, le pseudocode des algorithmes et le langage normatif, veuillez consulter le document original.