Chapitre 1 : Routage Dynamique
Routage statique est inadapté si: Routage Dynamique
● La topologie du réseau change souvent. ● C’est la façon de mettre à jour la table de
● + 10 Routeur =>Pas de mécanisme qui routage qui change.
réoriente le trafic en cas de panne sur ● Les routeurs communiquent entre eux
une liaison d'un réseau pour échanger des informations à
● Le chemin emprunté par un paquet IP
travers un protocole de communication.
n’est pas forcément le plus court chemin.
● Lorsqu'un protocole de routage met à
jour une table de routage, son objectif
est d’inclure le meilleur chemin dans la
table de routage
METRIQUE : C’est une valeur associée à chaque route du réseau et qui est utilisée par les
protocoles de routage dynamique pour choisir le meilleur chemin. cela est verifié quand la
métrique est petite.
1. La Bande passante (Débit ) : le débit d’une liaison Ethernet est de 10 ou 100 Mbits/s.
2. Le Délai : temps requis pour acheminer un paquet sur le lien.
3. La Charge : la quantité d'activité sur une ressource réseau ex : routeur ou liaison.
4. La Fiabilité : Taux d'erreurs de chaque liaison du réseau.
5. Le Nombre de sauts : nombre de routeurs par lesquels un paquet doit passer avant
d'arriver à destination.
6. Le Coût : valeur arbitraire, habituellement basée sur la bande passante, la dépense
d’argent ou d'autres mesures, attribuées par un administrateur de réseau.
7. Toute combinaison de ces valeurs : une fonction d’une ou plusieurs métriques
LE TEMPS DE CONVERGENCE
C’est le temps nécessaire pour que tous les routeurs aient une vue globale de la topologie
réseau c.-à-d. à chaque fois que la topologie du réseau change les informations
détenues par des routeurs doivent aussi changer =>tous les routeurs sont synchronisés. Le
processus et le temps de convergence des routeurs varient selon les protocoles de routage
1
Classification des protocoles de routage dynamique
À vecteur se base sur le nombre de sauts ( distance ) ou la longueur du chemin qui sera
de distance emprunté par le paquet pour trouver le meilleur chemin .
À état de se base sur l’état des liens (active ou non) pour créer la topologie exacte (avoir une
liens vision globale du réseau) de tout le réseau pour calculer le plus court chemin selon le
coût.
Hybride Cette méthode combine les algorithmes d'état de liens + de vecteur de distance.
Familles de protocoles de routage
1/IGP: assurent le routage interne à un AS
RIP , OSPF , IS-IS , IGRP “CISCO”, E-IGRP”CISCO”
2/EGP: assurent le routage entre les AS.
EGP, BJP , ES-IS
Principe du RIP « métrique : Nombre de saut » « Algorithme : ‘bellman-ford’ »
1/Phase d’initialisation
✔ RIP affecte la valeur 0 pour un réseau connecté, de 1 pour un réseau atteint pas le
biais d’un routeur et ainsi de suite.
✔ Les routeurs n’ont qu’une vision locale du réseau =>les routeurs directement connectés.
✔ Chaque entrée du vecteur est composée de : la destination + la distance.
2/Ajout d’une route
✔ Chaque routeur diffuse périodiquement (par défaut 30 s) le contenu de sa table de
routage à ses voisins immédiats.
✔ Le routeur à son tour reçoit des informations d’autres routeurs voisins.
⮚ Si une destination n’existe pas dans sa table de routage est reçue par le routeur alors il
l’insert dans sa table de routage avec la distance reçue+1 et comme prochain saut le
routeur qui a envoyé l’information.
⮚ Si une destination existant dans la table de routage est reçue par le routeur alors il
compare le coût (distance) et garde l’entrée la plus petite
3/Suppression d’une route
Une route est inaccessible si :
2
1/Un lien tombe en panne _toute les routes accessibles par ce lien sont considérées
inaccessibles.
2/Mettre la distance à l’infini (une grande valeur connue).
3/Diffuser l’information aux autres routeurs.
Problème du comptage à l’infini ?
✔ Le RIP peut engendrer des boucles de calcul et des boucles de routage lorsque des
pannes arrivent dans le réseau.
Solutions du problème du comptage à l’Infini
1/définir la valeur MAX de la distance
✔ la distance maximale entre deux réseaux avec RIP est 15 routeurs
✔ RIP utilise la valeur 16 _route est infinie et invalide (à supprimer de la table)
2/split horizon
3
Interdire aux nœuds de signaler qu’ils connaissent une destination au routeur par lequel ils
l’ont apprise.
3/utilisation des timer hors service
⮚ Utiliser un timer « holddown Timer » : lorsqu’on détecte un lien en panne, on ignore
toutes les mises à jour sur cette route pendant une certaine durée ( par défaut 60s ) .
⮚ Diffuser l’information aux autres routeurs. ces derniers vont aussi armer un timer
(ignorer toutes les information sur la route ) .
⮚ Supprimer la route après l’expiration du timer.
Problèmes liés à RIP
⮚ Lenteur : les routeurs n’ont connaissance d’un changement d’état du réseau que par
l’intermédiaire de leurs voisins.
⮚ Ce protocole n'est pas bien adapté aux réseaux de grande taille.
Si le nombre de réseaux croît, la taille des informations de mise à jour devient importante
et plus de routeurs échangent leurs informations =>consommation de la bande passante
⮚ Limitation de la métrique à 16.
Versions de RIP
RIPv1 ✔ Les messages RIPv1 sont envoyés en broadcast
✔ Ne supporte pas les sous réseaux ( il n’envoi pas le masque sous réseaux )
RIPv2 ✔ Permet d’envoyer le Netmask
✔ Pour limiter les diffusions, les paquets RIP sont émis sur l’adresse multicast
[Link]
✔ Pour des raisons de sécurité une authentification sommaire est ajoutée aux
paquets RIP
RIPng Pour IPv6
IGRP : Interior Gateway Routing Protocol est un protocole à vecteur de distance mis au
point par CISCO .Informations de routage diffusées toutes les 90 s.
La métrique utilisé est une combinaison de :
Bande passante +Délai +Charge du lien +Fiabilité +Unité de transfert maximale (MTU)
4
Il existe 2 chemins possibles entre les deux postes A et B.
•Le chemin le plus court mais le plus lent sera choisi par RIP : R1 => R2
•Le chemin le plus long mais le plus rapide sera choisi par IGRP : R1 => R3=> R4 =>R2
OSPF : Open Shortest Path First “ l’algorithme de Djikstra”
⮚ Les protocoles de routage à état de lien maintiennent une BDD dite BDD topologique
représentant la topologie complète du réseau
⮚ Les routeurs OSPF échangent des informations concernant l'état de leurs liaisons qui sont
up (en activité) ou down (hors service)
⮚ OSPF associe un coût à chaque lien en fonction du débit .La formule Coût = 108 / Débit
Principe d’OSPF
5
Principe d’OSPF « Ajout & suppression d’un lien »
⮚ Le routeur qui détecte le changement, diffuse l’information (Link state Update) aux
autres routeurs voisins qui vont à leur tour la propager à leur voisins,…. Etc
⮚ Chaque routeur qui reçoit les changements va mettre à jour sa BDD topologique.
⮚ Recalculer le plus court chemin et construire la nouvelle table de routage .
Le protocole "Hello"
⮚ Les routeurs utilisent le protocole HELLO pour la découverte des voisins et la
vérification périodique de leur présence (10s) sur chacune de leur interface
⮚ Les routeurs OSPF voisins en déduisent la présence du routeur et lebon fonctionnement
de la liaison
⮚ Si après 40 s un routeur OSPF n'a pas reçu un paquet Hello de l’un de ses routeur voisins
=>Alors il déduit l'absence du routeur et l'interruption de la liaison.
Remarques : Les valeurs des temporisateurs peuvent être modifiées
Inconvénients du routage à état de lien
Traitement et Mémoire Bande passante
✔ Les routeurs doivent utiliser plus de ✔ La largeur de bande consacrée à
mémoire et exécuter plus de traitements l‘initialisation (découverte du réseau) de
que pour les protocoles à vecteur de
Données + MAJ peut être très importante. .
distance.
6
✔ La mémoire doit donc être en mesure de
contenir toute les informations de mise à
jour.
Amélioration de l’OSPF
✔ le réseau est découpé en plusieurs zones « area » chacun contient moins de 50 routeurs.
✔ routeurs internes : Les routeurs à l’intérieur d’une zone et il utilise le protocole OSPF
✔ une zone BACKBONE ( area0 ), qui consiste en un ensemble de routeurs reliant les
différentes area.
⮚ routeurs de bordure ( ABR : Area Border Router) : effectuent ces échanges entre les
zones pour établir la communication entre Les routeurs d’une zone avec la zone 0 .
Seule la liste des réseaux contenus dans une zone est envoyée dans une autre zone et non
pas l’état des liaisons =>lors du calcul du plus court chemin , considérer
uniquement l’état des liens dans la même zone.
⮚ La liste des réseaux contenus dans une zone est ensuite diffusée à l’intérieur des zone
par inondation.
dans la table de routage sous la forme :
[ distance administrative/ métrique ]
• Distance administrative des
protocoles :
– Directement connecté : 0
– Route Statique : 1
– BGP : 20
– OSPF :110
– RIP :120
Le réseau Internet
C’est un super-réseau qui permet de connecter des ordinateurs utilisent des OS différents ou
d'autres réseaux distants dans le monde entier. Ce réseau universel n'appartient à personne
en particulier, il est Administré par des entités différentes et ayant des intérêts.
Fournisseurs d’Accès Internet FAI « Internet Service Provider ISP »
Sont des opérateurs qui permettent aux utilisateurs d’accéder à Internet, on peut les classer en
4 Catégories : Local – régional – national– de transite
Comme on peut distinguer des types de relations :
7
Client fournisseur A=> B - pair à pair A<=> B, Relation de Transit
Interconnexion des ISP : Points d’échange
⮚ Les liaisons locales sont moins chères que les liaisons internationales.
⮚ Une interconnexion locale est utile pour économiser le trafic sur les liens internationaux
et avoir de meilleures performances.
Il faut mettre en œuvre une politique de routage pour :
✔ Gérer le trafic local entre ISP.
✔ S’assurer que les “peer : voisin ” n’utilisent pas votre infrastructure du transit pour
accéder à d’autres réseaux.
✔ Il faut contrôler la liste des réseaux qu’on annonce aux voisins (même la liste qu’on
reçoit).
✔ Protocoles de routages nécessaires ( Le routage statique n’est pas adapté ) .
Système Autonome (Autonomous System : AS)
⮚ Un AS est un ensemble de réseaux IP géré par une seule entité (Entreprise,
Etablissement, ISP, Opérateurs).
⮚ Chaque AS possède un identificateur codé sur 16-bits (1- 65534).
Type du trafic dans un AS :
✔ Trafic local : source ou destination dans l’AS.
✔ Trafic Transit : le trafic qui passe par un AS à destination d’autres AS (Source et
destination extérieures à un AS =>utilise les ressources de l’AS)
Type d’AS :
✔ AS final : possède une seule connexion avec un autre AS. Il véhicule uniquement un
trafic local.
✔ AS multihomed : possède plusieurs connections avec plusieurs autres AS. Il achemine
pas le trafic du transit.
✔ AS de transit : possède plusieurs connections avec plusieurs AS. Il achemine le trafic
local et de transit
Principe de routage externe
✔ Le problème du routage externe n’est pas seulement de déterminer le chemin le « plus
court ». Mais, il faut avoir la possibilité d’imposer des contraintes de routage.
✔ Le protocole de routage externe permet de faire un routage politique.
✔ Le protocole de routage externe concerne les routeurs aux frontières des AS qui
s’échangent les informations de routage (adresses contenues dans les AS).
8
Fonctionnement de BGP Session BGP
⮚ Les routeurs BGP établissent des « peerings, relation de voisinage » entre eux pour
échanger des informations de routage =>à chaque mise à jour de la table de routage (ajout,
Suppression ou modification).
⮚ Un routeur BGP ouvre une session avec ses voisins BGP
Sessions fiables : connexion TCP port 179
Deux types de voisins :
• Voisins dans l’AS iBGP (interior BGP)
• Voisins extérieur eBGP (exterior BGP)
Paramètres de routage utilisés par BGP
As-Paths Local-preference
la longueur du chemin en nombre de pour choisir une route de sortie de
AS traversés.
l’AS parmi plusieurs routes possible.
Origin Metric
« IGP » : la route vient de l’AS Pour une même destination, les réseaux marqués
d’origine (un « i » apparaît dans avec la valeur de « metric » la plus faible sont
l’information de routage). préférés aux autres réseaux.
« EGP » : la route est apprise par un
EGP (un « e »apparaît dans
l’information de routage)
« Incomplète » : la route est inconnue
(un « ? » apparaît dans l’information de
routage) (ex: une route statique
redistribuée dans BGP)
9
Choix du plus court chemin par BGP
⮚ la plus grande "préférence locale"
⮚ une route de type "internal" (IGP (i) est plus petit que EGP (e), et EGP est plus petit que
Incomplete (?) ) .
⮚ le chemin (As-Path) le plus court ;
⮚ la métrique la plus faible.
Principe de filtrage avec BGP
Dans BGP il faut pouvoir filtrer les propagations de route. Par exemple :
– ne pas propager vers un AS une route apprise depuis un AS précis.
– on veut interdire à un AS de propager une route qu’on lui a passée.
⮚ On veut que R2 ne retransmette à R3 que le réseau [Link]/24 issu de R1 et pas le réseau
[Link]/24.
Le filtrage peut se faire selon les paramètres suivants :
– Par route(ou adresse) : on interdit la propagation par BGP d’une adresse ou d’un ensemble
d’adresses.
neighbor [Link] distribute-list 10 out
access-list 10 deny [Link] [Link]
access-list 10 permit [Link] [Link]
– Par chemin : on interdit la propagation par BGP de l’ensemble des routes apprises depuis
un AS ou une suite d’AS
neighbor [Link] filter-list 10 out
ip as-path access-list 10 deny _1$
ip as-path access-list 10 permit .*
– Par communauté : on interdit à un voisin de propager certaines routes qu’on lui a
diffusées. Certaines « communautés » sont prédéfinies :
Communauté « no-export » : ne pas ré-annoncer à des voisins eBGP
Communauté « no-advertise » : ne pas ré-annoncer du tout (ni eBGP, ni iBGP)
neighbor [Link] send-community
neighbor [Link] route-map rm out
route-map rm permit 10
set community no-export
10
11