Protocoles et services réseaux

Ce laboratoire présente les concepts fondamentaux du routage IP, ses algorithmes et protocoles principaux. Il permet de comprendre comment les routeurs déterminent le meilleur chemin dans un réseau maillé en utilisant des tables de routage mises à jour dynamiquement ou statiquement. Pour réaliser ce TP, il est nécessaire de disposer d’un environnement réseau simulé ou réel, ainsi que des outils pour consulter et modifier les tables de routage (ex. commandes netstat, show ip route).

Objectifs

• Comprendre la fonction et le principe du routage IP.
• Identifier les différents types de routage : statique et dynamique.
• Analyser et interpréter une table de routage.
• Appliquer et différencier les algorithmes de routage Link-State et Distance Vector.
• Connaître les protocoles de routage RIP et OSPF et leur fonctionnement.

Prérequis et installation

• Connaissances de base en réseaux IP et adresses IP.
• Accès à un système UNIX ou Windows avec la commande netstat -r ou à un routeur Cisco avec la commande show ip route.
• Environnement permettant la simulation ou la configuration de routeurs (ex. Cisco Packet Tracer, GNS3).
• Compréhension des notions de graphes et de coûts dans un réseau.

Définition et principe du routage IP

Le routage IP est la fonction qui permet de déterminer le meilleur chemin dans un réseau maillé vers une destination identifiée par une adresse IP. Chaque nœud (routeur ou station) possède une table de routage contenant les informations nécessaires pour atteindre la destination via le prochain nœud.

Le routage peut être statique, où les routes sont configurées manuellement, ou dynamique, où les tables de routage sont mises à jour automatiquement par échange périodique d’informations.

Pour consulter la table de routage :

# Sur une station UNIX ou Windows
netstat -r

# Sur un routeur Cisco
show ip route

Une route par défaut peut être configurée pour acheminer les paquets vers toutes les destinations non explicitement listées dans la table.

Types de routage

Il existe deux types principaux de routage :

• Routage statique : les routes sont ajoutées ou supprimées manuellement.

  # Exemple sous Windows ou UNIX pour ajouter une route
  route add @IP_destination @IP_router metric
  
  # Exemple sous Cisco pour ajouter une route
  ip route @IP_destination netmask @IP_router metric
  

• Routage dynamique : les tables de routage sont mises à jour automatiquement grâce à l’échange périodique d’informations entre routeurs.

Algorithmes de routage

Le routage repose sur des algorithmes qui calculent les chemins optimaux dans un réseau modélisé en graphe :

• Algorithmes Link-State (état de lien) : chaque routeur connaît la topologie complète et le coût des liens. Exemple : algorithme de Dijkstra.
• Algorithmes Distance Vector (vecteur de distance) : chaque routeur connaît uniquement le coût des liens vers ses voisins et échange régulièrement ses tables de distances avec eux.

Algorithme de Dijkstra (Link-State)

But : calculer le chemin de coût minimal entre un nœud source et toutes les autres destinations.

Notation :

• c(i,j) : coût du lien entre les nœuds i et j (infini s’ils ne sont pas voisins)
• D(v) : coût courant du chemin de la source vers le nœud v
• p(v) : nœud précédent sur le chemin vers v
• N : ensemble des nœuds dont le coût minimal est connu

Procédure :

1  Initialisation :
2    N = {A}  # A est le nœud source
3    Pour tout nœud v
4      si v est adjacent à A
5        alors D(v) = c(A,v)
6      sinon D(v) = infinity
7   boucle
8      Trouver w ∉ N tel que D(w) est minimal
10    ajouter w à N
11    Mettre à jour D(v) pour tous les nœuds v ∉ N adjacents à w :
12       D(v) = min( D(v), D(w) + c(w,v) )
13   jusqu’à ce que N contienne tous les nœuds

À chaque itération, on étend l’ensemble N des nœuds avec coût minimal connu et on met à jour les distances vers les nœuds voisins.

Algorithme Distance Vector (DV)

Chaque nœud maintient une table de distances indiquant le coût pour atteindre chaque destination via chacun de ses voisins. L’algorithme est itératif, asynchrone et distribué :

• Itératif : continue jusqu’à convergence (plus aucun changement dans les tables)
• Asynchrone : pas besoin d’horloge globale
• Distribué : chaque nœud communique seulement avec ses voisins

Notation :

• X : nœud source
• D(Y,Z) : coût du chemin de X à Y en passant par Z
• c(X,Z) : coût du lien entre X et Z

Formule :

D(Y,Z) = c(X,Z) + min { D(Y,w) }

où w sont les voisins de Z.

Initialisation dans chaque nœud X :

1  Pour tout nœud adjacent v :
2      D(*,v) = inf
3      D(v,v) = c(X,v)
4  Pour toute destination y
5      Envoyer min D(y,w) à tous les voisins w

Protocoles de routage

Protocole RIP (Routing Information Protocol)

• Protocole à vecteur de distance (Distance Vector)
• Coût mesuré en nombre de sauts (max 15)
• Échange d’informations de routage avec voisins directs toutes les 30 secondes
• Vecteur de distance contient jusqu’à 25 réseaux de destination

Protocole OSPF (Open Shortest Path First)

• Protocole à état de lien (Link-State)
• Coût du chemin configurable (pas forcément nombre de sauts)
• Échange de messages Hello entre voisins pour vérifier l’état des liens
• Annonce des états des liens à tous les routeurs du système autonome, pas seulement aux voisins directs
• Messages d’annonce échangés périodiquement (au moins toutes les 30 minutes) et à chaque changement d’état de liaison

Résultats attendus

• Compréhension claire de la structure et du contenu d’une table de routage.
• Capacité à interpréter les résultats des commandes netstat -r et show ip route.
• Application correcte de l’algorithme de Dijkstra pour déterminer le chemin le plus court dans un graphe donné.
• Compréhension du fonctionnement itératif et distribué de l’algorithme Distance Vector.
• Identification des différences entre les protocoles RIP et OSPF dans la gestion des routes.

Pièges courants

• Confusion entre routage statique et dynamique : ne pas oublier que le routage statique nécessite une mise à jour manuelle des tables.
• Oublier de prendre en compte la route par défaut, ce qui peut empêcher l’acheminement vers des destinations non listées explicitement.
• Dans l’algorithme de Dijkstra, ne pas ajouter correctement le nœud avec le coût minimal à l’ensemble N peut fausser les calculs.
• Dans l’algorithme Distance Vector, ne pas attendre la convergence complète peut conduire à des routes incorrectes.
• Confondre le coût dans RIP (nombre de sauts limité à 15) avec le coût paramétrable dans OSPF.