Algorithme de Dijkstra et Protocoles de Routage

Présentation Générale

• Le document présente un cours sur les réseaux informatiques (INF4032)
• Le conférencier est Bassem Haidar
• L'école est l'ESIea (École d'Ingénieurs du Monde Numérique)

Routage Statique

• Un routeur apprend les routes distantes de deux manières :
• Saisie manuelle (route statique) dans la table de routage
• Apprentissage dynamique via un protocole de routage.
• Les routes statiques ne s'adaptent pas automatiquement aux changements de topologie
• Il faut les reconfigurer manuellement.

Pourquoi Utiliser le Routage Statique ?

• Configuration simple pour les petites topologies
• Bonne sécurité (moins de données à configurer)
• Pas besoin de ressources supplémentaires.
• Route vers la destination toujours la même.

Quand Utiliser les Routes Statiques ?

• Réseaux stubs (réseaux qui ne communiquent qu'avec un seul voisin)
• Liaison vers d'autres réseaux externes, internet.
• Liaison vers un seul réseau.

Types de Routes Statiques

• Utiliser les routes statiques pour connecter à un réseau spécifique.
• Connecter des routeurs stubs.
• Résumer les entrées de la table de routage, ce qui réduit la taille des annonces de routage
• Créer une route de secours en cas de défaillance d'un lien principal.

Protocoles de Routage Dynamique

• Découverte des réseaux distants
• Actualisation des informations de routage
• Choix du meilleur chemin vers la destination
• Adaptabilité aux changements de topologie

Systèmes Autonomes (AS)

• Un ensemble de routeurs et réseaux gérés par la même organisation
• Echange de paquets avec le même protocole de routage.

Caractérisation d'un AS

• Identification par un numéro AS (numéro unique)
• Différents types d'organisations et leurs numéros AS
• Système autonome qui utilise des protocoles de routage spécifique.

Types de Protocoles de Routage

• Protocoles IGP (Interior Gateway Protocol) - routage intra-système autonome
• Protocoles EGP (Exterior Gateway Protocol) - routage inter-système autonome

Protocoles de Routage à Vecteur de Distance

• Le vecteur de distance identifie la distance vers un réseau cible, en se basant sur une métrique comme le nombre de sauts, le coût de la bande passante ou le délai.
• Le vecteur indique la direction à prendre pour atteindre le réseau cible.

Fonctionnement des Protocoles de Routage Dynamique à Vecteur de Distance

• Envoi et réception des messages de routage sur les interfaces
• Partage des informations de routage avec les autres routeurs qui utilisent le même protocole de routage.
• Échange des informations de routage pour découvrir les réseaux distants.
• Notification aux autres routeurs de toute modification de topologie.

Démarrage à Froid d'un Routeur

• Le routeur applique la configuration enregistrée
• Détecte les réseaux connectés directement
• Ajout des adresses IP de ces interfaces à la table de routage.

Découverte du Réseau

• Envoi de paquets de mise à jour contenant les informations de la table de routage à toutes les interfaces
• Réception des mises à jour de routage des routeurs connectés directement
• Ajout des informations reçues à la table de routage.

Échange des Informations de Routage

• Les protocoles de routage à vecteur de distance utilisent le découpage d'horizon pour éviter les boucles
• Les informations ne sont pas envoyées par l'interface par laquelle elles ont été reçues.

Exécution de la Convergence

• Le réseau a convergé lorsque tous les routeurs disposent d'informations complètes et précises sur l'ensemble du réseau
• Le temps de convergence dépend de la rapidité des échanges d'informations entre les routeurs.

Technologies Liées au Vecteur de Distance

• RIPv1, RIPv2, IGRP, EIGRP, OSPF, IS-IS et BGP sont des protocoles de routage à vecteur de distance.
• Ces protocoles partagent les mises à jour entre voisins.
• La connaissance de la topologie du réseau n'est pas requise pour ces protocoles.
• Certains protocoles envoient des mises à jour périodiquement.

Algorithme du Vecteur de Distance

• Mécanisme d'envoi et de réception des informations de routage
• Mécanisme de calcul des meilleurs chemins et d'installation de routes dans la table de routage
• Mécanisme de détection des modifications topologiques et de réaction à celles-ci

Protocole RIP

• Facile à configurer, et les mises à jour de routage sont régulières (toutes les 30 secondes).
• Utilise le nombre de sauts comme métrique.
• Limité à 15 sauts.
• Protocole RIPv2 supporte le VLSM et CIDR

Protocole EIGRP

• Mises à jour déclenchées limitées
• Mécanisme de conservation des messages Hello.
• Gestion d'une table topologique.
• Convergence rapide.
• Prise en charge de multiples protocoles de couche 3.

Routage Dynamique à État de Liens

• Les protocoles de routage à état de liens sont aussi appelés protocoles à plus court chemin (SPF)
• Ils utilisent l'algorithme de Dijkstra pour calculer les meilleurs chemins.
• Chaque routeur apprend la topologie complète du réseau.
• Mise à jour basée sur le changement de topologie du réseau

Algorithme de Dijkstra

• Initialisation
• Boucle de recherche du nœud avec le coût minimal.
• Mettre à jour les coûts des nœuds voisins
• Répéter jusqu'à ce que tous les nœuds soient dans N'

Exemple SPF

• Utilisation de la table pour trouver le chemin le plus court vers les réseaux de destination.
• Calcul du coût pour chaque chemin possible

Processus de Routage à État de Liens

• Chaque routeur reçoit des informations sur les réseaux auxquels il est directement connecté.
• Chaque routeur se présente à ses voisins
• Chaque routeur construit un paquet contenant l'état des liens connectés directement (LSP).
• Chaque routeur diffuse le LSP à tous ses voisins.
• Tous les routeurs utilisent la base de données pour construire la carte topologique et calculer le meilleur chemin vers chaque réseau de destination.

Mises à Jour d'État de Liens - Dites Hello

• La deuxième étape consiste à faire en sorte que chaque routeur utilise un protocole Hello pour détecter les voisins sur ses liaisons
• Lorsque deux routeurs découvrent qu'ils sont voisins, ils forment une contiguïté
• Si un routeur cesse de recevoir les paquets Hello d'un voisin, ce dernier est considéré comme injoignable

Création de l'arborescence SPF

• Chaque routeur utilise la base de données à états de liens et l'algorithme SPF pour construire l'arborescence SPF
• R1 identifie ses réseaux directement connectés et les coûts
• R1 ajoute les réseaux inconnus et les coûts associés
• L'algorithme calcule ensuite les meilleurs chemins pour atteindre chaque réseau
• Chaque routeur construit sa propre arborescence SPF indépendamment

Ajout des Routes OSPF dans la Table de Routage

• Grâce aux informations de plus court chemin, les meilleurs chemins sont ajoutés à la table de routage
• Les routes connectées directement et les routes statiques sont également incluses dans la table de routage.

Algorithme de Dijkstra (Exemple/Autres exemples)

Protocole BGP

• Protocole externe (EGP) utilisé pour la gestion des groupes de réseaux autonomes (AS)
• Utilise un seul point de référence pour gérer les réseaux d'un voisin.
• Prenant ses décisions de routage au niveau réseau.
• permet les échanges entre AS.
• Des attributs et la configuration stratégique contribuent à influencer le choix de la meilleure solution.

eBGP Session et iBGP Session

• eBGP : Sessions entre différents systèmes autonomes (AS)
• iBGP : Sessions entre les routeurs d'un même système autonome (AS)

BGP Update – Attributs

• AS-Path
• Next-Hop
• Local preference
• Multi-Exit Discriminator (MED)
• Community
• Origin
• Aggregator

AS Path

• Attribut assigné par le routeur envoyant le message BGP, ajoutant son propre numéro AS au message.
• Contient la liste des AS traversés par le message.
• Permet de détecter les boucles de routage (ignoré si le message contient son propre numéro AS).
• Permite l'application de stratégies de routage.

Illustration des Concepts

• Illustration schématique des concepts de routage entre différents opérateurs régionaux et nationaux, ainsi que des clients et des réseaux de la compagnie.

Avantages des Protocoles à État de Liens

• Chaque routeur crée sa propre carte topologique du réseau.
• Mise à jour immédiate via l'inondation des paquets LSP.
• Les LSP sont envoyé uniquement en cas de modifications.
• Conception hiérarchique pour mise en œuvre de multiples zones.

Inconvénients des Protocoles à État de Liens

• Besoins significatifs en mémoire et en traitement.
• Besoins importants de bande passante due à la diffusion des LSP.
• Utilisation de plusieurs zones pour réduire la taille des bases de données à états de liens.

Testez vos connaissances sur l'algorithme de Dijkstra et les protocoles de routage à vecteur de distance. Ce quiz couvre les concepts clés, les étapes de l'algorithme, ainsi que les protocoles utilisés en réseau. Préparez-vous à évaluer votre compréhension des réseaux informatiques.