Chapitre 2 : Le routage IP

Diery NGOM
Enseignant-chercheur en Informatique, UFR SATIC-UADB
Contact : [Link]@[Link]

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 1
 Plan :
I. Présentation du routage
 Définition et principe
 Table de routage
 Routage statique et routage dynamique
 Comparaison entre routage statique et
routage dynamique

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 2
 Plan (suite 1):
II. Les algorithmes de routage
 Notions sur la théorie des graphes
 Problème du plus court chemin dans un
graphe
 Algorithme de Dijkstra
 Algorithme de Bellman-Ford
 Algorithme de l’arbre couvrant
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 3
 Plan (suite 2):
III. Protocoles de routage et système autonome
 Protocole de routage
 Système Autonome (AS)
 Protocole de routage à vecteur de distance
o RIPv1 (Routing Information Protocol version 1)
o RIPv2 (Routing Information Protocol version 2)

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 4
 Plan (suite 3):
o IGRP (Interior Gateway Routing Protocol)
o EIGRP (Enhanced Interior Gateway Routing
Protocol)
 Protocole de routage à état des liens
o OSPF (Open Shortest Path First)
 Comparaison entre protocole de routage à
vecteur de distance et protocole de routage à
état des liens
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 5
 I. Présentation du routage
Définition et principe
On appelle routage la fonction qui permet à un
routeur de faire passer des paquets d'un réseau à
un autre.
Actuellement, la plupart des réseaux utilisent la
pile protocolaire TCP/IP. Donc, le routage se fait
souvent à l'aide du protocole IP.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 6
Dans chaque en-tête d’un paquet IP transmis
sur un réseau IP, il y a un champ contenant
l'adresse IP source et l'adresse IP de
destination.

Le routage se fait grâce à l’adresse IP de

destination.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 7
On divise le routage en deux grandes familles :

 Le routage direct : il s’agit délivrer un

datagramme à une machine raccordée au
même LAN.
 Pour se faire, l’émetteur trouve l’adresse
physique du correspondant (ARP), puis
encapsule le datagramme dans une trame et
l’envoie sur le LAN.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 8
 Le routage indirect : Le destinataire n’est pas
sur le même LAN que celui de la source (grâce
au résultat du ET logique effectuée entre
adresses IP et masque de sous-réseau).

 Il est absolument nécessaire de franchir une

passerelle connue d’avance ou d’utiliser une
route par défaut.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 9
Principe de base : si l’adresse de destination
n’est pas dans le réseau local (déterminé avec le
masque), on envoie les paquets à la passerelle
(gateway, routeur) qui saura où envoyer le
paquet.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 10
Chaque routeur utilise une table de
routage qui lui permet de choisir un certain
chemin pour atteindre le réseau de
destination.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 11
 Table de routage

La table de routage est une table de

correspondance entre l'adresse de la
machine visée et le nœud suivant auquel le
routeur doit délivrer le message.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 12
En réalité, il suffit que le message soit délivré
sur le réseau qui contient la machine. Il n'est
donc pas nécessaire de stocker l'adresse IP
complète de la machine : seul l’identifiant
réseau (NetID) a besoin d'être stocké.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 13
La table de routage est donc un tableau
contenant des paires d'adresses. Ainsi grâce à
cette table, le routeur, connaissant l'adresse du
destinataire encapsulée dans le message, va
être capable :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 14
 de savoir sur quelle interface envoyer le
message (cela revient à savoir quelle carte
réseau utiliser);

et à quel routeur, directement

accessible sur le réseau auquel cette carte
est connectée, remettre le datagramme.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 15
 Exemple de table de routage :

Réseau de Masque de Passerelle Métrique

destination sous réseau

[Link] [Link] [Link] 1

[Link] [Link] [Link] 1

[Link] [Link] [Link] 1

…. …. …. ….

[Link] [Link] [Link] 1

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 16
En fonction de l'adresse IP de destination, le
routeur va tenter de choisir la meilleure route
à prendre.

Si on reprend l'exemple de la table de routage

précédente, le choix de la route passe par les
étapes suivantes :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 17
1)Le routeur reçoit un paquet dont le
destinataire est [Link];

2) Il consulte sa table de routage pour vérifier

si cette adresse IP correspond à l'un des
entrée de sa table de routage;

3) Le réseau correspondant est le

[Link]/[Link], il faudra donc
passer la main à la passerelle [Link]
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 18
 Route par défaut

Quand un routeur ne connaît pas le réseau

de destination, il utilise la route par défaut,
c'est à dire celle qu'on prend quand on ne sait
pas faire autrement.

Cette route est référencée sur chaque routeur

par l'adresse [Link]

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 19
La commande netstat –rn permet de
visualiser la table de routage au niveau de
l’interface utilisateur.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 20
 Routage statique et routage dynamique
Sur un routeur, il existe deux manières pour
Configurer des routes :

Le mode statique appelé routage statique;

Le mode dynamique appelé routage

dynamique
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 21
 Routage statique

L’administrateur doit configurer les routes

manuellement;

utilisé plutôt dans les petites structures ;

beaucoup plus de chances pour se tromper, s’il

y a beaucoup de routes à renseigner;
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 22
D'autre part, si un routeur voisin change de
configuration ou est en panne, les autres
routeurs voisins ne seront pas au courant de
cet événement.

Chaque table de routage doit contenir une

route par défaut qui sera utilisée si le
routeur ne connaît pas le réseau de
destination.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 23
Cette route est notamment utilisée pour
aller sur Internet puisqu'on ne peut pas
connaître toutes les adresses IP du monde.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 24
 Routage dynamique

Nécessite de configurer un protocole de

routage;

Tous les routeurs ne prennent pas en charge

n'importe quel protocole de routage;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 25
Plus adapté aux grands réseaux, aux réseaux
évolutifs;

Plus difficile à mettre en place;

Par contre, une fois ce système mis en place,

tout se fait automatiquement . Si un routeur
tombe en panne ou si un nouveau routeur
arrive sur le réseau, les tables de routage sont
mises à jour automatiquement.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 26
 Comparaison entre routage statique et
routage dynamique
Routage statique Routage dynamique
Avantages Simple à mettre en place Choisit les routes en
fonction de plusieurs
critères;

Modifie sa route en
fonction des changements
de topologie
Inconvénients Nécessite une Nécessite un protocole
intervention humaine de routage;
pour chaque changement
de réseau; Nécessite un peu de
bande passante
Les routes choisies
seront toujours les mêmes
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 27
 II. Les algorithmes de routage
 La fonction principale de la couche réseau
est de router les paquets de la machine
source à la machine destinataire.

 L’algorithme de routage est la partie

logicielle de la couche réseau qui a la
responsabilité de décider sur quelle ligne de
sortie un paquet entrant doit être transmis.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 28
Un algorithme de routage doit posséder les
propriétés suivantes :

Exactitude;
Simplicité;
Robustesse;
Stabilité;
Justice (vis à vis des voisins);
Optimisation.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 29
La stabilité est un objectif important.

Il existe des algorithmes de routage qui ne

convergent jamais vers un équilibre quelle
que soit la durée de Fonctionnement.

Justice et optimisation sont sacrées pour un

algorithme de routage.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 30
Les algorithmes de routage peuvent être
regroupés en deux classes principales :

Les algorithmes non adaptatifs, leurs

décisions de routage ne se fondent pas sur
des mesures ou des estimations du trafic et
de la topologie;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 31
Les algorithmes adaptatifs, qui modifient
leurs décisions de routage pour refléter aussi
bien les changements de topologie que de
trafic dans le réseau.

Pour bien comprendre le fonctionnement

des algorithmes de routage, il est nécessaire
d’avoir des notions sur la théorie des graphes.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 32
Quelques notions sur la théorie des graphes
Les graphes modélisent de nombreuses
situations concrètes où interviennent des
objets en interaction.

Les interconnexions routière, ferroviaire ou

aériennes entre différentes agglomérations;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 33
Les liens entre les composants d'un circuit
électronique;

Les liens entre les différents équipements

d’un réseaux téléphonique, informatique,
électrique, etc.

Le plan d'une ville et de ses rues.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 34
Les graphes permettent de manipuler plus
facilement des objets et leurs relations avec
une représentation graphique naturelle.

L'ensemble des techniques et outils

mathématiques mis au point en théorie des
graphes permettent de démontrer facilement
des propriétés, d'en déduire des méthodes de
résolution, des algorithmes, ...
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 35
 Quel est le plus court chemin (en distance ou
en temps) pour se rendre d'une ville à une
autre?

 Comment minimiser la longueur totale des

connexions d'un circuit?

 Quel est le chemin le plus court, le moins

couteux dans un réseau pour transmettre un
paquet d’une source vers un destinataire?
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 36
Un graphe permet de décrire un ensemble
d'objets et leurs relations, c'est à dire les
liens entre les objets.

 Les objets sont appelés les nœuds, ou encore

les sommets du graphe.

 Un lien entre deux objets est appelé une

arête.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 37
 Définition d’un graphe
Un graphe G est un couple (V,E) où

 V est un ensemble fini d'objets. Les

éléments de V sont appelés les sommets du
graphe;

 E est sous-ensemble de VxV. Les éléments

de E sont appelés les arêtes du graphe.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 38
 Une arête e du graphe est une paire e = (x,y)
de sommets. Les sommets x et y sont les
extrémités de l'arête.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 39
Exemple d’un graphe à 8 sommets nommés de a
à h et 10 arêtes

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 40
 G = (V,E)

 V = { a, b, c, d, e, f, g, h }

 E = { (a,d), (b,c), (b,d), (d,e), (e,c), (e,h),

(h,d), (f,g), (d,g), (g,h) }

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 41
Notre définition d'un graphe correspond au
cas des graphes simples, pour lesquels il
existe au plus une arête liant deux sommets.

Dans le cas contraire le graphe est dit

multiple. Nous ne nous intéresserons ici
qu'au cas des graphes simples sans boucle.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 42
 Définitions et terminologies

 Deux sommets x et y sont adjacents s’il existe

l'arête (x,y) dans E. Les sommets x et y sont
alors dits voisins.

 Une arête est incidente à un sommet x si x est

l'une de ses extrémités.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 43
 Le degré d'un sommet x de G est le nombre
d'arêtes incidentes à x. Il est noté d(x).

 Pour un graphe simple le degré de x

correspond également au nombre de
sommets adjacents à x.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 44
 Exemple

Dans le graphe le sommet d a un degré 5.

d(d) = 5
Les arêtes incidentes à d sont : (d,a), (d,b) ,
(d,e), (d,h) et (d,g).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 45
Pour un graphe simple d'ordre n, le degré
d'un sommet est un entier compris entre 0 et
n-1.

Un sommet de degré 0 est dit isolé : il n'est

relié à aucun autre sommet.

Citons ici deux propriétés très simples et

souvent utiles.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 46
 La somme des degrés des sommets d'un
graphe est égal à 2 fois son nombre d'arêtes;

 Le nombre de sommets de degré impair

d'un graphe est pair;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 47
 Un sous-graphe de G consiste à considérer
seulement une partie des sommets de V et les
liens induits par E.

 Pour un graphe G = (V,E), un sous-graphe de

G est un graphe H=(W, E(W)) tel que W est
un sous-ensemble de V, et E(W) sont les arêtes
induites par E sur W, c'est à dire les arêtes de E
dont les 2 extrémité sont des sommets de W.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 48
E(W) ={ (x,y)ЄE | x,y ЄW }

Un exemple de sous-graphe de l’exemple

précédent :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 49
Le sous-graphe H induit par l'ensemble
W={ b, c, d, g, h } de sommets.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 50
 Un graphe complet est un graphe où chaque
sommet est relié à tous les autres sommets.
Le graphe complet d'ordre n est noté Kn.
Dans ce graphe chaque sommet est de degré
n-1.

 Exemple de graphe complet :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 51
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 52
 Un chemin est une liste P=(x1,x2,…..,xk) de
sommets telle qu'il existe dans le graphe une
arête entre chaque paire de sommets
successifs.

Pour tout i=1,…..,k-1, (xi,xi+1)ЄE

 La longueur du chemin correspond au

nombre d'arêtes parcourues : k-1.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 53
 Exemple
Un chemin de longueur 5 dans le graphe reliant
les sommets f à b est p=(f, g, h, e, d, b)

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 54
 Remarque
Il existe bien d'autres chemins pour aller de f à b.
Exemples :
Le chemin (f, g, d, b) de longueur 3, le
chemin (f, g, d, h, e, d, b) de longueur 6, ou
encore (f, g, d, h, e, d, h, e, d, b) de longueur 9,
... (d, h, e, d) est appelé un cycle. Ce cycle
pouvant être emprunté autant de fois que l'on
veut, il y a un nombre infini de chemins de f à b.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 55
 Graphe connexe

Un graphe est connexe si et seulement si, il

existe un chemin entre chaque paire de
sommets.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 56
Exemple de graphe connexe

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 57
 Propriétés
 Un graphe G d'ordre n connexe comporte au
moins n-1 arêtes.

 Un cycle est un chemin simple rebouclant

sur lui-même. Si dans un graphe G tout
sommet est de degré supérieur ou égal à 2,
alors G possède au moins un cycle.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 58
 Un cycle eulérien est un cycle passant une
et une seule fois par chaque arête du graphe.

 Un graphe est dit Eulérien si il admet un

cycle eulérien.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 59
 Théorème

 Un graphe est eulérien si et seulement si, il

est connexe et tous ses sommets sont de
degré pair.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 60
 Problème du plus court chemin dans un
graphe
Lorsqu'un chemin existe entre deux sommets
dans un graphe, l'être humain se pose
rapidement la question non seulement de
trouver un tel chemin, mais bien souvent il est
intéressé par le plus court chemin possible
entre ces deux sommets.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 61
Nous aimerions disposer d'une méthode
systématique capable, pour tout graphe et
pour toute paire de sommets s et t, de
déterminer le plus court chemin entre eux.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 62
Résoudre ce problème va donc consister à
proposer un algorithme, aussi rapide que
possible.

Le problème de trouver un plus court chemin

est un problème d'optimisation auquel
nous sommes confrontés.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 63
Exemple de la recherche du plus court chemin
dans un graphe

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 64
Il s'agit donc de partir de s (distance 0), et de
visiter successivement ses voisins (distance 1),
puis les voisins de ses voisins non encore
visités (distance 2), les voisins des voisins des
voisins non encore visités, et ainsi de suite...

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 65
 Algorithme de recherche
ENTREES Graphe G=(V,E), Sommet s
Initialiser tous les sommets à non marqué
Marquer s
TantQue il existe un sommet non marqué
adjacent à un sommet marqué
Sélectionner un sommet y non marqué
adjacent à un sommet marqué et
Marquer y
FinTantQue Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 66
Pour trouver les plus court chemins dans un
graphe valué, nous allons voir 2 algorithmes
différents :

Algorithme de Dijkstra;

Algorithme de Bellman-Ford.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 67
 Algorithme de Dijkstra

L’algorithme de Dijkstra est une adaptation de

l'algorithme de recherche pour calculer les
plus court chemin d'un sommet s à tous les
autres sommets du graphe.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 68
 Algorithme de Dijkstra (suite)

L'algorithme de Dijkstra est un algorithme de

marquage, une adaptation pour le problème du
plus court chemin de l'algorithme général de
recherche.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 69
Comme pour la longueur en nombre
d'arêtes, l'idée est d'explorer le graphe dans le
"bon" ordre, des sommets les plus proches de
s aux sommets les plus éloignés pour
pouvoir au fur et à mesure calculer leur
distance à s.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 70
 ALGORITHME Dijkstra
ENTREES G=(V,E) un graphe avec une valuation positive c des
arêtes, s un sommet de V
Initialiser tous les sommets à non marqué ; Initialiser tous les
labels L à ∞
L(s) := 0
Tant Que il existe un sommet non marqué
//Sélection du plus proche sommet non marqué
Choisir le sommet y non marqué de plus petit label L
Marquer y
// Mise à jour des labels de ses voisins non marqués
Pour chaque sommet z non marqué voisin de y
L(z) := min {L(z) , L(y) + c(y,z)}
Fin Pour
Fin TantQue

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 71
 Algorithme de Bellman-Ford

Cet algorithme est plus complexe, plus long en

temps, mais plus puissant : il détermine la
distance de tous les plus courts chemins entre
toutes les paires de sommets d'un graphe,
pouvant avoir des valuations négatives ou
positives de ses arêtes.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 72
Son principe repose sur un paradigme
algorithmique très général :
la programmation dynamique.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 73
 Algorithme de l’arbre couvrant

Un arbre couvrant pour un graphe G=(V,E)

est un arbre construit uniquement à partir des
arêtes de E et qui connecte ("couvre") tous les
sommets de V.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 74
Le problème de l'arbre couvrant de
poids minimum consiste à trouver un
arbre couvrant dont la somme des poids c(e)
des arêtes est minimum.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 75
La seule condition, nécessaire et suffisante,
pour qu'un graphe admette un arbre couvrant
est qu'il soit connexe.

Un arbre couvrant de poids minimum (MST,

Minimum Spanning Tree) est en général
différent de l'arbre des plus courts chemins
(SPT, Shortest Paths Tree) construit par
exemple par Dijsktra.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 76
 Exemple

Un arbre des plus courts chemins (SPT) de racine A

Sa hauteur est 7
Son poids est 14
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 77
 Définition d’un réseau

Un réseau est un graphe orienté N=(V,A)

avec une valuation positive de ses arcs. La
valuation c(x,y) d'un arc (x,y) est appelée la
capacité de l'arc.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 78
On distingue sur N deux sommets particuliers :
Une source S et une destination T. Les autres
sommets sont les nœuds intermédiaires du
réseau (routeurs ou commutateurs).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 79
III. Protocole de routage et système
autonome

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 80
 Protocole de routage
Un protocole de routage est un système de
communication utilisé entre les routeurs.

Permet l’échange d’informations sur la

topologie du réseau entre les différents
routeurs;

Ces informations servent à construire et à

mettre à jour une table de routage.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 81
Permettent donc aux routeurs de
cartographier le meilleur chemin vers
n’importe quel autre routeur ou segment
réseau dans le même réseau ou encore sur
Internet.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 82
 Exemples de protocoles de routage

RIP (Routing Information Protocol);

IGRP (Interior Gateway Routing Protocol);

EIGRP (Enhanced Interior Gateway Routing

Protocol);

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 83
Exemples de protocoles de routage (suite)

OSPF (Open Shortest Path First);

IS-IS (Intermediate System-to-Intermediate

System) de Cisco.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 84
 Système Autonome

Ensemble d’équipements gérés par la même

administration typiquement un FAI ou une
plus grande organisation qui possède des
connexions redondantes avec le reste du
réseau Internet.

Notion administrative et non technique.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 85
Internet est un ensemble de systèmes
autonomes (SA).

En règle générale, chaque SA est administré

par une entité unique.

Chaque SA a sa propre technologie de routage,

qui peut être différente de celle des autres SA.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 86
Le protocole de routage utilisé au sein d’un
SA est appelé IGP (Interior Gateway
Protocol).

Par contre, le protocole de routage utilisé

entre différents SA est appelé EGP (Exterior
Gateway Protocol).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 87
 Exemple de SA :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 88
Internet est un ensemble de SA
interconnectés. Par conséquent tous les
routeurs ne font pas le même travail selon le
type de réseau sur lequel ils se trouvent.

Il y a différents niveaux de routeurs comme

indiqué sur le schéma ci-dessous :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 89
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 90
On distingue :

Les routeurs noyaux sont les routeurs

principaux car ce sont eux qui relient les
différents réseaux ;

Les routeurs externes permettent une

liaison des SA entre eux;
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 91
Les routeurs internes permettent le
routage des informations à l'intérieur d’un
SA.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 92
Il existe deux familles de protocoles de
routage :

 Les protocoles de routage à vecteur de

distance ;

 Les protocoles de routage à état de lien.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 93
 Protocoles de routage à vecteur de
distance

Détermine la direction et la distance jusqu’à

une liaison quelconque de l’inter-réseau;

Protocole basé sur le nombre de sauts;

Utilise l’algorithme de Bellman-Ford;

Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 94
Seul compte le nombre de sauts, c'est à dire que
la route la plus courte en nombre de routeurs à
traverser est toujours privilégiée;

Chaque routeur doit disposer d’une table de

routage indexée, dotée d’une entrée pour chaque
sous-réseau;

Les tables de routage sont mises à jour

régulièrement par concertation mutuelle entre
routeurs voisins.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 95
Les tables de routage sont mises à jour
périodiquement ou lorsque la topologie du
réseau change;

Il est important qu'un protocole de routage

puisse mettre à jour de façon efficace les
tables de routage;

Les algorithmes à vecteur de distance

prévoient que chaque routeur transmette
aux routeurs voisins l'intégralité de sa table
de routage.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 96
 Problèmes liés aux boucles de routage à
vecteur de distance

Des boucles de routage peuvent apparaître

lorsque des tables de routage incohérentes
ne sont pas mises à jour en raison d'une
convergence plus lente dans un
environnement réseau changeant.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 97
Exemple de boucle de routage

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 98
 Exemple de boucle de routage (suite)
Juste avant la panne du réseau 1, tous les
routeurs disposent d’une base de
connaissances cohérente et de tables de
routage correctes. On dit alors que le réseau a
convergé.

Pour la suite de cet exemple, supposons que

le meilleur chemin du routeur C vers le
réseau 1 passe par le routeur B et que la
distance entre le routeur C et le réseau 1 soit
égale à 3.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 99
Lorsque le réseau 1 tombe en panne, le routeur
E envoie une mise à jour au routeur A. Ce
dernier cesse d’acheminer des paquets vers le
réseau 1, mais les routeurs B, C et D continuent
de les acheminer car ils n’ont pas encore été
informés de la panne. Lorsque le routeur A
transmet sa mise à jour, les routeurs B et D
cessent d'acheminer des paquets vers le réseau 1.
Toutefois, le routeur C n'a toujours pas reçu de
mise à jour. Pour lui, le réseau 1 est toujours
accessible via le routeur B.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 100
A présent, le routeur C envoie une mise à jour
périodique au routeur D pour lui indiquer un
chemin vers le réseau 1 passant par le routeur B.
Le routeur D modifie sa table de routage pour
refléter cette information erronée et la transmet
au routeur A. Ce dernier la transmet à son tour
aux routeurs B et E, et ainsi de suite. Tous les
paquets destinés au réseau 1 génèrent alors une
boucle à partir du routeur C vers les routeurs B,
A et D, qui revient au routeur C.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 101
Les mises à jour erronées du réseau 1
continueront de former une boucle jusqu'à ce
qu'un autre processus mette fin au bouclage.
En raison de cette condition, appelée
métrique de mesure infinie, les paquets
tournent sans cesse sur une boucle bien que le
réseau de destination (réseau 1) soit en panne.
Pour détecter l’existence de cette boucle de
routage, les routeurs comptent à l’infini, les
informations erronées.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 102
Processus du comptage à l’infinie

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 103
Si aucune mesure n'est prise pour arrêter ce
processus, la métrique à vecteur de distance
du nombre de sauts est incrémentée chaque
fois que le paquet passe par un autre
routeur;

Les paquets tournent en boucle sur le réseau

en raison de la présence d’informations
erronées dans les tables de routage.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 104
Les algorithmes de routage à vecteur de
distance sont autocorrectifs;

Toutefois, pour régler un problème de boucle

de routage, une métrique de mesure infinie
peut s'avérer nécessaire;

Pour éviter que le problème se prolonge, un

nombre de saut maximal est défini comme
métrique de mesure infinie.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 105
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 106
Grâce à cette méthode, le protocole de routage
permet à la boucle de routage d'exister jusqu'à
ce que la métrique dépasse la valeur maximale
autorisée. Le graphique indique une valeur
métrique de 16 sauts qui dépasse la valeur
maximale par défaut du vecteur de distance
égale à 15 sauts. Le routeur ignore donc le
paquet. Dans tous les cas, le réseau 1 est
considéré comme inaccessible lorsque la
valeur métrique dépasse la valeur maximale.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 107
 Remarque
D’autres techniques peuvent être utilisées
par les routeurs en fonction des protocoles
de routage qu’ils exécutent pour éliminer les
boucles de routage :

Split horizon;
Poisson reverse;
Compteurs de retenue;
Mises à jour déclenchées.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 108
 RIP (Routing Information Protocol)
Protocole à vecteur de distance;

Le plus utilisé à ce jour dans les réseaux

actuels;

Basé sur des normes ouvertes;

Facile à mettre en œuvre;

Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 109
 RIP (suite)

Calcule la distance jusqu’à un hôte en

mesurant le nombre de sauts (routeurs) et
privilégie le chemin le plus court(sélection
de la meilleur route);

Met à jours les tables de routage

régulièrement.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 110
Il existe deux versions du protocole RIP :

RIP v1 (RIP version 1);

RIP v2 (RIP version 2).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 111
 RIP v1

Considéré comme un protocole IGP par

classes (classful);

Diffuse intégralement sa table de routage à

chaque routeur voisin, à intervalles
prédéfinis;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 112
 RIP v1 (suite)
L’intervalle par défaut est de 30 secondes;

Utilise le nombre de sauts comme métrique,

avec une limite de 15 sauts maximum;

La valeur 16 est considérée comme infinie et

indique une mise à l’écart de la route
correspondante.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 113
 Avantages de RIP v1
RIP v1 est très populaire car il est compatible
avec tous les routeurs IP;

 Son succès repose essentiellement sur sa

simplicité et sa compatibilité universelle;

RIP v1 est capable de gérer l’équilibrage de

charge sur au plus de six chemins de coût égal,
avec quatre chemins par défaut.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 114
 Limitation de RIP v1

Il n’envoie pas d’informations sur les

masques de sous-réseau dans ses mises à
jour;

Il envoie des mises à jour sous forme de

broadcasts sur [Link];

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 115
 Limitations de RIP v1 (suite)

Il ne prend pas l’authentification en charge;

Il ne prend en charge ni VLSM, ni le routage

CIDR (Classless Interdomain Routing).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 116
 RIP v2

RIP v2 est une version améliorée de RIP v1;

Les deux protocoles partagent un certain

nombre de caractéristiques.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 117
 RIP v2 (suite)
RIP v2 est un protocole à vecteur de distance
utilisant le nombre de sauts comme
métrique;

Il utilise des compteurs de retenue pour

empêcher les boucles de routage (valeur par
défaut : 180 secondes);

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 118
Il utilise la règle «split horizon» pour
empêcher les boucles de routage;

Il utilise 16 sauts comme métrique de mesure

infinie.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 119
 Règle du «split horizon»
La règle de «split horizon» est basée sur la
théorie selon laquelle il n’est pas utile de
renvoyer les informations relatives à une route
en sens inverse. C’est-à-dire, les mises à jour
de routage envoyées par un routeur à son
voisin ne contiennent pas les informations
qui ont été précédemment apprises grâce à ce
routeur voisin.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 120
 Avantages de RIP v2

RIP v2 présente une fonctionnalité de routage

CIDR lui permettant d’envoyer des
informations sur les masques de sous réseau
avec la mise à jour des routes.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 121
 Avantages de RIP v2 (suite)
Par conséquent, RIP v2 prend en charge le
routage CIDR qui permet à différents sous
réseaux du même réseau d’utiliser des
masques de sous-réseau distincts, comme
dans VLSM;

RIP v2 permet l’authentification dans ses

mises à jour. Il est possible d’utiliser une
combinaison de clés sur une interface;
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 122
Comme vérification d’authentification, il
permet de choisir le type d’authentification à
utiliser dans les paquets RIP v2;

Il peut s’agir de texte en clair ou d’un cryptage

basé sur l’algorithme d’authentification MD5.
Le type d’authentification par défaut est le texte
en clair.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 123
L’algorithme MD5 peut être utilisé pour
authentifier la source d’une mise à jour de
routage.
MD5 est généralement utilisé pour le cryptage
des mots de passe enable secret et n'a pas
d'algorithme de réversibilité connu;

En fin, pour une meilleure efficacité, RIP v2

utilise l’adresse de classe D [Link] pour
envoyer les mises à jour de routage en
multicast.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 124
Comparaison entre RIP v1 et RIP v2

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 125
RIP v1 RIP v2
Comparaison entreFacile
Facile à configurer
RIPà configurer
v1 et RIP v2
Prend en charge uniquement un Prend en charge l’utilisation du routage
protocole de routage par classe(classful) CIDR(classless)

La mise à jour de routage ne contient Envoie des informations sur les masques
aucune information de sous-réseau de sous-réseau avec des mises à jour de
routes
Ne supporte pas le routage CIDR, ce qui Supporte le routage CIDR, ce qui permet
oblige tous les équipements d’un même à des équipements d’un même réseau
réseau à utiliser le même masque de d’utiliser différents masque de sous-
sous-réseau réseau

Aucune authentification dans les mises Permet l’authentification dans ses mises
à jour à jour de routage
Envoie les broadcasts sur [Link] Envoie les mises à jour de routage en
multicast sur [Link] ,ce qui est plus
efficace
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 126
 IGRP (Interior Gateway Routing Protocol)
Protocole de routage à vecteur de distance
mise au point par Cisco;

Envoie les informations de routage par

intervalle de 90 secondes et donne des
informations sur un AS particulier;

RIP est limité à 15 ou 16 sauts (RIPv1 ou

RIPv2) alors que IGRP est limité à 255 sauts.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 127
 Caractéristiques de IGRP
Polyvalence lui permettant de traiter
automatiquement des topologies complexes
et indéfinies;

Flexibilité nécessaire à la segmentation avec

des caractéristiques différentes en termes de
bandes passantes et de délai;

Evolutivité lui permettant de fonctionner

sur des réseaux de grandes tailles.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 128
 IGRP (suite)
IGRP utilise par défaut la bande passante et
le délai comme métriques;

Par ailleurs IGRP peut être configuré en

utilisant une combinaison de variables pour
la détermination de la métrique. Ces
variables sont la bande passante, le délai, la
charge et la fiabilité.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 129
EIGRP (Enhanced Interior Gateway Routing
Protocol)
développé pour résoudre les problèmes
associés au routage dans de grands réseaux
multi-fournisseurs;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 130
 EIGRP (suite)
Prend en compte les métriques suivantes :
 bande passante
 charge
délai
 fiabilité

Il est possible de pondérer ces métriques

afin de privilégier certains aspects du
chemin.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 131
 Remarque

Bien que EIGRP est classé dans la famille

des protocoles à vecteur de distance,
techniquement il est un protocole de
routage à vecteur de distance “avancé” qui
incorpore les avancés des deux familles de
protocoles, vecteur de distance et état des
liens.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 132
 Remarque (suite)

Il combine les qualités des deux familles de

protocoles et est souvent référé à un
protocole de routage «hybride».

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 133
 Protocoles de routage à état des liens

Fonctionnent différemment des protocoles

de vecteur de distance;

Basés sur l’algorithme de Dijkstra.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 134
Plusieurs paramètres peuvent entrer en
compte pour calculer la meilleure route à
prendre;

Les tables de routages sont mises à jour

uniquement quand une route est modifiée;

 Gèrent une base de données complexe

d’informations topologiques;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 135
L’algorithme à vecteur de distance comprend
des informations non spécifiques sur les
réseaux distants et ne fournit aucune
information sur les routeurs distants;

L’algorithme de routage à état de liens gère

une base de connaissances complète sur ces
routeurs distants et sur leurs interconnexions.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 136
 Fonctionnement des protocoles de routage
à état des liens
Recueillent les informations de tous les autres
routeurs du réseau ou à l’intérieur d’une zone du
réseau préalablement définie;

Une fois toutes les informations collectées,

chaque routeur, indépendamment des autres,
calcule ses meilleurs chemins vers toutes les
destinations du réseau.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 137
Étant donné que chaque routeur met à jour sa
propre vue du réseau, il y a moins de risque
qu’il propage les informations incorrectes
fournies par un de ses voisins.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 138
Les protocoles de routage à état de liens
assurent les fonctions suivantes :

ils réagissent rapidement aux changements

qui interviennent sur le réseau;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 139
 ils envoient des mises à jour déclenchées
lorsqu’un changement se produit sur le réseau;

ils envoient des mises à jour périodiques

appelées rafraîchissements d’état de liens;

Ils utilisent un mécanisme HELLO pour

déterminer l’accessibilité de leurs voisins
comme indiqué sur la schéma ci-dessous :

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 140
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 141
Chaque routeur surveille l’état de ses voisins
directement connectés par la diffusion
multicast de paquets HELLO;

Chaque routeur surveille aussi tous les

routeurs de son réseau ou de sa zone au moyen
de mises à jour de routage à état de liens(LSA);

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 142
Le paquet HELLO contient des informations
sur les réseaux qui sont reliés au routeur. Par
exemple, dans la figure ci- dessus , P4 a pris
connaissance de ses voisins, P1 et P3, sur le
réseau C.

Les LSA fournissent des mises à jour sur l’état

des liens qui constituent des interfaces sur
tous les routeurs du réseau.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 143
Un routeur qui exécute un protocole d’état de
liens assure les fonctions suivantes :

il utilise les informations HELLO et les mises à

jour de routage à état de liens (LSA) qu’il reçoit
des autres routeurs pour construire une base
de données relative au réseau;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 144
il utilise l’algorithme du plus court chemin
d’abord (SPF) pour calculer la route la plus
courte vers chaque réseau;

il stocke ces informations de route dans sa

table de routage.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 145
 OSPF (Open Shortest Path First)

 OSPF est un protocole de routage à état de

liens basé sur des normes ouvertes.

 Il est spécifié dans différentes normes du

groupe IETF (Internet Engineering Task
Force).

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 146
 OSPF (suite)

Le terme «Open» de OSPF signifie qu’il s’agit

d’une norme ouverte au public et non
propriétaire;

OSPF est en train de s’imposer comme

protocole IGP de prédilection par rapport à
RIP v1 et RIP v2, car il est évolutif;
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 147
RIP est limité à 15 sauts ;

RIP converge lentement et il choisit parfois

des routes lentes parce qu’il fait l’impasse sur
des facteurs critiques, tels que la bande
passante dans la détermination de la route.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 148
OSPF surmonte les limitations de RIP et
s’avère un protocole de routage robuste et
évolutif adapté aux réseaux d’aujourd’hui;

Il peut être utilisé et configuré en tant que

zone unique pour les petits réseaux;

Il peut également être utilisé pour les grands

réseaux.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 149
Il inclut des métriques de coûts tenant compte
de :

 la vitesse d’acheminement;
 du trafic (QoS);
 de la fiabilité;
 de la sécurité;

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 150
Un des inconvénients majeurs de OSPF est
qu’il ne supporte que la pile protocolaire
TCP/IP.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 151
Notion de zone OSPF

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 152
Base de donnée d’adjacence et messages
LSA

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 153
Chaque routeur conserve une liste de voisins
adjacents, appelée base de données
d'adjacence (ou de contiguïté).
La base de données d'adjacence est une liste
de tous les routeurs voisins avec lesquels le
routeur a établi des communications
bidirectionnelles.
Cette liste est propre à chaque routeur.

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 154
Tous les routeurs voisins échangent des
messages de mise à jour d’états des liens
appelés messages LSA.
Pour un nombre de n routeurs dans un réseau,
le nombre d’adjacences créés est n(n-1)/2.
Donc, pour un réseau composé de 5 routeurs,
ce nombre est égal à 10. Pour un réseau de 20
routeurs, ce nombre est : 20 (20-1)/2 = 190.
Ainsi, dans un tel scénario le nombre de
messages LSA qui seront échangés entre
routeurs voisins va engendrer une inondation
dans le réseau.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 155
Pour résoudre ce problème d’inondation avec
les messages LSA surtout dans le cas des
réseaux de grandes échelles (des dizaines de
routeurs), les routeurs OSPF choisissent un
routeur désigné (DR) qui va diffuser les
messages LSA.
Un autre routeur de secours (BDR) est
également désigné et sera utilisé en cas de
panne du routeur DR (voir schéma ci-
dessous).
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 156
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 157
 Le routeur DR est choisi pour diffuser les
massages LSA dans le réseau.
 Les autres routeurs au lieu d’inonder le réseau
par les messages LSA, les envoient au DR et au
BDR en utilisant l’adresse multicast [Link]
(appelée AllDRouters).
 Après avoir reçu ces messages LSA des autres
routeurs, le routeur DR les envoie aux autres
routeurs en utilisant l’adresse multicast
[Link] (appelée AllSPFRouters)
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 158
 Le processus d’élection des routeurs DR et
BDR est assez simple.
 Le DR est le routeur avec la plus haute priorité
d’interface OSPF, la BDR est celui avec la
deuxième priorité d’interface OSPF.
 Si leurs priorités sont égales, le routeur avec
l’ID de routeur le plus élevé est élu.
 La commande show ip ospf neighbor en
mode privilégié permet de voir le statut des
routeurs OSPF.
Cours de Routage et Commutation-L3 AMRT-S5-
2015/UFR SATIC-UADB- M. NGOM 159
Comparaison les protocoles de routage à
vecteur de distance et les protocoles de
routage à état de lien

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 160
Vecteur de distance Etat de lien

Visualise la topologie du réseau du Dispose d’une vue commune de la

point de vu de leurs voisins topologie

Ajoute des vecteurs de distance d’un Calcule le plus court chemin vers les
routeur à l’autre autres routeurs

Mises à jour périodiques fréquentes Mises à jour déclenchées par

Convergence lente événements
Convergence plus rapide
Passe des copies des tables de
routages aux routeurs voisins Passe les mises à jour du routage à
état de lien aux autres routeurs voisins

Cours de Routage et Commutation-L3 AMRT-S5-

2015/UFR SATIC-UADB- M. NGOM 161