Protocoles de routage
1) Particularité d’Internet
Comme son nom l’indique, le réseau Internet (Interconnected Networks) est une interconnexion de différents réseaux.
La particularité de ces différents réseaux repose sur le fait qu’ils utilisent tous le modèle TCP/IP. En effet le réseau
Internet est tellement étendu qu’il est inconcevable de se limiter aux réseaux locaux car même s’il est possible d’inter-
connecter directement des réseaux locaux à l’aide de commutateurs ou de concentrateurs sans recourir à des protocoles
supplémentaires, ce procédé comporte de nombreux défauts empêchant leur extension à tout Internet :
– gestion complexes des tables d’association des commutateurs ;
– problèmes de sécurité sur un unique domaine de diffusion ;
– consommation excessive de la bande passante sur le réseau ;
– incompatibilité des protocoles de communications pour des technologies différentes (filaire, sans fil, etc).
Le protocole IP (Internet Protocol) est un protocole de niveau 3 dans le modèle OSI qui va jouer le rôle d’une couche
unificatrice afin d’interconnecter des réseaux utilisant des protocoles de niveau 2 différents. L’interconnexion de deux
réseaux (ou plus) se fait à l’aide d’un nouvel équipement appelé routeur . Pour acheminer les données d’un réseau à
un autre, les routeurs mettent en jeu un protocole de routage qui permet de calculer la meilleure route sur Internet
pour joindre une destination.
2) Adressage IP
Une adresse IP est une adresse qui permet d’identifier une machine dans le réseau. Il existe deux versions en fonction
du protocole utilisée. Une adresse IPv4 utilise 32 bits alors qu’une adresse IPv6 utilise 128 bits.
Une adresse IPv4 est généralement représentée sous la forme de 4 blocs (4 nombres entiers compris entre 0 et 255) et
séparée de points ([Link] par exemple). Il y donc 256 4 = 2 32 ≃ 4 milliards adresses IPv4 différentes.
Cette adressage n’est plus adaptée car le nombre d’appareils connectés est supérieur à 4 milliards, mais grâce au ré-
seau privé d’entreprise ou familiale, seule la box ou le routeur est directement relié à internet et dispose d’une adresse
publique c’est-à-dire visible sur le réseau internet. Les équipements connectés à la box ont des adresses privées , ces
adresses peuvent être réutilisées sur chaque réseau privé puisque ces réseaux ne sont pas directement reliées à internet,
les données passent par une passerelle (le routeur ou la box) pour rejoindre le réseau internet.
La norme IPv6 a été déployée fin des années 90 et a pour but de remplacer progressivement la norme IPv4. La tran-
sition est très lente et beaucoup d’adressage reste en IPv4. Cette nouvelle norme est généralement représentée par 8
blocs de 4 chiffres hexadécimaux ([Link] par exemple). Cette norme permet
d’adresser : (16 4 )8 = 2128 ≃ 3, 4 × 1038 machines. C’est un nombre énorme !
3) Adresse IPv4 et masque réseau
Une adresse IP comporte un double rôle. En plus du rôle d’identificateur, l’adresse IP permet également de localiser un
hôte. En effet, les premiers bits d’une adresse IP, le préfixe , servent de localisateur, c’est-à-dire qu’ils correspondent
à l’adresse du réseau dans lequel se situe l’hôte. Les derniers bits d’une adresse correspondent à l’identificateur de
l’hôte dans le réseau cité. Pour distinguer la séparation entre localisateur et identificateur on utilise un masque . Un
masque de réseau a le même format qu’une adresse IP. Les bits à 1 contigus de poids fort désignent la partie réseau
de l’adresse et les bits à zéro de poids faible la partie numérotation des machines sur le réseau (identificateur).
Le masque de réseau permet donc de récupérer le préfixe de l’adresse en faisant, à partir des écritures binaires, un ET
logique sur chaque bits des deux adresses.
Exemple : avec l’adresse IPv4 : [Link] et le masque [Link]
adresse décimal binaire
IP : [Link] 11000000 10101000 00001001 00010010
Masque : [Link] 11111111 11111111 11111100 00000000
Adresse réseau : [Link] 11000000 10101000 00001000 00000000
=⇒ Plage réseau : de [Link] à [Link], soit 210 = 1024 adresses dans ce sous réseau.
Remarque : La notation abrégée du couple adresse IP et masque s’écrit : [Link]/22.
L’avantage des adresses hiérarchiques est que les routeurs transmettent les paquets en ne tenant compte que de la
partie réseau de l’adresse. Les routeurs ne se soucient pas de la partie hôte car tous les hôtes sont dans la même direction.
1 NSI Tle - 2023/24
4) Adressage et mode de communication
• unicast : La communication a lieu entre une source et une destination.
Les paquets de données sont acheminés sur le réseau suivant l’adresse du destinataire
« encapsulée » dans la trame transmise. Normalement, seul le destinataire intercepte
et décode le paquet qui lui est adressé.
• broadcast : Les données sont envoyés à toutes les interfaces du réseau local. La
technique de broadcast permet d’envoyer des paquets à tous les participants d’un
réseau informatique sans que les adresses des destinataires soient connues. Chaque
réseau dispose à cet effet d’une adresse de broadcast réservée.
• multicast : une source envoie le même contenu à plusieurs destinataires faisant
partie d’un même groupe identifié par une adresse IP. La source génère un unique
paquet et les routeurs l’acheminent en limitant sa transmission aux réseaux qui
contiennent un membre du groupe ou qui doivent être traversés pour en atteindre
un, ce qui limite la congestion du réseau. Les adresses de classe D sont réservées au
multicast et sont uniquement utilisées comme adresse de destination.
• anycast : plusieurs destinations possèdent la même adresse IP. La communication
a lieu entre une source et l’IP de la destination la plus proche de la source. Ce mode
de communication est utilisé pour équilibrer la charge sur plusieurs serveurs. Un
service est dupliqué afin de supporter un grand nombre de clients. Le serveur de
nom (DNS) ainsi que les fournisseurs de contenus recourent souvent à ce mode de
communication.
5) Les algorithmes de routage
Les tables de routage des routeurs peuvent être construites de plusieurs manières. Dans le cas du routage statique , la
table est établie et modifiée manuellement à partir d’un centre de contrôle. Ce type de routage simple peut être utilisé
pour un petit réseau local avec une connexion externe. Cependant pour les grands réseaux, cette approche est difficile
à mettre en oeuvre et en cas de panne du centre de contrôle ou si celui-ci vient à être isolé d’une partie du réseau, le
réseau peut être paralysé ou du moins être incapable de réagir aux événements.
C’est pour cette raison que l’on préfère souvent laisser un algorithme distribué et itératif décider de manière autonome
des évolutions des tables de routage. On parle de routage dynamique , la table est alors mise à jour pérodiquement
et automatiquement à l’aide de protocoles spécifiques, qui peuvent s’adapter à la topologie du réseau. Les tables de
routage peuvent alors évoluer au fil du temps en fonction de l’évolution du réseau (ajout de routeurs, d’équipements
ou défaillance de routeurs ou de liaisons).
Chaque routeur du réseau va utiliser le même protocole pour découvrir petit à petit la topologie du réseau en échan-
geant régulièrement sa table de routage avec ses voisins et en la mettant à jour en fonction des informations reçus.
Deux types d’algorithmes de routage dynamique existent :
• Les algorithmes à vecteur de distance .
Ici, tous les routeurs disposent d’une table de routage qui précise, pour chaque destination possible, la meilleure
distance connue (i.e. le nombre de routeurs à traverser) et par quel routeur voisin l’atteindre. Par conséquent,
un routeur ne connait pas le chemin complet (i.e. la liste complète des routeurs à traverser) pour joindre une
destination, mais uniquement le coût du chemin et le prochain saut vers cette destination (plus simplement la
direction d’où la notion de vecteur).
Afin de compléter leurs tables de routage, les routeurs échangent périodiquement des vecteurs de distance. Ces
échanges n’ont lieu qu’entre routeurs voisins (i.e. directement connectés entre eux). Un vecteur de distance
consiste en un couple destination/distance.
Le protocole RIP est le protocole à vecteur de distance le plus utilisé sur les réseaux TCP/IP.
2 NSI Tle - 2023/24
• Les algorithmes à état des liens .
Ici, chaque routeur est en mesure de construire une carte complète de la topologie du réseau. À l’aide de cette
carte, chaque routeur peut calculer l’ensemble des plus courts chemins pour atteindre toutes les destinations
possibles. L’ensemble des plus courts chemins calculés par un routeur forme un arbre dont les premiers sauts
sont reportés dans sa table de routage. C’est généralement l’algorithme de Dijkstra qui est utilisé pour le calcul
des plus courts chemins.
À l’initialisation, chaque routeur doit être en mesure de lister chaque lien actif avec ses voisins et le coût de
ces liens. La métrique généralement utilisé pour estimer le coût d’un lien est une dérivée de la bande passante
disponible sur ce lien. Ensuite les routeurs diffusent ces informations appelés état des liens à l’ensemble des
routeurs participant au routage et pas uniquement à leurs voisins comme dans un protocole de routage à vecteur
de distance.
Le protocole OSPF est le protocole à état des liens le plus utilisé sur les réseaux TCP/IP.
6) Le protocole RIP (Routing Information Protocol)
Initialement chaque routeur a la connaissance de ses routeurs voisins ainsi que des sous réseaux auquels il est connecté.
Grâce aux messages qu’envoie régulièrement le routeur à ses voisins et en mesurant les temps de réponse de ces ma-
chines, un routeur peut déterminer si un des ses routeurs voisins est en panne ou si la liaison est rompue. Il peut
ensuite propager l’information à ses voisins. De cette manière, de proche en proche, tous les routeurs vont finir par
partager la même connaissance de la topologie du réseau.
Pour que ces échanges soit bien coordonnés, les routeurs doivent suivre le même protocole.
Principe du protocole RIP
Chaque routeur transmet à ses voisins les adresses de ses propres voisins et celles qu’il a reçues par d’autres routeurs.
En plus des adresses, le routeur indique la distance, exprimée en nombre de sauts (nombre de routeurs qui le sépare
d’une machine donnée). Ce sont ces couples (adresse, distance) appelée vecteurs de distance qui sont échangés entre
routeurs dans le protocole RIP.
Le plus court chemin vers chaque destination (celui qui traverse le moins de routeur) est ensuite calculé de manière
distribuée sur chaque routeur à l’aide de l’algorithme de Bellman-Ford et reporté dans la table de routage.
Distance maximale
Dans RIP la distance maximale d’une route est fixée à 15 routeurs , au delà la route est effacée ou ignorée.
Détection des pannes
Un routeur considère qu’un voisin est en panne (ou que la liaison vers son voisin est coupée) s’il ne reçoit pas de
réponse à une demande RIP au bout de trois minutes. Quand un routeur détecte qu’un sous-réseau est inaccessible il
envoie cette information à ces voisins sous forme d’une route avec une distance infinie (distance de 16 pour RIP).
Délai de convergence
C’est le temps nécessaire pour que tous les routeurs aient la même vue de la topologie du réseau. Le fait de limiter
cette distance à sauts à 15, permet d’obtenir un délai de convergence assez court. Par contre le protocole RIP ne peut
être utilisé que pour les petits réseaux (moins de 15 sauts chaque route).
Boucle de routage
Une boucle de routage peut se produire quand les informations contenues dans les tables de routage amènent un paquet
à tourner en boucle dans le réseau sans jamais pouvoir atteindre sa destination. Il y a deux solutions pour empêcher
ce phénomène. Le protocole RIP est conçu de manière à ce que ces boucles de routage ne puissent pas être créées lors
de la mise à jour des tables.
Inconvénients du protocole RIP
Le protocole RIP a deux inconvénients majeurs : il ne peut s’appliquer qu’aux petits réseaux (car il ignore les routes
de plus de 15 sauts) et ne tient pas compte de la nature des liaisons (fibre optique, satellite, sans fil, etc) et donc
du débits des liaisons entre routeurs. C’est pour palier à ces défauts que le protocole OSPF a été développé dans les
années 90 par l’organisme de normalisation international IETF (Internet Engineering Task Force).
3 NSI Tle - 2023/24
7) Protocole OSPF (Open Shortest Path First)
Ce protocole prend en compte la bande passante des liaisons de communications pour calculer les meilleures routes. La
bande passante est la quantité d’information qui peut être transmise par unité de temps. Habituellement, on mesure ce
débit en nombre de bits par seconde (bit/s ou bps). Pour pénaliser les liaisons lentes (avec une faible bande passante)
la métrique utilisée pour estimer le coût d’un lien est modélisée par la formule :
débit de référence
coût = où d est la bande passante de cette liaison en bit/s.
8
d
La valeur 10 est généralement choisie comme débit de référence pour associer un coût de 1 à une liaison FastEthernet
avec un débit de 100 Mbits/s. Ainsi, une liaison plus lente par cable Ethernet de 10 Mbits/s aura un coût de 10.
Fonctionnement dans une zone OSPF
Afin que le protocole OSPF puisse être facilement utilisé dans de grands réseaux, on répartit les routeurs de manière
logique dans différentes zones (une zone est un ensemble de machines).
Pour chaque zone (area) une table d’états de lien est construite et maintenue. La table de routage est construite à
partir de cette base de données. Ce résultat est obtenu grâce à l’application de l’algorithme de routage SPF.
Étape 1 : Découverte des voisins
Chaque routeur envoie, périodiquement, des messages de type hello à travers toutes ses interfaces réseaux. Les
paquets hello permettent à chaque routeur de s’annoncer auprès de ses voisins et d’intégrer dans une base de donnée
les adresses IP de ces voisins actifs et les coûts des liaisons entre eux.
Dès son initialisation ou à la suite d’un changement dans la topologie, le routeur va générer un paquet LSA (link-state
advertisement). Cette annonce va représenter la collection de tous les états des liens de voisinage du routeur.
Étape 2 : Inondations et mises à jour
Tous les routeurs de la zone vont s’échanger ces états de liens par inondation (flooding).
Chaque routeur qui reçoit des mises à jour d’état de lien (link-state update), en gardera une copie dans sa base de
donnée et propagera la mise à jour auprès des autres routeurs.
Étape 3 : Calcul des routes
Après que la base de données de chaque routeur ait été complétée, chacun va calculer l’arbre du chemin le plus court
(Shortest Path Tree) vers toutes les destinations avec l’algorithme Dijkstra . Le coût d’une route utilisée ici est la
somme des coûts des liaisons entre les routeurs traversés. La meilleure route sera celle ayant le coût le plus faible.
Chaque routeur va construire alors sa table de routage en choisissant les meilleures routes à inscrire.
Étape 4 : Maintenance des routes
Un nouvel état des liens n’est envoyé que lors d’une modification de la topologie (e.g. panne sur un lien). Chaque
nouvel état des liens ne comporte des informations que sur les liens qui ont été modifiés ce qui limite le volume des
données échangées. Puis l’algorithme “Dijkstra” recalcule les chemins les plus courts à inscrire dans la table de routage.
Organisation des zones
L’organisation des zones suit une structure hiérarchique très simple. Chaque
zone a un numéro unique.
La zone 0, obligatoire pour le protocole OSPF est appelé backbone . Il s’agit
d’une zone centrale à laquelle tous les autres zones sont connectées.
Pour être connecté à la backbone, une zone dispose d’un routeur particulier
appelé ABR (Area Border Router). Les routeurs ABR sont les seuls à être
rattachés à deux zones (leur zone et la backbone). Les autres routeurs sont
rattachés à une seule zone et ne communiquent qu’avec les routeurs de cette
zone.
Un ABR possède autant de bases de données d’états de lien qu’il y a d’inter-
faces connectées à des zones différentes.
Chacune de ces bases de données contient la topologie entière de la zone
connectée et peut donc être agrégée en une seule route IP.
Ces informations peuvent être transmises à la zone de backbone pour la distribution.
Un élément clé est qu’un ABR est l’endroit où l’agrégation doit être configurée pour réduire la taille des mises à jour
de routage qui doivent être envoyées ailleurs.
4 NSI Tle - 2023/24
