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

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Ligne 56 : Ligne 56 :
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. Pour cela, les tables de routage doivent être correctement initialisées avant le transfert.
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. Pour cela, les tables de routage doivent être correctement initialisées avant le transfert.


La mise à jour des tables routage peut permettre de trouver des chemins plus courts ou plus rapides pour acheminer une donnée à une IP précise. Les algorithmes de routage peuvent en effet être conçus pour tenir compte des performances des différents chemins entre deux routeurs. Ils peuvent aussi 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. Cette mise à jour peut être gouvernée par un routeur central, qui communique aux autres routeurs les informations de mise à jour : on parle alors de routage centralisé. Mais c'est assez inefficace sur la plupart des réseaux de grande taille, dont internet, où un tel mode de fonctionnement est inadapté. Dans ce 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 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.
Ils peuvent aussi 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. Cette mise à jour peut être gouvernée par un routeur central, qui communique aux autres routeurs les informations de mise à jour : on parle alors de routage centralisé. Mais c'est assez inefficace sur la plupart des réseaux de grande taille, dont internet, où un tel mode de fonctionnement est inadapté. Dans ce cas, le routage est un routage décentralisé : chaque routeur met à jour sa table de routage individuellement, sans intervention d'un routeur central.


{{NavChapitre | book=Les réseaux informatiques
{{NavChapitre | book=Les réseaux informatiques

Version du 18 mai 2018 à 21:41

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.

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. Pour cela, l'émetteur et le récepteur se voient attribuer un numéro, l'adresse logique. On verra dans le chapitre suivant que cette adresse et une adresse dite IP, du nom du protocole IP qui standardise ces adresses et leur utilisation. Une fois les deux machines identifiées, il reste encore à 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.

Les différents modes de routage

Unicast
Anycast
Broadcast
Multicast

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.

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

Une opération distribuée

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. 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.

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. Pour cela, les tables de routage doivent être correctement initialisées avant le transfert.

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.

Ils peuvent aussi 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. Cette mise à jour peut être gouvernée par un routeur central, qui communique aux autres routeurs les informations de mise à jour : on parle alors de routage centralisé. Mais c'est assez inefficace sur la plupart des réseaux de grande taille, dont internet, où un tel mode de fonctionnement est inadapté. Dans ce cas, le routage est un routage décentralisé : chaque routeur met à jour sa table de routage individuellement, sans intervention d'un routeur central.