Sources principales de ce cours :

Le programme

Introduction

Introduction : dans un réseau, les routeurs jouent un rôle essentiel dans la transmission des paquets sur Internet : les paquets sont routés individuellement par des algorithmes. Les pertes logiques peuvent être compensées par des protocoles reposant sur des accusés de réception ou des demandes de renvoi, comme TCP.

Capacités attendues

Capacités attendues : identifier, suivant le protocole de routage utilisé, la route empruntée par un paquet.

Commentaires : en mode débranché, les tables de routage étant données, on se réfère au nombre de sauts (protocole RIP) ou au coût des routes (protocole OSPF). Le lien avec les algorithmes de recherche de chemin sur un graphe est mis en évidence.

Préambule / révisions

Binaire

Pour cette partie, il est nécessaire de maîtriser les notions suivantes :

À revoir si besoin dans le cours de 1ère NSI…

IP et sous-réseaux

Une adresse IPv4 est composée de 32 bits (4 octets), généralement écrite en notation décimale pointée, par exemple 192.168.1.1.

Un sous-réseau est une plage d’adresses IP contiguës, définie par une adresse de réseau et un masque de sous-réseau. Le masque est souvent exprimé en notation CIDR (Classless Inter-Domain Routing), par exemple 192.168.1.0/24.

Ici, le /24 indique que les 24 premiers bits de l’adresse sont utilisés pour le réseau (masque 255.255.255.0), laissant les 8 bits restants pour les hôtes dans ce sous-réseau.

Calcul de la plage d’adresses

Méthode :

  1. Convertir l’adresse IP et le masque de sous-réseau en binaire.
  2. Appliquer un ET binaire entre l’adresse IP et le masque pour obtenir l’adresse de réseau.
  3. Pour obtenir l’adresse de diffusion, inverser le masque (NON) et appliquer un OU binaire avec l’adresse de réseau.
  4. Les adresses entre l’adresse de réseau et l’adresse de diffusion sont les adresses utilisables pour les hôtes.

Exemple (celui de la vidéo) : 15.33.131.0/20, masque 255.255.240.0.

Les 2 premiers octets (16 bits) font partie du réseau, le 4e octet ne contient que des bits d’hôte : seul le 3e octet est coupé (4 bits réseau, 4 bits hôte).

             3e octet         4e octet
adresse   : 131 = 1000 0011   0
masque    : 240 = 1111 0000   0
ET        : 128 = 1000 0000   0    -> réseau    : 15.33.128.0
NON masque:  15 = 0000 1111   255
OU        : 143 = 1000 1111   255  -> diffusion : 15.33.143.255

Hôtes : de 15.33.128.1 à 15.33.143.254, soit 232−20−2=212−2=40942^{32-20} - 2 = 2^{12} - 2 = 4094 adresses.

Remarque : bien que 15.33.131.0 se termine par 0, ce n’est pas l’adresse du réseau, mais une adresse de machine tout à fait valide de ce réseau.

De nombreux outils en ligne (ou la commande ipcalc) permettent de vérifier ces calculs.

Exercice

Pour chaque sous-réseau ci-dessous, déterminer l’adresse de réseau, l’adresse de diffusion, et la plage d’adresses utilisables pour les hôtes.

Réponses détaillées
Sous-réseau Réseau Diffusion Hôtes Nombre
10.0.0.0/8 10.0.0.0 10.255.255.255 10.0.0.1 à 10.255.255.254 16 777 214
192.168.1.0/24 192.168.1.0 192.168.1.255 192.168.1.1 à 192.168.1.254 254
172.16.0.0/16 172.16.0.0 172.16.255.255 172.16.0.1 à 172.16.255.254 65 534
172.23.208.0/21 172.23.208.0 172.23.215.255 172.23.208.1 à 172.23.215.254 2 046
138.124.18.129/13 138.120.0.0 138.127.255.255 138.120.0.1 à 138.127.255.254 524 286

Détail des deux derniers :

  • /21 : masque 255.255.248.0, le 3e octet est coupé. 208=11010000208 = 1101\,0000, ET 248=11111000248 = 1111\,1000 donne 11010000=2081101\,0000 = 208 (réseau). OU 000001110000\,0111 donne 11010111=2151101\,0111 = 215 (diffusion).
  • /13 : masque 255.248.0.0, le 2e octet est coupé. 124=01111100124 = 0111\,1100, ET 248=11111000248 = 1111\,1000 donne 01111000=1200111\,1000 = 120 (réseau). OU 000001110000\,0111 donne 01111111=1270111\,1111 = 127 (diffusion). Les octets suivants (18.129) sont des bits d’hôte : ils passent à 0 pour le réseau, à 255 pour la diffusion.

Exercices de bac : sous-réseaux

Extraits des annales (liens sur le site web). Ne traiter que les questions indiquées : les autres questions portent sur le routage (RIP, OSPF), vu plus tard.

Bac sous-réseaux : pour démarrer

Masques /24 et /16.

Bac sous-réseaux : lire un schéma

Quelle adresse pour quelle machine ?

Bac sous-réseaux : plus difficile

Masques non alignés sur un octet.

Routage de l’information

Principe

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.

Sur Internet, chaque routeur décide seulement du prochain saut (next hop) : aucun routeur ne choisit le chemin complet.

Techniques d’adressage et de routage

En fonction du nombre de destinataires et de la manière de délivrer le message, on distingue :

Unicast, broadcast, multicast, anycast

Tables de routage

Les données nécessaires à la décision de transmission sont regroupées dans des tables de routage. Chaque entrée associe un préfixe (réseau de destination) à un moyen d’acheminer le paquet (passerelle et interface), ainsi qu’une métrique (mesure de « distance »).

Pour un paquet donné, le routeur choisit :

  1. parmi les entrées dont le préfixe contient l’adresse de destination, celle dont le préfixe est le plus long (la plus précise)
  2. à préfixe égal, celle de plus petite métrique

La route par défaut 0.0.0.0/0 contient toutes les adresses : elle n’est utilisée que si aucune autre entrée ne correspond.

Exercice

En utilisant la table de routage ci-dessous, quel chemin est choisi pour un paquet à destination des adresses suivantes : 10.1.2.3, 139.124.18.207, 192.168.1.44, 192.168.133.22 ?

Destination Chemin (Next hop) Métrique
10.0.0.0/24 10.0.0.254 eth0 1
0.0.0.0/0 10.0.0.254 eth0 1000
192.168.0.0/16 192.168.0.1 eth1 5
192.168.133.0/24 172.16.0.1 eth2 2
Réponses détaillées
  • 10.1.2.3 : 10.0.0.0/24 ne contient que 10.0.0.0 à 10.0.0.255, donc pas 10.1.2.3 (piège). Seule la route par défaut correspond : 10.0.0.254 via eth0.
  • 139.124.18.207 : aucune entrée spécifique, route par défaut : 10.0.0.254 via eth0.
  • 192.168.1.44 : contenu dans 192.168.0.0/16 (mais pas dans 192.168.133.0/24) : 192.168.0.1 via eth1.
  • 192.168.133.22 : contenu à la fois dans 192.168.0.0/16 et dans 192.168.133.0/24. Le préfixe le plus long l’emporte : 172.16.0.1 via eth2. Ce serait encore le cas si la route /16 avait une meilleure métrique.

Routage statique / dynamique

Les tables de routage peuvent contenir des entrées :

Protocoles de routage

Principe

Un protocole de routage spécifie comment les routeurs communiquent entre eux pour distribuer des informations qui leur permettent de sélectionner des itinéraires entre deux nœuds quelconques d’un réseau.

Initialement, chaque routeur ne connaît que les réseaux qui lui sont directement rattachés. Le protocole de routage partage cette information d’abord entre voisins immédiats, puis dans tout le réseau, de manière à ce que chaque routeur acquière une connaissance suffisante de la topologie du réseau.

Les protocoles de routage doivent s’adapter dynamiquement à des conditions changeantes (coupure de ligne, ajout d’un routeur…).

AS

Un AS (Autonomous System) est une collection de préfixes IP d’un ou plusieurs réseaux contrôlés par une même entité administrative (fournisseur d’accès, grande entreprise, université…), et définissant une politique de routage vers l’internet.

Types de protocoles

Lien avec les graphes

Un réseau se modélise par un graphe pondéré (cf cours plus tard ;):

Trouver la meilleure route revient à chercher un plus court chemin :

RIP

Fonctionnement

Chaque routeur RIP (Routing Information Protocol) gère une table de routage.

Initialement, un routeur ne connaît que les réseaux auxquels il est connecté.

Toutes les 30 secondes, chaque routeur envoie sa table de routage complète (vecteurs de distance = [destination, distance]) à ses voisins immédiats, qui utilisent alors ces informations pour compléter leur propre table de routage.

Ces échanges se poursuivent en permanence. Lorsque plus aucun changement n’est détecté dans les tables de routage, on dit que le protocole a convergé.

RIP utilise le nombre de sauts (hops) comme métrique, avec un maximum de 15 : une distance de 16 signifie « inaccessible ».

Mise à jour d’une table

Le routeur R reçoit de son voisin V une route vers D, à distance d :

Attention à la convention : dans ce cours (comme chez Cisco), un réseau directement connecté est à distance 0. Certains sujets de bac comptent 1 : toujours lire l’énoncé.

Évolution

En cas de panne, le routeur coupé cesse d’envoyer des mises à jour à ses voisins. Au bout de 180 secondes sans actualisation, les routeurs voisins déclarent les routes correspondantes inaccessibles (distance 16), puis les suppriment. Cette information est propagée au reste du réseau, et les routeurs finissent par trouver une route de remplacement, si elle existe.

Avantages et inconvénients

Avantages

Inconvénients

Exemples et ressources

Liens sur le site web.

Exercice

Routage RIP
Réponses détaillées

Convention : réseau directement connecté = distance 0. En cas d’égalité, les deux voisins sont indiqués (le routeur garde la première route reçue).

Destination R1 R2 R3 R4 R5
10.0.0.0/8 connecté R1 ou R3, 1 connecté R3, 1 R3, 1
20.0.0.0/8 connecté connecté R1 ou R2, 1 R2, 1 R3 ou R4, 2
30.0.0.0/8 R2 ou R3, 1 connecté connecté R2 ou R3, 1 R3, 1
40.0.0.0/8 R2, 1 connecté R2 ou R4, 1 connecté R4, 1
50.0.0.0/8 R3, 1 R3 ou R4, 1 connecté connecté R3 ou R4, 1
60.0.0.0/8 R2 ou R3, 2 R4, 1 R4 ou R5, 1 connecté connecté
70.0.0.0/8 R3, 1 R3, 1 connecté R3 ou R5, 1 connecté
192.168.1.0/24 connecté R1, 1 R1, 1 R2 ou R3, 2 R3, 2
192.168.2.0/24 R3, 2 R3 ou R4, 2 R5, 1 R5, 1 connecté

Chaque case indique le routeur suivant et la distance. La table de R1 est celle donnée par un vrai routeur Cisco :

Table de routage RIP de R1

Chemin de 192.168.1.1 vers 192.168.2.1 : R1 → R3 → R5 (distance 2). Ce chemin emprunte deux liaisons série, les plus lentes du réseau : RIP ne le voit pas.

OSPF

Fonctionnement

Chaque routeur OSPF (Open Shortest Path First) communique avec ses voisins immédiats en envoyant un message HELLO en multicast, à intervalle régulier (10 secondes par défaut, 30 sur certains types de liens). Ce message permet de détecter la présence de voisins et de confirmer la connectivité.

Régulièrement, et immédiatement lors d’un changement d’état, chaque routeur communique l’état de ses liens (réseaux connectés, voisins, coûts) par des messages LSA (Link State Advertisements) à ses voisins. Ceux-ci retransmettent alors ce message à leurs voisins, et ainsi de suite (flooding, inondation).

L’ensemble des messages LSA permet de construire sur chaque routeur la connaissance de l’ensemble de la topologie du réseau (protocole à état de liens). Chaque routeur peut alors calculer le chemin le plus court vers chaque destination (algorithme de Dijkstra).

Métrique

La métrique est un coût associé à chaque lien, un entier entre 1 et 65535. Le coût d’une route est la somme des coûts des liens traversés.

La spécification ne donne pas de signification particulière à ce coût, la contrainte étant qu’additionner les coûts de liens successifs pour déterminer le coût total doit avoir un sens.

Par défaut (Cisco), le coût d’un lien vaut BPrefBPlien\frac{BP_{ref}}{BP_{lien}}, avec BPref=100Mbit/sBP_{ref}=100\ Mbit/s (108bit/s10^8\ bit/s). Un lien à 10Mbit/s10\ Mbit/s aura par exemple un coût de 10.

Le coût étant au minimum 1, tous les liens à 100 Mbit/s et plus ont le même coût. Pour les distinguer, on peut fixer manuellement le coût de chaque lien, ou bien choisir une bande passante de référence plus grande.

Au bac, la formule du coût est donnée par l’énoncé (souvent 108d\frac{10^8}{d} ou 109d\frac{10^9}{d}, avec dd le débit en bit/s).

Évolution

Lorsque les messages HELLO détectent un changement d’état d’un lien (panne ou rétablissement), un message LSA est immédiatement envoyé à tous les voisins, qui le propagent à leur tour. Chaque routeur peut alors recalculer les chemins les plus courts.

Il faut 4 HELLO manqués (par défaut) pour considérer qu’un lien est tombé, soit 40 ou 120 secondes suivant l’intervalle de HELLO. La convergence est ensuite rapide (quelques secondes), contrairement à RIP.

Exemples et ressources

Liens sur le site web.

Exercice

Routage OSPF

On suppose que les liaisons Ethernet ont un débit de 100 Mbit/s, les liaisons série un débit de 10 Mbit/s, et que BPref=100Mbit/sBP_{ref} = 100\ Mbit/s.

Réponses détaillées

Coûts : Ethernet 100100=1\frac{100}{100} = 1, série 10010=10\frac{100}{10} = 10.

  • coût 1 : R1–R2 (20), R2–R3 (30), R3–R4 (50), R4–R5 (60)
  • coût 10 : R1–R3 (10), R2–R4 (40), R3–R5 (70)

Tables (routeur suivant, coût ; réseau connecté = coût 0) :

Destination R1 R2 R3 R4 R5
10.0.0.0/8 connecté R1 ou R3, 1 connecté R3, 1 R4, 2
20.0.0.0/8 connecté connecté R2, 1 R3, 2 R4, 3
30.0.0.0/8 R2, 1 connecté connecté R3, 1 R4, 2
40.0.0.0/8 R2, 1 connecté R2 ou R4, 1 connecté R4, 1
50.0.0.0/8 R2, 2 R3, 1 connecté connecté R4, 1
60.0.0.0/8 R2, 3 R3, 2 R4, 1 connecté connecté
70.0.0.0/8 R2, 2 R3, 1 connecté R3 ou R5, 1 connecté
192.168.1.0/24 connecté R1, 1 R2, 2 R3, 3 R4, 4
192.168.2.0/24 R2, 4 R3, 3 R4, 2 R5, 1 connecté

R1 n’utilise plus du tout sa liaison série vers R3 : passer par R2 coûte 2, au lieu de 10.

Chemin de 192.168.1.1 vers 192.168.2.1 : R1 → R2 → R3 → R4 → R5, coût 4. Le chemin choisi par RIP (R1 → R3 → R5) coûte 20 : OSPF préfère un chemin plus long en sauts, mais n’utilisant que des liaisons rapides.

Exercices de bac : routage

Index des exercices

Extraits des annales (liens sur le site web), avec les thèmes de chaque exercice. Entre parenthèses : les autres thèmes du même exercice.

Les exercices portant uniquement sur les sous-réseaux sont listés dans la partie Préambule / révisions.

2021

2022

2023

2024

2025

2026