Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

UPMC - Licence Informatique 3I014 - Réseaux 1 TD 5 ROUTAGE 1. GENERALITES 1.1.

UPMC - Licence Informatique 3I014 - Réseaux 1 TD 5 ROUTAGE 1. GENERALITES 1.1. Définitions Le routage est le processus qui consiste, dans un réseau, ou au travers de différents réseaux, à trouver un chemin entre une source et une destination. C’est l'une des fonctionnalités principales de la couche réseau. On appelle routeur un équipement relié à au moins deux réseaux et dont le rôle est de réémettre des paquets venus d'une de ses interfaces vers une autre. Schématiquement, on peut représenter l'Internet comme une hiérarchie de routeurs. On appelle système autonome (Autonomous System ou AS) un ensemble de routeurs et de réseaux contrôlés par une même autorité administrative ; on peut donc voir l’Internet comme un ensemble d'AS. On distingue les routeurs situés à l'intérieur d'un même AS de ceux qui permettent de relier entre eux différents AS. A l'intérieur d'un AS, on parle de protocoles de routage intra-domaine (Interior Gateway Protocol ou IGP) ; entre différents AS, il s'agit de protocoles de routage inter-domaines (Exterior Gateway Protocol ou EGP). Le terme « routage » est utilisé en français pour désigner deux fonctions très différentes : § La fonction d’adaptation des chemins (routing) dont le but est de construire et de mettre à jour des tables de routage dans les routeurs (et commutateurs) du réseau, cette fonction étant réalisée à l’aide des protocoles de routage ; § La fonction d’acheminement (forwarding) dont le but est de trouver un chemin pour chaque paquet arrivant sur l’entrée d’un routeur (ou d’un commutateur), cette fonction étant réalisée par consultation des tables de routage (ou de commutation). Une table de routage comporte au moins deux colonnes : la première pour la destination (ou pour le réseau de destination) et la seconde pour l'adresse de l'élément réseau correspondant au « saut » suivant (next hop) sur le « meilleur » chemin vers la destination souhaitée. 1.2. Protocoles de routage 1.2.1. Quelles sont les propriétés que doit posséder un « bon » protocole de routage ? Tout protocole de routage doit communiquer des informations sur la topologie globale du réseau à chaque routeur afin que celui-ci puisse prendre une décision locale de routage. Or, cette information globale est difficile à collecter, sujette à des modifications fréquentes et de plus, volumineuse. Un « bon » protocole de routage visera donc : § une minimisation des messages de contrôle échangés ; § une minimisation de l'espace des tables de routage : tout d'abord, pour minimiser le coût des routeurs, et ensuite pour minimiser le trafic d'information de routage (puisque les routeurs s'échangent leurs tables de routage pour garantir une vue consistante de la topologie du réseau) ; § la robustesse : éviter les trous noirs, les boucles et les oscillations ; UPMC - Licence Informatique 3I014 - Réseaux 2 § l'utilisation du chemin « optimal », qui n'est pas forcément le plus court : il peut s'agir du chemin au délai le plus court, du chemin le plus sécurisé, du chemin le moins cher, ou tout simplement du chemin utilisant le moins de sauts. Le routage est, par essence, un problème de la théorie des graphes : il s'agit de trouver le chemin de coût minimum entre deux nœuds quelconques, sachant que le coût d'un chemin est la somme des coûts des liens qui le composent. Il existe plusieurs classes de techniques de routage : § Le routage isolé : cette classe regroupe des techniques qui ne nécessitent aucun échange d'information entre les nœuds et ne construisent pas de table de routage. Comme exemple de routage isolé, on peut citer le routage par inondation dans lequel chaque nœud retransmet toujours tous les paquets sur toutes ses interfaces, sauf l'interface entrante. § Le routage centralisé : on dispose d'un centre de contrôle de routage qui reçoit périodiquement des informations décrivant l'encombrement du réseau. Il en déduit les tables de routage de chaque routeur et les leur expédie. § Le routage distribué : chaque routeur échange périodiquement des informations avec ses voisins et recalcule sa table de routage. Deux types d'algorithmes de routage distribué sont largement utilisés : – Le routage à vecteurs de distance (utilisé par exemple avec le protocole RIP) ; – Le routage à état des liens (utilisé par exemple avec le protocole OSPF). Dans ce TD nous nous intéresserons principalement aux algorithmes à vecteurs de distance et à états des liens. Leurs caractéristiques communes sont les suivantes : § ils supposent que chaque routeur connaît l'adresse de chacun de ses voisins, ainsi que le « coût » pour l'atteindre ; § ils permettent à chaque routeur de déterminer l'information de routage globale, i.e. le prochain nœud pour atteindre chaque destination possible sur la route la plus courte, en échangeant de l'information de routage seulement avec ses voisins. 2. ALGORITHMES A VECTEURS DE DISTANCE 2.1. Principe L'algorithme de base est dû à Bellman-Ford. Chaque nœud est supposé connaître la « distance » (ou le « coût ») qui le sépare de chacun de ses voisins (une liaison hors service a un coût infini). Périodiquement, chaque nœud envoie à chacun de ses voisins la liste des distances estimées vers chaque nœud du réseau : c'est le vecteur de distance. Il reçoit en retour une liste similaire de chacun de ses voisins. Lorsque le nœud i reçoit le vecteur de distance Vj de son nœud voisin j, Vj(k) lui donne la distance (estimée par j) pour aller de j à k, et il sait donc qu'il peut atteindre k via j, avec un coût de Vj(k) augmenté du coût de sa liaison à j. En poursuivant ce calcul pour chacun de ses voisins, i peut déterminer l'estimation qui lui semble la meilleure pour atteindre chaque destination, et inscrire cette estimation ainsi que la liaison correspondante dans sa table de routage. UPMC - Licence Informatique 3I014 - Réseaux 3 2.2. Exercices 2.2.1. Soit le réseau composé des 5 nœuds A, B, C, D et E, et des 6 liaisons Vab, Vad, Vbc, Vbe, Vce et Vde. A chaque liaison, supposée symétrique, est associée une distance égale à 1. L'algorithme utilisé par le protocole de routage est de type Bellman-Ford. A B C D E Vab Vad Vde Vbe Vbc Vce a. On supposera que le réseau vient d'être mis en service et que chaque nœud n'a qu'une connaissance locale de la topologie du réseau (il ne connaît que ses voisins). Donner les tables de routage initiales des différents nœuds. T0 état initial Les tables de routage sont : A B C D E dest next dist dest next dist dest next dist dest next dist dest next dist B B 1 A A 1 B B 1 A A 1 B B 1 D D 1 C C 1 E E 1 E E 1 C C 1 E E 1 D D 1 b. On considèrera la séquence d'échange de vecteurs de distance suivante : T1 B, D reçoivent VA (vecteur de distance de A) T2 A, C, E reçoivent VB T3 A, E reçoivent VD T4 B, D reçoivent VA, VE T5 B, E reçoivent VC T6 A reçoit VB T7 C, D reçoivent VE Donnez la table de routage (incluant les distances) de chaque nœud, obtenue une fois que l'algorithme de routage a convergé. T1 B, D reçoivent VA = (B1, D1) B traite VA : il sait maintenant qu'il peut joindre D via A avec un coût de 1 (le D1) plus le coût de sa propre liaison avec A (1) ; B met à jour sa table de routage. D traite VA : il sait maintenant qu'il peut joindre B via A avec un coût de 1 (le B1) plus le coût de sa propre liaison avec A (1) ; D met à jour sa table de routage. UPMC - Licence Informatique 3I014 - Réseaux 4 A B C D E dest next dist dest next dist dest next dist dest next dist dest next dist B B 1 A A 1 B B 1 A A 1 B B 1 D D 1 C C 1 E E 1 B A 2 C C 1 D A 2 E E 1 D D 1 E E 1 T2 A, C, E reçoivent VB = (A1, C1, D2, E1) A traite VB : il sait maintenant qu'il peut joindre C via B avec un coût de 1 (le C1) plus le coût de sa propre liaison avec B (1), d'où une nouvelle entrée dans la table de routage; il sait qu'il peut joindre D via B avec un coût de 2+1 = 3, ce qui est supérieur à son coût courant, donc pas de modification pour l'entrée correspondant à D; il sait qu'il peut joindre E via B avec un coût de 1+1 = 2, d'où une nouvelle entrée dans la table. Idem pour C et E. A B C D E dest next dist dest next dist dest next dist dest next dist dest next dist B B 1 A A 1 A uploads/Ingenierie_Lourd/ outage.pdf