Vidéo d'introduction aux protocoles de routage
Pour bien suivre ce cours, il est nécessaire de maitriser les bases sur les réseaux (réseau local, adresse IP, adresse réseau...) N'hésitez pas à vous replonger dans le cours de première si nécessaire.
Les réseaux locaux peuvent être reliés entre eux par l'intermédiaire de routeurs. Il ne faut jamais perdre de vue qu'Internet résulte de l'interconnexion de réseaux par des routeurs.
Nous avons sur ce schéma les éléments suivants :
- 15 ordinateurs : M1 à M15
- 6 switchs : R1 à R6
- 8 routeurs : A, B, C, D, E, F, G et H
Comme nous l'avons déjà dit ci-dessus, un routeur permet de relier ensemble plusieurs réseaux locaux. Un routeur est composé d’un nombre plus ou moins important d’interfaces réseau (cartes réseau). Les routeurs les plus simples que l’on puisse rencontrer permettent de relier ensemble deux réseaux (ils possèdent alors 2 interfaces réseau), mais il existe des routeurs capables de relier ensemble une dizaine de réseaux. N'importe quel ordinateur peut jouer le rôle de routeur (à partir du moment où il possède au moins 2 interfaces réseau), mais on rencontre souvent des "machines" dédiées (par exemple de marque CISCO)
Revenons maintenant à l’analyse de notre schéma :
Nous avons 6 réseaux locaux, chaque réseau local possède son propre switch.
Les ordinateurs M1, M2 et M3 appartiennent au réseau local 1. Les ordinateurs M4, M5 et M6 appartiennent au réseau local 2. Nous pouvons synthétiser tout cela comme suit :
- réseau local 1 : M1, M2 et M3
- réseau local 2 : M4, M5 et M6
Exemple : M13 veut communiquer avec M9
Nous pouvons avoir : M13 → R6 → Routeur G → Routeur F → Routeur E → R4 → M9
ou encore : M13 → R6 → Routeur G → Routeur F → Routeur H → Routeur C → Routeur D → Routeur E → R4 → M9
On pourrait penser que le chemin "Routeur F → Routeur E" est plus rapide et donc préférable au chemin "Routeur F → Routeur H", cela est sans doute vrai, mais imaginez qu’il y ait un problème technique entre le Routeur F et le Routeur E, l’existence du chemin "Routeur F → Routeur H" permettra tout de même d’établir une communication entre M13 et M9.
Déterminer un chemin possible permettant d’établir une connexion entre la machine M4 et M14.
On peut se poser la question : comment les switchs ou les routeurs procèdent pour amener les paquets à bon port.
Nous avons vu l'année dernière que 2 machines appartenant au même réseau local doivent avoir la même adresse réseau . Dans le schéma ci-dessus M1 et M4 n'ont pas la même adresse réseau (car elles n'appartiennent pas au même réseau local), si M1 cherche à entrer en communication avec M4, le switch R1 va constater que M4 n'appartient pas au réseau local (grâce à son adresse IP), R1 va donc envoyer le paquet de données vers le routeur A. Cela sera donc au routeur A de gérer le "problème" : comment atteindre M4 ?
Chaque routeur possède une table de routage. Une table de routage peut être vue comme un tableau qui va contenir des informations permettant au routeur d'envoyer le paquet de données dans la "bonne direction".
Soit le schéma suivant :
Étudiez attentivement le schéma ci-dessus. Le choix des adresses IP des machines a été fait au "hasard" (ne cherchez pas une signification là où il n'y en a pas). En revanche, vérifiez que tout est cohérent : adresses machines avec adresses réseaux (les adresses réseaux sont notées à côté des différents switch (par exemple le switch R1 est utilisé dans le réseau d'adresse 172.168.0.0/16)).
Vous avez sans doute remarqué que nous avons 2 routeurs :
- le routeur A qui possède 3 interfaces réseau que l'on nomme eth0, eth1 et eth2. Les adresses IP liées à ces interfaces réseau sont : 172.168.255.254/16 (eth0), 172.169.255.254/16 (eth2) et 192.168.7.1/24 (eth1)
- le routeur G qui possède 2 interfaces réseau que l'on nomme eth0 et eth1. Les adresses IP liées à ces interfaces réseau sont : 10.255.255.254/8 (eth0) et 192.168.7.2/24 (eth1)
Voici les informations présentes dans la table de routage de A :
- le routeur A est directement relié au réseau 172.168.0.0/16 par l'intermédiaire de son interface eth0
- le routeur A est directement relié au réseau 172.169.0.0/16 par l'intermédiaire de son interface eth2
- le routeur A est directement relié au réseau 192.168.7.0/24 par l'intermédiaire de son interface eth1 (le réseau 192.168.7.0/24 est un peu particulier car il est uniquement composé des routeurs A et G)
- le routeur A n'est pas directement relié au réseau 10.0.0.0/8 mais par contre il "sait" que les paquets à destination de ce réseau doivent être envoyé à la machine d'adresse IP 192.168.7.2/24 (c'est à dire le routeur G qui lui est directement relié au réseau 10.0.0.0/8)
On peut résumer tout cela avec le tableau suivant (table de routage simplifiée de A) :
| Réseau | Moyen de l'atteindre | Métrique |
|---|---|---|
| 172.168.0.0/16 | eth0 | 0 |
| 192.168.7.0/24 | eth1 | 0 |
| 172.169.0.0/16 | eth2 | 0 |
| 10.0.0.0/8 | 192.168.7.2/24 | 1 |
Même si dans les véritables tables de routage ont utlise exclusivement les adresses IP, on pourra, dans le cadre de ce cours, utiliser les noms à la place des adresses IP (On dira pour le schéma ci-dessus que M1, M2 et M3 appartiennent au réseau R1, M4, M5 et M6 appartiennent au réseau R2 et que M7 et M8 appartiennent au réseau R3).
On aura alors la table de routage écrit de cette façon :
| Réseau | Moyen de l'atteindre | Métrique |
|---|---|---|
| réseau R1 | eth0 | 0 |
| Routeur G | eth1 | 0 |
| Réseau R3 | eth2 | 0 |
| Réseau R2 | Routeur G | 1 |
On peut traduire ce tableau par :
- pour atteindre le réseau R1, on doit "sortir" du routeur par eth0 (le réseau R1 est directement relié au routeur A)
- pour atteindre le réseau R3, on doit "sortir" du routeur par eth2 (le réseau R3 est directement relié au routeur A)
- pour atteindre le routeur G, on doit "sortir" du routeur par eth1 (le routeur G est directement relié au routeur A)
- pour atteindre le réseau R2, on doit "envoyer" le paquet de données vers le routeur G qui "saura quoi faire avec" (le réseau R2 n'est pas directement relié au routeur A)
Déterminez la table de routage du routeur G (ne pas tenir compte de la colonne métrique pour le moment)
Dans des réseaux très complexes, chaque routeur aura une table de routage qui comportera de très nombreuses lignes (des dizaines voir des centaines...). En effet chaque routeur devra savoir vers quelle interface réseau il faudra envoyer un paquet afin qu'il puisse atteindre sa destination. On peut trouver dans une table de routage plusieurs lignes pour une même destination, il peut en effet, à partir d'un routeur donné, exister plusieurs chemins possibles pour atteindre la destination. Dans le cas où il existe plusieurs chemins possibles pour atteindre la même destination, le routeur va choisir le "chemin le plus court". Pour choisir ce chemin le plus court, le routeur va utiliser la métrique : plus la valeur de la métrique est petite, plus le chemin pour atteindre le réseau est "court". Un réseau directement lié à un routeur aura une métrique de 0.
Comment un routeur arrive à remplir sa table de routage ?
La réponse est simple pour les réseaux qui sont directement reliés au routeur (métrique = 0), mais comment cela se passe-t-il pour les autres réseaux (métrique supérieure à zéro) ?
Il existe 2 méthodes :
- le routage statique : chaque ligne doit être renseignée "à la main". Cette solution est seulement envisageable pour des très petits réseaux de réseaux
- le routage dynamique : tout se fait "automatiquement", on utilise des protocoles qui vont permettre de "découvrir" les différentes routes automatiquement afin de pouvoir remplir la table de routage tout aussi automatiquement.
Un peu de pratique
1 Commande ping en routage dynamique
1. Dans le logiciel filius, ouvrez le document Routage.fls
2. Passez en mode simulation en cliquant sur
.
3. Allez sur l’ordinateur dont l’adresse IP est 192.168.1.1 (en double cliquant sur cet ordinateur), puis installez le logiciel « Ligne de commande » .
4. Lancez le logiciel « Ligne de commande » , puis tapez la commande ping 192.168.2.2. Observez le chemin suivi par l’information. Vous remarquerez que tout se passe bien, aucun paquet n’est perdu, les deux ordinateurs peuvent communiquer sans problème.
2 Configuration des tables de routage en routage statique
1. Retournez en mode conception cliquant sur .
2. Double cliquez sur chacun des 4 routeurs et décochez la case « Routage automatique » . Vous pouvez vérifier que cette fois la commande ping ne fonctionne plus. Observez où s’arrêtent les paquets. Il va falloir configurer manuellement les tables de routage des routeurs de sorte que les ordinateurs puissent à nouveau communiquer.
3. Dans un premier temps, configurez la table de routage du routeur A et celle du routeur B pour que le ping entre 192.168.1.1 et 192.168.2.2 puisse fonctionner. Pour cela, il va falloir aller dans l’onglet « Table de routage » du routeur A et ajouter une ligne pour indiquer que tous les paquets à destination du réseau 192.168.2.0 (avec le masque 255.255.255.0) doivent être envoyés au routeur B (adresse 192.168.8.2) en sortant du routeur A par l’interface dont l’adresse IP est 192.168.8.1.
Là vous pouvez constater en réessayant le ping que les paquets arrivent bien à l’ordinateur 192.168.2.2, mais que la réponse n’arrive pas à destination. Il faudra alors configurer la table de routage du routeur B pour que le ping puisse réussir.
Protocoles de routage
Un réseau de réseaux comportant des routeurs peut être modélisé par un graphe : chaque routeur est un sommet et chaque liaison entre les routeurs ou entre un routeur et un switch est une arête. Les algorithmes utilisés par les protocoles de routages sont donc des algorithmes issus de la théorie de graphes.
On trouve plusieurs protocoles de routage, nous allons en étudier deux : RIP (Routing Information Protocol) et OSPF (Open Shortest Path First).
Représentation sous forme de graphe
Un réseau peut être schématisé sous forme de graphe.
Chaque sommet, désigné par une lettre, représente un routeur ou un hôte. Les arêtes entre les sommets correspondent aux sous-réseaux du graphe. On a de plus indiqué sur chaque arête un coût correspondant à la métrique choisie pour le protocole OSPF.
Ce graphe est non orienté (les liens sont à double-sens) et pondéré (un poids est affecté à chaque lien)
On pourrait construire un graphe dans lequel les sommets représenteraient les sous-réseaux et les arêtes les routeurs, mais on ne pourrait plus indiquer les coûts.
Le protocole RIP
Le protocole RIP utilise le nombre de sauts comme métrique, avec une limite fixée à 15 sauts pour éviter les boucles. On va choisir la route minimisant ce nombre. C’est un des protocoles les plus simples à mettre en place mais il n’est pas très efficace puisqu’il ne tient pas compte de la vitesse des connexions (bande passante…). Une métrique à 0 signifie que le réseau de destination est connecté au routeur, un métrique égal à 16 qu’il n’est pas joignable. Toutes les trente secondes, un routeur reçoit les tables de routage des routeurs voisins et les utilise pour mettre à jour sa propre table de routage en rajoutant les nouvelles destinations accessibles en au plus 15 sauts et modifiant les routes des destinations existantes si une solution en moins de sauts apparait.
Regardez cette vidéo de Claude Chaudet (Institut Mines-Télécom) qui expose le principe du routage à vecteur de distance.
Construction de la table de routage
Suivant le protocole RIP, le routeur va privilégier les routes avec le moins de sauts. La table de routage est construite étape par étape en commençant par les sommets accessibles directement, puis ceux accessibles en un saut, puis deux sauts…
Le principe de l'algorithme
Lorsqu'un routeur reçoit une nouvelle route de la part d'un voisin, 4 cas sont envisageables :- Il découvre une route vers un nouveau **réseau inconnu**
==> Il l'ajoute à sa table.
- Il découvre une route vers un réseau **connu**, **plus courte** que celle qu'il possède dans sa table
==> Il actualise sa table.
- Il découvre une route vers un réseau **connu**, **plus longue** que celle qu'il possède dans sa table
==> Il ignore cette route.
- Il reçoit une route vers un réseau **connu** en provenance d'un routeur **déjà existant dans sa table**
==> Il met à jour sa table car la topologie du réseau a été modifiée.
Tables de routage simplifiée du routeur A
Selon le protocole RIP
Protocole OSPF
Le protocole OSPF est un des trois protocoles de routage les plus utilisés sur Internet (avec IS-IS et BGP).
Le protocole OSPF (Open Shortest Path First) rentre dans la catégorie des protocoles à état de lien.
Dans le protocole à vecteur de distance que nous venons de voir, on cherche à minimiser le nombre de sauts, mais sans aucune garantie que le chemin emprunté soit en réalité le plus performant (en termes de débit par exemple). De plus avec RIP, chaque routeur ne connaît que ses voisins immédiats, il n'a donc pas connaissance de l'ensemble de la topologie du réseau. Enfin, le protocole RIP est limité aux petits réseaux (15 routeurs maximum) et est assez gourmand en termes de bande passante puisqu'il nécessite l'échange d'un volume de données assez important.
Cette vidéo de Claude Chaudet (Institut Mines-Télécom) expose le principe du routage à état de lien.
Le principe de l'algorithme
Le protocole OSPF propose une approche tout à fait différente : au lieu de s'intéresser au nombre de sauts, on va chercher à optimiser le débit des liaisons empruntées. Pour cela, chaque routeur va devoir connaître l'intégralité du réseau avec le débit associé à chaque lien afin d'appliquer un algorithme de recherche de chemin optimal.
On peut faire un parallèle entre le fonctionnement d'OSPF et celui de nos logiciels de guidage par GPS. En effet, dans ce type de logiciels :
- l'ensemble de la carte de France et de ses routes est connue du logiciel
- le type de chaque route est renseigné ainsi que la vitesse autorisée sur la route
- le calcul d'itinéraire va permettre le calcul d'un chemin permettant par exemple d'emprunter les routes sur lesquelles la vitesse est la plus importante (temps le plus court).
Le principe de l'algorithme repose sur celui de Djikstra
dans le cas d'un réseaux
Djisktra permet de minimiser la longueur d'un chemin, or nous souhaitons maximiser le débit sur nos liaisons. Il faut donc considérer l'inverse de la bande passante des liens pour appliquer Djisktra : maximiser les débit revient à minimiser l'inverse des débits.
Par exemple:
- 1 Gb/s sera affecté du poids 1
- 10 Gb/s sera affecté du poids 0.1
- 100 Mb/s sera affecté du poids 10
Tables de routage simplifiée du routeur A
Selon le protocole OSPF
On applique d’abord l’algorithme de Dijkstra pour déterminer les routes les plus rapides (selon la métrique utilisée) pour atteindre chaque destination. On peut ensuite faire la table de routage.
Vous voila prêt pour un TP 👍
voir nav bar