Les switch fabric peuvent s'implémenter de diverses manières :
- un réseau d'interconnexions configurable selon selon les besoins ;
- une mémoire ;
- un bus.
Certains switchs traitent les ports d'entrée à tour de rôle, l'un après l'autre : on parle de switchs à partage de temps, aussi appelés time-sharing switch chez les anglo-saxons. D'autres switchs permettent de gérer tous les ports d'entrée à la fois : on parle de switchs à partage d'espace, ou space-sharing switchs chez les anglo-saxons.
- Switchs fabric à base de bus ou de multiplexeurs
- Switchs fabric à mémoire partagée
- Switchs à base de réseau d'interconnexions
Switchs fabric à base de bus ou de multiplexeurs
Switchs à base de multiplexeurs
Certains switchs sont crées avec des multiplexeurs et des démultiplexeurs commandés par la CAM table ou la table de routage :
Switchs à base de bus
Pour faciliter l'implémentation du multicast et du broadcast, certains switchs émulent les liaisons point à point entre ports à partir d'un bus ou d'un réseau en anneaux : ce sont les switchs à média partagés.
Avec partage de temps
L'architecture la plus simple pour ce genre de switch est celle-ci :
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 filtreur d'adresse pour comparer l'adresse MAC/IP associé au port (CAM table) et l'adresse MAC de destination : si il y a égalité, alors on peut recopier la donnée sur le port de sortie. Dit autrement, la CAM table est distribuée dans les différents filtreurs d'adresse (ce qui rend sa mise à jour relativement mal-aisée, au passage).
Switchs totalement interconnectés
Les switchs vus plus haut sont des switchs à partage de temps (sauf le tout premier). Pour éviter cela, il suffit d'utiliser un bus par port d'entrée, chaque bus ayant ses propres filtreurs d'adresse : on obtient alors un switch totalement interconnecté.
Avec ces switchs, il se peut que plusieurs paquets soient destinés à un seul port de sortie. Dans ce cas, ces paquets sont accumulés dans une mémoire tampon en sortie des filtreurs d'adresse : ces switchs utilisent l'output buffering. Les sorties des différents filtreurs d'adresse sont donc directement reliés à cette mémoire, et peuvent écrire dedans sans problème. Cela signifie que la mémoire tampon est donc multiports.
Switch Knockout
Utiliser une mémoire multiports reliée à autant de filtreurs d'adresse est clairement un challenge quand le nombre de ports de sortie est trop grand. De plus, ce n'est utile que quand tous les paquets reçus sur les ports d'entrée doivent être routés sur un seul port de sortie. Dans la majorité des cas, seule une faible quantité de ports d'entrée veut router un paquet sur le même port de sortie.
Dans ces conditions, certains switchs ne permettent de router qu'un nombre limité de paquets sur le même port en même temps pour économiser du circuit. On obtient alors un Knockout switch. Le principe est très simple : les filtreurs d'adresse associés à un port de sortie sont suivis par un concentrateur, qui sélectionne L paquets parmi les N filtreurs d'adresse. Seuls ces N paquets sont envoyés dans les FIFO du port de sortie. Si jamais le nombre de paquets destinés au port de sortie dépasse la limite L, seuls L paquets seront conservés et les autres seront perdus.
Switchs fabric à mémoire partagée
Certains switchs replacent le bus interne par une mémoire RAM : ce sont les switchs à mémoire partagée. Ces switchs permettent de gérer l'arbitrage directement dans la switch fabric : la mémoire centrale stocke les FIFO d'arbitrage des ports d'entrée.
Le switch présenté dans le schéma ci-dessus peut être transformé en switch sans partage de temps avec une mémoire multiport : il suffit d'avoir autant de ports d’écriture que de ports d'entrée, et d’adapter les circuits de gestion de la mémoire. Dans ce qui va suivre, mes schémas utiliseront un switch à partage de temps.
Linked-list switch
Reste que ces FIFOs peuvent s'implémenter de différentes manières. Une première méthode mémorise les FIFOs dans des listes doublement chainées dans la RAM. Les circuits qui gèrent la mémoire partagée doivent gérer eux-même les listes chainées, ce qui fait qu'ils contiennent deux registres par liste : un pour l'adresse de la tête de la 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 switch 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 FIFO.
FIFO switch
La seconde méthode :
- réserve la mémoire centrale pour le stockage des paquets ;
- et maintient l'ordre d'envoi des paquets dans des FIFO, qui mémorisent les adresses des paquets dans la mémoire centrale.
La taille fixe des FIFOs ne permet pas d'allouer toute la mémoire pour seulement quelques ports. Mais cette organisation permet de gérer facilement le multi-cast et le broadcast : on peut facilement ajouter un paquet dans toutes les FIFO, simultanément avec un circuit d'ajout conçu pour.
CAM switch
Une autre solution, nettement plus simple, consiste à remplacer la mémoire RAM du switch par un cache (une mémoire associative, plus précisément). Chaque ligne de cache mémorise :
- un paquet ;
- le numéro de port de sortie ;
- l'ordre d'envoi du paquet, afin de simuler une FIFO
Pour mémoriser l'ordre d'envoi, le switch attribue un numéro de séquence à chaque paquet : plus ce numéro est grand, plus le paquet est ancien.
Switchs à base de réseau d'interconnexions
Switch crossbar
Le switch crossbar utilise un réseau d'interconnexion dont les fils sont organisés en lignes et en colonnes. A l'intersection de chaque ligne et de colonne, on trouve :
- soit un interrupteur qui relie la ligne et la colonne ;
- soit des FIFO d'arbitrage à pour gèrer l'Head-Of-Line Blocking.
Le nombre d'interrupteurs/FIFO est de N * M pour un switch à N ports d'entrée et M ports de sortie : pour les switchs qui ont un grand nombre de ports d'entrée et de sortie, cela devient rapidement impraticable. Pour éviter cela, les switchs à 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 : les simulations montrent que le rapport entre performance et nombre de portes logiques utilisées est meilleur avec cette technique.
Switch CLOS
On peut utiliser plusieurs switchs crossbar pour former un switch plus gros. Cette méthode donne ce que l'on appelle un réseau CLOS. Un réseau CLOS est conçu à partir de trois couches de réseaux crossbar : une couche d'entrée, une couche intermédiaire, et une couche de sortie.
Il est aussi possible d'utiliser plus de trois couches. Par exemple, on peut créer un switch CLOS à partir de plusieurs couches de crossbar 2 - 2 : on parle alors d'un réseau de Benes.
Switch de Banyan
Dans ce qui va suivre, nous allons nous intéresser aux switchs de Banyan.
Briques de base
Les versions les plus simples des switchs de Banyan sont conçues à partir de switchs à deux entrées et deux sorties, qui ressemblent à ceci :
On peut adapter les switchs de Banyan pour qu'ils n'utilisent pas des switchs 2 - 2, mais 3 - 3, ou 4 - 4, voire plus : on parle alors de switchs de Banyan augmentés. Qui plus est, ces briques de base peuvent contenir des FIFO et de la logique de traitement, comme pour les switch Crossbar.
Switch de Banyan
Ces switchs sont empilés pour former des couches, chaque couche possédant autant de sorties et d'entrée qu'il y en a dans le switch de Banyan final : si un switch a 8 entrées et 8 sorties, alors chaque couche aura 8 sorties et 8 entrées (et cela marche aussi avec 4, 16, etc). Le nombre de couches est égal au logarithme du nombre de ports d'entrée/sortie N, ce qui fait que le nombre de switchs de base utilisé est proportionnel à $N \times \log{N}$ : on économise donc des portes logiques comparé à un crossbar.
Le switch de Banyan le plus simple est composé de deux couches, et possède donc 4 entrées et 4 sorties. Il ressemble à ceci :
Pour un switch à 8 entrées et 8 sorties, voici ce que cela donne :
Et ainsi de suite…
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. Et non, je ne pose pas cet exercice parce que j'ai la flemme de vous l'expliquer…
Blague à part, 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 switch à 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 switchs 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 switchs ne sont pas sans défauts. En effet, ces switchs 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 switch 2 - 2, d'où conflit.
Switch Batcher-Banyan
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 switchs de Banyan sont précédés d'un circuit de tri conçu avec des switchs 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.
Switch Sunshine
Le switch de Banyan, et ses dérivés ont un défaut : il ne peut router qu'un seul paquet à la fois sur une sortie. Pour router plusieurs paquets sur une seule sortie, on est obligé d'utiliser plusieurs réseaux de Banyan. Plus exactement, il faut utiliser autant de réseaux de Banyan qu'il y a de ports d'entrée/sortie. Chaque réseau est alors relié à la mémoire FIFO utilisé pour l'output buffering.
Mais, encore une fois, il est rare que tous les ports d'entrée doivent transmettre un paquet sur un unique port de sortie. Dans cette situation, il vaut mieux concevoir un switch capable de gérer un nombre de paquets concurrents sur le même port plus petit. Ce nombre sera noté L. Ainsi, on peut alors se contenter d'utiliser seulement L réseaux de Banyan, chacun étant couplé à un tampon de sortie pour l'output buffering.
Fait intéressant, cela peut aussi s'appliquer avec un switch Batcher-Banyan : le réseau de Banyan et les buffers de sortie sont dupliqués en L exemplaires, mais le circuit de tri n'a pas besoin de l'être. Dans ces conditions, le circuit de tri est relié à un répartiteur qui répartit les paquets sur les réseaux de Banyan adéquats en fonction de leur adresse de destination.
Mais que faire des paquets en trop ? On pourrait les oublier et les jeter une bonne fois pour toute. Mais les switch Sunshine décident de simplement mettre en attente ces paquets, afin de les renvoyer une fois que les réseaux de Banyan le permettent. Ces paquets sont mis en attente dans une FIFO, et sont renvoyés au cycle suivant en entrée du trieur de paquet.