« 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 :
[[File:Internet-transit.svg|vignette|Routage.]]
[[File:Internet-transit.svg|vignette|Routage.]]


Il est maintenant temps de laisser les réseaux locaux derrière nous et de passer aux réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, mais il ne faut pas oublier l'ensemble des réseaux étendus. Sur ces réseaux étendus et sur Internet, 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. 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.
Il est maintenant temps de laisser les réseaux locaux derrière nous et de passer aux réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, mais il ne faut pas oublier l'ensemble des réseaux étendus. Sur ces réseaux étendus et sur Internet, 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. Déterminer quel est le chemin que doit parcourir la donnée pour arriver la destination est ce qu'on appelle le '''routage'''.


==Les différentes formes de routage==
==Les différentes formes de routage==

Version du 27 janvier 2019 à 20:22

Routage.

Il est maintenant temps de laisser les réseaux locaux derrière nous et de passer aux réseaux composés d'une interconnexion de réseaux locaux plus simples. Internet est l'un d'entre eux, mais il ne faut pas oublier l'ensemble des réseaux étendus. Sur ces réseaux étendus et sur Internet, 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. Déterminer quel est le chemin que doit parcourir la donnée pour arriver la destination est ce qu'on appelle le routage.

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

Pour savoir où envoyer les paquets recus, le routeur contient une table qui associe chaque IP de destination et le prochain intermédiaire. Cette table porte un nom : c'est la table de routage. Nous en reparlerons plus en détail dans le prochain chapitre. Pour le moment, nous allons simplement dire qu'elle permet de savoir où envoyer chaque paquet reçu. Nous n'avons pas besoin de plus.

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