I. Introduction▲
Bonjour, et bienvenue dans la traduction française du quatrième article de la série d'articles « le réseau dans les jeux vidéo » écrits par Glenn Fiedler.
Dans l'article précédent, nous avons mis en place notre propre concept de connexion virtuelle en UDP.
Maintenant, nous allons ajouter la fiabilité, l'ordonnancement et l'évitement de la congestion à notre connexion UDP virtuelle.
C'est de loin l'aspect le plus compliqué du réseau bas niveau du jeu vidéo, ça va donc être un article plutôt intense. Accrochez-vous et allons-y !
II. Le problème avec TCP▲
Ceux d'entre vous qui sont familiers avec TCP savent que celui-ci possède son propre concept de connexion, fiabilité et ordonnancement et d'évitement de la congestion. Pourquoi alors réécrivons-nous notre propre miniversion de TCP en UDP ?
Le problème est que les jeux d'action multijoueurs s'appuient sur un flot continu de paquets envoyés à une vitesse de 10 à 30 paquets par seconde. Et pour la plupart de ces paquets, leurs données sont si critiques que seules les plus récentes sont probantes. Ceci inclut des données comme les entrées du joueur, la position, l'orientation et la vitesse de chaque joueur, et l'état des objets physiques dans le monde.
Le problème avec TCP est qu'il fait abstraction de l'envoi de données comme un flux fiable et ordonné. À cause de ça, si un paquet est perdu, TCP doit s'arrêter d'envoyer des données et attendre que le paquet soit renvoyé. Ça interrompt le flot continu de paquets et les paquets les plus récents doivent attendre que les paquets renvoyés arrivent. Ainsi les paquets arrivent dans l'ordre.
Nous avons besoin d'un type différent de fiabilité. Au lieu d'avoir chaque donnée traitée comme un flux fiable et ordonné, nous voulons envoyer des paquets à une vitesse continue stable et être notifiés lorsque les paquets sont reçus par l'autre machine. Ça permet d'envoyer les données critiques sans attendre le renvoi des paquets, tout en nous laissant choisir comment gérer les paquets perdus dans l'application.
Il n'est pas possible d'implémenter un système de fiabilité avec ces propriétés en TCP, nous n'avons donc que seul choix de construire le notre en UDP.
Hélas, la fiabilité n'est pas la seule chose que nous devons réécrire. TCP fournit aussi un évitement de la congestion, pour adapter dynamiquement la vitesse des données envoyées aux propriétés de la connexion. Par exemple, TCP enverra moins de données à travers un modem 28.8 K qu'à travers une ligne T1, et il est capable de le faire sans savoir par avance de quel type de connexion il s'agit !
II-A. Numéros de séquence▲
Revenons à la fiabilité !
Le but de notre système de fiabilité est simple : nous voulons savoir quels paquets arrivent de l'autre côté de notre connexion.
D'abord, nous avons besoin d'une façon d'identifier les paquets.
Et si nous ajoutions le concept « d'identifiant de paquet » ? Faisons-en une valeur entière. Nous pourrions le commencer à 0, et l'incrémenter à chaque paquet envoyé. Le premier paquet envoyé serait le numéro 0, et le centième serait le numéro 99.
Il s'agit d'une technique plutôt classique. C'est même utilisé par TCP ! Ces identifiants de paquet sont appelés numéros de séquence (sequence numbers). Bien que nous n'allons pas implémenter la fiabilité exactement comme TCP le fait, ça a du sens d'utiliser la même terminologie. Nous les appellerons donc numéro de séquence à partir de maintenant.
Puisque UDP ne garantit pas l'ordre des paquets, le centième paquet reçu n'est pas forcément le centième paquet envoyé. Nous devons donc insérer le numéro de séquence quelque part dans notre paquet pour que la machine distante sache de quel paquet il s'agit.
Nous avons déjà un en-tête simple pour la connexion virtuelle de l'article précédent, nous allons donc ajouter le numéro de séquence à notre en-tête ainsi :
[uint32 protocol id]
[uint séquence]
(paquet…)Maintenant, quand la machine reçoit un paquet, elle connait son numéro de séquence selon l'expéditeur.
II-B. Accusés de réception▲
Maintenant que nous pouvons identifier les paquets en utilisant leur numéro de séquence, la prochaine étape est d'informer l'autre machine des paquets que nous avons reçus.
Logiquement c'est plutôt simple, nous avons juste à noter chaque paquet reçu, et renvoyer les numéros de séquence à l'expéditeur.
Puisque nous envoyons des paquets en continu entre les machines, nous pouvons juste ajouter l'accusé de réception à l'en-tête de notre paquet, tout comme nous l'avons fait pour le numéro de séquence :
[uint32 protocol id]
[uint séquence]
[uint acquittement]
(paquet…)Notre approche est la suivante :
- à chaque paquet envoyé, nous incrémentons le numéro de séquence local ;
- quand nous recevons un paquet, nous comparons le numéro de séquence du paquet au numéro de séquence du dernier paquet reçu, appelé le numéro de séquence distant. Si le paquet est plus récent, nous mettons à jour la séquence distante avec celle du paquet ;
- quand nous créons un en-tête, la séquence locale devient la séquence du paquet, et la séquence distante devient l'accusé de réception.
Ce simple système d'accusé de réception fonctionne tant qu'un paquet est reçu pour chaque paquet envoyé.
Mais que se passe-t-il si nous recevons deux paquets avant d'en envoyer un seul ? Nous avons la place pour seulement un accusé de réception par paquet, alors que faire ?
Considérons maintenant le cas où une machine envoie des paquets plus rapidement que l'autre. Si le client envoie 30 paquets par seconde, et que le serveur en envoie seulement 10, nous avons besoin d'au moins trois accusés de réception dans chaque paquet envoyé du serveur.
Compliquons les choses ! Que se passe-t-il si un paquet contenant un accusé de réception est perdu ? L'expéditeur pensera que le paquet a été perdu alors qu'il a été reçu !
Il semble que nous devions rendre notre système de fiabilité… plus fiable !
II-C. Accusés de réception fiables▲
Maintenant nous divergeons de TCP.
L'accusé de réception envoyé par TCP est le numéro de séquence du prochain paquet qu'il attend de recevoir, dans l'ordre. Si TCP ne reçoit pas d'accusé de réception pour un paquet, il s'arrête et renvoie le paquet à nouveau. C'est exactement le comportement que nous voulons éviter !
Donc dans notre système de fiabilité, nous ne renvoyons jamais un paquet avec un numéro de séquence donné. Nous envoyons la séquence n une et une seule fois, puis nous envoyons n+1, n+2, etc. Nous ne nous arrêtons pas et ne renvoyons le paquet n s'il est perdu, nous laissons l'application libre de créer un nouveau paquet avec les données perdues, si besoin, et ce paquet est envoyé avec un nouveau numéro de séquence.
Puisque nous différons de TCP, nous pouvons avoir des trous dans notre ensemble de paquets que nous acquittons. Il n'est donc plus suffisant d'avoir que le numéro de séquence du paquet reçu le plus récent.
Nous devons inclure de multiples accusés de réception par paquet.
De combien d'accusés de réception avons-nous besoin ?
Comme dit plus haut, nous avons le cas où une machine envoie les paquets plus rapidement que l'autre. Supposons que le pire cas possible est une machine envoyant 10 paquets par seconde, pas moins, tandis que l'autre en envoie 30 au maximum. Dans ce cas, nous avons besoin de trois accusés de réception par paquet en moyenne, mais si les paquets s'agglutinent, il en faut plus. Partons sur un pire cas de 6-10.
Qu'en est-il des accusés de réception qui n'arrivent pas parce que le paquet qui le contient est perdu ?
Pour résoudre ça, nous allons utiliser une stratégie réseau classique de redondance pour contrer la perte de paquet !
Incluons 33 accusés de réception par paquet, et non pas jusqu'à 33, mais toujours 33. Donc pour chaque accusé de réception, nous le renvoyons de manière redondante jusque 32 fois supplémentaires, juste au cas où un paquet avec l'accusé de réception n'arrive pas à destination !
Mais comment pouvons-nous inclure 33 accusés de réception dans un paquet ? Avec 4 octets par accusé de réception, ça fait 132 octets !
L'astuce est de représenter les 32 accusés de réception précédents en utilisant un champ de bits comme ceci :
[uint32 protocol id]
[uint séquence]
[uint acquittement actuel]
[uint acquittements précédents]
(paquet…)Nous définissons les « acquittements précédents » pour que chaque bit corresponde à un accusé de réception des 32 précédents notre accusé de réception actuel. Disons que notre accusé de réception actuel est 100. Si le premier bit des « acquittements précédents » est à 1, alors le paquet est aussi un accusé de réception du paquet numéro 99. Si le second bit est à 1, alors le paquet 98 est acquitté. Etc. jusqu'au 32e bit pour le paquet 68.
Notre algorithme ressemble maintenant à ça :
- à chaque envoi de paquet, nous incrémentons le numéro de séquence local ;
- quand nous recevons un paquet, nous comparons son numéro de séquence au numéro de séquence distant. Si la séquence du paquet est plus récente, nous mettons à jour le numéro de séquence distant ;
- quand nous créons un en-tête, le numéro de séquence local devient le numéro de séquence du paquet, et la séquence distante devient l'accusé de réception. Le champ « acquittements précédents » est calculé en regardant dans une queue de jusque 33 paquets qui contient les numéros de séquence dans la plage [séquence distante - 32, séquence distante]. Nous mettons le nième bit à 1 si le numéro de séquence distant-n est dans la liste des paquets reçus ;
- quand un paquet est reçu, on scanne le champ « acquittements précédents ». Si le nième bit est à 1, alors on acquitte le paquet numéro de séquence-n, s'il n'a pas déjà été acquitté.
Avec cet algorithme amélioré, nous devons perdre 100 % des paquets pendant plus d'une seconde pour qu'un accusé de réception n'arrive pas à destination. Et bien sûr ça prend en compte aisément les vitesses d'envoi différentes et l'agglutinement des paquets reçus.
II-D. Détection des pertes de paquet▲
Maintenant que nous savons quels paquets sont reçus par la machine distante, comment détecter les paquets perdus ?
L'astuce est de prendre le problème à l'envers, si vous n'avez reçu aucun accusé de réception pour un paquet donné dans un certain temps, alors nous considérons ce paquet perdu.
Étant donné que nous n'envoyons pas plus de 30 paquets par seconde, et que nous envoyons un accusé de réception avec redondance 30 fois, si vous n'avez reçu aucun accusé de réception d'un paquet en une seconde, il est plus que probable que le paquet ait été perdu.
Nous devons donc faire preuve d'astuce ici, puisque nous pouvons savoir de manière 100 % sûre quels paquets arrivent à destination, mais nous ne pouvons qu'être raisonnablement certain de quels paquets n'arrivent pas.
Ça implique que chaque donnée que vous renvoyez avec cette technique de fiabilité a besoin d'avoir son propre identifiant de message, pour que si vous le recevez plusieurs fois vous puissiez le défausser. Ceci peut être fait par l'application.
II-E. Gestion de la réinitialisation du numéro de séquence▲
Aucune discussion sur les numéros de séquence et accusés de réception ne serait complète sans traiter le cas de la réinitialisation du numéro de séquence !
Les numéros de séquence et accusé de réception sont des entiers non signés 32 bits, ils peuvent donc représenter les nombres dans la plage [0, 4294967295]. C'est un nombre très élevé ! Si élevé que si vous envoyez 30 paquets par seconde, il faudrait plus de quatre ans et demi pour que le numéro de séquence déborde et se réinitialise.
Mais peut-être que vous voulez sauver un peu de bande passante, alors vous les diminuez pour des entiers 16 bits. Vous sauvez 4 octets par paquet, mais maintenant ils se réinitialisent en seulement une demi-heure !
Donc, comment gérer cette réinitialisation ?
L'astuce est de comprendre que si le numéro de séquence est déjà très élevé, et que le numéro de séquence est très faible, alors vous avez eu une réinitialisation. Donc même si le nouveau numéro de séquence est numériquement plus faible que le numéro de séquence actuel, il représente un paquet plus récent.
Par exemple, admettons que nous codons nos numéros de séquence sur 1 octet (ce n'est pas recommandé au passage ;) ) alors ils se réinitialiseront après 255 ainsi :
…, 252, 253, 254, 255, 0, 1, 2, ...
Pour gérer ce cas, nous avons besoin d'une nouvelle fonction qui est consciente que les numéros de séquence se réinitialisent après 255, ainsi 0, 1, 2 sont considérés plus récents que 255. Sinon, notre système de fiabilité arrête de fonctionner quand nous recevons le paquet 255.
La voici :
bool sequence_more_recent( unsigned int s1, unsigned int s2, unsigned int max )
{
return ( ( s1 > s2 ) && ( s1 - s2 <= max/2 ) )
|| ( ( s2 > s1 ) && ( s2 - s1 > max/2 ) );
}Cette fonction marche en comparant les deux nombres et leur différence. Si leur différence est inférieure à ½ de la valeur maximum du numéro de séquence, alors ils doivent être proches l'un de l'autre - alors nous vérifions juste si l'un est supérieur à l'autre, comme d'habitude. Mais s'ils sont éloignés, leur différence sera supérieure à ½ de la valeur maximum, alors nous considérons que la séquence est plus récente s'il est inférieur au numéro de séquence actuel.
Ce dernier cas est celui qui gère la réinitialisation des numéros de séquence, pour que 0, 1, 2 soient considérés plus récents que 255.
Si simple et élégant !
Soyez sûr d'inclure ceci dans chaque processus de numéro de séquence !
II-F. Évitement de la congestion▲
Maintenant que nous avons résolu le problème de fiabilité, il reste celui de l'évitement de la congestion. TCP le fournit, mais UCP n'a rien de tel !
Si nous envoyons des paquets sans aucune forme de contrôle de flot, nous risquons d'inonder la connexion et d'induire une latence sévère (supérieure à 2 secondes !) puisque les routeurs entre nous et l'autre machine deviendront congestionnés et mettront en attente les paquets. Ça arrive parce que les routeurs essayent coûte que coûte de remettre nos paquets, et donc les placent dans une file d'attente avant de considérer leurs rejets.
Alors que ce serait bien de pouvoir indiquer aux routeurs que nos paquets sont critiques et devraient être rejetés au lieu de les placer en attente si le routeur est surchargé, nous ne pouvons pas vraiment faire ça sans réécrire le programme de tous les routeurs du monde !
Alors nous nous concentrons sur ce qui est faisable : éviter d'inonder la connexion au préalable.
Il s'agira d'implémenter notre propre algorithme basique d'évitement de la congestion. Et j'insiste sur basique ! Tout comme pour la fiabilité, nous n'avons aucune chance d'avoir une solution aussi générale et robuste que l'implémentation de TCP au premier essai, alors gardons les choses aussi simples que possible.
II-G. Mesurer le temps de parcours (Round Trip Time - RTT)▲
Puisque pour éviter la congestion il suffit d'éviter d'inonder la connexion et d'augmenter le temps de parcours (Round Trip Time - RTT), ça a du sens que la métrique la plus importante soit le temps de parcours lui-même pour savoir si nous inondons notre connexion ou non.
Il nous faut un moyen de mesurer le RTT de notre connexion.
Voici une technique basique :
- pour chaque paquet envoyé, nous ajoutons une entrée dans une queue contenant le numéro de séquence et l'heure d'envoi ;
- à chaque réception d'accusé de réception, nous cherchons son entrée et nous inscrivons la différence entre l'heure d'envoi enregistrée et son heure de réception. Il s'agit du RTT pour ce paquet ;
- parce que l'arrivée des paquets varie avec l'instabilité du réseau, nous devons lisser cette valeur pour fournir quelque chose de probant. Donc à chaque calcul d'un nouveau RTT, nous passons un pourcentage entre notre RTT actuel et le RTT du paquet. 10 % semble bien en pratique. C'est appelé une moyenne mobile exponentielle lissée, et ça a pour effet de lisser le bruit dans le RTT avec un filtre passe-bas ;
- pour s'assurer que la queue d'envoi ne grandit pas indéfiniment, nous supprimons les paquets quand ils ont passé un certain RTT maximal. Comme vu plus haut, il est très probable qu'un paquet non acquitté dans la seconde soit perdu, donc une seconde est une bonne valeur pour notre RTT maximal.
Maintenant que nous avons notre RTT, nous pouvons l'utiliser comme métrique pour contrôler notre évitement de la congestion. Si le RTT devient trop important, nous diminuons la vitesse d'envoi, si elle a une valeur acceptable, nous pouvons essayer d'envoyer les données plus rapidement.
II-H. Simple évitement de la congestion binaire▲
Comme dit plus haut, ne soyons pas gourmands, nous implémenterons un évitement de la congestion très basique. Ce système aura deux modes. Bon et mauvais. Je l'appelle simple évitement de congestion binaire.
Admettons que vous envoyez des paquets d'une certaine taille, disons 256 octets. Vous voulez envoyer ces paquets 30 fois par seconde, mais si les conditions sont mauvaises, vous pouvez descendre à 10 fois par seconde.
Donc des paquets de 256 octets 30 fois par seconde, donne environ 64 kbit/s, et 10 fois par seconde environ 20 kbit/s. Il n'y a aucun réseau haut débit dans le monde qui ne soit pas capable de gérer au moins 20 kbit/s, nous partirons donc de cette hypothèse. Contrairement à TCP qui est générique pour tout type d'appareil, nous allons supposer une bande passante minimale supportée par les machines sur lesquelles notre code tournera.
Voici donc l'idée de base. Quand les conditions du réseau sont « bonnes » nous envoyons 30 paquets par seconde, et quand elles sont « mauvaises » nous descendons à 10 paquets par seconde.
Bien sûr vous pouvez définir « bon » et « mauvais » comme vous le souhaitez, mais j'ai eu de bons résultats en prenant en compte uniquement le RTT. Par exemple, si le RTT dépasse un seuil (disons 250 ms) alors vous savez que vous êtes probablement en train d'inonder la connexion. Bien sûr, cela suppose que personne ne dépasserait les 250 ms dans des conditions normales, ce qui est raisonnable étant donné notre prérequis en débit.
Comment passer d'un état bon à mauvais et inversement ? L'algorithme que j'utilise habituellement est le suivant :
- si vous êtes dans le mode « bon » et que les conditions deviennent mauvaises, passer immédiatement en mode « mauvais » ;
- si vous êtes en mode « mauvais », et que les conditions ont été bonnes pendant une durée ‘t', retourner en mode « bon » ;
- pour éviter que les modes ne changent rapidement, si vous repassez en mode « mauvais » en moins de 10 s, doublez la durée ‘t' nécessaire pour retourner en mode « bon ». Limiter cette valeur à un maximum, disons 60 s ;
- pour éviter de punir les bonnes connexions quand elles ont de courtes périodes de ratés, pour chaque 10 s passées en mode « bon », diminuer la durée ‘t' nécessaire pour revenir d'un mode « mauvais ». Limiter cette valeur à un minimum, par exemple 1 s.
Avec cet algorithme, vous vous adapterez rapidement aux mauvaises conditions et baisserez votre vitesse d'envoi à 10 paquets par seconde, évitant l'inondation de la connexion. Vous essayerez aussi prudemment de rester en mode « bon », en conservant l'envoi de paquets à une vitesse plus élevée de 30 par seconde, tant que les conditions du réseau sont bonnes.
Bien sûr, vous pouvez implémenter des algorithmes bien plus compliqués. Le pourcentage de paquets perdus peut être pris en compte, même l'instabilité du réseau (la variation de la vitesse de réception des accusés de réception), et non juste le RTT.
Vous pouvez aussi être bien plus gourmand avec l'évitement de la congestion, et essayer de découvrir si vous pouvez envoyer des données bien plus rapidement (par ex. en LAN), mais vous devez être très prudent ! Trop de gourmandise augmente les risques d'inondation de la connexion !
II-I. Conclusion▲
Notre nouveau système de fiabilité nous laisse envoyer des paquets à une vitesse soutenue et nous informe des paquets reçus. À partir de là nous pouvons déduire les paquets perdus, et renvoyer les données qui ne sont pas arrivées si nécessaire.
De plus nous avons un simple système d'évitement de la congestion qui alterne entre 10 et 30 paquets envoyés par seconde, selon les conditions du réseau, pour éviter d'inonder la connexion.
Il y a de nombreux détails d'implémentation trop spécifiques pour être mentionnés dans cet article, soyez donc sûr de consulter le code source exemple pour voir comment c'est implémenté. Je vous assure que c'est facile à lire et bien structuré pour vous aider !
C'en est fini de la fiabilité, ordonnancement et évitement de congestion, sûrement l'aspect le plus compliqué du réseau bas niveau.
III. Remerciements▲
Cet article est une traduction autorisée de l'article de Glenn Fiedler.
Merci aussi à Claude Leloup pour sa relecture orthographique.