Construire un protocole de jeu en réseau

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

Dans l'article précédent, nous avons discuté la façon de factoriser lecture et écriture d'un paquet dans une unique fonction de sérialisation.

Nous voulons maintenant insérer des données intéressantes dans nos paquets, mais un problème immédiat apparaît : quelle taille un paquet devrait faire ?

Pour répondre à cette question vous devez comprendre le concept de maximum transmission unit .

Quand vous envoyez un paquet via internet, il se transmet d'un ordinateur (ou routeur) à un autre afin d'atteindre sa destination. C'est ainsi qu'un système de commutation de paquets fonctionne. Ce n'est pas comme s'il y avait un câble directement connecté entre l'adresse IP source et de destination la dans la plupart des cas.

Chaque ordinateur (ou routeur) traversé impose une taille maximale de paquet appelée MTU. Et si un routeur reçoit un paquet plus grand que son MTU, il a le choix de

1. fragmenter le paquet au niveau de la couche IP et le transférer ;
2. abandonner ce paquet.

Voilà le problème que je vois à chaque fois. Les gens écrivent un jeu multijoueur où le paquet moyen est de taille plutôt petite, disons quelques centaines d'octets, mais de temps en temps quand beaucoup de choses se passent dans leur jeu et qu'un pic de paquets perdus se produit, le paquet est plus gros qu'à son habitude...

Soudainement, pour un très faible pourcentage des joueurs, c'est l'enfer .

Encore l'année dernière (2015) je parlais à Alex Austin à l'Indiecade à propos du réseau dans son jeu Sub Rosa. Il avait cet étrange bogue réseau qu'il ne pouvait pas reproduire. Sans raison apparente, certains clients (un ou deux sur l'ensemble de ses joueurs !) étaient déconnectés aléatoirement du jeu quand un tas de choses se produisaient. En regardant les journaux, Alex disait qu'il semble que les paquets ont juste arrêté d'être échangés.

Ça ressemblait exactement à un problème de MTU pour moi, et bien sûr, quand Alex a limité la taille maximale d'un paquet à une valeur raisonnable le bogue a disparu.

Quelle est donc une « taille de paquet raisonnable » ?

Sur Internet aujourd'hui (2016, IPv4) le MTU est typiquement de 1500 octets. À quelques octets près pour l'en-tête UDP/IP et vous trouverez que le nombre typique avant que les paquets commencent à être abandonnés ou fragmentés est aux alentours de 1472.

Vous pouvez essayer vous-même en exécutant cette commande sur MacOS X : ping -g 56 -G 1500 -h 10 -D 8.8.4.4

Sur ma machine ça échoue juste sous les 1500 octets comme attendu :

1404 bytes from 8.8.4.4: icmp_seq=134 ttl=56 time=11.945 ms
1414 bytes from 8.8.4.4: icmp_seq=135 ttl=56 time=11.964 ms
1424 bytes from 8.8.4.4: icmp_seq=136 ttl=56 time=13.492 ms
1434 bytes from 8.8.4.4: icmp_seq=137 ttl=56 time=13.652 ms
1444 bytes from 8.8.4.4: icmp_seq=138 ttl=56 time=133.241 ms
1454 bytes from 8.8.4.4: icmp_seq=139 ttl=56 time=17.463 ms
1464 bytes from 8.8.4.4: icmp_seq=140 ttl=56 time=12.307 ms
1474 bytes from 8.8.4.4: icmp_seq=141 ttl=56 time=11.987 ms
ping: sendto: Message too long
ping: sendto: Message too long
Request timeout for icmp_seq 142

Pourquoi 1500 ? Il s'agit du MTU par défaut sur MacOS X. C'est aussi le MTU par défaut sur Windows. Nous avons donc une limite haute pour la taille de nos paquets en supposant que vous vous souciez que vos paquets atteignent les machines Windows et Mac sans être fragmentés et sans risquer d'être abandonnés : 1472 octets .

Quelle est donc la limite basse ? MacOS X me laisse configurer la valeur du MTU entre 1280 et 1500 donc ma première idée pour internet IPv4 aujourd'hui serait 1200 octets . Au regard d'IPv6, il s'agit également d'une bonne valeur à utiliser pour un MTU conservateur, puisque tous les paquets de taille <= 1280 octets sont garantis d'être transférés sans fragmentation par la couche IP.

Ceci correspond aux chiffres que j'ai vus tout au long de ma carrière. D'expérience les jeux n'essayent que rarement de faire compliqué comme tenter de déterminer un MTU optimal, ils supposent juste un MTU raisonnablement conservateur et l'utilisent. Si un paquet plus grand que ce MTU a besoin d'être envoyé, le protocole du jeu le fragmente et le réassemble à la réception.

C'est exactement ce que je vais vous montrer dans cet article.

Commençons à créer notre propre système de fragmentation et assemblage de paquet en décidant de la représentation des fragments à travers le réseau. Idéalement, nous voudrions des paquets fragmentés et non fragmentés compatibles avec la structure de paquet existante que nous avons déjà créée, sans surcoût pour le protocole quand nous envoyons des paquets de taille inférieure au MTU.

Voici la structure de paquet à la fin de l'article précédent :

[protocol id] (32 bits) // non envoyé mais utilisé pour calculer le crc32 
[crc32] (32 bits) 
[packet type] (2 bits)
(variable length packet data according to packet type) 
[end of packet serialize check] (32 bits)

Dans notre exemple nous avons trois types de paquet : A, B et C.

Faisons en sorte qu'un de ces types génère des paquets plus grands que le MTU :

static const int MaxItems = 4096 * 4;

struct TestPacketB : public protocol2::Packet
{
    int numItems;
    int items[MaxItems];

    TestPacketB() : Packet( TEST_PACKET_B )
    {
        numItems = random_int( 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
            items[i] = random_int( -100, +100 );
    }

    template <typename Stream> bool Serialize( Stream & stream )
    {
        serialize_int( stream, numItems, 0, MaxItems );
        for ( int i = 0; i < numItems; ++i )
            serialize_int( stream, items[i], -100, +100 );
        return true;
    }
};

Ceci peut sembler artificiel, mais dans le monde réel ces situations arrivent vraiment. Par exemple, si vous avez une technique où vous envoyez tous les évènements non acquittés du serveur au client et rencontrez une hausse d'évènements et un pic de perte de paquets, vous pouvez aisément finir avec des paquets plus grands que le MTU, alors que votre taille moyenne de paquet est plutôt faible.

Dans la plupart des cas, c'est une bonne idée d'éviter ceci en implémentant une technique où vous incluez uniquement une partie des évènements ou mises à jour de l'état dans chaque paquet afin de rester sous une taille maximale spécifique. Cette technique fonctionne bien dans de nombreux cas… mais il y a un cas où elle ne marche pas : l'encodage delta (delta encoding ).

Les paquets créés par un encodeur delta ont une taille proportionnelle au nombre d'états modifiés entre l'état courant et le précédent. S'il y a beaucoup de différences entre les états alors le delta sera grand et vous ne pouvez rien faire pour contrer cela. Si ce delta se retrouve à devenir plus gros que le MTU, pas de chance, vous devez toujours l'envoyer ! Donc si malgré l'encodage delta vous remarquez que vous ne pouvez pas vraiment limiter la taille de vos paquets à une valeur inférieure au MTU, alors une stratégie de fragmentation et d'assemblage de paquet prend tout son sens.

Retournons à notre structure de paquet. C'est assez commun d'ajouter un numéro de séquence en en-tête de chaque paquet. Ce n'est en rien compliqué. C'est juste un numéro de paquet qui s'incrémente avec chaque paquet envoyé. Par exemple : 0, 1, 2, 3. J'aime utiliser 16 bits pour les numéros de séquence même s'ils se répètent après environ 15 minutes @ 60 paquets par seconde, c'est très improbable de recevoir un paquet vieux de ~15 minutes envoyé sur le réseau qui créera confusion avec un paquet plus récent ayant le même numéro. Si c'est un problème pour vous, envisagez d'utiliser des numéros de séquence de 32 bits à la place.

Quelle que soit la taille des numéros de séquence que vous choisissez, ils sont utiles pour un tas de choses comme implémenter la fiabilité et détecter et écarter les paquets désordonnés. De plus, nous aurons définitivement besoin de numéroter les paquets quand nous les fragmenterons parce que nous avons besoin d'identifier à quel paquet chaque fragment appartient.

Ajoutons donc un numéro de séquence à notre paquet :

[protocol id] (32 bits)   // non envoyé mais utilisé pour calculer le crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type] (2 bits)
(variable length packet data according to packet type)
[end of packet serialize check] (32 bits)

Voici la partie intéressante. Nous pourrions ajouter juste un bit is_fragment à l'en-tête, mais alors dans le cas commun d'un paquet non fragmenté vous perdez un bit qui vaudra toujours zéro. Nul.

Ce que je fais à la place c'est ajouter un type spécial « paquet fragment » :

enum TestPacketTypes
{
    PACKET_FRAGMENT = 0,     // RESERVED 
    TEST_PACKET_A,
    TEST_PACKET_B,
    TEST_PACKET_C,
    TEST_PACKET_NUM_TYPES
};

Et il se trouve que ça ne coûte rien parce que quatre types de paquet conviennent aux 2 bits que nous utilisons déjà pour le type de paquet. Désormais quand un paquet est lu, si le type de paquet est zéro alors nous savons que c'est un paquet fragment, sinon nous exécutons le code ordinaire de lecture d'un paquet non fragmenté.

Désignons ce à quoi ce paquet ressemble. Nous autoriserons un maximum de 256 fragments par paquet avec un fragment d'une taille de 1024 octets. Ce qui donne un paquet de taille maximale 256 k que nous pouvons envoyer avec ce système, ce qui devrait être suffisant pour tout un chacun, mais s'il vous plaît ne me citez pas sur ça.

Avec un en-tête de petite taille fixe, en-tête UDP et en-tête IP, un paquet fragment sera largement sous la valeur conservative de MTU de 1200. De plus, avec 256 fragments maximum par paquet nous pouvons représenter un identifiant dans la portée [0,255] et le nombre total de fragments par paquet [1, 256] avec 8 bits.

[protocol id] (32 bits)   // non envoyé mais utilisé pour calculer le crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

Remarquez que nous rembourrons les bits jusqu'au prochain octet avant d'écrire les données du fragment. Pour quoi faire ? Deux raisons :

1. C'est plus rapide de copier les données du fragment dans le paquet via memcpy que de tasser chaque octet avec le bitpacker ;
2. Nous économisons un peu de bande passante en n'envoyant pas la taille des données du fragment. Nous la déduisons en soustrayant l'index de l'octet du paquet au début des données du fragment de la taille totale du paquet.

Envoyer des fragments de paquet est simple . Vérifiez juste si la taille du paquet envoyé est <= au MTU conservateur et, si c'est le cas, envoyez le paquet normalement. Sinon, calculez combien de fragments de 1024 octets sont nécessaires et découpez le paquet en conséquence, construisez ces fragments et envoyez-les sur le réseau. Fire and forget  ! « Envoyez puis oubliez ! »

Une conséquence de cette approche est que tout fragment de ce paquet perdu entraîne la perte du paquet entier. Donc si vous avez de la perte de paquets, envoyer un paquet de 256 k en 256 fragments n'est probablement pas une bonne idée.

C'est une mauvaise idée parce que la probabilité de perdre un paquet augmente significativement avec le nombre de fragments. Pas tout à fait linéairement, mais d'une façon quelque peu compliquée que vous pouvez découvrir ici .

Pour faire court, pour calculer la probabilité de perdre un paquet, vous devez calculer la probabilité que tous les fragments soient remis avec succès et soustraire ce résultat à un, vous donnant ainsi la probabilité qu'au moins un fragment a été perdu.

Ceci vous donne la probabilité que votre paquet fragmenté soit perdu :

1 - (probabilité qu'un fragment soit remis) ^ (nombre de fragments)

Par exemple, si nous envoyons un paquet non fragmenté sur le réseau avec 1% de perte de paquets, il y a une chance sur 100 que le paquet sera perdu, ou, de manière redondante : 1 - (99/100) ^ 1 = 1/100 = 1 %

Les chances de perdre un paquet augmentent avec le nombre de fragments :

• Deux fragments : 1 - (99/100) ^ 2 = 2 % ;
• Dix fragments : 1 - (99/100) ^ 10 = 9.5 % ;
• 100 fragments : 1 - (99/100) ^ 100 = 63.4 % ;
• 256 fragments : 1 - (99/100) ^ 256 = 92.4 %.

Je recommande donc que vous y alliez tranquille sur le nombre de fragments. Il est mieux d'utiliser cette stratégie seulement pour les paquets nécessitant 2-4 fragments, et seulement pour les données critiques qui peuvent être perdues sans trop de soucis comme l'encodage delta d'un état. Ce n'est clairement pas une bonne idée d'envoyer un tas d'évènements fiables et ordonnés dans un paquet énorme et compter sur la fragmentation et l'assemblage du paquet pour vous sauver la mise.

Un autre usage typique pour des grands paquets est lorsqu'un client rejoint la partie. Vous voulez généralement envoyer une grande quantité de données fiables à ce client. Peut-être pour représenter l'état initial du monde pour une participation tardive. Quelle que soit la raison, n'envoyez pas ces données en utilisant l'astuce de fragmentation de cet article. À la place, jetez un œil au prochain article qui vous permet d'envoyer un grand nombre de données rapidement et de manière fiable en cas de perte de paquets en renvoyant les fragments jusqu'à réception.

Tandis qu'envoyer des paquets fragmentés est super simple, les recevoir est plutôt délicat.

La raison est que non seulement nous devons conserver une structure de données pour temporiser et réassembler les fragments en paquets, nous devons aussi faire attention à ce que personne n'essaye de faire planter l'application en envoyant des paquets malveillants.

Voici le paquet fragment que nous recevons :

[protocol id] (32 bits)   // not actually sent, but used to calc crc32
[crc32] (32 bits)
[sequence] (16 bits)
[packet type = 0] (2 bits)
[fragment id] (8 bits)
[num fragments] (8 bits)
[pad zero bits to nearest byte index]
<fragment data>

Et voici une liste de façons dont je pourrais essayer d'attaquer votre protocole et planter votre serveur :

• essayer d'envoyer des identifiants de fragments désordonnés pour planter votre mémoire. Par exemple : envoyer les fragments 0 et 255 alors que le paquet n'a que deux fragments ;
• envoyer un paquet n avec disons deux fragments, puis envoyer plus de fragments que le paquet n'en contient en espérant que vous ne le réalisiez pas et corrompez votre mémoire ;
• envoyer des paquets avec de grands fragments, supérieurs à 1 k, dans l'espoir que vous corrompiez votre mémoire en essayant de copier les données du fragment dans votre structure de données, ou manquiez de mémoire en allouant les fragments ;
• envoyer continuellement des fragments de taille maximum (256/256 fragments) pour que vous ayez besoin d'allouer beaucoup de mémoire et plantiez votre système. Disons que vous avez une fenêtre glissante de 256 paquets, 256 fragments maximum par paquet, et chaque fragment fait 1 k. Ce qui fait 67 108 864 octets ou 64 Mo par client alloué au maximum. Puis-je faire planter le serveur de cette façon ? Puis-je fractionner votre mémoire avec quelques paquets fragmentés de tailles diverses ? Vous seul en tant que propriétaire du serveur pouvez en être sûr. Cela dépend de votre budget mémoire et comment vous allouez la mémoire pour stocker les fragments. Si c'est un problème, limitez le nombre de fragments dans le tampon à tout moment (parmi tous les paquets) ou considérez réduire le nombre maximum de fragments par paquet. Pensez à allouer statiquement la structure de données pour les fragments ou utiliser une pool mémoire pour réduire la fragmentation.

Comme vous pouvez le voir, du côté de la réception, vous êtes plutôt vulnérable et devez être extrêmement prudent et vérifier absolument tout. En dehors de ça, c'est assez simple : gardez les fragments dans une structure de données, quand tous les fragments pour un paquet sont arrivés (garder le compte), réassemblez-les dans un paquet plus grand et retourner ce gros paquet à l'application.

Quel genre de structure de données est logique ici ? Rien d'extraordinaire ! C'est ce que j'aime appeler un tampon séquentiel. L'astuce-clé que je voudrais partager avec vous pour faire cette structure efficacement est :

const int MaxEntries = 256;

struct SequenceBuffer
{
    bool exists[MaxEntries];
    uint16_t sequence[MaxEntries];
    Entry entries[MaxEntries];
};

Plusieurs choses se passent ici. D'abord, une structure de tableaux (structure-of-arrays , SoA) permet une mise en cache rapide et efficace afin de tester si une entrée particulière existe dans le tampon, même si l'entrée d'un paquet donné est large (et pour la fragmentation et l'assemblage d'un paquet elle pourrait l'être).

Comment donc utiliser cette structure de données ? Quand vous recevez un fragment de paquet, il contient un numéro de séquence pour identifier à quel paquet ce fragment appartient. Le numéro de séquence est en constante évolution (à l'exception près de la réinitialisation après sa valeur maximale) donc l'astuce principale est de convertir ce numéro en index de roulement pour le tableau comme ceci :int index = sequence % MaxEntries;.

Maintenant vous pouvez vérifier rapidement avec une complexité de O(1) si une entrée spécifique existe déjà pour cette séquence, et vérifier si cette entrée correspond au numéro de séquence du paquet que vous souhaitez lire ou écrire. Vous devez vérifier l'existence et le numéro de séquence parce que tous les numéros de séquence sont valides (par exemple 0) et parce que l'entrée pour votre paquet pourrait déjà exister, mais appartenir à un autre numéro de séquence plus ancien (par exemple une autre séquence dont l'index de roulement est le même modulo MaxEntries ).

Donc quand le premier fragment d'un nouveau paquet arrive, vous convertissez la séquence en un index, vous vous rendez compte qu'il n'existe pas encore, donc pour exécuter exists[index] = 1 et sequence[index] pour correspondre au paquet en cours et stocker ce fragment dans l'entrée dans le tampon de séquence. La prochaine fois qu'un fragment arrive, vous avez le même numéro de séquence, et remarquez qu'une entrée pour cette séquence existe déjà, et que la séquence de votre paquet correspond à celle de votre structure, donc vous accumulez le prochain fragment dans cette entrée, et vous continuez jusqu'à ce que tous les fragments aient été reçus.

Et c'est pour ainsi dire tout à haut niveau. Pour une explication plus complète de cette approche veuillez vous référer au code source exemple de cet article. Cliquer ici pour avoir l'exemple pour cette série .

Une dernière chose dont j'aimerais parler pour clôturer cet article. J'ai l'impression que je rendrais un mauvais service si je ne mentionnais pas cette approche à mes lecteurs.

Écrire un protocole réseau est difficile. Tellement difficile que je l'ai fait à partir de rien au moins dix fois, mais à chaque fois je parvenais à échouer d'une nouvelle façon. Vous pourriez penser que j'ai fini par apprendre, mais ce genre de chose est compliqué. Vous ne pouvez pas juste écrire le code et vous attendre à ce qu'il marche. Vous devez le tester !

Ma stratégie quand j'écris la couche bas niveau d'un protocole réseau est  :

• codez défensivement . Mettez des assertions de partout. Ces assertions vont être déclenchées et seront de précieux indices quand quelque chose va mal tourner ;
• ajoutez des tests fonctionnels et assurez-vous que tout fonctionne pendant que vous l'écrivez. Mettez votre code à l'épreuve pendant son écriture et assurez-vous qu'il fonctionne en même temps que vous le créez. Pensez aux cas concrets qui doivent être correctement gérés et ajoutez des tests correspondants ;
• ajouter juste quelques tests fonctionnels n'est pas suffisant. Il y a énormément de cas auxquels vous n'aviez pas pensé ! Maintenant vous devez devenir vraiment vicieux. J'appelle ça le test du savon et je n'ai jamais, ne serait-ce qu'une seule fois, implémenté un protocole réseau qui n'a pas eu des problèmes relevés par ce test. Pour ces tests, écrivez juste une boucle infinie qui réalise des opérations quelconques pour éprouver votre système. Par exemple des paquets de tailles aléatoires, avec un taux de perte élevé, des paquets désordonnés ou dupliqués via un simulateur. Votre test est réussi s'il s'exécute toute une nuit sans causer le moindre problème et ne déclenche aucune assertion ;
• si vous rencontrez le moindre problème pendant vos tests. Vous pourriez avoir besoin d'ajouter des entrées et détails dans le journal (plus de logs ) du moteur ou du test afin de comprendre les raisons de l'échec. Une fois que vous avez compris ce qui se passe, STOP. Ne le corrigez pas immédiatement pour exécuter le test à nouveau. C'est stupide. Ajoutez plutôt un test unitaire pour reproduire le problème que vous essayez de corriger, vérifiez que ce test reproduit l'erreur, et que votre correction fonctionne. Seulement après ces étapes, retournez à vos tests et assurez-vous de les faire tourner toute la nuit. De cette façon les tests unitaires documentent le comportement de votre système attendu et peuvent rapidement être exécutés dans le futur pour vous assurer que ce n'est pas à nouveau dysfonctionnel avec de nouveaux changements.

C'est mon procédé et il a l'air de fonctionner plutôt bien. Si vous faites le design d'un protocole réseau bas niveau, le reste de votre jeu dépend de ce code. Vous devez être absolument sûr qu'il fonctionne avant de pouvoir l'utiliser intensément et ajouter du contenu l'utilisant, sinon c'est comme un château de cartes. Un jeu en réseau est suffisamment complexe pour ne pas avoir à suspecter que votre protocole bas niveau pourrait avoir des défauts ou des bogues. Alors, assurez-vous de savoir qu'il marche  !

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