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 déonnes, 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

Routage de l’information

Principe

https://en.wikipedia.org/wiki/Routing

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.

Techniques d’addressage et de routage

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

  • unicast : association unique entre une source et une destination
  • broadcast : distribution à toutes les destinations
  • multicast : distribution à un groupe de destinations
  • anycast : distribution à une destination donnée parmi un groupe de destinations
xxxcast

Tables de routage

Les données nécessaires à la prise de décision de transmission d’un chemin sont regroupées dans des tables de routage. Chaque entrée d’une table de routage associe un préfixe à un moyen d’acheminer la trame vers la destination, ainsi qu’une métrique (mesure de “distance”).

Si plusieurs routes sont possibles, la route choisie est celle avec la plus petite métrique.

Exercice : en utilisant la table de routage ci-dessous, quel chemin est choisi pour une trame à 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 10
192.168.133.0/24 192.168.1.1 eth2 1

Routage statique / dynamique

Les tables de routage peuvent contenir des entrées :

  • statiques : entrées manuellement, pas de changement
  • dynamiques : déterminées par un protocole de routage

Protocoles de routage

Principe

https://en.wikipedia.org/wiki/Routing_protocol

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

AS

Un AS (autonomous system) est une collection de préfixes IP d’un ou plusieurs réseaux controllés par une même entité administrative, et définissant une politique de routage vers l’internet.

Types de protocoles

  • IGP (interior gateway protocols, interne à un AS) de type 1 (link-state routing protocols). Exemple : OSPF (utilise la bande passante comme métrique)
  • IGP type 2 (distance-vector routing protocols). Exemple : RIP (utilise le nombre de sauts comme métrique)
  • EGP (exterior gateway protocols, routage entre AS). Exemple : BGP

RIP

Fonctionnement

Chaque routeur RIP (Routing Information Protocol) gère une table de routage. Initialement, un routeur ne connaît que les réseaux auquel il est connecté. Toutes les 30 secondes, chaque routeur envoie sa table de routage complète (vecteurs de distance = [adresse, distance]) à ses voisins immédiats, qui utilisent alors ces informations pour compléter leur propre table de routage.

Ces échanges se poursuivent jusqu’à ce que tous les routeurs disposent de la même table de routage, décrivant l’intégralité de la topologie du réseau. Ces étapes sont appelées convergence.

RIP utilise le nombre de sauts (hops) comme métrique de routage, et autorise un nombre de sauts maximum : 15

Evolution

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 suppriment alors les routes correspondantes, et cette information est alors propagée au reste du réseau.

Limites et avantages

Avantages :

  • simplicité : RIP est simple à configurer
  • ressources : RIP est peu gourmand en ressources
  • compatibilité : RIP est compatible avec quasi tous les routeurs

Inconvénients :

  • taille : la limite de 15 sauts limite la taille des réseaux routables
  • convergence : la convergence est lente
  • fonctionnalités : RIP ne prend pas en compte la bande passante des liens

Exemple de table RIP

RIP table

Exercice

  • déterminer le plan du réseau depuis la table de routage précédente (sachant que dans la notation [Y/X], X désigne le coût, ici le nombre de sauts)
  • écrire la table de routage du routeur connecté au réseau 192.168.2.0/24
  • quel chemin sera choisi pour un paquet partant de 192.168.1.1 à destination de 192.168.2.1

Correction

Routage RIP

Voir figure 3

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

Chaque routeur communique la liste des réseaux auxquels il est connecté par des message LSA (Link State Advertisements) à ses voisins. Ceux-ci retransmettent alors ce message à leurs voisins, et ainsi de suite.

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

Métrique

La métrique utilisée est une métrique additionnée sur l’ensemble des liens réseau, variant entre 1 et 65535.

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

Cisco utilise une valeur par défaut du coût d’un lien qui vaut BPrefBPlien\frac{BP_{ref}}{BP_{lien}}. Avec BPref=100Mbit/sBP_{ref}=100\ Mbit/s, un lien de 10Mbit/s10\ Mbit/s aura par exemple un coût de 10.

Pour tenir compte des connexions à très haute vitesse (1 Gbit/s et plus), on peut fixer manuellement le coût de chaque lien, ou bien fixer une bande passante de référence supérieure à celle par défaut.

Evolution

Lorsqu’une configuration de routage d’un routeur est modifiée (perte d’un voisin par exemple), il réémet sa nouvelle configuration de routage à ses voisins, et l’information est ainsi propagée de proche en proche.

La configuration est rafraîchie toutes les 30 secondes.

Exercice 1

En utilisant le routage OSPF dans le réseau de l’exercice précédent, déterminer quel chemin sera choisi pour un paquet partant de 192.168.1.1 à destination de 192.168.2.1 (FastEthernet0 correspond à 100Mbits/s et Serial correspond à 10Mbit/s)

Exercice 2

R1#sh ip route
Codes: C - connected, S - static, R - RIP, O - OSPF
Gateway of last resort is 192.168.3.2 to network 0.0.0.0

172.16.0.0/24 is subnetted, 1 subnets
C 172.16.0.0 is directly connected, Loopback0
10.0.0.0/24 is subnetted, 3 subnets
O 10.0.2.0 [110/2] via 10.0.0.2, 00:03:24, FastEthernet1/0
C 10.0.3.0 is directly connected, FastEthernet2/0
C 10.0.0.0 is directly connected, FastEthernet1/0
O E2 192.168.2.0/24 [110/20] via 10.0.0.2, 00:03:24, FastEthernet1/0
C 192.168.3.0/24 is directly connected, FastEthernet1/1
S* 0.0.0.0/0 [1/0] via 192.168.3.2
R2#sh ip route
Codes: C - connected, S - static, R - RIP, O - OSPF
Gateway of last resort is 10.0.0.1 to network 0.0.0.0

172.16.0.0/24 is subnetted, 1 subnets
C 172.16.0.0 is directly connected, Loopback0
10.0.0.0/24 is subnetted, 3 subnets
C 10.0.2.0 is directly connected, FastEthernet2/0
O 10.0.3.0 [110/2] via 10.0.2.1, 00:07:29, FastEthernet2/0
           [110/2] via 10.0.0.1, 00:00:08, FastEthernet1/1
C 10.0.0.0 is directly connected, FastEthernet1/1
C 192.168.2.0/24 is directly connected, FastEthernet1/0
O*E2 0.0.0.0/0 [110/1] via 10.0.0.1, 00:00:57, FastEthernet1/1
R3#sh ip route
Codes: C - connected, S - static, R - RIP, O - OSPF
Gateway of last resort is 10.0.2.2 to network 0.0.0.0

172.16.0.0/24 is subnetted, 1 subnets
C 172.16.0.0 is directly connected, Loopback0
10.0.0.0/24 is subnetted, 3 subnets
C 10.0.2.0 is directly connected, FastEthernet1/1
C 10.0.3.0 is directly connected, FastEthernet1/0
O 10.0.0.0 [110/2] via 10.0.2.2, 00:04:10, FastEthernet1/1
O E2 192.168.2.0/24 [110/20] via 10.0.2.2, 00:20:34, FastEthernet1/1
O*E2 0.0.0.0/0 [110/1] via 10.0.2.2, 00:01:43, FastEthernet1/1
Réseau OSPF