Les réseaux informatiques/La couche liaison

Comme dit dans le chapitre précédent, un réseau local est un réseau contenant peu d'ordinateurs, qui sont reliés entre eux par des câbles réseaux, des routeurs ou des switchs. La gestion des réseaux locaux est le fait de la couche liaison, qui prend en charge les fonctionnalités suivantes : la mise en forme des données envoyés sur le réseau, l'identification des ordinateurs et la détection/correction des erreurs de transmission.

L'adressage physique

Pour simplifier, chaque ordinateur d'un réseau local reçoit un numéro qui permet de l’identifier : l'adresse physique. Pour être plus précis, l'adresse MAC est attribué aux cartes réseaux, mais aussi aux concentrateurs, aux routeurs, et à d'autres types de matériels. L'utilisation principale est celle des cartes réseaux : chaque carte réseau d'un ordinateur dispose de sa propre adresse physique. Par abus de langage, on dit que c'est l’ordinateur qui a cette adresse MAC, ce qui est rarement problématique. Mais il existe quelques rares cas où un ordinateur a plusieurs cartes réseaux, et donc plusieurs adresses physiques ! D'autres équipements, comme les routeurs ou les commutateurs ont une adresse physique, qui permet de s'y connecter si besoin. Cela peut, par exemple, servir à configurer un routeur/commutateur via un ordinateur connecté sur le réseau, sans avoir à se brancher directement sur le routeur/commutateur. Les administrateurs réseaux utilisent souvent cette possibilité pour configurer les routeurs d'un réseau depuis leur bureau, sans avoir à se déplacer dans plusieurs bâtiments pour chaque configurer chaque routeur à la main.

L'adressage MAC (Media Access Control)

MAC-48 Address

De nos jours, les adresses physiques sont définies par le standard MAC (Media Access Control). Avec ce standard, chaque adresse physique fait 6 octets (48 bits), et est appelée une adresse MAC.

Chaque équipement réseau dispose d'une adresse MAC unique au monde, attribuée par son fabricant. Mais l'utilisateur peut changer l'adresse MAC d'un réseau ou d'un ordinateur. Pour indiquer si l'adresse a été changée par l'utilisateur, l'adresse MAC contient un bit U/L. Il vaut 1 si l'adresse a été changée par l'utilisateur et 0 si l'adresse est l'adresse MAC originelle.

Les réseaux locaux eux-mêmes ont une adresse MAC, ce qui sert pour connecter des réseaux locaux entre eux. Si on envoie un paquet sur l'adresse d'un réseau, celle-ci sera envoyée à tous les ordinateurs du réseau : on parle alors de broadcast, ou encore de diffusion. Pour savoir si l'adresse MAC est celle d'un réseau ou d'un équipement réseau, chaque adresse MAC contient un bit I/G, qui vaut 1 si l'adresse est celle d'un réseau et 0 sinon.

Bit I/G	Bit U/L	Reste de l'adresse MAC
0	0	L'adresse MAC n'a pas été modifiée par l'utilisateur. L'adresse MAC se décompose en une adresse de 24 bits qui identifie un ordinateur dans le réseau, et un Organizationally Unique Identifier (OUI) de 24 bits qui identifie le constructeur du matériel.
0	1	L'adresse MAC a été modifiée par l'utilisateur.
1	0	Le reste de l'adresse pointe vers un réseau local.
1	1	Le reste de l'adresse est intégralement remplie avec des bits à 1. Elle est interprétée comme étant une adresse de broadcast pour le réseau local.

L'utilité de l'adressage MAC

L'adressage MAC permet de résoudre un problème se pose sur tous les réseaux (diffusants ou non). Grâce à lui, on peut déterminer le destinataire d'une trame pour qu'elle arrive à destination. Pour cela, chaque trame contient toutes les informations nécessaires pour identifier le destinataire. La trame précise son destinataire dans son en-tête de couche liaison, en donnant son adresse MAC.

Sur les réseaux diffusants, les trames sont envoyées à tous les ordinateurs en même temps, même à ceux qui ne sont pas destinataires de la donnée. Les récepteurs espionnent le support de transmission en permanence pour détecter les trames qui leur sont destinées, mais ils ne doivent pas prendre en compte les trames dont ils ne sont pas destinataires. Pour cela, toute trame indique quelle est son adresse MAC de destination. L'adresse en question est intégrée à la trame et est placée à un endroit précis, le plus souvent à son début. Les ordinateurs ont juste à extraire l'adresse MAC de la trame, et la comparer avec la leur pour savoir s'ils sont destinataires. Pour que la transmission soit la plus rapide, il vaut mieux que les périphériques sachent le plus rapidement si la trame leur est destinée, ce qui demande de mettre l'adresse au début de la trame.

Le codage du début et de la fin de transmission

Sur un réseau local, les données sont échangées sous la forme de paquets de données de taille fixe, qui sont émis par un ordinateur et se propagent dans le réseau local jusqu’à l'ordinateur de destination. Les paquets de données en question s'appellent des trames réseau. Le terme trame réfère aux données transmises : toutes les informations nécessaires pour une transmission sont regroupées dans ce qu'on appelle une trame qui est envoyée telle quelle.

Le codage des trames indique comment l'émetteur doit envoyer les données sur le support de communication, ce qui permet aux récepteurs de détecter les données transmises et les interpréter. Une trame doit fournir plusieurs informations. Premièrement, le codage des trames doit permettre une synchronisation des équipements réseaux, qui ne fonctionnent pas forcément à la même vitesse. Cela se fait par la transmission d'un signal de synchronisation ou signal d'horloge dans les trames. Enfin, la trame doit contenir toutes les données de la transmission, et de quoi contrôler celle-ci : indiquer les récepteurs, dire quand commence la transmission et quand elle se termine, etc. Mais surtout, le codage des trames doit indiquer quand commence une transmission et où elle se termine. Le récepteur ne reçoit en effet qu'un flux de bits et doit en extraire les trames. Cette extraction n’est pas simple et l'émetteur doit fatalement ajouter des bits pour coder le début et la fin des trames.

Inactiver la liaison à la fin de l'envoi d'une trame

Une première solution est de laisser la liaison complètement inactive durant un certain temps, entre l'envoi de deux trames. La liaison reste à 0 Volts durant un temps fixe à la fin de l'émission d'une trame. Les composants détectent alors ce temps mort et en déduisent que l'envoi de la trame est terminée. Malheureusement, cette méthode pose quelques problèmes.

• Premièrement, elle réduit les performances. Une bonne partie du débit binaire de la liaison passe dans les temps morts de fin de trame, lorsque la liaison est inactivée.
• Deuxièmement, certaines trames contiennent de longues suites de 0, qui peuvent être confondues avec une liaison inactive.

Dans ce cas, le protocole de couche liaison peut résoudre le problème en ajoutant des bits à 1, dans les données de la trame, pour couper le flux de 0. Ces bits sont identifiés comme tel par l'émetteur, qui reconnait les séquences de bits problématiques.

Les octets START et STOP

De nos jours, la quasi-totalité des protocoles utilisent la même technique : ils placent un octet spécial (ou une suite d'octet) au début de la trame, et un autre octet spécial pour la fin de la trame. Ces octets de synchronisation, respectivement nommés START et STOP, sont standardisés par le protocole.

Problème : il se peut qu'un octet de la trame soit identique à un octet START ou STOP. Pour éviter tout problème, ces pseudo-octets START/STOP sont précédés par un octet d'échappement, lui aussi standardisé, qui indique qu'ils ne sont pas à prendre en compte. Les vrais octets START et STOP ne sont pas précédés de cet octet d'échappement et sont pris en compte, là où les pseudo-START/STOP sont ignorés car précédés de l'octet d'échappement. Cette méthode impose au récepteur d'analyser les trames, pour détecter les octets d'échappements et interpréter correctement le flux de bits reçu. Mais cette méthode a l'avantage de gérer des trames de longueur arbitrairement grandes, sans vraiment de limites.

Trame avec des octets d'échappement.

Une autre solution consiste à remplacer l'octet/bit STOP par la longueur de la trame. Immédiatement à la suite de l'octet/bit START, l'émetteur va envoyer la longueur de la trame en octet ou en bits. Cette information permettra au récepteur de savoir quand la trame se termine. Cette technique permet de se passer totalement des octets d'échappement : on sait que les octets START dans une trame sont des données et il n'y a pas d'octet STOP à échapper. Le récepteur a juste à compter les octets qu'il reçoit et 'a pas à détecter d'octets d'échappements. Avec cette approche, la longueur des trames est bornée par le nombre de bits utilisés pour coder la longueur. Dit autrement, elle ne permet pas de trames aussi grandes que possibles.

Trame avec un champ "longueur".

Dans le cas où les trames ont une taille fixe, à savoir que leur nombre d'octet ne varie pas selon la trame, les deux techniques précédentes sont inutiles. Il suffit d'utiliser un octet/bit de START, les récepteurs ayant juste à compter les octets envoyés à sa suite. Pas besoin de STOP ou de coder la longueur de la trame.

Les bits de START/STOP

Il arrive plus rarement que les octets de START/STOP soient remplacés par des bits spéciaux ou une séquence particulière de fronts montants/descendants.

Une possibilité est d'utiliser les propriétés certains codages, comme le codage de Manchester. Dans celui-ci, un bit valide est représenté par un front montant ou descendant, qui survient au beau milieu d'une période. L'absence de fronts durant une période est censé être une valeur invalide, mais les concepteurs de certains bus ont décidé de l'utiliser comme bit de START ou STOP. Cela donne du sens aux deux possibilités suivantes : la tension reste constante durant une période complète, soit à l'état haut, soit à l'état bas. Cela permet de coder deux valeurs supplémentaires : une où la tension reste à l'état haut, et une autre où la tension reste à l'état bas. La première valeur sert de bit de START, alors que l'autre sert de bit de STOP. Cette méthode est presque identique aux octets de START et de STOP, sauf qu'elle a un énorme avantage en comparaison : elle n'a pas besoin d'octet d'échappement dans la trame, pas plus que d'indiquer la longueur de la trame.

Un autre exemple est celui des bus RS-232, RS-485 et I²C, où les bits de START et STOP sont codés par des fronts sur les bus de données et de commande.

La fiabilité des transmissions

Lorsqu'une trame est envoyée, il se peut qu'elle n'arrive pas à destination correctement. Des parasites peuvent déformer la trame et/ou en modifier des bits au point de la rendre inexploitable. Dans ces conditions, il faut systématiquement que l'émetteur et le récepteur détectent l'erreur : ils doivent savoir que la trame n'a pas été transmise ou qu'elle est erronée. Pour cela, il existe diverses méthodes de détection et de correction d'erreur. On en distingue deux classes : celles qui ne font que détecter l'erreur, et celles qui permettent de la corriger.

Détection et correction d'erreur

Tous les codes correcteurs et détecteurs d'erreur ajoutent tous des bits aux données de base, ces bits étant appelés des bits de correction/détection d'erreur. Ces bits servent à détecter et éventuellement corriger toute erreur de transmission/stockage. Plus le nombre de bits ajoutés est important, plus la fiabilité des données sera importante. Dans le cas le plus simple, on se contente d'un simple bit de parité. Dans d'autres cas, on peut ajouter une somme de contrôle ou un code de Hamming à la trame. Cela permet de détecter les erreurs de transmission, et de la corriger dans certains cas.

Bit de parité

Nous allons commercer par aborder le bit de parité/imparité, une technique utilisée dans un grand nombre de circuits électroniques, comme certaines mémoires RAM, ou certains bus (RS232, notamment). Il permet de détecter des corruptions qui touchent un nombre impair de bits. Si un nombre pair de bit est modifié, il sera impossible de détecter l'erreur avec un bit de parité. Il faut noter que ce bit de parité, utilisé seul, n permet pas de localiser le bit corrompu. Ce bit de parité est ajouté aux bits à stocker. Avec ce bit de parité, le nombre stocké (bit de parité inclus) contient toujours un nombre pair de bits à 1. Ainsi, le bit de parité vaut 0 si le nombre contient déjà un nombre pair de 1, et 1 si le nombre de 1 est impair. Si un bit s'inverse, quelle qu'en soit la raison, la parité du nombre total de 1 est modifié : ce nombre deviendra impair si un bit est modifié. Et ce qui est valable avec un bit l'est aussi pour 3, 5, 7, et pour tout nombre impair de bits modifiés. Mais tout change si un nombre pair de bit est modifié : la parité ne changera pas. Ainsi, on peut vérifier si un bit (ou un nombre impair) a été modifié : il suffit de vérifier si le nombre de 1 est impair.

Le bit d'imparité est similaire au bit de parité, si ce n'est que le nombre total de bits doit être impair, et non pair comme avec un bit de parité. Sa valeur est l'inverse du bit de parité du nombre : quand le premier vaut 1, le second vaut 0, et réciproquement. Mais celui-ci n'est pas meilleur que le bit de parité : on retrouve l'impossibilité de détecter une erreur qui corrompt un nombre pair de bits.

Pour obtenir plus d'informations sur le calcul logiciel de ce bit, je vous suggère de lire le chapitre de mon cours sur les opérations bits à bits : Bit de parité.

Code de Hamming

Le code de Hamming se base sur l'usage de plusieurs bits de parité pour un seul nombre. Chaque bit de parité n'est cependant pas calculé en prenant en compte la totalité des bits du nombre : seul un sous-ensemble de ces bits est utilisé pour calculer chaque bit de parité. Chaque bit de parité a son propre sous-ensemble, tous étant différents, mais pouvant avoir des bits en commun. Le but étant que deux sous-ensembles partagent un bit : si ce bit est modifié, cela modifiera les deux bits de parité associés. Et la modification de ce bit est la seule possibilité pour que ces deux bits soient modifiés en même temps : si ces deux bits de parité sont modifiés en même temps, on sait que le bit partagé a été modifié. Pour résumer, un code de Hamming utilise plusieurs bits de parité, calculés chacun à partir de bits différents, souvent partagés entre bits de parité.

Hamming(7,4)

Le code de Hamming le plus connu est certainement le code 7-4-3, un code de Hamming parmi les plus simples à comprendre. Celui-ci prend des données sur 4 bits, et leur ajoute 3 bits de parité, ce qui fait en tout 7 bits : c'est de là que vient le nom de 7-4-3 du code. Chaque bit de parité se calcule à partir de 3 bits du nombre. Pour poursuivre, nous allons noter les bits de parité p1, p2 et p3, tandis que les bits de données seront notés d1, d2, d3 et d4. Voici à partir de quels bits de données sont calculés chaque bit de parité :

Bits de parité incorrects	Bit modifié
Les trois bits de parité : p1, p2 et p3	Bit d4
p1 et p2	d1
p2 et p3	d3
p1 et p3	d2

Il faut préciser que toute modification d'un bit de donnée entraine la modification de plusieurs bits de parité. Si un seul bit de parité est incorrect, il est possible que ce bit de parité a été corrompu et que les données sont correctes. Ou alors, il se peut que deux bits de données ont été modifiés, sans qu'on sache lesquels.

Sommes de contrôle

Les sommes de contrôle sont des techniques de correction d'erreur, où les bits de correction d'erreur sont ajoutés à la suite des données. Les bits de correction d'erreur, ajoutés à la fin du nombre à coder, sont appelés la somme de contrôle. Techniquement, les techniques précédentes font partie des sommes de contrôle au sens large. Mais il existe un sens plus restreint pour le terme de somme de contrôle. Ce terme est souvent utilisé pour des techniques telle l'addition modulaire, le CRC, et quelques autres. Toutes ont en commun de traiter les données à coder comme un gros nombre entier, sur lequel on effectue des opérations arithmétiques pour calculer les bits de correction d'erreur. La seule différence est que l'arithmétique utilisée est quelque peu différente de l'arithmétique binaire usuelle. Dans les calculs de CRC, on utilise une arithmétique où les retenues ne sont pas propagées. Le calcul des additions et soustractions est alors extrêmement simple : elles se résument à de vulgaires XOR.

Une méthode très utilisée dans le cadre du réseau consiste à prendre les données à envoyer, à les diviser par un nombre entier arbitraire, et à utiliser le reste de la division euclidienne comme somme de contrôle. Cette méthode, qui n'a pas de nom, est similaire à celle utilisée dans les Codes de Redondance Cyclique. Effectuer une division dans l'arithmétique utilisée est alors très simple : il suffit d’effectuer la division comme en décimal, en remplaçant les soustractions par des XOR. C'est ainsi que sont calculés les CRC : on divise les données par un diviseur standardisé pour chaque CRC, dans l'arithmétique mentionnée précédemment, et on utilise le reste de la division comme somme de contrôle. L'avantage de ces CRC est qu'ils sont faciles à calculer en matériel. Le remplacement des soustractions entières par des XOR facilite fortement les calculs et leur implémentation. Les circuits de calcul de CRC sont ainsi très simples à concevoir : ce sont souvent de simples registres à décalage à rétroaction linéaire améliorés.

L'Automatic repeat request

ACK TCP

Si l'erreur peut être corrigée par le récepteur, tout va bien. Mais il arrive souvent que ce ne soit pas le cas : l'émetteur doit alors être prévenu et agir en conséquence. Pour cela, le récepteur peut envoyer une trame à l'émetteur qui signifie : la trame précédente envoyée est invalide. Cette trame est appelée un accusé de non-réception. La trame fautive est alors renvoyée au récepteur, en espérant que ce nouvel essai soit le bon. Mais cette méthode ne fonctionne pas si la trame est tellement endommagée que le récepteur ne la détecte pas. Pour éviter ce problème, on utilise une autre solution, beaucoup plus utilisée dans le domaine du réseau. Celle-ci utilise des accusés de réception, à savoir l'inverse des accusés de non-réception. Ces accusés de réception sont envoyés à l'émetteur pour signifier que la trame est valide et a bien été reçue. Nous les noterons ACK dans ce qui suivra.

Après avoir envoyé une trame, l'émetteur va attendra un certain temps que l'ACK correspondant lui soit envoyé. Si l’émetteur ne reçoit pas d'ACK pour la trame envoyée, il considère que celle-ci n'a pas été reçue correctement et la renvoie. Pour résumer, on peut corriger et détecter les erreurs avec une technique qui mélange ACK et durée d'attente : après l'envoi d'une trame, on attend durant un temps nommé time-out que l'ACK arrive, et on renvoie la trame au bout de ce temps si non-réception. Cette technique porte un nom : on parle d'Automatic repeat request.

Le protocole Stop-and-Wait

Dans le cas le plus simple, les trames sont envoyées unes par unes au rythme d'une trame après chaque ACK. En clair, l'émetteur attend d'avoir reçu l'ACK de la trame précédente avant d'en envoyer une nouvelle. Parmi les méthodes de ce genre, la plus connue est le protocole Stop-and-Wait.

Cette méthode a cependant un problème pour une raison simple : les trames mettent du temps avant d'atteindre le récepteur, de même que les ACK mettent du temps à faire le chemin inverse. Une autre conséquence des temps de transmission est que l'ACK peut arriver après que le time-out (temps d'attente avant retransmission de la trame) soit écoulé. La trame est alors renvoyée une seconde fois avant que son ACK arrive. Le récepteur va alors croire que ce second envoi est en fait l'envoi d'une nouvelle trame !

Pour éviter cela, la trame contient un bit qui est inversé à chaque nouvelle trame. Si ce bit est le même dans deux trames consécutives, c'est que l'émetteur l'a renvoyée car l'ACK était en retard. Mais les temps de transmission ont un autre défaut avec cette technique : durant le temps d'aller-retour, l'émetteur ne peut pas envoyer de nouvelle trame et doit juste attendre. Le support de transmission n'est donc pas utilisé de manière optimale et de la bande passante est gâchée lors de ces temps d'attente.

Les protocoles à fenêtre glissante

Les deux problèmes précédents peuvent être résolus en utilisant ce qu'on appelle une fenêtre glissante. Avec cette méthode, les trames sont envoyées les unes après les autres, sans attendre la réception des ACKs. Chaque trame est numérotée de manière à ce que l'émetteur et le récepteur puisse l’identifier. Lorsque le récepteur envoie les ACK, il précise le numéro de la trame dont il accuse la réception. Ce faisant, l'émetteur sait quelles sont les trames qui ont été reçues et celles à renvoyer (modulo les time-out de chaque trame).

On peut remarquer qu'avec cette méthode, les trames sont parfois reçues dans le désordre, alors qu'elles ont été envoyées dans l'ordre. Ce mécanisme permet donc de conserver l'ordre des données envoyées, tout en garantissant le fait que les données sont effectivement transmises sans problèmes. Avec cette méthode, l'émetteur va accumuler les trames à envoyer/déjà envoyées dans une mémoire. L'émetteur devra gérer deux choses : où se situe la première trame pour laquelle il n'a pas d'ACK, et la dernière trame envoyée. La raison est simple : la prochaine trame à envoyer est l'une de ces deux trames. Tout dépend si la première trame pour laquelle il n'a pas d'ACK est validée ou non. Si son ACK n'est pas envoyé, elle doit être renvoyée, ce qui demande de savoir quelle est cette trame. Si elle est validée, l'émetteur pourra envoyer une nouvelle trame, ce qui demande de savoir quelle est la dernière trame envoyée (mais pas encore confirmée). Le récepteur doit juste mémoriser quelle est la dernière trame qu'il a reçue. Lui aussi va devoir accumuler les trames reçues dans une mémoire, pour les remettre dans l'ordre.