Stop-and-wait ARQ

Le Stop-and-wait ARQ (aussi appelé Send-and-wait ARQ) est la plus simple forme de méthode ARQ, qui vise à fiabiliser les échanges de données.

Principe

Lors d'un échange Stop-and-wait ARQ, l'émetteur envoie une seule trame de données à la fois. Après avoir émis une trame, l'émetteur n'envoie pas de données supplémentaires tant qu'il n'a pas reçu d'acquittement (ACK) de la part du destinataire. Ce dernier n'envoie un ACK qu'après avoir reçu une trame correcte. Si l'émetteur ne reçoit pas d'ACK avant l'expiration d'un délai prédéfini (appelé timeout), il ré-émet la trame précédemment envoyée.

En général, l'émetteur ajoute un code de contrôle d'erreur à la fin de chaque trame ; à la réception, le destinataire utilise ce code afin de contrôler l'intégrité de la trame, c'est-à-dire l'absence d'erreur ajoutée par le canal de transmission. Si le destinataire constate que la trame est correcte, il envoie un ACK. Dans le cas contraire, il rejette la trame et n'envoie pas d'ACK, faisant ainsi croire à l'émetteur que la trame a été perdue.

Le comportement décrit ci-dessus est l'implémentation la plus simple de la méthode Stop-and-Wait. Cependant, en pratique, cette implémentation engendre plusieurs problèmes.

Problèmes

Un premier problème vient de la possibilité de perte ou de mauvaise transmission de l'ACK. Dans ce cas de figure, l'émetteur ne reçoit pas (ou mal) l'ACK, le délai d'attente passe (timeout) et la trame est ré-émise. Le destinataire reçoit donc au total deux exemplaires de la même trame et n'a aucun moyen de savoir si la deuxième trame reçue est une copie de la première ou la trame suivante (qui peut contenir les mêmes données).

Un autre problème survient lorsque le canal de transmission possède une forte latence, ce qui fait que le délai d'attente expire avant que la trame atteigne le destinataire (et donc que l'ACK atteigne l'émetteur). Dans ce cas, l'émetteur envoie une seconde fois le paquet et le destinataire reçoit deux copies de la même trame ; il envoie donc deux ACK. L'émetteur, qui s'attend à recevoir un seul ACK, en reçoit alors deux, ce qui pose problème s'il interprète le deuxième ACK comme étant destiné à la prochaine trame.

Solution

La stratégie la plus courante pour éviter ces problèmes consiste à définir un bit de numéro de séquence dans l'en-tête de la trame. Ce numéro de séquence change de valeur (alternativement 0 et 1) à chaque nouvelle trame émise. Quand le destinataire envoie l'ACK, il inclut le numéro de séquence du prochain paquet attendu. Ainsi, le destinataire peut détecter des duplications de trames en vérifiant l'alternance des numéros de séquence : si deux trames consécutives ont le même numéro de séquence, cela signifie que l'une est la copie de l'autre, la deuxième trame est donc éliminée. De même, si deux ACKs consécutifs ont le même numéro de séquence alors c'est qu'ils sont liés à la même trame.

Efficacité

Par rapport aux autres ARQs, le Stop-and-wait ARQ est peu efficace. En effet, en supposant que l'échange de données se déroule idéalement (pas de perte de paquets ou d'ACKs), le délai entre chaque paquet est égal au double du délai de transmission (en négligeant le temps de traitement). Le débit effectif au sein du canal n'est qu'une fraction du débit maximal théorique.

Pour résoudre ce problème, il est possible d'envoyer plusieurs paquets successivement (avec un numéro de séquence sur plusieurs bits) en attendant un ACK pour le groupe de paquets. C'est la méthode utilisée dans le Go-Back-N ARQ et le Selective Repeat ARQ.

Références

• (en) Tanenbaum, Andrew S., Computer Networks, 4th ed. ISBN 0-13-066102-3
• (en) Maral G., Bousquet M., Satellite Communications Systems: Systems, Techniques and Technology, John Wiley and Sons, 2002, 757 p. (ISBN 0-47-149654-5) [lire en ligne] 

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Stop-and-wait ARQ » (voir la liste des auteurs)