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, constituant ainsi la topologie du réseau.

Exemple : un réseau reliant plusieurs LAN

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 (IP) : il décapsule les paquets jusqu’à pouvoir lire les adresses IP des expéditeurs et destinataires.

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.

Plusieurs questions se posent à présent :

Comment les routeurs 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, …). Il possède une adresse IP différente pour chacun de ces sous-réseaux.

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

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 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 réseau)
  • routes dynamiques (apprises par des protocoles de routage dynamique)

Chaque ligne de la table contient une route :

• l’adresse du réseau de destination (masque compris)
  
• 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 :

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 :

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 :

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

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.

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

 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 :

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

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 est un nombre entier compris entre 1 et 65535 : il ne peut pas être nul. On arrondira à 1 tous les résultats inférieurs à 1.

Ainsi, la métrique d’une route est l’addition des coûts des liaisons pour arriver à la destination.

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

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