Fonctionnement d'un ordinateur/Le matériel réseau

Dans ce chapitre, nous allons étudier plus en détail le matériel réseau, à savoir les hub, les switch, et les routeurs. Il existe de nombreux protocoles pour gérer la transmission sur un réseau, mais nous ne verrons que les protocoles Ethernet, MAC et IP, seuls pertinents pour ce chapitre. Les deux premiers, MAC et Ethernet, se chargent de la communication entre deux ordinateurs reliés par un câble réseau ou via un réseau local (à travers un concentrateur/commutateur, comme on le verra plus loin). Le protocole IP et ses associés gèrent les transferts sur des réseaux étendus internet, où tout transfert passe par un grand nombre d'intermédiaires.

Hub/switch/routeur.

Les commutateurs

Rappelons que les données sont transmises sur un réseau local sous la forme de trames, des blocs de données de taille fixe. Chaque trame contient à la fois des données utiles, mais aussi un en-tête qui contient toutes les informations nécessaires à la gestion de la trame. Notamment, chaque trame indique d'elle-même sa destination dans le réseau. L'ordinateur de destination est identifié par une adresse MAC de 6 octets (48 bits).

Réseau local en étoile.

Il existe plusieurs types de réseaux locaux, mais ceux que nous allons étudier sont des réseaux en étoile, où tous les ordinateurs sont reliés à un équipement central. L'équipement central sert de relai : il reçoit des trames (des paquets de données utiles) et les envoie aux ordinateurs de destination. Suivant la manière dont fonctionne l'équipement central, on distingue le concentrateur du commutateur. Un concentrateur est l'équivalent réseau d'un bus. Il redistribue chaque trame sans se préoccuper de sa destination. Chaque trame est envoyée à tous les ordinateurs/équipements réseau auquel il est connecté, sauf l'émetteur. Les concentrateurs sont à contraster avec les commutateurs, au fonctionnement similaire, mais qui n'envoient les trames qu'au composant de destination.

Différence entre concentrateur (à gauche) et commutateur (à droite).

Pas besoin de parler plus en détail du concentrateur : nous avons déjà parlé des bus dans un chapitre à part et le concentrateur en lui-même n'est rien d'autre qu'un bus ! Par contre, il est intéressant de parler du commutateur. Lorsqu'il reçoit une trame, le commutateur l'analyse, déduit quel est l'ordinateur de destination et renvoie la trame sur le port associé à l'ordinateur de destination. Pour faire son travail, le commutateur dispose de plusieurs sous-circuits :

• Un circuit extrait l'adresse MAC de destination des trames reçues.
• Un circuit qui décide, en fonction de l'adresse MAC de destination, sur quel port l'envoyer (le forwarding engine).
• Un circuit d'interconnexion qui relie chaque port à tous les autres.

Micro-architecture d'un switch

L'encapsulation et la commutation

Avant de nous intéresser au circuit d'interconnexion, nous allons étudier les deux autres circuits, à savoir : l'interpréteur de paquets, qui détecte ou analyse les trames/paquets, et le Forwarding Engine, qui détermine le port de destination à partir de l'adresse MAC de destination.

À l'intérieur du forwarding engine, on trouve une table de correspondance qui associe chaque adresse MAC à un port : la table CAM, aussi appelée CAM table en anglais. Elle peut être implémentée de plusieurs manières : avec une machine à états finis matérielle, avec une mémoire RAM ou avec une mémoire associative. La dernière solution est la plus utilisée, même si des solutions hybrides sont aussi relativement courantes. D'ailleurs, les mémoires associatives sont souvent appelées des mémoires CAM (Content Adressable Memories), ce qui a donné son nom à la table CAM. Il faut noter que le contenu de la table CAM a une durée de péremption, appelée le Time To Live, qui vaut entre 0 et 255 secondes. Elle permet de mettre à jour un réseau local sans avoir à redémarrer le commutateur. Par exemple, on peut remplacer un ordinateur branché sur le commutateur, ce dernier ne restera pas bloqué sur l'ancien ordinateur et finira par repérer le nouveau quand la table CAM aura été purgée.

Un commutateur doit découvrir par lui-même les adresses MAC des composants qu'on branche sur ses ports : il ne peut pas les connaitre à l'avance. Pour cela, le commutateur utilise une méthode assez simple. Au démarrage du commutateur, la table CAM est vide, le commutateur ne sait pas qui est qui sur ses ports. Quand il reçoit une trame, il met à jour la table CAM avec l'adresse MAC de l'émetteur de la trame : cela fait un port de connu. Une fois que tous les ordinateurs ont envoyé quelque chose sur le réseau, il connait tous les ports. Si aucun port n'est associé à une adresse de destination, le commutateur envoie le paquet à tous les ports.

Il faut noter que le switch peut être pipeliné, pour gagner en performance : il suffit d'insérer des mémoires tampons entre les différents circuits cités au-dessus.

Le circuit d'interconnexion (Switch Fabric)

Le circuit d'interconnexion, aussi appelée la switch fabric, relie les ports entre eux et est équivalent à un ensemble de connexions point à point configurables. Il est totalement configurable : il suffit de lui envoyer le numéro du port d'entrée et du port de sortie et le circuit d'interconnexion connecte ces deux ports (les autres ports restent déconnectés, en principe et sauf optimisation).

Switch Fabric.

Les techniques de broadcast ou de multicast permettent d'envoyer une donnée présentée sur un port d'entrée sur plusieurs sorties. Cela permet d'envoyer un message identique à plusieurs ordinateurs en même temps, sans devoir envoyer plusieurs copies. Certains commutateurs permettent de gérer cela directement dans le matériel, soit en dupliquant les paquets, soit en connectant une entrée sur plusieurs sorties. Dans ce qui va suivre, nous allons classer les commutateurs en deux types : les commutateurs à partage de temps et les commutateurs à partage d'espace.

Les commutateurs à partage d'espace

Les commutateurs à partage d'espace sont de loin les plus simples à comprendre. Ils sont simplement composés d'un ensemble de liaisons point à point, qui relient chacune un port d'entrée à un port de sortie. Chaque port d'entrée est relié à chaque port de sortie, chaque liaison pouvant être activée ou désactivée selon les besoins.

Il est possible de concevoir ce circuit avec des multiplexeurs.

Switch conçu avec des multiplexeurs.

Il est aussi possible d'utiliser un réseau crossbar. Ce dernier est composé de fils organisés en lignes et en colonnes. À l'intersection de chaque ligne et de colonne, on trouve un interrupteur qui relie la ligne et la colonne.

Réseau Crossbar.

Il est aussi possible de fabriquer un commutateur en combinant plusieurs commutateurs plus petits, avec moins d'entrées. La méthode la plus simple pour cela utilise plusieurs commutateurs crossbar pour former un commutateur plus gros, les différentes manières donnant respectivement un réseau CLOS, un réseau de Benes, un réseau de banyan, les Switch Sunshine, et bien d'autres.

Dans ce qui va suivre, nous allons nous intéresser aux commutateurs de Banyan, conçus à partir de commutateurs à deux entrées et deux sorties. Les commutateurs simples sont empilés en plusieurs couches, chaque couche possédant autant de sorties et d'entrée qu'il y en a dans le commutateur de Banyan final : si un commutateur a 8 entrées et 8 sorties, alors chaque couche aura 8 sorties et 8 entrées. Le nombre de couches est égal au logarithme du nombre de ports d'entrée/sortie N, ce qui fait que le nombre de commutateurs de base utilisé est proportionnel à N × log (N) : on économise donc des portes logiques comparé à un crossbar.

Le commutateur de Banyan le plus simple est composé de deux couches, et possède donc 4 entrées et 4 sorties. Il ressemble à ceci :

Switch de Banyan à deux couches (4 entrées et 4 sorties)

Pour un commutateurs à 8 entrées et 8 sorties, voici ce que cela donne :

Switch de Banyan à 3 couches (8 entrées et 8 sorties)

En guise d'exercice, regardez bien les schémas, et essayez d'en déduire la logique de construction. Vous verrez, rien de bien sorcier. Il existe différents types de réseaux de Banyan, qui portent les doux noms d'Omega, d'Alpha, etc. Ces réseaux se construisent simplement : si on prend un commutateur à N entrées (et autant de sorties), alors chaque couche doit réaliser une permutation des entrées et sorties, permutation qui doit respecter certaines propriétés pour tenir compte du fait que les commutateurs de base ont deux entrées et deux sorties. Le principe de création dépend donc des permutations utilisées sur chaque couche.

Mais ces commutateurs ne sont pas sans défauts. En effet, ces commutateurs sont dits bloquants : il se peut que deux paquets destinés à des ports de destination différents ne puissent pas voir leurs demandes assouvies simultanément. Cela arrive quand deux paquets veulent sortir sur le même port d'un des commutateurs 2 - 2, d'où conflit. Cependant, on peut éviter ces conflits internes en triant les paquets suivant leur port de destination avec un algorithme bien précis. En conséquence, certains commutateurs de Banyan sont précédés d'un circuit de tri conçu avec des commutateurs 2 - 2, empilés en couches, ainsi qu'avec de la logique de configuration composée de comparateurs : l'ensemble forme un switch Batcher-Banyan.

Il est possible d'adapter le principe des commutateurs de Banyan pour qu'ils n'utilisent pas des switchs 2 - 2 (deux entrées et deux sorties), mais 3 - 3, ou 4 - 4, voire plus : on parle alors de commutateurs de Banyan augmentés. Qui plus est, les commutateurs simples peuvent contenir des FIFO et de la logique de traitement, comme pour les commutateurs Crossbar.

Les commutateurs à partage de temps

Les commutateurs à partage de temps n'utilisent pas de liaisons point à point, mais les émulent à partir d'un bus ou d'un réseau en anneaux. De ce fait, ils sont parfois appelés des commutateurs à média partagés. Avec eux, chaque entrée est traitée à tour de rôle, l'une après l'autre.

Switch à partage de temps conçu avec des multiplexeurs.

Avec cette architecture, implémenter le multicast ou le broadcast est relativement complexe. Pour résoudre ce problème, il suffit de relier chaque port de sortie sur le bus interne directement, sans démultiplexeur. En faisant cela, chaque port de sortie doit filtrer les paquets qui ne lui sont pas destinés. Pour cela, on ajoute un filtre d'adresse pour comparer l'adresse MAC/IP associée au port (CAM table) et l'adresse MAC de destination : s'il y a égalité, alors on peut recopier la donnée sur le port de sortie. Ces commutateurs sont des commutateurs à partage de temps (sauf le tout premier).

Switch à média partagé.

L'arbitrage des trames

Le réseau d’interconnexion est relativement lent et il arrive que de nouvelles trames arrivent pendant qu'il est en train de transmettre un paquet. Dans ce cas, il est nécessaire de mettre les trames en attente tant que le paquet précédent n'est pas totalement traité. De même, il faut gérer le cas où plusieurs paquets veulent accéder au même port de sortie, ce qui impose d'envoyer les paquets les uns après les autres (il arrive cependant que certains paquets soient perdus). Dans tous les cas, qui dit mise en attente dit : utilisation de mémoires tampons de type FIFO. Un commutateur contient donc de nombreuses mémoires FIFO. Celles-ci sont d'autant plus grosses que son réseau d'interconnexion est lent et que les trames arrivent rapidement. Mettre les trames en attente dans des mémoires FIFO permet de gérer la plupart des situations. Mais il arrive que de nouvelles trames arrivent alors que les tampons sont déjà pleins. Dans ce cas, les paquets en trop sont perdus et n'arrivent pas à destination : on laisse la situation entre les « mains » du logiciel.

L'arbitrage hors du réseau d'interconnexion

Dans le cas le plus simple, les FIFO tampons sont placés en-dehors du réseau d'interconnexion. On peut les mettre avant le réseau d'interconnexion, ou après, ou les deux.

S'ils sont placés entre le réseau d'interconnexion et l'interface réseau de sortie, on parle d'output buffering.

Output buffering

S'ils sont placés en entrée du réseau d'interconnexion, on parle d'input buffering.

Input buffering

Il est parfaitement possible d'utiliser les deux en même temps, ce qui porte le nom d'input-output buffering.

Input-Output buffering

Si une requête est en attente via input buffering, elle va bloquer les requêtes suivantes sur le port d'entrée, même si celles-ci ont un port de sortie différent : on parle d'head of line blocking. Pour l'éliminer, certains commutateurs utilisent le Virtual output queing. Cela consiste à découper chaque FIFO en plusieurs FIFO, chacune prenant en charge les paquets destinés à un port de sortie précis. Avec cette technique, on peut traiter les requêtes dans le désordre, afin de profiter au maximum des ports libres.

Head-of-line blocking.

L'arbitrage dans le réseau d'interconnexion

Certains commutateurs intègrent les FIFOs directement dans le réseau d'interconnexion. Dans le cadre d'un réseau crossbar, il suffit de remplacer les interrupteurs ligne/colonne par des FIFO. Mais pour les commutateurs qui ont un grand nombre de ports d'entrée et de sortie, cela devient rapidement impraticable. Pour éviter cela, les commutateurs à haute performance réduisent la taille des FIFO intégrées dans le crossbar, mais rajoutent de grosses FIFO sur les ports d'entrée (input buffering). Les simulations montrent que le rapport entre performance et nombre de portes logiques utilisées est meilleur avec cette technique.

Switch Crossbar avec arbitrage intégré.

L'arbitrage sur les commutateurs à partage d'espace

Pour les commutateurs à partage d'espace, les tampons FIFO sont incorporés directement entre le MUX pour les ports d'entrée, et le reste (filtreur d'adresse ou DEMUX). Les FIFOS en question sont généralement implémentées avec une mémoire qui stocke les données des tampons FIFO et leur ordre d'arrivée. Le commutateur présenté dans le schéma ci-dessous peut être transformé en commutateur sans partage de temps avec une mémoire multiport qui a autant de ports d'écriture que de ports d'entrée. Dans ce qui va suivre, mes schémas utiliseront un commutateur à partage de temps.

Switch à mémoire partagée.

Implémenter plusieurs FIFO avec une seule mémoire peut se faire de plusieurs manières différentes. La solution la plus simple consiste à utiliser un cache (une mémoire associative, plus précisément). Chaque byte de cette mémoire mémorise un paquet, son numéro de port de sortie et son ordre d'envoi (afin de simuler une FIFO). Pour mémoriser l'ordre d'envoi, le commutateur attribue un numéro de séquence à chaque paquet : plus ce numéro est grand, plus le paquet est ancien. Obtenir le prochain paquet à envoyer demande simplement d'envoyer le numéro du prochain paquet (déterminé par un compteur) et le numéro du port de sortie à la mémoire associative. Celle-ci renvoie alors le paquet à envoyer sur ce port de sortie.

Une autre solution consiste à utiliser une mémoire RAM pour stocker les paquets dans des listes doublement chainées. Il y a une liste par port de sortie : tous les paquets destinés à un port de sortie sont ajoutés à la liste qui lui est associée. Les circuits qui gèrent la mémoire RAM doivent gérer eux-mêmes les listes chaînées, ce qui fait qu'ils contiennent deux registres par liste : un pour l'adresse en tête de liste et un pour le dernier élément. Il y a un circuit pour l'ajout et un autre pour le retrait des paquets. En plus de cela, les circuits de gestion de la mémoire doivent allouer dynamiquement les nœuds de la liste et libérer la mémoire. La mémoire utilise des Bytes démesurément grands, capables de mémoriser un paquet de plusieurs centaines de bits sans problèmes. Ainsi, le commutateur a juste besoin de mémoriser quels sont les Bytes libres et les Bytes occupés dans une mémoire annexe : la free list, souvent implémentée avec une mémoire FIFO.

• Une première méthode mémorise les données dans la RAM, ainsi que l'ordre de stockage des paquets.

Linked-list switch

• La deuxième méthode réserve la mémoire centrale pour le stockage des paquets et maintient l'ordre d'envoi des paquets dans des tampons FIFO, qui mémorisent les adresses des paquets dans la mémoire centrale. La taille fixe des mémoires FIFO ne permet pas d'allouer toute la mémoire pour seulement quelques ports. Mais cette organisation permet de gérer facilement le multicast et le broadcast : on peut facilement ajouter un paquet dans toutes les mémoires FIFO, simultanément avec un circuit d'ajout conçu pour.

FIFO switch

Les routeurs

Routage.

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 le réseau Internet. Sur le réseau Internet, les données sont transmises en paquets de taille variable, qui sont appelés sobrement des paquets réseau, ou encore des paquets. Chaque paquet se propage dans le réseau de proche en proche, passant par de nombreux intermédiaires avant d'arriver à destination. Ces intermédiaires sont appelés des routeurs.

Les routeurs sont similaires aux commutateurs, si ce n'est qu'ils gèrent des adresses différentes des adresses MAC : les adresses IP. Ces dernières permettent d'identifier un ordinateur sur Internet, mais n'a pas de lien avec les adresses MAC (qui sont limitées aux réseaux locaux). Pour simplifier, les routeurs reçoivent des paquets sur un port d'entrée, qui sont destinés à une adresse IP de destination, qui doit être envoyé à l'ordinateur de destination. Son fonctionnement est similaire à celui d'un commutateur amélioré. La seule différence notable est que la table CAM est remplacée par une table de routage, qui associe une adresse IP de destination au port de sortie qui correspond.

Routeurs de première génération

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

Routeurs de seconde génération

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

Routeurs de troisième génération

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

La carte réseau

La carte réseau est le composant qui permet à notre ordinateur de communiquer sur un réseau (local ou internet). Elle permet d'envoyer ou de recevoir des informations sur un câble réseau ou une connexion WIFI. Pour mieux comprendre son fonctionnement et les rôles qu'elle doit jouer, je vous conseille la lecture de mon wikilivre sur les réseaux informatiques, et notamment la lecture du chapitre sur la couche liaison.

La carte réseau communique avec le reste de l'ordinateur via le bus de la carte mère. Les données échangées sont mémorisées temporairement dans une mémoire tampon. Celle-ci permet de mettre en attente les données à envoyer tant que le réseau n'est pas disponible, ou d'accumuler les données reçues en attendant de les recevoir complètement. Ces données sont ensuite gérées par un circuit qui s'occupe de gérer les aspects réseau de la transmission : ajout/retrait des adresses MAC pour l'encapsulation, calcul de la somme de contrôle. Ce circuit est suivi d'une mémoire appelée la fenêtre glissante, qui contrôle l'ordre d'envoi des paquets. La carte réseau contient ensuite un circuit qui transforme les données à transmettre en ondes WIFI ou en signaux électriques (pour les câbles réseau). Dans tous les cas, les transferts d'informations se font en série (le câble est l'équivalent d'un bus série). L'interface de transfert contient donc deux registres à décalage : un pour faire la conversion parallèle -> série, et un autre pour la conversion série -> parallèle. En parallèle, on trouve un circuit qui détecte les conflits d'accès aux bus et qui les gère.

Architecture matérielle d'une carte réseau.