Protocoles de routage

Internet

Internet un réseau de réseaux, composé de millions de réseaux locaux, eux-mêmes regroupés en réseaux autonomes. Internet est un gigantesque graphe.

Routeur

Un routeur permet de relier ensemble plusieurs réseaux, il est composé d’un nombre plus ou moins important d’interfaces réseau. Il assure le routage des paquets d’une interface réseau vers l’autre.

Interface

Une interface est un point de connexion entre deux réseaux qui peut être physique ou virtuel (géré par le logiciel).

Pour pouvoir acheminer un paquet sur internet d’une source vers une destination, chaque interface est identifiée par son adresse IP.

1) Adresses IP

1.1) Binaire

voir cours de première : https://snt-nsi.net/nsi_premiere/types_de_base/representation_entiers/representation_des_entiers_naturels/

1.2) Adresses IPv4 et IPv6

Rappels de SNT : https://snt-nsi.net/snt/internet/protocole_tcp_ip/#protocole-ip

1.3) Masques de sous réseaux

On décompose les réseaux en sous réseaux pour pouvoir les administrer plus efficacement. Un masque de sous réseau permet d’identifier la partie correspondant au réseau dans l’adresse IP.

Par exemple, soit le masque de sous réseau suivant : 255.255.255.0

Et l’adresse IP : 192.168.1.1

Alors la partie réseau de l’adresse IP est : 192.168.1.1 Et la partie liée à l’hôte est : 192.168.1.1

On peut en déduire en utilisant l’exemple ci-dessus que 192.168.1.1 et 192.168.1.2 appartiennent au même sous réseau.

On obtient l'adresse du sous réseau avec l'opérateur AND et on obtient l'adresse de la machine (l'hôte) dans le sous réseau avec le AND du complément du masque.

Le complément (on inverse les bits) de 11111111.11111111.11111111.00000000 est 00000000.00000000.00000000.11111111.

1.4) Notation CIDR (Classless Inter-Domain Routing)

Il est commode de représenter le masque de sous réseau par un nombre entier au lieu d’utiliser 32 bits ou une adresse IP.

Dans l’exemple ci-dessus, on représente alors le masque de sous réseau de cette manière :

192.168.1.0 / 24 où 192.168.1.0 correspond à l’adresse du sous réseau et 24 correspond au masque de sous réseau en indiquant les bits à 1 de gauche à droite:

11111111.11111111.11111111.00000000 (3 paquets de 8 bits à 1 de gauche à droite = 24 )

A noter : cela laisse 256 - 2 adresses d’hôtes disponibles car une adresse est réservée pour identifier le réseau : 192.168.1.0 et une pour ce qu’on appelle une adresse de Broadcast qui permet d’envoyer un message à tous les hôtes appartenant au réseau.

Après ces rappels, nous allons étudier les différents types de routage : statique ou dynamique, et ensuite les deux protocoles qui vont nous intéresser pour ce cours : RIP et OSPF.

2) Routage

2.1) Table de routage

Pour permettre à un hôte d’un sous réseau donné de communiquer avec un hôte se trouvant dans un autre réseau, les paquets passent par des routeurs.

Le routage est décentralisé, c'est-à-dire que chaque routeur possède des informations sur son voisinage. Chaque routeur maintient alors une liste des réseaux connus, chacun de ces réseaux étant associé à un ou plusieurs routeurs voisins à qui le message peut être passé et à une information correspondant au coût ( la “distance”) pour se rendre entre ce routeur et le réseau de destination.

Exemple :

Cette liste s’appelle la table de routage. Il existe deux types de routage : le routage statique et le routage dynamique.

Nous allons étudier à quoi ces types de routage correspondent et dans quel cas on aura tendance à utiliser l’un plutôt que l’autre. C’est surtout le routage dynamique qui va nous intéresser.

2.2) Routage statique

Dans le routage statique, c’est l’administrateur qui construit et met à jour manuellement les tables de routage. Cela peut convenir lorsque le réseau est très petit ou pour certains besoins spécifiques, par exemple pour corriger un problème sur le réseau.

2.3) Routage dynamique

Nous allons étudier deux protocoles de routage dynamiques, tous deux basés sur des algorithmes de plus court chemin dans un graphe pondéré. L’un basé sur l’algorithme de Bellman-Ford et l’autre sur celui de Dijkstra.

Dans le routage dynamique, les tables de routage sont créées et mises à jour automatiquement par les routeurs. Un réseau peut être modélisé par un graphe, et alors le problème consiste pour les routeurs à déterminer quel sera le chemin qui permettra de transmettre le plus efficacement possible les paquets. Pour cela des algorithmes issus de la théorie des graphes sont utilisés. Il existe plusieurs protocoles de routage, dont notamment BGP (Border Gateway Protocol) que je vous invite à étudier si vous souhaitez comprendre le fonctionnement actuel d’internet.

2.3.1) RIP

Le protocole RIP repose sur l’algorithme de Bellman-Ford qui permet de déterminer les plus courts chemins dans un graphe. Pour cela, la métrique utilisée est le nombre de sauts (hops), c'est-à-dire le nombre de routeurs qui doivent être traversés pour atteindre le réseau cible. On parle de protocole à “vecteur de distance”.

Dans ce type de protocole , aucun routeur ne possède la vision globale du réseau, la diffusion des routes se faisant de proche en proche.

Toutes les 30 secondes, les routeurs mettent à jour leur table de routage grâce aux informations échangées entre routeurs voisins concernant les réseaux connus.

Exemple

On peut noter qu’il existe plusieurs trajets possibles, et donc plusieurs tables de routage possibles (exemple : A - D - F et A - E - F).

Si un routeur tombe en panne, l’information sera transmise dans les 30 secondes et les tables de routage seront mises à jour.

Ce protocole est rarement utilisé dans les réseaux de grande taille, car d’une part l’envoi de messages génère un trafic important et de plus le protocole RIP est limité à 15 sauts (on traverse au maximum 15 routeurs pour atteindre sa destination).

On préfère dans ce cas utiliser d’autres protocoles, comme par exemple OSPF.

2.3.2) OSPF

Contrairement à RIP, OSPF permet aux routeurs d'avoir une connaissance globale du réseau, c'est à dire que chacun des routeurs a les informations nécessaires concernant les autres routeurs se trouvant sur le réseau et la distance qui les sépare. C'est un protocole à "état de lien".

Au sein du protocole OSPF, il y a trois protocoles :

• le protocole Hello qui permet de vérifier les liens avec ses voisins
• le protocole d’inondation (flooding) : dès qu’un routeur détecte un changement au sein du réseau, il prévient les autres routeurs;
• le protocole d’échange qui permet aux routeurs d’échanger les données de la base de données topologique, afin qu’ils soient complètement synchronisés.

Pour établir la métrique, OSPF utilise la notion de “coût des liaisons”. La liaison étant le câble qui relie un routeur à un autre routeur.

En additionnant le coût de chacune des liaisons, OSPF calcule le coût total de la route. Pour déterminer les plus courts chemins, l’algorithme de Dijkstra est utilisé.

Le coût est lié au débit des liaisons entre routeurs. Le débit (aussi appelé “bande passante”) est le nombre de bits par seconde. Pour calculer le coût on utilise une formule du type :

\(Coût = \frac{10^{8}}{débit}\)

Le coût minimal est égal à 1. Cela signifie que dans cet exemple, il faudra un débit de 100Mb/s pour que le coût soit minimal.

Exemple

Le routeur choisit les chemins les plus courts (ceux qui sont surlignés).