Protocoles de Routage :¶

Rappels Network :¶

Comme nous l'avons précédemment observé, un cable éthernet peut suffire pour connecter deux machines, mais à partir de trois appareils il est nécessaire d'introduire un composant supplémentaire tel qu'un switch...

A faire vous même n°0 :

• Reprendre en main le logiciel Filius en refaisant les activtités de la page Simulation réseau proposée par David ROCHE ;

Les routeurs :¶

Pour interconnecter différents réseaux il est nécesaire d'introduire des routeurs.

Un routeur possède plusieurs interfaces (cartes) réseau qui vont lui permettrent de devenir la passerelle d'un réseau vers l'autre. Mais il ne suffit pas de connecter physiquement des routeurs pour que cela fonctionne...

Internet résulte de l’interconnexion de réseaux par des routeurs.

A faire vous même n°1 :

• Ouvrir dans filius le fichier ReseauComplexe.fls qui montre 15 machines réparties en 6 réseaux locaux et reliés par 8 routeurs.

• Observer ce shéma pour analyser les cas de communication suivants :

1. cas n°1 : M1 veut communiquer avec M3

Le paquet est envoyé de M1 vers le switch R1, R1 "constate" que M3 se trouve bien dans le réseau local 1, le paquet est donc envoyé directement vers M3.

On peut résumer le trajet du paquet par : M1 → R1 → M3

2. cas n°2 : M1 veut communiquer avec M6

Le paquet est envoyé de M1 vers le switch R1, R1 « constate » que M6 n’est pas sur le réseau local 1, R1 envoie donc le paquet vers le routeur A.

Le routeur A n’est pas connecté directement au réseau localR2 (réseau local de la machine M6), mais il "sait" que le routeur B est connecté au réseau local 2.

Le routeur A envoie le paquet vers le routeur B. Le routeur B est connecté au réseau local 2, il envoie le paquet au Switch R2. Le Switch R2 envoie le paquet à la machine M6.

Soit : M1 → R1→ Routeur A → Routeur B → R2 → M6

3. cas n°3 : M1 veut communiquer avec M9

M1 → R1 → Routeur A → Routeur B → Routeur D → Routeur E → R4 → M9

Ou bien : M1 → R1 → Routeur A → Routeur H → Routeur F → Routeur E → R4 → M9

Il est très important de bien comprendre qu’il existe souvent plusieurs chemins possibles pour relier 2 ordinateurs.

4. cas n°4 : 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.

5. cas n°5 : M4 veut communiquer avec M14

Déterminer un chemin possible permettant d’établir cette connexion

...

...

• Passer en mode simulation et utiliser la ligne de commande pour tester la communication entre machines avec un ping et la commande traceroute pour voir le chemin emprunté par les paquets...

Le routage :¶

Comment ça marche?

Deux machines dans le même réseau local doivent posséder la même adresse réseau.

Dans le schéma ci-dessous, on a noté les adresses IP des machines ainsi que les adresses réseaux (avec le switch).

La notation 175.3.1.2/16 signifie que c’est la machine 175.3.1.2 du réseau 175.3.0.0 (16 signifiant que les 16 premiers bits sont réservés à l’adresse réseau, ce qui correspond au masque 255.255.0.0).

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".

Dans le schéma précédent 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 : 175.3.255.254/16 (eth0), 192.168.5.1/24 (eth1) et 192.168.3.254/24 (eth2)
• 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.5.2/24 (eth1)

Voici les informations présentes dans la table de routage de A :

• le routeur A est directement relié au réseau 175.3.0.0/16 par l’intermédiaire de son interface eth0
• le routeur A est directement relié au réseau 192.168.3.0/24 par l’intermédiaire de son interface eth2
• le routeur A est directement relié au réseau 192.168.5.0/24 par l’intermédiaire de son interface eth1 (le réseau 192.168.5.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.5.2/24 (c’est à dire le routeur G qui lui est directement relié au réseau 10.0.0.0/8)

Ce qui peut se résumer par le tableau (simplifié) suivant : (la métrique correspond ici au nombre de "saut")

A faire vous même n°2 :

• Établir la table de routage du routeur G :

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.

A faire vous même n°3 :

• Faire le TP-TablesDeRoutage.pdf dans filius avec le fichier Routage.fls ;

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).

Le protocole RIP¶

Au départ, les tables de routage contiennent uniquement les réseaux qui sont directement reliés au routeur (dans notre exemple ci-dessus, à l’origine, la table de routage de A contient uniquement les réseaux 175.3.0.0/16, 192.168.5.0/24 et 192.168.3.0/24).

Chaque routeur envoie périodiquement (toutes les 30 secondes) à tous ses voisins (routeurs adjacents) un message. Ce message contient la liste de tous les réseaux qu’il connaît (dans l’exemple ci-dessus, le routeur A envoie un message au routeur G avec les informations suivantes : "je connais les réseaux 175.3.0.0/16, 192.168.5.0/24 et 192.168.3.0/24".

De la même manière G envoie un message à A avec les informations suivantes : "je connais les réseaux 192.168.5.0/24 et 10.0.0.0/8").

À la fin de cet échange, les routeurs mettent à jour leur table de routage avec les informations reçues (dans l’exemple ci-dessus, le routeur A va pouvoir ajouter le réseau 10.0.0.0/8 à sa table de routage. Le routeur A "sait" maintenant qu’un paquet à destination du réseau 10.0.0.0/8 devra transiter par le routeur G).

Pour renseigner la colonne "métrique", le protocole utilise le nombre de sauts, autrement dit, le nombre de routeurs qui doivent être traversés pour atteindre le réseau cible (dans la table de routage de A, on aura donc une métrique de 1 pour le réseau 10.0.0.0/8 car depuis A il est nécessaire de traverser le routeur G pour atteindre le réseau 10.0.0.0/8).

Le protocole RIP s’appuie sur l’algorithme de Bellman-Ford (algorithme qui permet de calculer les plus courts chemins dans un graphe).

A faire vous même n°4 :

Soit le réseau suivant:

• Établir la table de routage du routeur A en vous basant sur le protocole RIP (métrique = nombre de sauts).

• Quel est, d’après la table de routage construite ci-dessus, le chemin qui sera emprunté par un paquet pour aller d’une machine ayant pour adresse IP 172.18.1.1/16 à une machine ayant pour adresse IP 172.16.5.3/16 ?

...

...

Le protocole OSPF :¶

Comme dans le cas du protocole RIP, nous allons retrouver des échanges d’informations entre les routeurs (ces échanges sont plus "intelligents" dans le cas d’OSPF, ils permettent donc de réduire l’occupation du réseau).

Nous n’allons pas rentrer dans les détails de ces échanges et nous allons principalement insister sur la métrique produite par OSPF.

Le protocole OSPF, au contraire de RIP, n’utilise pas le "nombre de sauts nécessaire" pour établir la métrique, mais la notion de "coût des routes".

Dans les messages échangés par les routeurs on trouve le coût de chaque liaison (plus le coût est grand et moins la liaison est intéressante). Quand on parle de "liaison" on parle simplement du câble qui relie un routeur à un autre routeur.

Le protocole OSPF permet de connaître le coût de chaque liaison entre routeurs, et donc, de connaître le coût d’une route (en ajoutant le coût de chaque liaison traversée).

On notera que pour effectuer ces calculs, le protocole OSPF s’appuie sur l’algorithme de Dijkstra

Mais sur quoi repose cette notion de coût?

La notion de coût est directement liée au débit des liaisons entre les routeurs.

Le débit correspond au nombre de bits de données qu’il est possible de faire passer dans un réseau par seconde.

Le débit est donc donné en bits par seconde (bps), mais on trouve souvent des kilo bits par seconde (kbps) ou encore des méga bits par seconde (Mbps) => 1 kbps = 1000 bps et 1 Mbps = 1000 kbps.

Connaissant le débit d’une liaison, il est possible de calculer le coût d’une liaison à l’aide de la formule $ coût = 10^8 / débit$ avec le débit en bits par seconde.

Pour obtenir la métrique d’une route, il suffit d’additionner les coûts de chaque liaison (par exemple si pour aller d’un réseau 1 à un réseau 2 on doit traverser une liaison de coût 1, puis une liaison de coût 10 et enfin une liaison de coût 1, la métrique de cette route sera de 1 + 10 + 1 = 12)

Évidemment, comme dans le cas de RIP, les routes ayant les métriques les plus faibles sont privilégiées.

A faire vous même n°5 :

Soit le réseau suivant:

• En vous basant sur le protocole OSPF (métrique = somme des coûts), déterminer la table de routage du routeur A :

On donne les débits suivants :

• liaison routeur A - routeur B : 1 Mbps
• liaison routeur A - routeur C : 10 Mbps
• liaison routeur C - routeur B : 10 Mbps

• Quel est, d’après la table de routage construite ci-dessus, le chemin qui sera emprunté par un paquet pour aller d’une machine ayant pour adresse IP 172.18.1.1/16 à une machine ayant pour adresse IP 172.16.5.3/16 ?

...

...

Références aux programmes :¶

Architectures matérielles et réseaux :¶

Ce document, basé sur les travaux de David ROCHE et de Stephan VAN ZUIJLEN, est mis à disposition selon les termes de la Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International.

Pour toute question, suggestion ou commentaire : eric.madec@ecmorlaix.fr