Protocoles de Routage

Topologie d’un réseau

La fonction d’un réseau est d’interconnecter des machines entre elles, leur permettant ainsi d’échanger des informations, sous formes de paquets de données.

Un réseau est une interconnexion de réseaux plus petits, reliés entre eux par l’intermédiaire de routeurs, formant ainsi la topologie du réseau.

Exemple : un réseau reliant plusieurs LAN

Activité : routeurs
Sur le schéma du réseau donné en exemple plus haut, entourer les différents réseaux (version PDF imprimable).

 

 

Routeur

Routeur Wifi

Un routeur permet de relier ensemble plusieurs réseaux.

Pour cela, il doit être composé d’au moins deux interfaces réseau (« cartes » réseau : Ethernet, Wifi, …).

Il existe des routeurs capables de relier ensemble une dizaine de réseaux.

N’importe quel ordinateur peut jouer le rôle de routeur dès lors qu’il possède au moins 2 interfaces réseau.

 

On distinguera :

  • les routeurs d’accès qui permettent aux machines d’un sous-réseau d’accéder au réseau.
    On y connecte les clients et les serveurs, au sein de sous-réseaux (LAN).
  • les routeurs internes qui constituent la structure du réseau lui-même.
    Leur rôle est d’acheminer les paquets au sein du réseau en se les relayant. Les distances entre eux sont généralement longues et nécessitent des technologies adaptées (fibre optique, satellites, …).

Le routeur est un composant de la couche Internet : il décapsule les paquets jusqu’à pouvoir lire les adresses IP des expéditeurs et destinataires.

Activité : routeurs
Sur le schéma du réseau donné en exemple plus haut, repérer les routeurs d’accès et les routeurs internes.

 

 

Routage

Le routage est le mécanisme par lequel des chemins sont sélectionnés dans un réseau pour acheminer les données d’un expéditeur jusqu’à un ou plusieurs destinataires.

entre deux hôtes du même sous-réseau

Sur un même sous-réseau, tous les hôtes doivent avoir la même adresse réseau (NetId). Les paquets de données passent par les commutateurs (switch), un composant de la couche accès réseau . Un switch ne lit pas les adresses IP ! Le routage se fait à l’aide des adresses MAC (voir simulation d’un réseau)

Exemple : M1 et M2 appartiennent au même réseau local. la communication passe par le switch R1 qui connait les adresses MAC de tous les périphériques qui sont reliés à lui.

 

entre deux sous-réseaux différents

Deux hôtes de deux sous-réseaux différents ne possèdent pas la même adresse de réseau. Le destinataire n’étant pas sur le même réseau que l’expéditeur, le switch s’adresse à un routeur d’accès qui joue alors le rôle de passerelle (gateway). Chaque routeur du réseau possède une certaine « connaissance » de la topologie du réseau et peut faire passer le paquet qu’il reçoit à un routeur voisin.

Exemple : Dans le réseau A ci dessous, le routeur A joue le rôle de passerelle.

Mais il y a le plus souvent plusieurs routes possibles.

Exemple : M1 et M10 appartiennent à des sous-réseaux différents : la communication doit passer par des routeurs d’accès et des routeurs internes au réseau.
plusieurs routes permettent l’échange d’informations.

Activité
Déterminer un chemin possible permettant d’établir une connexion entre la machine M4 et M14.

 

Plusieurs questions se posent à présent :

Comment les routeurs procèdent acquièrent-t-ils une connaissance de la topologie du réseau ?

Comment le chemin entre deux machines est-il choisi, et par qui ?

 

 

Tables de routage

Chaque machine connectée à un réseau, et jouant un rôle de routeur, possède une table de routage : un tableau qui contient des informations permettant au routeur d’envoyer le paquet de données dans la « bonne direction ».

Un routeur possède plusieurs interfaces réseau (eth0, eth1, wlan0, wlan1, eno0, …), par lequel il est connecté à des sous-réseaux (autre routeur, réseau local, …) au sein desquels il possède une adresse IP.

Information sur les interfaces

Chaque OS possède sa propre nomenclature pour les interfaces réseau :

On peut obtenir la liste des interfaces disponibles sur une machine à l’aide de commandes :

  • Linux : ifconfig
  • Windows : ipconfig

Exemple : le routeur R1 possède 3 interfaces Ethernet (eth0, eth1 et eth2), lui permettant de faire le lien entre 3 réseaux

Masques réseau
Déterminer les masques de sous-réseau des 3 réseaux reliés par R1, ainsi que le nombre d’hôtes qu’ils peuvent accueillir.

 

Dans la table de routage d’un routeur, on trouve les informations suivantes :

  • Les adresses IP du routeur (il en possède une pour chacune de ses interfaces)
  • Les adresses IP des sous-réseaux auquel il est connecté
  • Les routes (directions à prendre) qu’il faut suivre pour atteindre un réseau
    • route par défaut (il en faut bien une)
    • routes statiques (configurées explicitement par l’administrateur)
    • routes dynamiques (apprises par des protocoles de routage dynamique)

Chaque ligne de la table contient une route :

  • l’adresse du réseau de destination
  • la direction à prendre pour l’atteindre :
    • Interface de sortie du routeur (adresse du routeur sur le sous-réseau de sortie)
    • Passerelle (adresse de la prochaine machine sur le sous-réseau de sortie)
  • la distance à parcourir (la métrique) avant de l’atteindre

Lorsqu’un routeur reçoit un paquet, il récupère l’adresse du réseau de destination :

  • si cette adresse est dans sa table de routage, il envoie le paquet vers l’interface associée,
  • dans le cas contraire le paquet est envoyé via l’interface par défaut.

Exemples :

si le routeur reçoit un paquet à destination de l’ordinateur 192.168.7.2 / 24, sa table de routage pourra contenir la route suivante :

Réseau destination Passerelle Interface Métrique
192.168.7.0 /24 eth1 1

l’ordinateur est directement relié au routeur,

    • il n’y a donc pas besoin de passerelle pour l’atteindre
    • la métrique est de 1 (un seul « saut »)

 

si le routeur reçoit un paquet à destination de l’hôte 172.21.34.21 /16, sa table de routage pourra contenir la route suivante :

Réseau destination Passerelle Interface Métrique
172.21.0.0 /16 10.1.2.2 eth0 8

 

si le routeur reçoit un paquet à destination d’un réseau qui n’est pas dans sa table, il choisit la route par défaut :

Réseau destination Passerelle Interface Métrique
défaut 10.1.2.2 eth0 1

 

Remarque : en pratique une table de routage ne comporte que des adresses IP. Par conséquent :

  • l’adresse du réseau de destination n’est pas au format CIRC mais au format IP réseau+masque réseau
    192.168.7.0 /24 → 192.168.7.0 et 255.255.255.0
  • l’interface est décrite par la propre adresse IP du routeur dans le sous-réseau auquel il est connecté avec cette interface
    eth1 → 192.168.7.254
  • le réseau de destination de la route par défaut est noté 0.0.0.0

 

 

Activité : table de routage

Soit le réseau suivant :

Table de routage du routeur A
Réseau destination Passerelle Interface Métrique
172.168.0.0/16 eth0 1
192.168.7.0/24 eth1 1
172.169.0.0/16 eth2 1
10.0.0.0/8 192.168.7.2/24 eth1 2

Le routeur A n’est pas directement relié au réseau 10.0.0.0 /8 mais il « sait » que les paquets à destination de ce réseau doivent être envoyés à 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)

Déterminer la table de routage du routeur G.

 

Activité : réseau et routage

Un réseau est constitué de 6 routeurs, dont les tables de routage sont :

Routeur A Routeur B Routeur C
Dest Pass Dest Pass Dest Pass
B B A A A A
C C C C B B
D C D C D D
E B E E E B
F B F E F D

 

Routeur D Routeur E Routeur F
Dest Pass Dest Pass Dest Pass
A C A B A D
B C B B B E
C C C B C D
E E D D D D
F F F F E E

 

Déterminer les routes de A à F, puis de F à A, puis de F à C

 

Dessiner une représentation sous forme de graphe du réseau ainsi constitué.

 

Tracer les routes de A à F et de F à C.

 

Dans des réseaux très complexes, les tables de routage des routeurs peuvent comporter 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 ce cas, le routeur va choisir la route « la plus courte« , c’est à dire celle ayant la valeur de métrique la plus petite (un réseau directement lié à un routeur aura une métrique de 1).

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 = 1), 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
  • le routage dynamique : tout se fait « automatiquement », on utilise des protocoles, partagés par tous les routeurs du réseau, qui vont leur permettre d’échanger des informations sur l’état du réseau afin de remplir leur table de routage automatiquement.

 

 


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 issus de la théorie de graphes.

Protocole RIP

Le protocole RIP (Routing Information Protocol) est un des premiers algorithmes utilisés pour établir les tables de routage des routeurs interconnectant des réseaux.

Il comporte les 3 règles suivantes :

 1  Initialement (à la mise sous tension), la table de routage d’un routeur contient uniquement des informations sur ses voisins directs (ceux auxquels il est connecté).

Exemple :

Initialement (mise sous tension) la table de routage de R1 contient uniquement les réseaux 192.168.1.0 /24 et 10.1.1.0 /30.

Table de routage de R1
Réseau destination Passerelle Interface Métrique
192.168.1.0 /24 wlan0 1
10.1.1.0 /30 eth1 1

Aucune passerelle n’est spécifiée car le routeur peut atteindre le réseau destination directement.

RIP : état initial
Réaliser la table de routage initiale du routeur R3.

 

 2  Chaque routeur envoie périodiquement (toutes les 30 secondes), à tous ses voisins (routeurs adjacents), un message contenant :

  • la liste de toutes les adresses de réseaux qu’il connait (ses voisins directs et ceux qu’il a reçu auparavant)
  • leur métrique (le nombre de sauts pour les atteindre)

Ce couple d’informations (réseau, métrique) est appelé vecteur de distance.

 

 3  À chaque réception d’un message de ce type, un routeur met à jour sa table de routage avec les informations reçues. Quatre cas peuvent se présenter :

  1. il découvre une nouvelle route vers un sous réseau qu’il ne connaissait pas encore
    il l’ajoute à sa table
  2. il découvre une nouvelle route plus courte vers un sous réseau qu’il connaissait déjà
    il remplace l’ancienne route par la nouvelle
  3. il reçoit une nouvelle route plus longue vers un sous réseau qu’il connaissait déjà
    il ne fait rien
  4. il reçoit une route existante dans sa table (passant par le même voisin), mais plus longue. Cela signifie que la route s’est allongée (panne ?).
    il met sa table à jour

 

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.

Exemple : le routeur R1 reçoit des messages de la part de son seul voisin R3. Ce message contient les vecteurs de distance suivants :

    • (10.1.2.0 /30 , 1)
    • (10.1.3.0 /30 , 1)
    • (10.1.4.0 /30 , 1)
    • et tous les vecteurs de distance concernant les autres réseaux qu’il « connait ».

Du point de vue de R1, R3 (d’adresse 10.1.1.2 /30) est une passerelle.

Sa table de routage devient alors :

Table de routage de R1
Réseau destination Passerelle Interface Métrique
192.168.1.0 /24 wlan0 1
10.1.1.0 /30 eth1 1
10.1.2.0 /30 10.1.1.2 /30 eth1
2
10.1.3.0 /30 10.1.1.2 /30 eth1
2
10.1.4.0 /30 10.1.1.2 /30 eth1 2

 

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

Activité : routage RIP dans la classe

L’activité suivante propose de réaliser un réseau constitué de tous les élèves de la classe.

Il est très important pour la réussite de cet exercice que chacun garde le silence et ne communique pas oralement, ni avec ses « réseaux voisins », ni avec quiconque !

Chaque élève joue le rôle d’un routeur et se voit attribuer un identifiant (une lettre), ainsi qu’une table de routage (PDF à télécharger)

Initialisation :

Le professeur désigne à chaque élève 2 à 3 « routeurs » voisins (physiquement proches).

Chaque élève initialise sa table de routage en y inscrivant ses voisins.

 

Élaboration des messages :

A intervalle de temps régulier (au signal donné par le professeur), chaque élève prépare un message RIP contenant :

  • la liste de toutes les identifiants réseaux qu’il connait (ses voisins directs et ceux qu’il a reçu auparavant)
  • leur métrique (le nombre de sauts pour les atteindre)

et en donne un à chacun de ses voisins.

 

Mise à jour des tables :

À la réception d’un message, chaque élève met à jour sa table de routage, selon les cas de figure suivants :

  1. il découvre une nouvelle route vers un sous réseau qu’il ne connaissait pas encore
    il l’ajoute à sa table
  2. il découvre une nouvelle route plus courte vers un sous réseau qu’il connaissait déjà
    il remplace l’ancienne route par la nouvelle
  3. il reçoit une nouvelle route plus longue vers un sous réseau qu’il connaissait déjà
    il ne fait rien
  4. il reçoit une route existante dans sa table (passant par le même voisin), mais plus longue. Cela signifie que la route s’est allongée (panne ?).
    il met sa table à jour

 

Activité : routage RIP

Soit le réseau suivant :

Déterminer la table de routage du routeur A après qu’elle a été remplie selon le protocole RIP (métrique = nombre de sauts).

 

La liaison entre les routeurs B et C devient défaillante.

Mettre à jour les tables de routage en appliquant le protocole RIP.

 

D’après cette table de routage, déterminer la route qui sera empruntée 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.

 

 

Délai de convergence

On appelle délai de convergence le temps nécessaire à ce que l’ensemble des routeurs soient configurés pour offrir les meilleurs routes possible. À chaque modification du réseau (ajout ou suppression de routeurs), il faut un certain temps pour que les échanges de messages RIP mènent à une situation stable.

C’est pour limiter ce délai de convergence que le protocole RIP est limité à 15 sauts.

 

Détection des pannes

Lorsqu’un routeur ne reçoit pas de réponse de la part d’un autre routeur à une demande RIP (après un certain laps de temps, 3 minutes), il considère que le routeur en question est en panne.

Afin qu’aucun paquet ne soit plus dirigé dans cette direction, il prévient ses voisins en leur envoyant une métrique égale à 16 (plus grande valeur possible pour le protocole RIP) concernant toutes les routes passant par le routeur qui ne répond pas.

 

Boucle de routage

Une boucle de routage est le phénomène qui se produit lorsqu’un paquet tourne en boucle et ne peut jamais atteindre sa destination.

Différentes règles dans le protocole RIP permettent d’éviter que cela se produise, et notamment la règle split horizon, qui interdit à un routeur d’envoyer une information de routage via le routeur qui lui a envoyé.

 

Le protocole RIP est aujourd’hui très rarement utilisé dans les grandes infrastructures car il génère, du fait de l’envoi périodique de messages, un trafic réseau important (surtout si les tables de routages contiennent beaucoup d’entrées). De plus, le protocole RIP est limité à 15 sauts (on traverse au maximum 15 routeurs pour atteindre sa destination). On lui préfère donc souvent le protocole OSPF.

 

Le protocole OSPF

Dans le protocole OSPF (Open Shortest Path First), comme dans le cas du protocole RIP, les routeurs échangent entre eux des informations, mais ces échanges sont plus « intelligents » dans le cas d’OSPF, permettant ainsi de réduire l’occupation du réseau.

  • Tous les routeurs ont une vision globale et identique du réseau : pour cela, ils reçoivent des informations depuis tout le réseau
  • Les distances prennent en compte le nombre de routeur à traverser (nombre de sauts), mais également le débit binaire de chaque « câble » (appelé aussi bande passante), exprimé en bits/s.

Le protocole OSPF permet à chaque routeur de connaitre le graphe complet des liaisons entre tous les routeurs du réseau, avec leur débits.

Ainsi, le « meilleur » chemin n’est pas forcément le plus court, mais le plus rapide.

Exemple : sur le réseau ci-dessous, considérons un paquet qui doit être transmis de F à C

    • le protocole RIP choisirait la route comportant le moins de sauts possible, soit F→H→C
    • le protocole OSPF en revanche choisira la route F→E→D→C,

La valeur de métrique retenue par le protocole OSPF n’est en réalité pas le débit, mais le coût, un nombre entier obtenu par la formule suivante :

\(\Large{\text{coût}=\frac{10^8}{\text{bande passante [bits/s]}}}\)

ATTENTION : le coût ne peut pas être nul. On arrondira à 1 tous les résultats inférieurs à 1.

Remarque : ainsi, comme pour le protocole RIP, plus la métrique est petite, meilleure est la route.

OSPF : coûts d'une liaison
Calculer les coûts des liaisons du réseau précédent.

 

 

 

Sources :
https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_routage.html
https://www.editions-ellipses.fr/acc ueil/10445-20818-specialite-numerique-et-sciences-informatiques-lecons-avec-exercices-corriges-terminale-nouveaux-programmes-9782340038554.html#/1-format_disponible-broche

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.