Fonctionnement d'un ordinateur/Les liaisons point à point

On a vu dans le chapitre précédent qu'il faut distinguer les liaisons point à point des bus de communication. Dans ce chapitre, nous allons voir tout ce qui a trait aux liaisons point à point, à savoir comment les données sont transmises sur de telles liaisons, comment l'émetteur et le récepteur s'interfacent, etc. Gardez cependant à l'esprit que tout ce qui sera dit dans ce chapitre vaut aussi bien pour les liaisons point à point que pour les bus de communication. En effet, les liaisons point à point font face aux même problèmes que les bus de communication, si ce n'est la gestion de l'arbitrage.

Deux composants électroniques communiquent entre eux en s'envoyant des trames, des paquets de bits où chaque information nécessaire à la transmission est à une place précise. Le codage des trames indique comment interpréter les données transmises. Le but est que le récepteur puisse extraire des informations utiles du flux de bits transmis : quelle est l'adresse du récepteur, quand la transmission se termine-t-elle, et bien d'autres. Les transmissions sur un bus sont standardisées de manière à rendre l'interprétation du flux de bit claire et sans ambiguïté.

Le terme trame est parfois réservé au cas où le paquet est envoyé en plusieurs fois. Le cas le plus classique est celui des bus série : la trame est envoyée bit par bit, donc en plusieurs fois. Le récepteur accumule les bits dans un registre à décalage, jusqu'à avoir une trame complète. Sur un bus parallèle, il peut y avoir des trames, si les données à transmettre sont plus grandes que la largeur du bus. Tout ce qui sera dit dans ce chapitre vaut pour les trames au sens ! paquet de données envoyé en plusieurs fois.

La taille d'une trame

La taille d'une trame est soit fixe, soit variable. Par fixe, on veut dire que toutes les trames ont la même taille, le même nombre de bits. Une taille de trame fixe rend l'interprétation du contenu des trames très simple. On sait où sont les données, elles sont tout le temps au même endroit, le format est identique dans toutes les trames. Mais il arrive que le bus gère des trames de taille variable.

Par exemple, prenons l'exemple d'un bus mémoire série, à savoir que la mémoire est reliée à l'extérieur via un bus série (certaines mémoires FLASH sont comme ça). Un accès mémoire doit préciser deux choses : s'il s'agit d'une lecture ou d'une écriture, quelle est l'adresse à lire/écrire, et éventuellement la donnée à écrire. Une trame pour le bus mémoire contient donc : un bit R/W, une adresse, et éventuellement une donnée. La trame pour la lecture n'a pas besoin de préciser de données à écrire, ce qui fait qu'elle contient moins de données, elle est plus courte. Pour une mémoire à accès série, reliée à un bus série, cela fait que la transmission de la trame est plus rapide pour une lecture que pour une écriture.

Sur un bus parallèle, la taille de la trame pose quelques problèmes. Dans le cas idéal, la taille de la trame est un multiple de la taille d'un mot, un multiple de la largeur du bus. Une trame contient N mots, avec N entier. Mais si ce n'est pas le cas, alors on fait face à un problème. Par exemple, imaginons que l'on doive envoyer une trame 2,5 fois plus grande qu'un mot. Dans ce cas, on envoie la trame dans trois mot, le dernier sera juste à moitié remplit. Il faut alors rajouter des bits/octets de bourrage pour remplir un mot.

Le codage des trames : début et de la fin de transmission

Le transfert d'une trame est soumis à de nombreuses contraintes, qui rendent le codage de la trame plus ou moins simple. Le cas le plus simple sont ceux où la trame a une taille inférieur ou égale à la largeur du bus, ce qui permet de l'envoyer en une seule fois, d'un seul coup. Cela simplifie fortement le codage de la trame, vu qu'il n'y a pas besoin de coder la longueur de la trame ou de préciser le début et la fin de la transmission. Mais ce cas est rare et n'apparait que sur certains bus parallèles conçus pour. Sur les autres bus parallèles, plus courants, une trame est envoyée morceau par morceau, chaque morceau ayant la même taille que le bus. Sur les bus série, les trames sont transmises bit par bit grâce à des circuits spécialisés. La trame est mémorisée dans un registre à décalage, qui envoie celle-ci bit par bit sur sa sortie (reliée au bus).

Il arrive qu'une liaison point à point soit inutilisée durant un certain temps, sans données transmises. Émetteur et récepteur doivent donc déterminer quand la liaison est inutilisée afin de ne pas confondre l'état de repos avec une transmission de données. Une transmission est un flux de bits qui a un début et une fin : le codage des trames doit indiquer quand commence une transmission et quand elle se termine. Le récepteur ne reçoit en effet qu'un flux de bits, et doit détecter le début et la fin des trames. Ce processus de segmentation d'un flux de bits en trames n’est cependant pas simple et l'émetteur doit fatalement ajouter des bits pour coder le début et la fin de la trame.

Ajouter un bit sur le bus de commande

Pour cela, on peut ajouter un bit au bus de commande, qui indique si le bus est en train de transmettre une trame ou s'il est inactif. Cette méthode est très utilisée sur les bus mémoire, à savoir le bus qui relie le processeur à une mémoire. Il faut dire que de tels bus sont généralement assez simples et ne demandent pas un codage en trame digne de ce nom. Les commandes sont envoyées à la mémoire en une fois, parfois en deux fois, guère plus. Mais il y a moyen de se passer de ce genre d'artifice avec des méthodes plus ingénieuses, qui sont utilisées sur des bus plus complexes, destinés aux entrées-sorties.

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.

Le codage des trames : les bits d'ECC

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, que nous avons abordées en partie dans les premiers chapitres du cours. On en distingue deux classes : celles qui ne font que détecter l'erreur, et celles qui permettent de la corriger. Tous les codes correcteurs et détecteurs d'erreur ajoutent tous des bits de correction/détection d'erreur aux données de base, aussi appelés des bits d'ECC. Ils 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.

Les bits d'ECC sont générés lors de l'envoi de la donnée sur la liaison point à point. Dans ce qui suit, on part du principe que l'on utilise une liaison série, la donnée est envoyée sur le bus bit par bit. La conversion parallèle-série est faite en utilisant un registre à décalage. La sortie du registre à décalage donne le bit envoyé sur le bus.

Le générateur/checker de parité

Dans le cas le plus simple, on se contente d'un simple bit de parité. C'est par exemple ce qui est fait sur les bus ATA qui relient le disque dur à la carte mère, mais aussi sur les premières mémoires RAM des PC. Lors de l'envoi d'une donnée, le bit de parité est généré par un circuit appelé le générateur de parité sériel. Comme son nom l'indique, il calcule le bit de parité bit par bit, avec une bascule et une porte XOR. Rappelons que le bit de parité se calcule en faisant un XOR entre tous les bits du nombre à envoyer.

Le registre à décalage est initialisé avec le nombre dont on veut calculer la parité. La bascule est initialisée à zéro et son but est de conserver le bit de parité calculé à chaque étape. À chaque cycle, un bit de ce nombre sort du registre à décalage et est envoyé en entrée de la porte XOR. La porte XOR fait un XOR entre ce bit et le bit de parité stocké dans la bascule, ce qui donne un bit de parité temporaire. Ce dernier est mémorisé dans la bascule pour être utilisé au prochain cycle. Le bit de parité final est disponible quand tous les bits ont été envoyés sur le bus, et la sortie du générateur de parité est alors connectée au bus pendant un cycle.

Générateur de parité sériel

Le générateur/checker de CRC

Dans d'autres cas, on peut ajouter une somme de contrôle ou un code de Hamming à la trame, ce qui permet de détecter les erreurs de transmission. Mais cet usage de l'ECC est beaucoup plus rare. On trouve quelques carte mères qui gèrent l'ECC pour la communication avec la RAM, mais elles sont surtout utilisées sur les serveurs.

Pour les transmissions réseaux, le code utilisé est un code de redondance cyclique, un CRC. 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. Le registre en question a la même taille que le mot dont on veut vérifier l'intégrité. Il suffit d'insérer le mot à contrôler bit par bit dans ce registre, et le CRC est calculé au fil de l'eau, le résultat étant obtenu une fois que le mot est totalement inséré dans le registre.

Circuit de calcul d'un CRC-8, en fonctionnement. Le diviseur choisi est égal à 100000111.

Le registre dépend du CRC à calculer, chaque CRC ayant son propre registre.

Circuit de vérification du CRC-8 précédent, en fonctionnement.

Les méthodes de retransmission

Les codes de détection d'erreurs permettent parfois de corriger une erreur de transmission. 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.