C6 Réseaux : Introduction au routage

PRONETIS©2014 - Philippe Prestigiacomo - Droits d'utilisation ou de reproduction réservésPRONETIS©2014 - Philippe Prestigiacomo - Droits d'utilisation ou de reproduction réservés

Interconnexion des réseaux - Routage

Concept de l’interconnexion

Équipement de la couche 3 - Domaine de broadcast

Détermination du chemin – Routage – Table de routage

Algorithmes de routage statiques et dynamiques

Routage à vecteur de distance et Routage par informations d’état de lien

Interconnexion inter-réseaux – Système autonome – Routage hiérarchique

Résumé des principaux protocoles de routage

Année 2014-2015

PRONETIS©2014 - Philippe Prestigiacomo - Droits d'utilisation ou de reproduction réservés

Principe : Généralité

� Concept de l’interconnexion

� Les routeurs (ou passerelles) possèdent une connexion sur chacun des réseaux:

Le routeur P interconnecte les réseaux A et B.

� Le rôle du routeur P est de transférer sur le réseau B, les paquets circulant sur le réseau A et destinés au réseau B et inversement.

2

P

Reseau A Reseau B


Principe : Généralité

� Concept de l’interconnexion

� P1 transfère sur le réseau B, les paquets circulant sur le réseau A et destinés auxréseaux B et C

� P1 doit avoir connaissance de la topologie du réseau; à savoir que C estaccessible depuis le réseau B.

� Le routage n'est pas effectué sur la base de la machine destinataire mais sur labase du réseau destinataire, donc de l’identifiant du réseau

3

P1

Reseau A Reseau B

P2

Reseau C


Réception d’un datagramme par un hôte et un routeur

� Parmi les opérations communes , figurent : � Vérification de la validité des champs IP « Header Length », « Total Length »

« Header Checksum » – Datagramme détruit en cas d’anomalie

� Traitement des options éventuelles

� Réassemblage en cas de fragmentation

� Parmi les opérations qui diffèrent

� Un hôte termine le traitement par la transmission du champ « Data » dupaquet réassemblé au protocole de niveau supérieur , identifié par le champ« protocol » de l’en-tête IP

� Un routeur quant à lui, retransmet le datagramme vers une autre machine .Il doit procéder en outre à la décrémentation de la valeur du champ « TTL » ,et si nécessaire à la fragmentation du paquet avant de le transmettre audriver de l’interface de niveau liaison approprié.

4


Equipement de la couche 3 - Symbole

� Routeur � Équipement de couche 3 permettant d’interconnecter deux réseaux ou plus en

se basant sur les adresses de couche 3.

� Le routeur permet également une segmentation des domaines de broadcast et des domaines de collisions.

5


Fonction de routage – couches TCP/IP

6

R1 R2Host AHost B

NETWORK

DATA LINK

PHYSICAL

NETWORK

DATA LINK

PHYSICALDE

CA

PS

ULA

TIO

N

DE

CA

PS

ULA

TIO

N

EN

CA

PS

ULA

TIO

N

EN

CA

PS

ULA

TIO

N

Domaine de Broadcast Domaine de BroadcastDomaine de Broadcast


� Processus de routage des datagrammes� Le routage est le processus permettant à un datagramme d’être acheminé vers le

destinataire lorsque celui-ci n’est pas sur le même réseau physique que l’émetteur.

� Le chemin parcouru est le résultat du processus de routage qui effectue les choixnécessaires afin d’acheminer le datagramme.

� Les routeurs forment une structure coopérative de telle manière qu’un datagrammetransite de routeur en routeur jusqu’à ce que l’un d’entre eux le délivre à sondestinataire. Un routeur possède plusieurs connexions réseaux tandis qu’une machinepossède généralement qu’une seule connexion.

7

Processus de routage


� Processus de routage des datagrammes

� Machines et routeurs participent au routage :

� les machines doivent déterminer si le datagramme doit être délivré sur le réseauphysique sur lequel elles sont connectées (routage direct) ou bien si le datagrammedoit être acheminé vers un routeur; dans ce cas (routage indirect), elle doit identifierle routeur approprié.

� les routeurs effectuent le choix de routage vers d’autres routeurs afin d’acheminer ledatagramme vers sa destination finale.

8

Processus de routage


Composante d’un routeur

Chaque routeur doit connaître l’adresse du routeur suivant sur le chemin.C’est pourquoi, le routeur doit gérer de manière statique ou dynamiqueune table de routage qui contient tous les réseaux accessibles et uneentrée de routage par défaut pour les destinations qui ne sont pasconnues directement.

� L’algorithme de routage est la partie logiciel de la couche réseau� Décider sur quelle ligne de sortie un paquet entrant doit être retransmis

� Décision prise pour chaque paquet entrant

� La table de routage constitue la base d’informations mise à jourpar l’algorithme de routage (composée en général d’un tripletadresse destination, route à prendre, coût)

9


Composante d’un routeur

10

Table de

Routage

133.22.55.128 17.214.136.245

File d’attente

Algorithme

de routage

17.214.136.245

195.23.69.28

133.22.55.128

Port d’entré

PRONETIS©2014 - Philippe Prestigiacomo - Droits d'utilisation ou de reproduction réservés11

Table de routage Routeur 1

Table de routageLivre Dunod Le Réseau Internet

Un paquet en provenancede 10.0.0.0/8 à destinationde 17.8.23.128/25 passerapar R1, puis par R2 etarrivera à destination

Routeur 1

Routeur 3

Routeur 2

192.169.1.0/25

10.0.0.0/8

17.8.23.128/25

172.16.0.0/24


Procédure appliquée pour router un datagramme

12

� Étape N°1 : Appliquer le(s) masque(s) du (des) réseau(x) local (aux) àl’adresse destination du datagramme; Comparer le résultat à l’entréeRéseau destination correspondante pour déterminer si la destinationappartient à un réseau local; si c’est le cas, faire sortir le datagrammepar l’interface liée à ce réseau; sinon passer à l’étape N°2

� Étape N°2 : Appliquer les masques contenus dans la table deroutage et comparer le résultat à l’entrée réseau destinationcorrespondante; si la destination appartient à l’un de ces réseaux, fairesortir le paquet par la sortie correspondante, et l’envoyer au prochainrouteur indiqué dans la table. Si aucune entrée de la table ne contient ladestination du datagramme, le détruire. En pratique, on définit une routepar défaut caractérisée par l’adresse destination 0.0.0.0 et la masque0.0.0.0


Algorithme de routage

� Propriétés d’un algorithme de routage� Exactitude, simplicité

� Robustesse – Acceptation des défaillances, changement de topologie et de trafic

� Stabilité et performance - Convergence rapide vers un équilibre

« Il faut distinguer une politique d’acheminement qui indiquecomment est choisie une route, du protocole de routage qui décritcomment sont construites les tables d’acheminement, c’est-à-direque ce protocole spécifie les échanges d’information entre nœuds,le mode de calcul de route et de coût. »

13


Algorithme de routage

� Compromis à faire – « Dilemme »� minimiser le délai moyen de traversée des paquets appartenant à une même

connexion versus maximiser le flux total du réseau pour l’ensemble desconnexions.

� Solution de compromis pour une majorité de réseau� Minimiser le nombre de sauts (de nœuds traversés) qu’un paquet doit faire

� Réduire ce nombre améliore les délais et réduit aussi la capacité de transport consommée et donc améliore le débit global

� Les routeurs ont besoin de découvrir la topologie réseau

� Les routeurs s’échangent des informations� Les routes valides et coûts associés

� Les routeurs dialoguent entre eux en utilisant un protocole de routage

14


Détermination du chemin

� Les méthodes de sélection du chemin permettent aux équipements decouche 3, les routeurs, de déterminer la route à suivre pour acheminerles informations au travers de différents réseaux.

� Les services de routage utilisent les informations de topologie du réseaupour évaluer les chemins. Ce processus prend en compte les« métriques » comme :� Nombre de routeurs à franchir pour joindre la destination : Hop count

� Vitesse des liaisons (débit) , etc.

15

Nombre de sauts Vitesse des liaisons


Détermination du chemin : les métriques

16

Quel est le meilleur chemin si le métrique est le nombre de sauts et si le métrique est le débit ?

En rouge , le meilleur chemin, avec le métrique basé sur le nombre de sautsEn marron, le meilleur chemin avec le métrique basé sur la vitesse des liaisons


Famille d’algorithmes de routage

� Famille des algorithmes de routage� Algorithmes non adaptatifs – routage statique : ne fondent pas leurs décisions

de routage sur des mesures ou des estimations du trafic et de la topologie

� Algorithmes adaptatifs : modifient leurs décisions en fonction des changementsde topologie, du trafic dans le réseau

� EnvironnementLes routeurs ou les lignes de communication peuvent tomber en panne etredevenir opérationnel en un court instant ….

Entraînant des perturbations au niveau des routeurs et certains peuvent avoirune vision inexacte de la topologie courante du réseau.

17


Routage statique

� Configuré manuellement par l’administrateur� Interface de sortie du routeur

� Prochaine adresse IP à atteindre (Next Hop)

18


Famille d’algorithmes de routage

� Algorithmes de routage adaptatifs diffèrent selon : � L’endroit où ils se procurent l’information (routeur adjacent, toutes les « x » ms,

lorsque le trafic réseau change ou bien la topologie)

� Le métrique d’optimisation utilisé : nombre de sauts, temps de traversée duréseau, vitesse des liaisons

� Deux types d’algorithmes de routage dynamique existent� Les algorithmes à vecteurs de distance pour lesquels les informations

échangées permettent pour chaque routeur de retenir la plus courte distance(le plus petit nombre de sauts) pour atteindre une destination

� Les algorithmes à état des liens basés sur la transmission d’une cartecomplète des liens possibles entre les routeurs, ceux-ci doivent ensuitelocalement calculer les meilleures routes pour une destination.

19


Routage dynamique à Vecteur de distance

� Principe� Chaque routeur dispose d’une table de routage précisant pour chaque

destination, la meilleure distance connue et par quelle ligne l’atteindre

� Distance Vectoring Routing� Métrique : nombre de sauts

� Connaissance de la distance qui sépare le routeur avec tous ses voisins

� Vecteur de distance : pour une destination donnée, la meilleure distance connue et par quelle ligne l’atteindre.

� Ces vecteurs sont contenus dans la table de routage

Se référer au livre Le réseau Internet Dunod

20


Routage dynamique à vecteur de distance

� Principe de fonctionnement� Toutes les « x » seconde, chaque routeur envoie un vecteur d’informations de

distance à ses voisins immédiats (les autres routeurs qui sont connectés auxmêmes réseaux physiques)

� Maintenance des listes des routes sous la forme : [ D, A ]

� D est la distance (selon le métrique choisi) qui sépare du réseau ou de la machine� A est l’adresse de destination (réseau ou machine)

� Le routeur qui reçoit les informations compare les routes reçues avec ses propres routes connues et met à jour sa table de routage.

21



22

L’entrée pour atteindre le réseau 4 est modifiée car le routeur J connaît une route plus courte. Le nombre de saut transmis est de 3, le routeur A ajoute 1 saut pour aller jusqu’à J.



� « Temps de convergence »� Convergence rapide en cas de « bonne nouvelle »

� Convergence lente en cas de « mauvaise nouvelle »

� Dans un sous-réseau dont la plus longue distance correspond par exemple à N sauts, au bout de N échanges de listes vectorielles tout le monde aura réactualisé les destinations

� Principales inconvénients� La taille des informations de routage est proportionnelle au nombre de routeurs

interconnectés, donc les informations échangées peuvent être volumineuses et peuvent saturer le réseau

� Les routeurs n’ont la connaissance d’un changement d’état du réseau que lorsque leur voisin le leur communique, ce qui peut être long.

23


Présentation du protocole RIP – Vecteur de distance

24


Présentation du protocole RIP – Vecteur de distance

25

Au démarrage, RIP demande les informations de ses voisins:

- Il envoie une requète sur le port UDP 520- Rip demande le vecteur de distance complet de chaque voisin- Toutes les implémentations ne suivent pas cette règle

A la réception des tables des voisins, RIP met à jour sa table de routage et son propre vecteur de distance en tenant compte des informations recues

Toutes les 30 secondes, une partie ou l’ensemble du vecteur distance est envoyé aux voisins- Diffusé à plusieurs routeurs - Emis directement sur les liaisons P-to-P- Un cout RIP de 1 indique une connexion directe au réseau- RIP-1 est utilise le broadcast, RIP-2 le multicast


Protocole de routage par État des liens

26



27

Tous les routeurs possèdent à un instant donné, la même table des liens. Si le routeur Aveut envoyer un paquet vers le routeur C, il calcule le plus court chemin vers C etsélectionne le routeur B pour lui envoyer le paquet. B trouve à son tour le plus courtchemin vers C qui est direct.



28

Les routeurs diffusent périodiquement l’état de chacun de leurs liaisons

- Les messages d’état des liaisons sont utilisés pour mettre à jour la base de données décrivant la topologie du réseau

- Chaque routeur voit le même message d’état des liaisons - Le calcul des routes (Djikstra) s’appuie sur des toutes les informations recues par le

routeur

- Le cout d’une route dépend en grande partie :- Du nombres de sauts- De la Bande passante- De la priorité du protocole- Du délais




Présentation du protocole OSPF à État des liens

� OSPF - Open Shortest Path First� N'envoie pas aux routeurs adjacents le nombre de sauts qui les sépare, mais l'état de la

liaison qui les sépare.

� Chaque routeur est capable de dresser une carte de l'état du réseau et peut parconséquent choisir à tout moment la route la plus appropriée pour un message donné.

� Initialisation : un routeur demande la table de routage complète de sesvoisins� Pour initialiser la carte représentant la topologie du réseau

� « Inonde » le réseau avec l’état de leurs propres connexions

� Donne aux autres routeurs les informations nécessaires à la mise à jour de leur table� Inonde également le réseau quand un lien change d’état

� Pour le calcul du chemin le plus court� Utilisation de l’algorithme du plus court chemin – algorithme de Dijkstra

Se référer au livre Le réseau Internet Dunod

30



31

Exemple de coût dans OSPF – Le métrique choisit est le débit.Suivant la table des liens et les coûts associés, la route OSPF passera par R2, R3, etR4 avec un coût total de 13.



� Avantages� Les métriques ne sont pas limitées à la distance

� Demande moins de ressources par rapport à RIPV2

� Le routage n’échange pas d’information de distance comme l’algorithme àvecteur de distance mais uniquement l’état des liens vers leurs voisins, cequi diminue la bande passante consommée

� Les routeurs consolident l’information sur les liens provenant desautres routeurs pour construire la topologie complète du réseau et endéduire le chemin le plus court vers chaque réseau

En conclusion : les algorithmes à état de liens sont plus complexes maisplus performants et mieux adaptés au facteur d’échelle que les algorithmesà Vecteur de distance

32


Illustration – Interconnexion de systèmes autonomes

� Exemple : http://www.robtex.com/dns/polytech-marseille.fr.html

33


Résumé - Protocoles de routage

34


Résumé - Protocoles de routage

35


Pause-réflexion

Avez-vous des questions ?

36


Résumé du module

37

Table de routageTable de routage

Protocole deRoutage

Protocole deRoutage

Algorithme de routage à

État de lien


État de lien


Vecteur de distances


Vecteur de distances

Systèmes Autonomes

AS

Systèmes Autonomes

AS

Routage INTRA/EXTRA

domaine

Routage INTRA/EXTRA

domaine


FIN DU MODULE

38


ED

B

F

192.35.4.0

192.168.1.0

2

1

2 3

1

2

5

3

1

1

1

A

C

5

39

Réseau de Destination Moyen de l’atteindre Coût

192.35.4.0 D->E->F 5

192.168.1.0 D 2

Déterminer la table de routage de chacun des routeurs utilisant le protocole

OSPF, sous la forme : Exemple Routeur A


Déterminer la table de routage de chacun des routeurs,

sous la forme :

Exemple R1

Destination Routeur

192.212.46.0/24 Connecté

130.190.0.0/16 Connecté

210.10.10.0/25 Connecté

192.212.64.0/24 192.212.46.2

210.10.10.128/25 210.10.10.2


Destination Routeur

10.0.0.0/8 Connecté

192.169.1.0/25 Connecté


172.16.0.0/24 192.169.1.127

17.8.23.128/25 10.0.0.1

33.22.1.0/28 10.0.0.1

Destination Routeur

10.0.0.0/8 192.169.1.126

192.169.1.0/25 Connecté

1.3.22.0/16 192.169.1.126

172.16.0.0/24 Connecté

17.8.23.128/25 Connecté

33.22.1.0/28 17.8.23.130

Destination Routeur


192.169.1.0/25 10.0.0.3

1.3.22.0/16 10.0.0.3

172.16.0.0/24 17.8.23.129

17.8.23.128/25 Connecté

33.22.1.0/28 Connecté

Table de routage pour R1 Table de routage pour R2

Table de routage pour R3

Dessinez la topologie suivante avec l’aide des

informations fournies dans les tables de routages

Education

C6 Réseaux : Introduction au routage