Routage dynamique et
les types de protocole de
routage dynamique EGP
KPAÏ ARNAUD Nom du Prof :
DEVAÏ M. GBOKPEYA
Routage dynamique RIPV2
Protocole de routage dynamique EGP
1
Motivations
Dans un environnement complexe, la mise en ouvre du routage
statique est souvent difficile à maintenir
La mise en place d'un mécanisme de routage dynamique
permet de faciliter les mises à jour
Principe de fonctionnement général du routage dynamique :
Chaque routeur diffuse la liste des réseaux sur lesquels il
est connecté
Chaque routeur met à jour sa table de routage à partir des
informations reçues depuis les autres
2
Objectifs
Caractéristiques
Adaptatif à l’évolution du réseau
Configuration simple
Objectifs d’un protocole de routage
Optimisation:sélection de la meilleure route parmi
plusieurs Élimination des boucle de routage Efficacité: peu
de consommation des ressources Stabilité: convergence
rapide Simplicité: configuration simple
3
Protocoles de routage
Le protocole de routage consiste à définir comment sont
échangées les informations de routage, et donc à :
découvrir les autres routeurs du
réseau construire les tables de routage
maintenir les tables de routage à jour
Attention : protocole de routage # politique de routage
(décision)
4
Routage Hiérarchique
Jusqu’ici nous avons étudié un réseau idéal
Tous les routeurs sont identiques Un seul
réseau
… pas vrai en pratique
Facteur d’échelle :avec 50
autonomie administrative
millions de destinations :
internet = réseau des réseaux
On ne peut pas enregistrer
toutes Chaque administrateur de
les destinations dans la table de réseau
routage! veut contrôler le routage dans
son
réseau
5
Routage Hiérarchique
Agréger les routeurs en routeurs de passerelle
régions autonomes, Routeurs spéciaux dans un
“autonomous systems” AS
Exécutent les protocoles de
(AS) ensemble de
routage intra-AS
réseaux
une contrôlés par Responsables du routage à
seule autorité. des destinations extérieurs à
l’AS
Les routeurs d’un même
AS exécutent le même
exécutent des protocoles
protocole de routage de routage inter-AS avec
rotocole de routage
p d’autres routeurs de
“intra- AS” passerelle
6
AS (Autonomous System)
7
IGP (Interior Gateway Protocol)
IGP : Protocole de routage utilise dans les réseaux sous
même entité administrative qu’à l’intèrieur d'une entité
(entreprise, association, etc.)
décisions (suppression/ajout d'une ligne) peuvent être prises
par un service unique
but : trouver la route la plus efficace, en faisant confiance aux
autres routeurs.
Protocole de type IGP : RIP, OSPF, IS-IS
8
EGP (Exterior Gateway Protocol)
EGP : Protocole de routage adapté à la redistribution de
préfixes
vers des réseaux extérieurs, ayant une entité administrative
différente
s'utilise
entre entités distinctes (souvent concurrentes). impossibilité
de prendre une décision qui s'imposera a tous. on n'est pas prévenu
de ce que vont faire les autres. idée de menace : le but n'est pas de
trouver la meilleure route mais au
contraire d'empêcher les routeurs de choisir une route dont on ne
voudrait pas. pas d'information de routage mais d'accessibilité
Protocole de type EGP : BGP
9
AS et protocoles de routage
10
Classification des algorithmes de routage
Information globale ou locale ? Statique ou dynamique ?
Statique :
Globale
Les routes ne changent pas dans
: Chaque routeur connaît toutes les le temps
informations de topologie, de
coût des liens, etc. Algorithme Dynamique
“link state (LS)” : Les routes changent
régulièrement
Locale
Le routeur ne connaît que le côut
: des liens vers les voisins. Mise
à jour régulière
En réponse aux changement
Calcul itératif et échange régulier
de coût des liens
d’infos avec les voisins
Algorithmes “distance vector
(DS)”
11
RIP: Routing Information Protocol
12
Routage à vecteur de distance
Périodiquement un routeur envoie une copie de sa table de
routage à tous les routeurs directement accessibles.
Lorsque que J transmet un rapport au routeur K, K examine
l'ensemble des destinations annoncées et leur distance. K
modifie son entrée vers une destination si :
J connait un plus court chemin ou si J annonce une destination
que K ne possède pas ou si une destination via J a changée
l'entrée de la table de K mise a jour signale la distance n +
1 (avec n la distance annoncée par J pour la destination)
13
Algorithme de routage à vecteur de distance
itératif :
Structurede la Table de distance
Continue
jusqu’à ce que les
nœuds ne s’échangent plus Propre à chaque nœud Une ligne
d’info par destination possible Une
Auto-terminaison : pas de colonne par voisin
«signal» d’arrêt exemple : dans le noeud X, pour la
asynchrone dest. Y via le voisin Z :
: L’échange des infos ne
nécessite pas d’horloge
distribué distance de X à
X =
: Chaque nœud ne D (Y,Z) Y, viaZ
communique qu’avec ses Z
= c(X,Z) + min {D (Y,w)}
voisins w
14
Table de distance : exemple
1 coût destination via
B C E
7 D () A B D
A 8 2 AB
1 1 14 5
E D
2
C 5
7 8
E D
D (C,D)= c(E,D) + min {D (C,w)}
D
w
6 9 4
= 2+2 = 4
E D
D (A,D)= c(E,D) + min {D (A,w)} 2
w 4 1
= 2+3 = 5
boucle!
E B 1
D (A,B)= c(E,B) + min w{D (A,w)}
= 8+6 = 14
15
Table de routage
coût destination via
E Lien sortant , coût
D ()A B D
A
5
1 14 A A,1
B 7 5
89 B D,5
C 6 4
11 C D,4
D 4 2
D D,4
Table de distance Table de routage
16
Algorithme de routage DV
Itératif, asynchrone : Chaque noeud :
chaque
itération locale est causée par :
Changement de coût d’un lien attend(un changement dans le
adjacent coût local ou un msg du voisin)
Message d’un voisin du au
changement de sa table de
distance
Distribué Recalculela table de distance
Chaque nœud annonce à ces
: voisins seulementquand sa table
de distance change
Si la table de distance change,
annonceaux voisins
17
Principes de RIP (1)
Chaque routeur annonce périodiquement (30s) tous ses réseaux
et le nombre de sauts pour y aller
Chaque machine écoute les annonces des passerelles et
actualise sa table de routage
Si au bout d'un certain temps (3mn=180s), un réseau n'est plus
annoncé, il est supprimé de la table de routage.
Il n'y a pas d'accusé de réception de message RIP utilise UDP, port
520
18
Principes de RIP (2)
2 types de routeurs
:Routeur actif : diffuse ses informations de routage vers les
autres nœuds.
Routeur passif : écoute ces informations et met à jour sa
table
de routage.
RIPv1 diffuse (broadcast) et RIPv2 multicast toute leur
table de routage toutes les 30 secondes.
chaque nœud n'a d'information que sur le prochain saut
(next hop)
pas de décisions globales
19
Problèmes de RIP v1
limite de 16 sauts pas aller plus ne se base que sur une seule
loin que 15 routeurs (hops) métrique ( hop ) peut choisir
converge lentement (si route des routes lentes.
changent souvent, peut ne pas pas de gestion de masque
se stabiliser) pas de routage de sous-
réseaux
informations circulent pas d'authentification
lentement
25 entrées maximum dans la
trafic important
boucles possibles
table de routage (car taille du
message= 512 o)
20
RIP v2
3 algorithmes de plus
: split horizon : les données ne sont pas renvoyées vers le
nœud d'ou on les a appris
hold down : Le routeur ignore les informations relatives à
un
réseau pendant une période xe après réception d'un message
qui en spécifie l'inaccessibilité.
poison reverse : si on détecte une route coupée et qu'on
reçoit un message avec un coût très supérieur au coût initial,
on ignore l'information (considérée revenue par une
boucle).
22
RIP v2
Plus les améliorations suivantes :
masque de sous-réseau : sous-réseaux possibles + agrégation
des routes authentiquassions (mot de passe en clair ou
chiffre sur 16
octets)
utilisation de domaines logiques (on ignore les messages
d'un
autre domaine)
23
RIPv2 : split horizon
Contre le problème de convergence lente : Un routeur ne
transmet pas les informations relatives a une route vers la
même interface que celle qui l'a initialement annoncé. Mais : boucle
de routage encore possibles pour certaines
topologies.
24
RIPv2 : mécanisme de gel (hold down)
Le routeur ignore les informations relatives a un réseau
pendant une période fixe (60s) après réception d'un
message qui en spécifie l’innaccessibilité
25
RIPv2 : poison reverse
Après la disparition d'une connexion, le routeur qui l'a annoncé
conserve l'entrée pendant plusieurs cycles de mise à jour en
incluant un coût infini dans ses messages de diffusion.
+ Mise à jour déclenchée : force le routeur à diffuser
immédiatement le message de mauvaise nouvelles sans attendre
le cycle de diffusion suivant.
Mais : si routeurs se partagent un réseau commun, une seule
diffusion modifie toutes les tables de routage.
déclenchement
d'un cycle de diffusion
avalanche de diffusion possible risque
d'apparition de boucle et de gel
+ consommation de bande passante !
26
RIPv1/v2 : Protocole
Protocole très simple ! Protocole base sur
UDP (port 520) Commande :
1 : demande d'information de routage 2 : réponse contenant les
info de la table de routage de l'expéditeur 9 : demande de mise à
jour (avec circuit de commande) 10 : réponse de mise à jour
(avec circuit de commande)
27
RIPv1/v2 : Protocole
RIPv1
Adresse IP du réseau : prend toute la classe
distance en terme de nombre de sauts.
RIPv2
Etiquette : pour distinguer les routes apprises par RIP
(par ex. si cohabitation avec d'autres protocoles)
Adresse IP du prochains
aut (optionnel)
Distance (entre 1 et 15. 16 est
l'infini)
28
Conclusions
RIP v2 corrige certains problèmes de RIP v1
adresse IP+masque "gestion de zone" (par
l‘étiquette)
Encore des problèmes :
métrique : sauts uniquement* portée maximum
de 15 sauts
taille de la table de 25 entrées maximum.
RIPv2 ne peut s'appliquer qu'aux petits et moyens réseaux.
29