« Les réseaux informatiques/Les protocoles de routage » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
mAucun résumé des modifications
Ligne 1 : Ligne 1 :
Il est maintenant temps de laisser les réseaux locaux derrière nous, et de voir plus grand. Par plus grand, je veux dire que nous allons aborder les réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, même si ce n'est pas le seul. Quoiqu'il en soit, ces interconnexions de réseaux ne fonctionnent que si divers mécanismes permettent à ces réseaux de communiquer.
Il est maintenant temps de laisser les réseaux locaux derrière nous, et de voir plus grand. Par plus grand, je veux dire que nous allons aborder les réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, même si ce n'est pas le seul.


[[File:Internet-transit.svg|vignette|Routage.]]
[[File:Internet-transit.svg|vignette|Routage.]]


Dans un réseau partiellement maillé, tel Internet, la donnée est propagée de proche en proche, d'intermédiaire en intermédiaire : on appelle ces intermédiaires des '''routeurs'''. Cette propagation doit cependant être gérée, histoire que la donnée arrive bien à destination. Ces mécanismes demandent d'identifier les machines émettrices et réceptrices avec une IP et de propager les segments/paquets de données de proche en proche, de l'adresse IP source vers l'IP destinatrice. Déterminer quel est le chemin que doit parcourir la donnée pour arriver la destination est ce qu'on appelle le '''routage'''. Divers protocoles s'occupent de faire fonctionner ce routage, et les plus connus sont clairement BGP et IGP. Nous les verrons probablement dans la suite du cours, ce chapitre se concentrant surtout sur les mécanismes cachés derrière le routage.
Sur ces réseaux, les paquets sont propagés de proche en proche, d'intermédiaire en intermédiaire, jusqu’à la destination. Les intermédiaires en question s’appellent des '''routeurs'''. Cette propagation doit cependant être gérée, histoire que la donnée arrive bien à destination. Ces mécanismes demandent d'identifier les machines émettrices et réceptrices avec une IP et de propager les segments/paquets de données de proche en proche, dans la bonne direction. Déterminer quel est le chemin que doit parcourir la donnée pour arriver la destination est ce qu'on appelle le '''routage'''. Divers protocoles s'occupent de faire fonctionner ce routage, et les plus connus sont clairement BGP et IGP. Nous les verrons probablement dans la suite du cours, ce chapitre se concentrant surtout sur les mécanismes cachés derrière le routage.


==Les routeurs==
==Les routeurs==

Version du 26 janvier 2019 à 20:33

Il est maintenant temps de laisser les réseaux locaux derrière nous, et de voir plus grand. Par plus grand, je veux dire que nous allons aborder les réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, même si ce n'est pas le seul.

Routage.

Sur ces réseaux, les paquets sont propagés de proche en proche, d'intermédiaire en intermédiaire, jusqu’à la destination. Les intermédiaires en question s’appellent des routeurs. Cette propagation doit cependant être gérée, histoire que la donnée arrive bien à destination. Ces mécanismes demandent d'identifier les machines émettrices et réceptrices avec une IP et de propager les segments/paquets de données de proche en proche, dans la bonne direction. Déterminer quel est le chemin que doit parcourir la donnée pour arriver la destination est ce qu'on appelle le routage. Divers protocoles s'occupent de faire fonctionner ce routage, et les plus connus sont clairement BGP et IGP. Nous les verrons probablement dans la suite du cours, ce chapitre se concentrant surtout sur les mécanismes cachés derrière le routage.

Les routeurs

Le routage est pris en charge par les routeurs qui propagent la donnée : chaque routeur prend une décision, et décide vers quel routeur ou ordinateur il doit propager la donnée. Il n'y a pas de serveur central qui déciderait comment router la donnée. En conséquence, cette opération demande des ressources matérielles pour décider vers quel voisin il faut envoyer la donnée. Et cela demande du temps de calcul, de la mémoire, et potentiellement d'autres ressources.

La table de routage

Un routeur peut être vu comme l'équivalent d'un commutateur, mais pour une interconnexion de réseaux : là où le commutateur connecte des machines dans un même réseau local, le routeur connecte et sert d'interface à deux réseaux différents. Il reçoit des paquets sur certains ports, et les renvoie sur d'autres : il doit juste envoyer les paquets reçus vers le meilleur port de sortie, celui qui rapprochera le paquet de sa destination. Pour cela, le routeur doit savoir quelle est la meilleure sortie pour chaque adresse IP de destination possible. Du moins, c'est la théorie, vu que le routeur peut compresser ces informations de différentes manières. Quoiqu’il en soit, le routeur doit bel et bien garder des correspondance entre une adresse IP de destination et le numéro du port sur lequel il doit envoyer le paquet. Tout cela est mémorisé dans une sorte de mémoire RAM : la table de routage. Cependant, ces tables de routage sont rarement complètes : elles ont une taille limitée, et elles ne peuvent pas mémoriser toutes les correspondances possibles et imaginables. Et cela peut poser quelques problèmes. Mettons-nous dans le cas où un routeur doit router un paquet vers une IP de destination, et où le routeur n'a pas de correspondance pour cette IP dans sa table de routage. Celui-ci ne sait pas sur quel port il doit router le paquet. Mais le routeur a une solution : router le paquet vers une route par défaut, vers un port choisi par défaut en cas d'absence de correspondance.

Les routeurs sont similaires aux commutateurs, si ce n'est qu'ils gèrent des adresses IP au lieu d'adresses MAC. Ils reçoivent des trames sur un port d'entrée, trames qui destinées à une adresse IP de destination. Cette trame doit être envoyée à l'ordinateur de destination, et donc envoyée sur un des ports de sortie du routeur, celui qui mènera ultimement la trame à destination. Son fonctionnement est similaire à celui d'un commutateur amélioré. Dans les grandes lignes, la table CAM est remplacée par une table de routage, qui associe une adresse IP de destination au port de sortie qui correspond. Le reste de l'architecture interne du routeur est basée soit sur un bus, soit sur une switch fabric.

Les générations de routeurs

Les tout premiers routeurs, dits de première génération, relient leurs ports d'entrée et de sortie avec un bus. ils contiennent aussi un processeur tout ce qu'il y a de plus normal pour traiter les trames IP, ainsi qu'une mémoire RAM pour stocker les trames et la table de routage. Chaque port est relié à de circuits chargés de gérer le port. Ces circuits reçoivent des trames, les envoient et effectuent quelques traitements basiques. Ils gèrent notamment tout ce qui a trait aux adresses MAC. Une fois que ces circuits ont fait leur office, ils envoient la trame traitée sur le bus interne au routeur. La trame est alors réceptionnée par le processeur, éventuellement stockée en mémoire RAM. Celui-ci accède alors à la table de routage, pour identifier le port de sortie. Enfin, le processeur envoie la trame vers le port de sortie qu'il a déduit de ses traitements. La trame est alors envoyée sur le réseau. Le défaut principal de ce type de routeur est que les transferts en direction du processeur principal saturent le bus dans certaines situations critiques.

1st-generation router architecture
1st-generation router architecture

Les routeurs de seconde génération sont plus complexes. Ceux-ci multiplient le processeur, la RAM et la table de routage en plusieurs exemplaires : un exemplaire par port. Ainsi, les trames reçues sur un port sont directement traités dans les circuits de gestion de ce port. Une fois traitée, elles sont envoyées directement sur le port de sortie, et envoyée immédiatement sur le réseau. Cependant, cela ne vaut que pour des trames simples. Les trames plus complexes doivent être traitées par un processeur plus complexe, non-attaché à un port. Ce processeur, le superviseur, est unique dans le routeur.

2nd-generation router architecture
2nd-generation router architecture

Cependant, les deux types de routeurs précédents utilisent un bus pour afin de faire communiquer les différents composants. Or, il se peut que les conflits d'accès au bus minent les performances. Pour éviter cela, certains routeurs remplacent le bus par une switch fabric, pour gagner en performance. Ainsi, les transfert n'entrent pas en conflit pour l'accès à un unique bus, chaque transfert pouvant se faire en parallèle des autres.

3rd-generation router architecture
3rd-generation router architecture

Les différentes formes de routage

Évidemment, il existe plusieurs manières de router les paquets à destination. Et on peut classer les différentes méthodes de routage en plusieurs catégories. Dans ce qui va suivre, nous allons donner quelques critères qui permettent de classer les protocoles de routage.

Les modes de routage

Le routage peut prendre différentes formes suivant le nombre de destinataires. Un ordinateur peut en effet vouloir communiquer avec un ordinateur bien précis, ou envoyer une donnée à plusieurs PC différents. Suivant le nombre de destinataire, on peut faire la différence entre Unicast, Anycast, Multicast et Broadcast.

Avec l'unicast, un ordinateur émet des données à destination d'un autre ordinateur bien identifié.

Avec l'anycast, un ordinateur émet des données vers un ordinateur qu'il ne connait pas : l'émetteur ne connait pas la destination de la donnée. L'ordinateur de destination n'est cependant pas choisit au hasard : c'est le protocole de routage qui choisit vers quel ordinateur émettre la donnée.

Avec le multicast, les données émises sont envoyées à un groupe d'ordinateur qui veulent recevoir cette donnée. Les ordinateurs qui veulent revoir la donnée se connectent à un serveur et s'inscrivent à un groupe de diffusion. Tous les ordinateur inscrits dans ce groupe recevront la donnée émise. C'est notamment utilisé lors du streaming d'évènements en live : on émet la donnée une fois, et celle-ci sera recopiée par les routeurs à toutes les personnes inscrites au groupe que le routeur connait. Pour faire simple, le groupe possède une adresse logique (une IP) qui permet de l'identifier. Quand une donnée est envoyée à l'adresse du groupe, le serveur reçoit le paquet et en envoie des copies à tous les ordinateurs du groupe. L'adresse IP du serveur/groupe est appelée une adresse multicast.

Avec le broadcast, le paquet émis est envoyé à tous les ordinateurs d'un réseau ou sous-réseau (un réseau local le plus souvent). Selon que le paquet se propage dans un réseau local ou sur internet, on distingue deux formes de broadcast.

  • Le broadcast limité a une portée limitée au réseau local de l'émetteur. Le paquet est envoyé aux voisins de l'ordinateur émetteur, mais reste confiné dans le réseau local. Il traverse les switchs et hubs, mais ne passe pas les routeurs : ces derniers n'envoient pas le paquet sur internet. L'adresse de broadcast utilisée est l'adresse 255.255.255.255.
  • Le broadcast dirigé est similaire au précédent, sauf que le paquet n'est pas confiné dans un réseau local et peut passer les routeurs pour se déplacer sur internet.
Unicast
Anycast
Broadcast
Multicast

Routage statique et dynamique

Le contenu de la table de routage peut être déterminé à l'avance par les concepteurs du réseau, ou mis à jour régulièrement (pour s'adapter à des ajouts ou retraits de machines). Dans le premier cas, les tables de routage sont remplies lors de l'allumage du routeur, et ne sont jamais mises à jour. On parle alors de routage statique, dans le sens où il ne peut pas évoluer sans que le gestionnaire du réseau ne fasse les modifications adéquates. Bien que très simple, cette approche a cependant de nombreux défauts. Déjà, saisir à la main chaque ligne de la table de routage est parfois long, compliqué, chronophage. Le faire de manière automatisée, chaque routeur construisant la table de routage de lui-même, étant de loin une meilleure solution. De plus, la table de routage ne peut pas s’adapter à une panne de réseau ou au changement de celui-ci. Toute modification des connexions intra-réseau demande de modifier la table de routage, manuellement.

Un routage dynamique permet de mettre à jour les tables de routage à la volée, régulièrement, sans intervention humaine. Cette mise à jour des tables de routage est alors prise en charge par un algorithme de routage, une sorte de programme intégré aux routeurs qui leur dit quoi faire pour se mettre à jour. Une sorte d'équivalent des mises à jour Windows, mais pour la table de routage. Ces algorithmes de routage sont pris en charge par des protocoles divers comme IGP ou BGP, que nous n'aborderons pas dans le détail tellement ils sont complexes. Les algorithmes de routage dynamique peuvent repérer les chemins endommagés, qui ne fonctionnent plus (un routeur débranché ou en panne, par exemple), et trouver des routes alternatives. Le réseau se reconfigure à chaque instant pour que le service soit maintenu, et que les performances soient conservées.

Routage centralisé ou distribué

On peut aussi distinguer les méthodes de routage selon la méthode utilisée pour mettre à jour les tables de routage. La mise à jour des tables de routage peut être gouvernée par un routeur central, qui communique aux autres routeurs les informations de mise à jour : on parle alors de routage centralisé. Dans l'autre cas, le routage est un routage décentralisé : chaque routeur met à jour sa table de routage individuellement, sans intervention d'un routeur central.

Les algorithmes de routage

Exemple de réseau représenté sous la forme de graphe, avec les tables de routage qui correspondent.

Tous les algorithmes de routage se basent sur les mêmes principes mathématiques, à savoir la théorie des graphes. Pour faire simple, ces algorithmes modélisent un réseau sous la forme d'un ensemble de points reliés par des flèches : les points représentent les routeurs et ordinateurs, alors que les flèches indiquent les liens entre ces routeurs. Un exemple de graphe est donné dans le dessin à votre droite. Le but de l'algorithme est de trouver un chemin dans ce graphe qui relie l'émetteur au destinataire. Il existe de nombreux algorithmes pour trouver le chemin le plus court entre deux points d'un graphe, et il n'est pas question d'en faire la liste ici. Cependant, sache que ceux-ci ne sont pas utilisés tels quels par les algorithmes de routage.

Graphe numéroté.

Les algorithmes de routage peuvent aussi tenir compte des performances des différents chemins entre deux routeurs. La mise à jour des tables routage permet alors de trouver des chemins plus courts ou plus rapides pour acheminer une donnée à une IP précise. Il suffit pour cela de tenir compte des temps de transferts entre routeurs. Pour cela il suffit d'associer à chaque flèche, chaque chemin entre deux routeurs, un poids qui indique sa rapidité. Plus la vitesse de transfert est faible entre ces deux routeurs, plus ce nombre sera fort. Pour chaque chemin identifié, l'algorithme additionne le temps de transfert de chaque flèche. Le but de l'algorithme est de trouver le chemin qui minimise le temps de transfert, qui minimise la somme finale.

Les algorithmes de routage par inondation (aléatoires)

Les algorithmes deroutage par inondation font un routage complètement aléatoire, où chaque routeur émet les paquets reçus sur toutes ses sorties. Ce qui explique le nom de cet algorithme : le routeur inonde le réseau du paquet reçu. Et aussi bizarre que cela puisse paraitre, cet algorithme garantit que le récepteur recevra le paquet, tant qu'il existe un paquet entre l'émetteur et le récepteur. De plus, cet algorithme réagit parfaitement aux changement du réseau : on peut changer les connexions du réseau sans que cela empêche le paquet d'arriver à destination. Mais les défauts sont assez évidents : beaucoup de bande passante est gâchée pour envoyer un paquet en plusieurs exemplaires.

Pour éviter cela, on peut modifier l'algorithme précédent et n'envoyer le paquet reçu que sur une seule sortie, qui est choisie aléatoirement. Cela évite d'envoyer plusieurs copies d'un même paquet, mais celui-ci prendra parfois un chemin assez tordu et mal commode pour arriver à destination. Le paquet peut se perdre en chemin et mettre beaucoup de temps avant d'arriver. Les performances du réseau sont améliorées, du terme de bande passante, mais pas en temps de latence, qui augmente. L'algorithme en question est appelé algorithme par inondation sélective.

Les algorithmes de routage de type "Vecteur de distance"

Les algorithmes de routage de type "État de lien"

Les Autonomous systems

Illustration de la communication entre deux Autonomous Systems, chacun appartenant à un fournisseur d'accès (ISP).

Le routage sur internet n'est pas effectué par une instance centralisée, vu la taille du réseau et son organisation. Difficile d'organiser autour d'un seul protocole ce qui est avant tout une interconnexion de réseaux très différents. Il est proprement impossible de décider de la table de routage de chaque routeur tant il y en a, sans même parler de propager les mises à jour des tables de routage. En réalité, Internet est organisé autour de réseaux indépendants qui sont chacun "indépendants" en terme de routage : les Autonomous systems, abréviés AS. Un AS est un ensemble de réseaux et de routeurs reliés entre eux, qui sont soumis à un même protocole de routage. Ceux-ci sont souvent soumis à une même entité commerciale ou administrative : par exemple, chaque fournisseur d'accès possède son propre AS. Chaque AS est identifié par un numéro, l'Autonomous System Number (ASN), attribué par diverses organisations internationales. Tous identifient un AS, à l'exception de quelques numéros dédiés à des usages un peu particuliers, dans les protocoles de routage par exemple.

Le routage est cohérent à l'intérieur d'un AS, alors qu'il ne l'est pas entre les AS, et cela se ressent dans les algorithmes de routage utilisés. Les AS utilisent des protocoles de type IGP (Interior Gateway Protocols) pour mettre à jour les tables de routage, alors que la communication entre AS est réalisée par des protocoles de type EGP (Exterior Gateway Protocols)/BGP (Border Gateway Protocols).

Le protocole BGP

Les protocoles IGP