Construire un protocole de jeu en réseau

Bonjour, je suis Glenn Fiedler et bienvenue sur le quatrième article de la série Construire un protocole de jeu en réseau.

Dans l'article précédent nous avons implémenté la fragmentation et le réassemblage de paquets de manière à pouvoir envoyer des paquets plus grands que le MTU.

Cette approche fonctionne très bien quand les blocs de données que vous envoyez sont critiques et peuvent être perdus, mais dans certains cas vous devez envoyer beaucoup de données rapidement et de manière fiable malgré la perte de paquets, et vous avez besoin que ces données arrivent.

Dans cette situation, une technique différente donne de bien meilleurs résultats.

Il est commun pour un serveur d'envoyer beaucoup de données lors de la connexion d'un client, par exemple l'état initial du monde virtuel à rejoindre au cours d'une partie.

Imaginons que ces données font 256 ko et que le client doive les recevoir avant de pouvoir rejoindre la partie. Le client est bloqué sur un écran de chargement en attendant les données, nous voulons donc évidemment les transmettre le plus vite possible.

Si nous envoyons les données avec la technique de l'article précédent, nous subissons l'amplification de perte de paquets parce qu'un unique fragment perdu entraîne la perte du paquet entier. Ceci a un effet particulièrement sévère. Notre exemple de 256 ko séparé en 256 fragments envoyés avec 1 % de perte a une chance de perte colossale de 92,4 % !

Puisque nous avons besoin que ces données arrivent, nous n'avons que le choix de continuer à les envoyer jusqu'à ce qu'elles parviennent. En moyenne, nous devons envoyer le bloc dix fois avant qu'il soit reçu. Vous pouvez rire, mais ceci est réellement arrivé sur un jeu AAA sur lequel j'ai travaillé !

Pour corriger ceci, j'ai implémenté un nouveau système pour envoyer de gros blocs, qui gère les paquets perdus en renvoyant les fragments jusqu'à ce qu'ils soient acquittés. Puis je me suis occupé de la problématique des gros blocs et les ai transférés via ce système, réglant le problème du nombre de joueurs qui restaient bloqués sur la connexion, tout en continuant à envoyer les données critiques (la représentation instantanée de l'état du jeu, ou snapshot) via le système classique de fragmentation et réassemblage de paquets.

Dans ce nouveau système, les blocs de données sont appelés morceaux (chunks). Les morceaux sont coupés en tranches (slices). Ce changement de nom permet de garder la terminologie du système de morceaux (morceaux et tranches ou chunks et slices) distincte de la fragmentation et du réassemblage de paquets (paquets et fragments).

L'idée de base est que les tranches sont envoyées à travers le réseau de manière répétée jusqu'à ce qu'elles soient toutes arrivées. Puisque nous implémentons ceci sur UDP, ce concept simple devient un peu plus compliqué dans son implémentation parce que nous devons construire notre propre système de fiabilité basique pour que l'émetteur sache quelles tranches ont été reçues.

Cette fiabilité devient vite délicate si nous avons plusieurs morceaux en cours d'émission, donc nous poserons une simple hypothèse par avance : nous n'enverrons qu'un seul et unique morceau via le réseau à la fois. Ceci ne signifie pas que l'émetteur ne peut pas avoir une file d'attente locale pour les morceaux, juste qu'en termes de trafic réseau il n'y aura toujours qu'un seul morceau en cours de transfert (in flight) à un moment donné.

Cela rend le processus plus intuitif, car tout l'intérêt du système de morceaux est de les envoyer de manière fiable et ordonnés. Si vous vous retrouvez, pour quelque raison que ce soit, à envoyer les morceaux 0 et 1 en même temps, quel est l'intérêt ? Vous ne pouvez pas traiter le morceau 1 tant que le morceau 0 n'est pas arrivé, sinon ce ne serait pas fiable et ordonné.

Ceci dit, si vous creusez un peu, vous remarquerez qu'envoyer un morceau à la fois vient avec un cout, et il s'agit d'un délai de RTT entre la réception du morceau n et le démarrage du morceau n+1 du côté du receveur.

Ce cout est totalement acceptable pour l'envoi occasionnel de gros morceaux comme des données envoyées une seule fois lors de la connexion du client, mais n'est absolument pas acceptable pour des données envoyées 10 ou 20 fois par seconde comme les snapshots. Souvenez-vous donc que ce système est utile pour de gros blocs de données envoyées peu fréquemment, pas pour des données critiques.

Il y a deux aspects au système de morceaux, l'émetteur et le receveur.

L'émetteur d'un côté crée une file de morceaux et envoie les tranches sur le réseau. Le receveur lit ces paquets de tranche et les réassemble en morceau d'un autre côté. Le receveur a aussi pour responsabilité d'informer l'émetteur de quelles tranches ont été reçues via acquittements.

Le code réseau sur lequel je travaille est généralement client/serveur, et dans ce cas je veux d'ordinaire être capable d'envoyer des blocs de données du serveur vers le client et du client vers le serveur. Ainsi, il y a deux émetteurs et deux receveurs, un émetteur chez le client pour correspondre avec le receveur chez le serveur et vice-versa.

Pensez à l'émetteur et au receveur comme point d'entrée pour le protocole de transmission des morceaux qui définissent la direction des échanges. Si vous voulez envoyer des morceaux dans une autre direction, ou même étendre l'émetteur pour supporter le peer-to-peer, ajoutez juste un émetteur et un receveur pour chaque direction que vous souhaitez utiliser.

Les échanges réseau pour ce système sont faits via deux types de paquets :

• paquet de tranche (slice paquet) - qui contient une tranche d'un morceau d'une taille jusque 1 ko ;
• paquet d'acquittement (ack paquet) - un champ de bits qui indique quelles tranches ont été reçues jusque-là.

Le paquet de tranche est envoyé de l'émetteur vers le receveur. Il s'agit du paquet transférant la charge utile (payload), des données du morceau, à travers le réseau et est conçu de telle sorte que chaque paquet ait une taille inférieure au MTU conservateur de 1200 octets. Chaque tranche fait un maximum de 1 ko et il y a maximum 256 tranches par morceau, par conséquent le maximum de données qui peuvent être envoyées avec ce système est 256 ko.

const int SliceSize = 1024;
const int MaxSlicesPerChunk = 256;
const int MaxChunkSize = SliceSize * MaxSlicesPerChunk;

struct SlicePacket : public protocol2::Packet
{
    uint16_t chunkId;
    int sliceId;
    int numSlices;
    int sliceBytes;
    uint8_t data[SliceSize];

    template <typename Stream> bool Serialize( Stream &amp; stream )
    {
        serialize_bits( stream, chunkId, 16 );
        serialize_int( stream, sliceId, 0, MaxSlicesPerChunk - 1 );
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk );
        if ( sliceId == numSlices - 1 )
        {
            serialize_int( stream, sliceBytes, 1, SliceSize );
        }
        else if ( Stream::IsReading )
        {
            sliceBytes = SliceSize;
        }
        serialize_bytes( stream, data, sliceBytes );
        return true;
    }
};

Il y a deux points que j'aimerais éclaircir à propos du Slice Packet. Premièrement, même s'il n'y a qu'un seul morceau en cours de transfert sur le réseau, il est tout de même nécessaire d'inclure l'identifiant de morceau (0, 1, 2, 3, etc.) parce que les paquets envoyés en UDP peuvent être reçus dans le désordre.

Second point. À cause de la façon dont les morceaux sont tranchés, nous savons que toutes les tranches excepté la dernière auront une taille de SliceSize (1024 octets). Nous en tirons profit pour gagner un peu de bande passante en envoyant la taille de la tranche uniquement pour la dernière, mais il y a un compromis : le receveur ne connaît la taille du morceau qu'à la réception de la dernière tranche.

L'autre paquet envoyé par ce système est le paquet d'acquittement. Ce paquet est envoyé dans le sens contraire, du receveur vers l'émetteur. Ceci est la partie fiabilité du protocole réseau des morceaux. Son but est d'informer l'émetteur de quelles tranches ont été reçues.

struct AckPacket : public protocol2::Packet 
{ 
    uint16_t chunkId; 
    int numSlices; 
    bool acked[MaxSlicesPerChunk]; 

    bool Serialize( Stream & stream )
    { 
        serialize_bits( stream, chunkId, 16 ); 
        serialize_int( stream, numSlices, 1, MaxSlicesPerChunk ); 
        for ( int i = 0; i < numSlices; ++i ) 
        {
            serialize_bool( stream, acked[i] ); return true; } };
        }
    }
};

Acks est la version courte de « acknowledgements », l'anglais pour acquittements. Donc un acquittement pour la tranche 100 signifie que le receveur reconnaît avoir reçu la tranche 100. Il s'agit d'une information des plus importantes pour l'émetteur parce que non seulement ça lui permet de déterminer quand toutes les tranches ont été reçues et donc de savoir quand arrêter de les envoyer, mais ça lui permet également d'utiliser la bande passante plus efficacement en envoyant uniquement les tranches qui n'ont pas été acquittées.

En regardant de plus près le paquet d'acquittement, à première vue il semble un peu redondant. Pourquoi envoyons-nous les acquittements pour toutes les tranches dans chaque paquet ? Et bien, ces paquets sont envoyés en UDP il n'y a donc aucune garantie qu'ils arriveront tous. Vous ne voulez certainement pas que l'information concernant quelles tranches ont été acquittées ou non soit désynchronisée entre l'émetteur et le receveur.

Nous avons donc besoin de fiabilité pour les acquittements, mais nous ne voulons pas implémenter un système d'acquittement pour les acquittements parce que ce serait beaucoup trop de problèmes. Puisque dans le pire des cas le champ de bits est seulement de 256 bits ou 32 octets, nous envoyons juste l'état complet de toutes les tranches acquittées dans chaque paquet d'acquittement. Quand le paquet d'acquittement est reçu, nous considérons une tranche acquittée dès qu'un paquet marque cette tranche comme acquittée alors qu'elle ne l'était pas encore localement.

Cette dernière étape, de forcer l'état des tranches non acquittées vers acquittées, comme un fusible qui saute, fait que nous pouvons gérer les paquets d'acquittement délivrés dans le désordre.

Commençons par l'implémentation de l'émetteur.

La stratégie pour l'émetteur est :

• envoyer des tranches en continu jusqu'à ce qu'elles soient toutes acquittées ;
• ne pas renvoyer les tranches déjà acquittées.

Nous utilisons la structure de données suivante pour l'émetteur :

class ChunkSender
{
    bool sending;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numAckedSlices;
    int currentSliceId;
    bool acked[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
    double timeLastSent[MaxSlicesPerChunk];
};

Comme mentionné plus haut, un seul morceau est envoyé à la fois, il y a donc un état « envoi en cours » qui est vrai (true) si nous sommes actuellement en train d'envoyer un morceau, faux si nous sommes au repos et prêt à ce que l'utilisateur fournisse un nouveau morceau à envoyer. Dans cette implémentation, vous ne pouvez pas envoyer un autre morceau tant que l'actuel est toujours en train d'être envoyé sur le réseau. Si ce fonctionnement vous déplaît, ajouter une file en tête de la structure.

Ensuite, nous avons l'identifiant du morceau que nous sommes en train d'envoyer, ou, si rien n'est en cours d'envoi, l'identifiant du prochain morceau à envoyer, suivi de la taille du morceau et du nombre de tranches qui le composent. Nous gardons trace également, pour chaque tranche, si elle a été acquittée ou non, ce qui permet de calculer combien l'ont été jusque-là tout en ignorant les acquittements redondants. Un morceau est considéré complètement reçu par l'émetteur quand numAckedSlices == numSlices est vrai.

Nous gardons aussi trace de l'identifiant de la tranche en cours pour l'algorithme déterminant quelles tranches sont à envoyer. Ce dernier fonctionne ainsi : au commencement de l'envoi d'un morceau, commencez à la tranche 0 et allez de gauche à droite et réinitialisez à 0 quand vous passez la dernière tranche. Au bout d'un moment, vous arrêterez d'itérer parce que vous n'avez plus de bande passante disponible pour envoyer des tranches. À ce moment, enregistrez l'index de la tranche en cours, son identifiant, pour pouvoir repartir de celle-ci la prochaine fois. Cette dernière partie est importante parce qu'elle distribue les envois de façon homogène entre les tranches, et non juste les quelques premières.

Maintenant, discutons limitation de la bande passante. Évidemment vous n'allez pas juste envoyer des tranches continuellement ou vous noieriez votre connexion très rapidement. Comment donc limitons-nous la bande passante de l'émetteur ? Mon implémentation fonctionne ainsi : lors du parcours des tranches pour les envoyer, estimez grossièrement quelle taille son paquet ferait à l'envoi. Par exemple : taille de la tranche + quelques octets pour l'en-tête de votre protocole et l'en-tête UDP/IP. Puis comparez la taille requise avec la taille disponible à l'envoi dans votre budget de bande passante. Si vous n'avez pas cumulé assez de bande passante, arrêtez. Sinon, soustrayez les octets requis pour envoyer la tranche puis recommencez ce procédé avec la tranche suivante.

D'où vient le nombre d'octets disponibles ? À chaque frame, avant de mettre à jour l'émetteur de morceau, prenez votre bande passante (par exemple 256 kbps), convertissez-la en octets par seconde, puis ajoutez cette valeur multipliée par un delta temps (dt) dans un accumulateur.

Une vitesse d'envoi conservative de 256 kbps signifie que vous pouvez envoyer 32 000 octets par seconde, ajoutez donc 32 000 * dt à l'accumulateur. Une vitesse moyenne de 512 kbps signifie 64 000 octets par seconde. Une vitesse plus agressive de 1 mbps correspond à 125 000 octets par seconde. De cette façon à chaque mise à jour vous accumulez un nombre d'octets que vous êtes autorisé à envoyer, et quand vous avez envoyé toutes les tranches que vous pouvez avec ce budget, vous pouvez conserver les octets restants pour la prochaine tentative d'envoi de tranches.

Il existe une subtilité dans l'émetteur de morceaux qui est d'implémenter un délai minimum avant renvoi pour chaque tranche, sinon vous vous retrouverez dans des cas où, pour les petits morceaux ou les dernières tranches d'un morceau, que les mêmes tranches soient spammées sur le réseau.

Pour cette raison, nous conservons un tableau de l'heure d'envoi de chaque tranche. Une possibilité pour ce délai de renvoi est de garder une estimation du RTT et de renvoyer une tranche seulement si elle n'a pas été acquittée après RTT*1,25 depuis son dernier envoi. Ou, vous pourriez juste renvoyer la tranche si elle n'a pas été envoyée dans les dernières 100 ms. Ça marche pour moi !

Faites les calculs et vous remarquerez qu'il faut toujours un certain temps pour faire parvenir un morceau de 256 ko :

• 1 Mbps = 2 s ;
• 512 kbps = 4 s ;
• 256 kbps = 8 s :(

Ce n'est pas terrible. L'important ici est d'être rapide et fiable. L'accent est mis sur la rapidité. Ne serait-il pas sympa de pouvoir faire parvenir le morceau plus rapidement ? Le cas typique d'utilisation du système de morceaux prend en charge ceci. Par exemple, un gros bloc de données envoyé au client immédiatement après sa connexion ou des données qui doivent lui parvenir avant qu'il ne quitte un écran de chargement et ne commence à jouer. Vous voulez que ces échanges se passent le plus vite possible et dans ces cas-là l'utilisateur n'a pas vraiment grand-chose d'autre à faire avec sa bande passante, pourquoi ne pas alors en utiliser autant que possible ?

Par le passé j'ai essayé un truc avec d'excellents résultats : envoyer une rafale initiale. En supposant que la taille du morceau n'est pas trop importante, et que l'envoi de morceaux n'est pas fréquent, je ne vois aucune raison pour laquelle vous ne pourriez pas envoyer sur le réseau le morceau entier, toutes les tranches qui le composent, en paquets séparés en un splendide pic d'envoi et de bande passante, attendre 100 ms, puis reprendre la stratégie d'envoi de tranches classique en limitant la bande passante.

Pourquoi ceci marche ? Dans le cas où l'utilisateur a une bonne connexion internet (plusieurs dizaines de Mbps ou mieux…), les tranches sont envoyées très rapidement en effet. Dans le cas où la connexion n'est pas terrible, le pic sera mis en tampon et la plupart des tranches seront envoyées aussi vite que possible avec pour seule limite la bande passante disponible. Après ça, repasser à la technique habituelle avec une vitesse moindre se chargera de renvoyer les tranches qui ne sont pas parvenues lors de l'envoi initial.

Ceci semble un peu risqué, laissez-moi donc l'expliquer. Si l'utilisateur ne peut pas supporter ce pic, vous comptez sur le fait que les routeurs Internet préfèrent fortement mettre en tampon les paquets à presque tout prix plutôt que de les défausser. Ceci est un truc lié à TCP. Normalement, je déteste ça parce que ça introduit de la latence dans la livraison des paquets et sème le chaos parmi les paquets du jeu que vous voulez envoyer aussi vite que possible, mais dans ce cas c'est un bon comportement parce que le joueur n'a vraiment rien d'autre à faire que d'attendre que le morceau parvienne à destination.

N'allez juste pas trop loin avec le spam où la congestion persistera après l'envoi du morceau et affectera le jeu pendant quelques secondes. D'autre part, assurez-vous d'augmenter la taille du tampon des sockets du système d'exploitation pour qu'il soit supérieur à votre plus gros morceau (je recommande au moins deux fois plus grand), sinon vous allez perdre des tranches avant qu'elles ne parviennent au câble.

Enfin, je veux que vous soyez des citoyens du réseau responsables, donc même si je recommande d'envoyer toutes les tranches dans une rafale initiale, il est important que je mentionne que je pense que ceci est un comportement uniquement approprié, et seulement de façon très limitée, pour de petits morceaux de quelques centaines de ko en 2016, et seulement si votre jeu n'est pas en train d'envoyer quoi que ce soit d'autre qui soit critique.

S'il vous plait, n'utilisez pas cette technique de rafale si votre morceau est vraiment gros, par exemple plusieurs mégaoctets de données, parce que c'est bien trop gros pour compter sur la bonté des étrangers, j'ai nommé les tampons des routeurs entre vous et le destinataire de votre paquet. Pour ceci il faut implémenter quelque chose de plus malin. Quelque chose qui s'adapte et essaye d'envoyer des données aussi vite qu'il le peut, mais ralentit quand il détecte qu'une latence trop importante ou de la perte de paquets en conséquence d'une connexion noyée. Un tel système est hors du cadre de cet article.

Maintenant que l'émetteur est en place, intéressons-nous au receveur.

Comme dit plus tôt, contrairement au système de fragmentation et réassemblage de paquets de l'article précédent, le système de morceaux n'autorise l'échange que d'un seul et unique morceau à la fois.

De ce fait, la partie réception du système de morceaux est beaucoup plus simple :

class ChunkReceiver
{
    bool receiving;
    bool readyToRead;
    uint16_t chunkId;
    int chunkSize;
    int numSlices;
    int numReceivedSlices;
    bool received[MaxSlicesPerChunk];
    uint8_t chunkData[MaxChunkSize];
};

Nous avons un état de la réception d'un morceau en cours via le booléen receiving, plus un état qui indique que le morceau a été entièrement reçu et est prêt à être récupéré par l'utilisateur via le booléen readyToRead. Ceci dans le cas où la queue de réception a la taille minimale de 1. Si vous n'aimez pas ça, vous pouvez bien sûr ajouter une file.

Dans cette structure nous sauvegardons aussi la taille du morceau (bien qu'elle ne soit connue précisément qu'à la réception de la dernière tranche), via numSlices et numReceivedSlices, ainsi que l'état reçu ou non de chaque tranche. Cet état par tranche nous permet de défausser les paquets contenant des tranches déjà reçues, et compter le nombre de tranches reçues jusque-là (puisque nous pouvons recevoir une tranche plusieurs fois, nous incrémentons le nombre de tranches reçues uniquement la première fois que nous recevons une tranche donnée). Ceci sert aussi à la génération des paquets d'acquittement. Le morceau est complet du point de vue du receveur quand numReceivedSlices == numSlices.

À quoi ressemble donc le processus de réception de morceau complet ?

D'abord, le receveur s'initialise pour démarrer au morceau 0. Quand un paquet de tranche du morceau 0 arrive, receiving passe de false à true, les données de cette première tranche sont insérées dans chunkData à la bonne position, numSlices prend la valeur extraite du paquet, numReceivedSlices est incrémentée de 0 à 1, et le booléen d'état correspondant à cette tranche dans le tableau des entrées est mis à true.

À chaque réception d'un paquet de tranche, vérifiez qu'elle corresponde au morceau en cours et que numSlices soit cohérent, sinon ignorez le paquet. Les paquets dont la tranche a déjà été reçue sont aussi ignorés. Sinon, les données de la tranche sont copiées à leur place correcte dans le tableau chunkData, numReceivedSlices est incrémenté et le booléen d'état de cette tranche est mis à true.

Ce processus continue jusqu'à ce que toutes les tranches du morceau aient été reçues, moment où le receveur passe receiving à false et readyToRead à true. Tant que readyToRead vaut true, les paquets de tranche reçus sont défaussés. Là, le processus de réception de morceaux est complété, typiquement pendant la même frame. Le client vérifie « est-ce que j'ai un morceau à lire ? » et traite les données du morceau. Toutes les données du morceau sont réinitialisées à leur valeur par défaut, sauf l'identifiant du morceau qui s'incrémente de 0 à 1, et nous sommes prêts à recevoir le morceau suivant.

Le système de morceaux est simple dans son concept, mais son implémentation ne l'est certainement pas. Je vous encourage à regarder attentivement le code source pour cet article pour plus de détails.

Cet article est une traduction autorisée de l'article de Glenn Fiedler.