Le routage dynamique

Sommaire :

 Principes et avantages du routage dynamique
Evolution des algorithmes de routage dynamique
Introduction au routage dynamique dans IP
Les protocoles de routage interne
Les protocoles de routage externe

 

Principes et avantages du routage dynamique

Pour rappel, la fonction de routage doit garantir qu'un noeud I interconnectant deux ou plusieurs sous-réseaux soit capable, à la réception, sur un des un de ces sous-réseaux, d'un paquet à destination de d, de réexpédier ce paquet, via un autre sous-réseau, vers un nœud J appartenant à une route d'accès vers d (opération de relayage ou commutation).

En garantissant cette fonctionnalité, tous les noeuds I d'un réseau global R permettent l'acheminement d'un paquet émis par une source quelconque s de R vers une destination quelconque d de R. Ceci contribue à la réalisation du service de la couche Réseau. 

Pour être capable de prendre une telle décision de relayage, un nœud dispose en permanence de l'information lui permettant de décider vers quel prochain nœud il convient de réexpédier un paquet à destination de d. Cette information prend la forme d'une table de routage dont chaque entrée exprime une association entre une destination d et le prochain nœud situé sur une route conduisant à d.

La façon dont est obtenue cette information de routage est directement liée à la politique de routage. Il existe 2 grandes classes de politiques de routage :

Ø  le routage non adaptatif ou STATIQUE
Ø  le routage adaptatif ou DYNAMIQUE 

ROUTAGE STATIQUE :

Dans ce cas, le choix de la route à emprunter pour aller du noeud I au noeud J ( " I et J) est calculé par avance. L’information correspondante est mise en place, sous la forme de tables, sur tous les routeurs et exploitable dès leur initialisation.

Les décisions de routage s'effectuent alors sans aucune considération de la variation de l'état courant du réseau : l’évolution de paramètres comme, par exemple, la topologie du réseau ou encore les taux de charge de trafic des liaisons, n’est pas considérée.

ROUTAGE ADAPTATIF ou DYNAMIQUE :

L’objectif d’une telle politique de routage est de favoriser des prises de décision de routage dynamiques. Elles vont évoluer au cours du temps afin de mieux prendre en compte les variations des paramètres (topologie, trafic…) et rendre adaptée à ces nouvelles situations les résultats de la fonction de routage.

Ainsi, le calcul périodique et automatique des tables de routage s'effectue à travers l'utilisation d'un algorithme de routage (très souvent issu de la théorie des graphes). Dans un contexte opérationnel, on entrevoit aisément l’allègement des tâches de configuration apporté par la mise en place de ces solutions : les équipements de routage devenant assez autonomes pour réagir, de façon pertinente, aux modifications des paramètres du réseau.

La pertinence pouvant aller jusqu’au calcul de « meilleur(s) chemin(s) » reflétant une optimisation du routage en fonction d’un (ou plusieurs) critère(s) d’évaluation spécifié(s).

L'implémentation d'un algorithme de routage peut parfois conduire à la définition d'un protocole de routage qui spécifie le format des informations de routage échangées entre les nœuds. Ainsi, en contre-partie de l’automatisation, il peut être parfois complexe de déployer et configurer de tels protocoles.

La suite de cette séquence dresse un panorama de l’évolution de ces algorithmes de routage dynamique, en détaillant les algorithmes distribués puisqu’ils constituent la base théorique des protocoles de routage dynamique présents dans l’environnement TCP/IP.

 

 

Evolution des algorithmes de routage dynamique

 

A/ Les différentes classes d’algorithmes

 Selon la provenance des informations utilisées pour calculer et modifier la valeur des tables de routage, quatre classes peuvent être définies :

Ø    algorithmes globaux , utilisent les informations collectées dans l'ensemble du sous-réseau : on parle    de routage centralisé.
Ø    algorithmes locaux exploitent uniquement l'information propre à un noeud : on parle de routage isolé.
Ø    algorithmes hybrides , reposent sur des solutions qui exploitent à la fois des informations locales et globales. 
Ø    algorithmes distribués , recalculent les solutions à partir des informations communiquées par leurs voisins (nœuds adjacents).

Comme déjà précisé, la plupart de ces algorithmes s’appuient sur ceux issus de la théorie des graphes. Citons les algorithmes de recherche de plus court chemin dans un graphe (Dijkstra, Bellman, Ford….).

Réseau

Graphe

Routeur – Nœud

Sommet

Liaison de communication

Arc

Coût d'une liaison

Longueur arc

Table de correspondance des notions "Réseau" et "Théorie des graphes"

Les critères de détermination du coût d’une liaison peuvent être quelconques. A titre d’exemples :

Ø       Nombre de sauts à effectuer
Ø        Temps moyen d'attente et de transmission pour un paquet test
Ø        Longueur des files d'attente
Ø        Coûts d'exploitation
Ø        Distance géographique
Ø        ...

Une combinaison multicritères est aussi envisageable.

Il peut être également envisagé de mettre en œuvre un routage multiple. Cette approche consiste à disposer de plus d’une alternative de routage pour une destination donnée (routage multi chemin) :

Ø chemins « presque équivalents » en terme de longueur
Ø chemins débutant de chacun des voisins
Ø chemins disjoints (Algo de Even)
Ø chemins de coût inférieur à une valeur seuil
Ø ...

  Adapté aussi bien au cas des datagrammes que des circuits, le routage multiple peut offrir les avantages suivants :

 

B/ Les algorithmes globaux ou routage centralisé

L’objectif d’un routage dynamique centralisé est de tendre vers une connaissance parfaite et globale de l'état du réseau pour prendre les décisions de routage optimales.

Le principe est basé sur l’existence dans le réseau d’un Centre de Contrôle de Routage (RCC – Routing Control Center). L’établissement des tables de routage s’opère en trois étapes .

Quels sont les avantages d’une telle approche ?

Quels en sont les inconvénients ?

 

C/ Les algorithmes hybrides

L’objectif est de partager la responsabilité du routage entre un RCC et chaque nœud. Le routage DELTA suit l’algorithme suivant :

Outre les bénéfices d’un routage multiple, on retrouve la plupart des inconvénients de la solution centralisée à cause de la présence d’un RCC.

 

D/ Les algorithmes locaux ou routage isolé

Le principe général de ces approches est d’établir un routage dynamique en utilisant uniquement la connaissance « locale ».

Il se retrouve illustré dans plusieurs algorithmes :

Principe :  
Chaque paquet entrant est réexpédié sur toutes les lignes de sortie exceptée la ligne d’arrivée.

Inconvénient :
Duplication des paquets

Palliatifs : 
Essayer de mettre en place un contrôle de congestion :

   v par utilisation de compteurs de sauts :

- l'émetteur :initialise ce compteur dans le paquet

- le noeud de commutation : décrémente la valeur du compteur de chaque paquet reçu ; élimine le paquet lorsque le compteur devient nul.

   v par utilisation d'estampilles dans les paquets

- l'émetteur : attribue un numéro de série au paquet

- le noeud de commutation : conserve les derniers numéros de série des paquets reçus en provenance de chaque émetteur ; élimine le paquet lorsque le numéro de série dont il est porteur est inférieur à ces valeurs.

Variantes de réexpédition des paquets :

v inondation sélective
v inondation optimale
v inondation aléatoire ...

Principe :
Chaque paquet entrant est réexpédié sur la ligne ayant la file d'attente la plus courte ( quelle que soit sa destination). L’objectif est donc de se débarrasser au plus vite d’un paquet (analogie avec « patate chaude »).

Illustration

Inconvénient :
 Pas obligatoirement optimal

Palliatif :
Combinaison avec un algorithme statique pour le choix de la ligne

 

Principe :
Chaque paquet entrant contient l'identificateur de la source et un compteur de sauts.

Un noeud de commutation maintient des tables de routage dont chaque entrée contient un triplet :

v un identificateur d'une source
v un nombre de sauts
v une ligne de provenance

 Le noeud de commutation modifie sa table de routage dans les 2 cas suivants :

v CAS 1 :  

SI  l'identificateur de la source du paquet entrant n'est pas encore présent dans sa table de routage
ALORS  Ajout du triplet correspondant

Illustration cas 1 :    

v CAS 2 :  

SI  l'identificateur de la source du paquet entrant est déjà présent dans sa table de routage
ET  la valeur du compteur de sauts du paquet est strictement inférieure à celle du nombre de sauts mémorisée dans la table de routage
ALORS  Mise à jour du triplet correspondant

 Illustration cas 2 :  

Dans tous les cas, le noeud de commutation incrémente le compteur de sauts du paquet avant de l’expédier.

Illustration 

Avantage :
En exploitant au niveau local l’information qui transite, l’algorithme converge progressivement vers une solution optimale.

Inconvénient :
Nécessité de disposer dans le format de l’en tête de chaque paquet d’un champ compteur de sauts et obligation de le modifier à chaque passage sur un nœud.

 

E/ Les algorithmes distribués

Chaque nœud va constituer dynamiquement ses tables de routage à partir d’informations provenant de ses voisins directs. Ainsi, chacun va adopter le même comportement cyclique qu’on peut résumer de façon générale comme suit :

1 - Constituer une information de routage initiale
2 - Communiquer régulièrement l’information de routage aux noeuds voisins
3 - Récupérer régulièrement les informations de routage en provenance des noeuds voisins
4 - Mettre à jour l’information de routage en tenant compte des informations provenant des voisins.

Il existe deux classes d’algorithmes de routage distribué :

Principe :

Chaque noeud conserve la valeur de la distance entre lui-même et chaque destination possible : c’est le vecteur distance.
Ce vecteur distance est calculé à partir des vecteurs distance des noeuds voisins.
Cette technique est directement issue des algorithmes de Bellman et de Ford (version distribuée de Bellman).

Vecteur distance et Table de routage :

Chaque entrée de la table de routage d’un noeud est un triplet dont les deux premiers termes appartiennent au vecteur distance de ce noeud :

Algorithme :

Initialement :

De façon courante :

- en y rajoutant une destination nouvellement apparue
- en minimisant la distance d’une destination déjà connue

 Quand communiquer les vecteurs aux voisins ?  

1.      initialement
2.     en cas de modification du vecteur distance
3.     lors de la découverte de l’interruption d’une liaison
4.     périodiquement

 Illustration :

La notation utilisée dans les schémas ci-après illustrant différentes étapes dans la convergence d’un algorithme par vecteur distance peut être formalisée comme suit :

 Un triplet (S-cible, coût, S-Suivant) associé à un nœud, exprime le fait qu’il existe pour atteindre le nœud de nom S-cible à une distance de coût qui passe par le nœud voisin S-Suivant.

illustration

 

Principe :

- Chaque noeud construit et maintient une copie complète de la carte du réseau et calcule localement les meilleurs chemins par l’algorithme de Dijsktra.
- Les modifications de topologie sont communiquées aux autres noeuds par un algorithme d’inondation sélective.

 Algorithme :

- Chaque routeur entre en contact avec ses voisins et apprend leurs noms.
- Chaque routeur construit un paquet connu sous le nom de « paquet d’état de liaison » ou LSP (Link State Packet) contenant une liste de noms des voisins repérés et des coûts des liaisons respectives.
- Le LSP est transmis d’une manière ou d’une autre à tous les autres routeurs, et chaque routeur enregistre le LSP généré le plus récemment par chaque autre routeur.
- Chaque routeur qui possède désormais une connaissance complète de la topologie du réseau et des coûts (convoyée par les LSPs), calcule les routes les plus courtes vers chaque destination par Dijkstra.

Quand communiquer les LSPs aux voisins ?

1.      initialement
2.     en cas de changement du coût d’une liaison
3.     lors de la découverte d’un nouveau voisin
4.     lors de l’interruption d’une liaison
5.     périodiquement

Comment sont transmis les LSPs entre les routeurs ?

Idée 1 : utiliser l'information de routage
 pb de récursivité (on utilise l’information de routage pour acheminer de l’information de routage)

Idée 2 : utiliser un algorithme d'inondation
 pb des doublons (duplication des LSPs)

Idée 3 : utiliser des estampilles
 pb de synchronisation des horloges des routeurs

Idée 4 : utiliser une combinaison  #séquence - âge
pour mettre en place une inondation sélective.

 Comment sont constitués les LSPs  ?

source

 numéro de séquence

 âge

liste des voisins

 Illustration : L'animation ci-après illustre les différentes étapes dans la convergence d’un algorithme par état de liaison.

1) Dans la premiere étape, des listes de doublets (S-voisin, coût) sont associés à chacun des nœuds. Chaque doublet représente un LSP et exprime le fait qu’il existe une liaison entre ce nœud et le nœud S-voisin ayant une distance de coût.

2) Les LSPs initiaux ont été diffusés sur l’ensemble du réseau. Ainsi chaque nœud dispose de la même connaissance à l’issue de cette diffusion.  On s’aperçoit que la récolte des LSPs a conduit à l’obtention d’une description totale d’un graphe valué correspondant au réseau.  

3) A partir de cette connaissance, chaque nœud va localement exécuter l’algorithme de DIJKSTRA pour calculer les meilleurs chemins et élaborer à partir de ces résultats les tables de routage. Ces dernières sont représentées par une liste de triplet (S-Dest, S-Suivant, Coût).

De la même façon que dans le scénario d’illustration de l’algorithme « vecteur distance », faisons l’hypothèse que la liaison AC tombe.  Une fois que les nœuds A et C ont chacun constaté le silence entre eux (absence de LSPs échangés depuis un certain temps), ils vont constituer de nouveaux LSPs retranscrivant cette situation et les diffuser au travers du réseau.

5) A l’issue de la diffusion sur le réseau, chaque nœud ayant constaté une modification de la topologie va appliquer l’algorithme de DIJKSTRA pour obtenir les nouvelles tables de routage. 

illustration

 

      VECTEUR DISTANCE versus ETAT de LIAISON :

Critère

Vecteur Distance

Etat de liaison

Rapidité de convergence

 lent

plus rapide

Occupation mémoire

 

parfois meilleur

Largeur de Bande

modeste

modeste

Calcul

modeste

modeste

Fonctionnalité

 

supérieure

Routage Multiple

possible

possible

      

PROTOCOLES de routage DISTRIBUES : normes et standards :

Introduction au Routage Dynamique dans IP 

 

L’Internet a introduit la notion de « système autonome » (AS – Autonomous System) pour faciliter la gestion du routage.
Un système autonome est un domaine de routage (réseaux et routeurs) sous une responsabilité administrative unique. Celle-ci est chargée de l’administration des plans d’adressage et de routage, de la sécurité, de la facturation…
Tout AS est officiellement identifié par un numéro sur 2 octets. C’est un organisme certifié (RIPE NCC (Europe), ARIN, APNIC, IANA) qui attribue ce numéro à l’organisation. Tout comme pour les adresses IP, des numéros sont réservés pour des usages privés.

Ainsi, l’Internet peut être vu comme un ensemble d’AS interconnectés. On peut alors distinguer deux catégories d’AS :

Découlant de cette décomposition, deux classes de protocoles de routage peuvent être définies :

 


Les Protocoles de Routage Interne 

 

A/ Le protocole RIP

RIP : Routing Information Protocol(RFC 1058 - 2453)

 

0

4

8

10

 

16

  

 

24             

 31

 Commande

 Version

 Zéro

 ID de famille d’adresse

 Zéro

 Adresse IP destination #1

 Zéro

Zéro

 Métrique vers destination IP #1

 Adresse IP destination #2

 Zéro

 Zéro

 Métrique vers destination IP #2

 … jusqu’à 25 destinations peuvent être mentionnées (taille max = 512 octets)

+ Champ COMMANDE : (8 bits)

+ Indique s’il s’agit : d’une requête (= 1)
(i.e. lors du démarrage, demande d’envoi d’informations de routage sans attendre la prochaine diffusion)
ou d’une réponse (= 2)
(cas de réponse à une requête, cas d’envoi périodique ou polling, ou cas d’envoi d’une mise à jour suite à une reconfiguration).

+ Champ NUMÉRO de VERSION :  (8 bits)

+  Numéro de version du protocole RIP.

+ Champ IDENTIFIANT de FAMILLE d’ADRESSE :  (16 bits)

 + Indique la nature de l’adressage réseau sur lequel porte le routage (= 2 pour IPv4.)

+  Champ ADRESSE DESTINATION #i :  (32 bits)

 + Adresse IP de destination (0.0.0.0 pour le routage par défaut).

+ Champ METRIQUE vers DESTINATION #i :  (32 bits)

+  Distance vers la destination #i en nombre de sauts (de 1 à 16). La valeur 16 indique une destination inaccessible.

Remarque : la valeur 0 n’est pas utilisée.

 

 

0

4

8

10

   

16

   

   

24

31

Commande

 Version

 Zéro

 ID de famille d’adresse

 ou  0xFFFF

 Marquage de Route

 ou   Mode d’authentification

 Adresse IP destination #1

Masque de sous-réseau

Prochain saut

 Métrique vers destination IP #1

 …

 ou

Mot de Passe (16 octets)

+ Champ IDENTIFIANT de FAMILLE d’ADRESSE :  (16 bits)

+  S’il vaut 0xFFFF, indique un message d’authentification.

+  Champ MARQUAGE ROUTE / MODE AUTHENTIFICATION:  (8 bits)

+  Indique s’il s’agit d’une route interne ou externe (compatibilité avec EGPs) dans le cas d’échange de route, le mode d’authentification dans le cas d’un message ayant le champ identifiant de famille à la valeur 0xFFFF (= 2 pour authentification par mot de passe, = 1/3 pour MD5 ).

+ Champ MASQUE de SOUS-RESEAU : (32 bits)

+  Masque de sous-réseau à appliquer à l’adresse IP de destination

+  Champ PROCHAIN SAUT : (32 bits)

+  Adresse IP du prochain saut auquel les paquets à destination de celle mentionnée doivent être expédiés.

+   Champ MOT de PASSE : (128 bits)

+  Mot de passe dans le cas d’une authentification.

Remarque  : authentification possible avec MD5 (calcul d’un sceau transmis avec les paramètres)

intégrité, non répudiation

 

 

B/ Le protocole OSPF

 OSPF : Open Shortest Path First(RFC 1247-1583-2178)

 

 

 

 

 0

      4

  

8

10

 

16

 

 

24

 31

Version

 Type

 Longueur Totale

 Identité du routeur source

 Identificateur de Zone

 Checksum

 Type authentification

 Authentification (8 octets)

+ Champ NUMÉRO de VERSION : (8 bits)

+  Numéro de version du protocole OSPF (2 actuellement)

+ Champ TYPE de MESSAGE : (8 bits)

+   Indique le type du message qui déterminera la structure des données émises après l’en-tête. Les différentes valeurs sont :

1 : message HELLO
2 : description d’une base de données
3 : demande d’un état des liaisons
4 : mise à jour de l’état des liaisons
5 : acquittement reconnaissant un état de liaison

+ Champ LONGUEUR TOTALE du paquet OSPF:  (16 bits)

+ Champ IDENTITE du ROUTEUR SOURCE :  (32 bits)

+  Identité du routeur émetteur fixée par l’administrateur (par convention l’adresse IP le plus basse).

+ IDENTIFICATEUR d’AIRE : (32 bits)

+  Identifiant de la zone sur laquelle le paquet est actif

+ Champ CHECKSUM sur l’en-tête: (16 bits)

+ Champ TYPE AUTHENTIFICATION : (16 bits)

+  Algorithme d’authentification utilisé
(0 - - >aucun, 1 - - > par mot de passe en clair, 2 - - > par MD-5).

+ Champ Données d’AUTHENTIFICATION : (64 bits).

 

- Routes dans le réseau
- Tables de routage vers les autres réseaux du domaine
- Table de routage vers les autres AS
- Adresses des routeurs dans le cas d’un réseau NBMA

 

plusieurs sous-protocoles s’exécutant « simultanément »

plusieurs formats de données 

 

- Surveillance de la topologie
 - Election du routeur désigné

 + Objectif  : apprendre dynamiquement les modifications de la topologie (pannes).

 + Principe  : Diffusion périodique de messages HELLO pour  :

+   Se signaler comme toujours actif
+   Vérifier la connectivité bi-directionnelle
+   Au démarrage, dans un réseau à diffusion, détecter les routeurs voisins, le routeur désigné… la mise à jour des BDR peut alors s’effectuer.

 +  Objectif  : réduire le nombre d’échanges de messages de mises à jour des bases de données de routage (BDR).

 +  Principe  : Election d’un routeur avec lequel dialoguent les autres pour la maintenance des BDR.

passer de n*(n-1)/2 à n-1 échanges

 +  Algorithme d’élection  : proche de celui de IEEE 802.5 pour l’élection du moniteur (priorité la plus forte, si égalité, celui ayant la valeur identificateur la plus grande est élu)

 

0

 

 4

  

8

10

 

16

 

 

24

 31

 En-Tête OSPF / TYPE = 1

 Netmask du routeur source

 Intervalle d’émission

 Options

 Priorité

 Intervalle de mort du routeur

 Routeur désigné

 Routeur désigné de secours

 Routeur voisin #1

 Routeur voisin #2

 …

 Routeur voisin #n

                   

+  Champ NETMASK : (32 bits)

+  Masque de sous-réseau du routeur émetteur

+  Champ INTERVALLE d’EMISSION : (16 bits)

+  Durée en secondes entre deux émissions de HELLO

+  Champ OPTIONS : (8 bits)

+  Caractérisation des capacités du routeur émetteur

 

DC

EA

N/P

 MC

 E

 T

Quand le bit est positionné à 1 :

DC : apte à gérer des circuits à la demande (X.25, RNIS…).
MC : apte à traiter de l’IP multicast.
E  : apte à gérer des routes apprises par un protocole de routage externe.
T  : apte à gérer le TOS (plus utilisé : 0 actuellement).

+  Champ PRIORITE : (8 bits)

+  Utilisé pour la phase d’élection du routeur désigné (Si 0, le routeur émetteur ne participe pas à l’élection (ex : au démarrage)).

+  Champ INTERVALLE de MORT : (32 bits)

+  Durée en secondes au bout de laquelle un routeur est considéré comme mort par l’émetteur (dans le cas de non réception de message HELLO de sa part).

+  Champs ROUTEUR DESIGNE et de SECOURS :  (2x32 bits)

+  Adresses IP du routeur désigné et de secours si élus et connus, 0.0.0.0. si non encore connus.

+  Champs ROUTEUR VOISIN #i : (nx32 bits)

+  Adresses IP des routeurs voisins que l’émetteur a reconnu par écoute du trafic HELLO
Tout routeur qui n’a pas émis pendant la période de mort est sorti de cette liste.

Remarque  : Tout routeur qui reçoit un message HELLO et se trouve dans la liste des voisins est certain d’une connectivité bidirectionnelle avec le routeur émetteur.

 

échanger des messages de description de BDR en mode « maître/esclave »

Le maître est celui qui a le plus grand identifiant. Il commence par émettre ses paquets D-D. Ceux-ci sont acquittés par l’émission des paquets D-D de l’esclave.

+  Champ MTU : (16 bits)

+  MTU de l’interface d’émission

+  Champ OTPIONS : (8 bits)

+  Idem paquet HELLO

+  Champ FLAGS : (8 bits)

 +  Gestion d’un dialogue :

I

M

MS

+ Quand le bit est positionné à 1 :

I : premier paquet de la description (Initial)
M : d’autres paquets suivent (More)
MS : le routeur émetteur est le maître, le récepteur l’esclave.

+  Champ NUMERO de SEQUENCE : (32 bits)

+  Numérotation unique, incrémentée par le maître

 

+  Champ AGE du LS : (16 bits)

+  Age de l’information annoncée (synchronisation sur la pérennité des informations)

+  Champ OPTIONS : (8 bits)

+  Idem paquet HELLO

+  Champ TYPE du LS : (8 bits)

+  Donne la nature de l’information :

1. liaison du routeur
2.  liaison dans le réseau (réseau NBMA)
3. liste des adresses des réseaux accessibles
4.  résumé des adresses des routeurs externes
5. réseaux externes accessibles appris par un EGP
6. routage multicast (RFC 1584)
7. réseaux externes particuliers et accessibles (RFC 1587)

+  Champ IDENTIFICATEUR de LS : (32 bits)

+  Diffère selon la valeur du champ type LS. Si type vaut :
1.  Identifiant du routeur producteur du messager
2.  Adresse IP du routeur désigné
3. Adresse du réseau accessible
4.  Identifiant du routeur frontière
5. Adresse du réseau externe

+  Champ ROUTEUR ANNONCANT : (32 bits)

+  Identifiant du routeur émetteur de l’annonce D-D

+  Champ NUMERO de SEQUENCE du LS : (16 bits)

+  Estampillage du LS (éliminer les duplicatas lors d’une inondation, opérer ou non une mise à jour dans la BDR)

+  Champ CHECKSUM : (16 bits)

+  Checksum sur l’en-tête d’annonce.

+   Champ LONGUEUR : (16 bits)

+  Longueur des données qui suivent

+  Champ DONNEES :

+  Information dont le format dépend du type d’EL…

 

 

C/ Apercu du protocole EIGRP (Cisco)

EIGRP : Enhanced Interior Gateway Routing Protocol (CISCO)

- Bande passante (par défaut) (fonction du type de l’interface)
- Délai
- Fiabilité (par calcul dynamique)
- Charge (calcul moyenne pondérée continue)

- Un routeur mémorise les Tables de Routage de ses voisins
  un nouvel itinéraire pour une destination donnée peut être ainsi instantanément retenu
- Si pour une destination, un routeur ne dispose pas d’un tel itinéraire, envoi d’une requête aux voisins qui se propage jusqu’à l’obtention d’un itinéraire
- En cas de changement d’une TR, seules les modifications sont envoyées et uniquement aux routeurs concernés
- Gestion des meilleures métriques

 

Les Protocoles de Routage Externe

 

A/ Routage interne versus routage externe

L’objectif du routage au sein d’un AS est surtout d’éviter la perte de connectivité : l’essentiel est d’obtenir une route possible. La constitution de cette route est relativement peu importante dans la mesure où, qu’elle quelle soit, elle implique toujours les équipements d’un même système autonome.

Celle-ci devient par contre primordiale dans une perspective de routage entre AS. Il s’agit là davantage d’un « routage politique ». En effet, le fait d’annoncer une route implique que l’AS accepte de véhiculer des informations vers cette destination et est capable de joindre cette destination annoncée.

Ces annonces peuvent être supportées par un EGP. Toutefois, il est toujours possible dans le cas du routage entre AS de mettre en place un routage statique. Voici quelques détails sur le dernier standard des EGPs : le protocole BGP.

 

B/ Apercu du protocole BGP

BGP : Border Gateway Protocol  V4 (RFC 1771)

-  193.55.64.0
 - 193.55.65.0
 - 193.55.66.0
 - 193.55.67.0
 - 193.55.64/22 résume ces quatre accessibilités

(Type de message BGP : 1)  

(Type de message BGP : 2)  

(Type de message BGP : 3)  

(Type de message BGP : 4)  

 

Dans la pratique il est courant que plusieurs routeurs « frontière » d’un même AS (celui d’un ISP par exemple) dialoguent chacun indépendamment avec des routeurs d’autres AS. Le problème est alors de mutualiser les routes apprises par l’ensemble de ces routeurs : chacun doit communiquer les annonces qu’il a apprises de son côté et récupérer celles des autres afin de les annoncer à son tour au routeur de l’AS qui le concerne. Ces routeurs vont pouvoir utiliser BGP de façon interne à l’AS.

Illustration :

Remarque :

Il est important d’assurer une synchronisation entre les versions externes et internes de BGP. Il faut attendre d’avoir eu connaissance des routes par le protocole interne avant d’envoyer celles-ci par le protocole externe.

          Les attributs :

Des attributs constituent des informations transportées dans des messages BGP à la fois pour assurer un bon déroulement du protocole et pour permettre la sélection des routes en cas d’annonces de routes identiques.
A titre d’exemple, voici quelques attributs définis dans BGP :