9.routage dynamique

Le Routage dynamique

• Le protocole RIP

• Le protocole IGRP

• Le protocole OSPF

Introduction

• Le routage statique est inadapté si : Le nombre de réseaux à connecter est important ( plus de 10 routeurs à

configurer ) La topologie du réseau change souvent Plusieurs routeurs existent et la reconfiguration doit être automatique en cas

de panne (Permet de réorienter le trafic en cas de panne sur une liaison d'un réseau ).

Le chemin emprunté par un paquet IP dans le routage statique n’est pas forcément le plus court chemin .

Routage dynamique • Routage dynamique : protocole de communication inter-routeurs

qui va permettre de construire automatiquement les tables de routages.

• Protocole de communication inter-routeurs : chaque routeur communique avec ses voisins directement accessibles pour échanger les informations.

• Le principe du routage ne change pas, c’est la façon de mettre à jour ( construire ) la table de routage qui change, puisqu’elle n’est plus manuelle mais dynamique.

Le routage dynamique•Le routeur assimile ( apprennent ) dynamiquement de nouvelles informations de routage (grâce à des protocoles spécifiques) vers d'autres réseaux.

•Lorsqu'un algorithme de routage met à jour une table de routage, son principal objectif est de déterminer la meilleure information à inclure dans la table afin de trouver le meilleur chemin.

• A chaque lien du réseau est associé une valeur appelée METRIQUE

• Tant que la métrique est petite meilleur est le chemin.

•La métrique est utilisé pour choisir le meilleur chemin .

A

B

CD

E4

1

2

6

12

3

LA Métrique•La métrique d'un lien peut être soit en fonction d'une seule caractéristique ou en fonction de plusieurs caractéristiques.

•Quelques métriques utilisées :

• Bande passante ( Débit ) : par exemple, une liaison Ethernet sera à 10 ou 100 Mbits/s.

• Le Délai : temps requis pour acheminer un paquet sur le lien .

• La Charge : la quantité d'activité sur une ressource réseau telle qu'un routeur ou une liaison.

• La Fiabilité : Taux d'erreurs de chaque liaison du réseau.

• Le Nombre de sauts : nombre de routeurs par lesquels un paquet doit passer avant d'arriver à

destination.

• Le Coût : valeur arbitraire, habituellement basée sur la bande passante, la dépense d’argent ou

d'autres mesures, attribuée par un administrateur de réseau.

• Toute combinaison de ces valeurs.

Le temps de convergence • À chaque fois que la topologie du réseau change ( le changement peut être à

cause d’un ajout d’un réseau ou une panne ) les informations détenues par des routeurs doit aussi changer.

• Après un changement de la topologie, les routeurs doivent recalculer les routes, ce qui perturbe le routage.

• Ces informations doivent refléter une vision globale cohérente de la nouvelle topologie.

• Cette vision se nomme convergence.

• Il y a convergence lorsque tous les routeurs ont une vue uniforme de la topologie réseau les routeurs sont synchronisés.

• Le processus et le temps de convergence des routeurs varient selon les protocoles de routage plus le temps de convergence est petit plus l’algorithme de routage est performant

Classification des algorithmes de routage dynamique

• Les algorithmes de routage peuvent être : – À vecteur de distance : ces algorithmes se basent sur le nombre de sauts

( distance ) ou la longueur du chemin qui sera emprunté par le paquet pour trouver le meilleur chemin les routeurs ont une vision local du la topologie du réseau .

– À état de liens : ces algorithmes se basent sur l’état des liens ( active ou non ) pou créer la topologie exacte de tout le réseau avoir une vision globale avant de calculer le plus court chemin

– Hybride : Cette méthode combine les aspects des algorithmes d'état de liens et de vecteur de distance.

RIP : Routing Information Protocol.

Le protocole RIP est un protocole à vecteur de distance.

Il diffuse périodiquement le contenu de sa table de routage à ses voisin immédiats ( les routeurs directement connectés ).

Chaque entrée de la table est composée de la destination, de la distance et du routeur de prochain saut .

La distance est la mesure du coût associé à la route le RIP utilise le nombre de saut comme métrique .

Le franchissement d'un routeur compte pour un pas ( un saut ).

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.

Métrique utilisé par le RIP

A

B

CD

ER1

R2

R5

R6

R3R4

La distance de A à E : est égale à zéro si on utilise le lien R1

La distance de A à E : est égale à 2 si on utilise les liens R 2 ,R5 et R4

passer par les routeur D et C

Principe RIP Initialisation

•Au démarrage le routeur détecte toutes les interfaces actives, et ainsi crée la table de routage des routes directes.

•Il envoie une requête sur chacune des interfaces afin d’obtenir les tables de routages complètes des autres routeurs voisins.

•Le routeur reçoit les listes de réseaux accessibles par les routeurs adjacents, avec une distance associée à chaque destination.

•Lorsqu’une nouvelle destination est reçue, le routeur l’ajoute à sa table de routage, indiquant comme adresse de destination, l’adresse source à l’origine du message RIP .

Exemple

Destination Distance Prochain pas

144.19.0.0 0 Direct

130.21.0.0 0 Direct


144.19.0.0 0 Direct

130.21.0.0 0 Direct

200.1.1.0 5 144.19.1.100

200.2.5.0 3 144.19.1.101

199.23.3.0 4 130.21.5.30

131.200.0.0 7 130.21.5.32

Au démarrage : le routeur détecte deux liens qui lui sont directement connecté

Après la réception des table de routage de ces voisins il va mettre à jour sa propre table de routage

Principe RIPAjout d’une route

•Après la phase d’initialisation, le routeur va diffuser régulièrement sur chacune de ses interfaces, par défaut toutes les 30 secondes, sa table de routage.

•Le routeur a sont tour il reçoit des informations d’autres routeurs .

• Si une destination existant dans la table de routage est reçue par le routeur alors il compare les distances et garde dans sa table de routage l’entrée ayant la plus petite distance .

• En suite il diffuse alors cette information sur les autres interfaces.

Exemple : ajout d’une route


144.19.0.0 0 Direct

130.21.0.0 0 Direct


144.19.0.0 0 Direct

130.21.0.0 0 Direct

200.1.1.0 5 144.19.1.100

200.2.5.0 3 144.19.1.101

199.23.3.0 4 130.21.5.30

131.200.0.0 7 130.21.5.32

Routeur 144.19.1.102

Destination Distance

144.19.0.0 3

200.1.1.0 4

200.2.5.0 2

199.23.3.0 6

131.200.0.0 9


144.19.0.0 0 Direct

130.21.0.0 0 Direct

200.1.1.0 4 144.19.1.102

200.2.5.0 2 144.19.1.102

199.23.3.0 4 130.21.5.30

131.200.0.0 7 130.21.5.32

Mise à jour

Comparaison

Principe RIP Suppression d’une route

•La distance maximal est de 16 (count to infinity) et correspond à un réseau inaccessible.

•Après 3 minutes (invalid timer), une route sur laquelle on n’a plus d’information devient inaccessible (coût de 16).

• Elle sera détruite de la table de routage 1 minute plus tard (route flush timer), de façon à diffuser l’information aux autres routeurs.

Problèmes liés à RIP Les protocoles à vecteur de distance ne communiquent leur informations que périodiquement Il se peut donc qu'il y ait des retards dans la propagation des mises à jour sur l'ensemble des routeurs du réseau

Lorsque les routes changent rapidement c’est possible d’avoir de mauvais

calcul de route Le routage ne sera alors pas optimisé ou des datagrammes seront

perdus.

. 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 Il apparaît donc que ce type de protocole n'est pas bien adapté

aux réseaux de grande taille.

Limitation du métrique à 16.

RIP ignore la notion d’adressage de sous-réseau ( la version RIP2 , le prend en charge )

Résolution du problème de convergence lente.

• Split horizon : Le routeur enregistre l'interface sur laquelle il reçoit les

nouvelles routes, il n'enverra pas les mises à jour de routage sur ces interfaces.

• Flash update : Le routeur n'attend pas l'expiration de son intervalle de diffusion

pour diffuser l'information.

IGRP : Interior Gateway Routing Protocol

I G R P (vecteur de distance)

•IGRP : Interior Gateway Routing Protocol est un protocole à vecteur de distance mis au point par CISCO

Informations de routage diffusées toutes les 90 secondes.

• la métrique utilisé est une combinaison de :

Bande passante

Délai

Charge du lien

Fiabilité (taux de succès)

Unité de transfert d'information maximale (MTU)

Exemple

Schéma : il existe 2 chemins possibles entre les deux postes.

Le chemin le plus court mais le plus lent sera choisi par RIP.

Le chemin le plus long mais le plus rapide sera choisi par IGRP.

19.2 Kbits/s

1.5 Mbits/s

1.5 Mbits/s1.5 Mbits/s

Routage avec état de lienOSPF : Open Shortest Path First

Routage avec état de lien

• Les protocoles à vecteur de distance ne sont pas bien adaptés aux réseaux de grande taille.

• Les protocoles de routage à état de lien maintient une Base de Données représentant la topologie complète du réseau .

• Cette BDD permet d'établir une carte représentée sous forme d'un arbre dans lequel les routeurs sont les nœuds et les réseaux sont les arcs. La racine de l'arbre est le routeur lui-même.

• A partir de cet arbre, calcule le chemin le plus court vers les destinations du réseau en partant de lui-même il peut ainsi construire sa table de routage.

• Le calcul est effectué indépendamment sur chaque routeur la convergence est donc rapide.

• Les routeurs OSPF échangent des informations concernant l'état de

leurs liaisons ( LSA ) .

• L'état d’un lien peut être : up (en activité) ou down (hors service).

• Connaître l'état d'une liaison permet à un routeur de savoir s'il existe

un chemin de communication direct entre deux routeurs.

• Chaque lien comporte une métrique ( un poids ) pas forcément le

nombre de sauts .

OSPF : Open Shortest Path First

OSPF Découverte du réseau

•Au démarrage , un routeur détecte les réseaux qui lui sont directement

connectés , et il initialise ça base de données topologique.

• par la suite , il sollicite touts les routeurs pour avoir des informations il

demande leurs base de données topologique .

•On se basant sur ces informations il va mettre à jour ça bases de données pour se

synchroniser donc l’ensemble de routeur vont avoir la même base de données

d'informations.

A

B

CD

E4 (R1)

1 ( R2)

2 ( R5)

6 (R6)

12 ( R3)

3 (R4)

A B C D E

B 12 A 12 B 6 A 1 A 4

D 1 C 6 D 2 C 2 C 3

E 4 E 3

Exemple de découverte du réseau pour le routeur A.

Calcul du plus court chemin • L'algorithme de routage Shortest Path First (SPF) sert de base aux opérations d'OSPF

il se base sur l’algorithme de Djikstra pour le calcul du plus cours chemin.

• le principe consiste à construire un arbre dont la racine est le routeur qui exécute l’algorithme .

• étapes 1 : Initialement , on place le routeur à la racine , en suite on place les routeurs qui lui sont directement accessible en indiquant les métriques correspondantes.

• étape2 : Par la suite , on prend la branche qui possède le plus petit poids et on place le routeur associé comme routeur racine , et on refait l’étape 1.

• étape 3 : Si on trouve une autre branche ayant un poids inférieur alors on abondons la branche courante et on refait l’étape 1 à partir de la nouvelle branche, jusqu’à traiter toute les chemin

• L’arbre calculé des plus courts chemins permet de construire la table de routage.

A

EDB

12 41

A

EB

12 41

D

C

2

A

EB

12 41

D

2

C

B E

6 3

A

41

D

2

C

B

6

E

C

3

A

41

D

2

C6

E

6

C

B

A

41

D

2

C6

E

B

Exemple : calcul de

l’arbre à partir de A A

B

CD

E4 (R1)

1 ( R2)

2 ( R5)

6 (R6)

12 ( R3)

3 (R4)

Génération de la nouvelle base de données

A

41

D

2

C6

E

B

A

B

CD

E4 (R1)

1 (R2)

2 (R5)

6 (R6)

12 (R3)3 (R4)

Destination

Passer par

Coût

A direct 0

B D 9

C D 3

D D 1

E E 4

Destination Passer par Coût

R1 direct 0

R2 direct 0

R3 direct 0

R3 D 9

R6 D 9

R4 D 3

R5 D 3

R6 D 3

R2 D 1

R5 D 1

R1 E 4

R4 E 4


R1, R2, R3 direct 0

R3, R6 D 9

R4, R5, R6 D 3

R2, R5 D 1

R1, R4 E 4

Génération de la nouvelle table de routageDestinatio

nPasser par Coût

A direct 0

B D 9

C D 3

D D 1

E E 4


R1 direct 0

R2 direct 0

R3 direct 0

R4 D 3

R6 D 3

R5 D 1

Génération de la nouvelle base de données

S’il y a une redondance

choisir la route

ayant le plus petit coût


R1 direct 0

R2 direct 0

R3 direct 0

R3 D 9

R6 D 9

R4 D 3

R5 D 3

R6 D 3

R2 D 1

R5 D 1

R1 E 4

R4 E 4

Exercice

A

B

CD

E4 (R1)

1 (R2)

3 (R5)

1 (R6)

2 (R3)

3 (R4)

Donner la table de routage du routeur A

OSPF (suite)Inconvénients du routage à état de liaison

•Traitement et MémoireLes routeurs doivent utiliser plus de mémoire et exécuter plus de traitements que pour les protocoles à

vecteur de distance.

Les routeurs mettent à jour leurs données par rapport à tous les autres routeurs Leur mémoire doit donc

être en mesure de contenir toute cette information.

Bande passanteLa largeur de bande consacrée à l'inondation initiale ( découverte du réseau ) de données peut être très

importante. Tous les routeurs transmettent des données de mise à jour à tous les autres routeurs. Ce

processus réduit temporairement la quantité de bande passante disponible pour les utilisateurs.

Ensuite, les protocoles nécessitent peu de bande passante pour transmettre des mise à jour qui ne reflètent

que des changements topologiques.

Amélioration de l’OSPF • Pour améliorer les performance du protocole OSPF , le réseau est découpé en

plusieurs zone ( area )

• Chaque area contient un ensemble de routeurs ( < 50 )

• Les routeur à l’intérieurs d’une zone sont dits routeurs internes et il utilise utilise le protocole OSPF .

• Il existe des routeur qui permet de relier les différentes zone.

• ces routeur appartienne à une zone appelée BACKBONE ( area 0 ), qui consiste en un ensemble de routeurs qui permet de relier les différentes area.

• Les routeur d’une zone qui communique avec la zone 0 sont dit routeur de brodeur ( ABR : Area Border Routers).)

Les routeur R1, R2, R3 et R4 appartient à l’area 1



Les routeurs R4, R5, R6, R10, R11, et R12 constituent le backbone ( area 0 )

OSPF avec un découpage en zone• Une base de données topologiques est une vue globale des réseaux en relation avec des

routeurs.

• La base de données topologiques contient la collection de LSAs reçue de tous les routeurs dans la même zone.

• Dans une zone , les bases de données topologiques de tous les routeurs sont identiques.

• La topologie d'une zone est invisible en dehors de la zone . En conservant des topologies des zone séparées OSPF génère moins de trafic de routage.

• La division en zone crée deux types de routages le routage intra-zone et le routage inter-zone.

• Les routeur du Backbone ( zone 0 ) utilise l’OSPF est responsable de l'acheminement de l'information de routage entre les zone. Elle se compose de tous les routeurs de frontière de secteur (Area Border Routers).

Router A - Internal Router

interface ethernet 1ip address 131.108.1.1 255.255.255.0

router ospf 1network 131.108.0.0 0.0.255.255 area 1

Router B - Internal Router


router ospf 202network 131.108.0.0 0.0.255.255 area 1

Router C - Area Border Router


interface serial 0ip address 131.108.2.3 255.255.255.0

router ospf 999network 131.108.1.0 0.0.0.255 area 1network 131.108.2.0 0.0.0.255 area 0

Exemple de configuration de l’OSPF avec des routeur CISCO

Documents

9.routage dynamique