I. Datagramme▲
Nous avons vu dès le premier chapitre UDP qu’un datagramme envoyé devrait avoir une taille aux alentours de 1400 o.
Mais en pratique, il est plutôt rare, voire quasiment impossible, que chaque message envoyé fasse exactement 1400 o.
I-A. Messages plus gros qu’un datagramme▲
Si un message dépasse cette taille limite, il devra être découpé et envoyé via plusieurs datagrammes qu’il faudra réunir à la réception pour reformer le message complet.
Ici plusieurs problématiques apparaissent déjà :
- Comment identifier de manière unique chaque fragment d’un tel message ?
- Comment rattacher chaque fragment à ce message (puisque les envois peuvent être dupliqués et désordonnés) ?
- Faut-il définir une taille maximale, ou un nombre de fragments maximal, pour un tel message ?
I-B. Messages plus petits qu’un datagramme▲
Si un message a une taille inférieure à cette limite, il ne posera pas problème et pourra être envoyé via un datagramme aisément comme nous le faisions au chapitre précédent. Mais ne peut-on pas faire mieux ?
I-B-1. Envoyer plusieurs messages par datagramme▲
Prenons un cas un peu extrême, et pourtant assez commun, d’un message de 15 o. Si notre datagramme peut accepter 1400 o, ça nous laisserait 1385 o libres, voire gâchés puisque notre unité d’échange est le datagramme.
Plutôt que d’envoyer un unique message par datagramme, faisons en sorte d’y empaqueter autant de messages que possible. Ainsi un datagramme pourrait contenir X messages, tous de tailles différentes, dans la limite de sa capacité maximale que nous avons définie à 1400 o.
Toutefois, cette solution vient avec son nouveau lot de problèmes :
- Comment identifier chaque message au sein d’un datagramme ?
- Comment délimiter chaque message au sein d’un datagramme ?
II. Paquets▲
Il apparaît donc que les notions de message, paquet et datagramme doivent être orthogonales. Un paquet ne peut plus se contenter d’être le simple container d’un message tel que dans les chapitres précédents.
Le datagramme sera l’objet de plus haut niveau qui sera envoyé avec ses propres informations, son propre en-tête, et contiendra un ou plusieurs paquets qui auront également chacun leurs propres informations et en-tête.
Le paquet sera l’objet de plus bas niveau qui servira au transfert d’un message. Un message pourra être représenté par un paquet unique s’il a une taille suffisamment petite. Dans le cas d’un message plus large qu’un paquet, il sera transféré via plusieurs paquets qui sont aussi appelés fragments ou paquet-fragments.
Un fragment est un paquet particulier mais un paquet avant tout. Aussi il est simple de mélanger les deux concepts et c’est souvent le cas par abus de langage.
Dans la suite du cours, sera appelé paquet l’unité envoyée via un datagramme, indépendamment qu’il s’agisse d’un paquet ou d’un fragment.
Lorsque je ferai référence à un fragment spécifiquement, le terme de paquet-fragment sera utilisé.
Si je fais référence à un paquet non fragment, il s’agira d’un paquet-message.
II-A. En-tête d’un paquet▲
Chaque paquet sera précédé d’un en-tête afin de l’identifier.
Un tel en-tête possédera :
- l’identifiant du paquet : un entier non signé incrémenté à chaque paquet envoyé ;
- l’information sur le type de paquet : s’il s’agit d’un message entier ou d’un fragment ;
- la taille du paquet, afin de délimiter le tampon à traiter.
II-B. Identifiant de paquet▲
Tout comme nous l’avons déjà réalisé pour le datagramme, il s’agira d’ajouter un identifiant, un entier non signé qui s’incrémente, à chaque paquet envoyé. Et pour des raisons similaires au datagramme, un uint16_t sera choisi ici aussi.
II-C. Type de paquet▲
Le type de paquet sera caractérisé par une énumération possédant 4 valeurs :
- Packet pour un message complet ;
- FirstFragment pour la première partie d’un message découpé ;
- LastFragment pour la dernière partie d’un message découpé ;
- Fragment pour les parties centrales d’un message découpé, s’il y en a.
Plusieurs raisons pour soutenir ce choix :
- avec seulement quatre valeurs, ce champ pourra être optimisé pour tenir sur seulement 2 bits par la suite ;
- en distinguant les trois types de fragments, il est plus simple de détecter les parts d’un message. En particulier si le dernier fragment du message précédent est perdu alors que nous avons reçu le premier fragment d’un nouveau message, il n’y a pas de confusion possible.
II-D. Taille du paquet▲
Puisque la limite d’un datagramme est d’environ 1400 o, un paquet ne pourra jamais dépasser cette taille. Aussi un uint16_t fera ici aussi l’affaire.
II-D-1. Taille d’un message▲
Vu que la taille d’un paquet est limitée, il convient également de limiter la taille d’un message : de délimiter combien de fragments peuvent définir un unique message.
Cette limite est arbitraire et définira en particulier la quantité de mémoire utilisée par votre moteur. Posons une limite de 32 fragments pour l’article et le cours, ce qui permet de transférer des messages de taille maximale ~43 Ko. Ceci devrait permettre de couvrir tous les cas y compris un peu extrêmes, mais gardez à l’esprit qu’une plus grande fragmentation augmente les chances de perte, comme le rappelle le tableau ci-dessous. Il ne faut donc pas en abuser - et favoriser les messages plus petits.
Et si par hasard vous avez besoin d’envoyer des données plus larges, il est tout à fait possible de les découper au préalable dans l’application plutôt que de laisser ce travail au moteur réseau.
Pertes | # fragments | Chances de livraison | Pertes | # fragments | Chances de livraison |
1.00% | 1 | 99.00% | 5.00% | 1 | 95.00% |
2 | 98.01% | 2 | 90.25% | ||
3 | 97.03% | 3 | 85.74% | ||
4 | 96.06% | 4 | 81.45% | ||
5 | 95.10% | 5 | 77.38% | ||
6 | 94.15% | 6 | 73.51% | ||
7 | 93.21% | 7 | 69.83% | ||
8 | 92.27% | 8 | 66.34% | ||
9 | 91.35% | 9 | 63.02% | ||
10 | 90.44% | 10 | 59.87% | ||
15 | 86.01% | 15 | 46.33% | ||
20 | 81.79% | 20 | 35.85% | ||
25 | 77.78% | 25 | 27.74% | ||
30 | 73.97% | 30 | 21.46% | ||
32 | 72.50% | 32 | 19.37% |
5% est la valeur généralement utilisée pour implémenter et déboguer un moteur réseau afin d’être résistant et pouvoir faire face aux pertes. Sur une connexion sans problème particulier, via internet, le taux de perte devrait être < 1% voire quasi-nul. Mais même le plus petit taux de perte est vite démultiplié si le message est très fragmenté.
II-E. Structure de paquet▲
Avec les informations des paragraphes précédents, nous arrivons donc sur une première structure de paquet comme ceci :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
struct
Packet
{
enum
class
Type : uint8_t
{
Packet,
FirstFragment,
Fragment,
LastFragment,
}
;
struct
Header
{
uint16_t id;
uint16_t size;
Type type;
}
;
static
constexpr
uint16_t PacketMaxSize =
Datagram::
DataMaxSize;
static
constexpr
uint16_t HeaderSize =
sizeof
(Header);
static
constexpr
uint16_t DataMaxSize =
PacketMaxSize -
HeaderSize;
static
constexpr
size_t MaxPacketsPerMessage =
32
;
static
constexpr
size_t MaxMessageSize =
MaxPacketsPerMessage *
DataMaxSize;
Header header;
std::
array<
uint8_t, DataMaxSize>
data;
}
;
Très certainement perfectible, ceci sera néanmoins notre base de travail.
III. Multiplexeur, Démultiplexeur▲
L’idée est donc d’avoir un traitement supplémentaire sur nos messages et paquets. Quand un message trop gros est mis en file d’envoi, il doit être découpé en plusieurs paquet-fragments de tailles correctes qu’il faudra recoller à la réception. Quand la file contient des petits paquets, il faut être capable d’en empaqueter plusieurs et de les redécouper à l’arrivée.
III-A. Interface▲
Nous aurons donc deux objets : un multiplexeur qui contiendra la file d’envoi, et un démultiplexeur qui effectuera les traitements à la réception.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
class
Multiplexer
{
public
:
Multiplexer() =
default
;
~
Multiplexer() =
default
;
void
queue(std::
vector<
uint8_t>&&
messageData);
size_t serialize(uint8_t*
buffer, const
size_t buffersize);
}
;
class
Demultiplexer
{
public
:
Demultiplexer() =
default
;
~
Demultiplexer() =
default
;
void
onDataReceived(const
uint8_t*
data, const
size_t datasize);
std::
vector<
std::
vector<
uint8_t>>
process();
}
;
III-B. Fonctionnement du multiplexeur▲
Le multiplexeur ne devrait pas être un challenge d’implémentation. Il aura pour but de contenir la liste d’envoi des paquets, et de les sérialiser dans le tampon fourni pour envoyer les données.
Lors de la mise en file d’envoi des données, il devra vérifier la taille des données du message à envoyer, afin de les découper en paquets de taille correcte si nécessaire. Si les données sont déjà suffisamment petites, on se contentera de les mettre en queue.
III-C. Fonctionnement du démultiplexeur▲
UDP pouvant entraîner des pertes de données, la réception pourra avoir des trous (c’est-à-dire : réception du paquet #1, perte du paquet #2, réception du paquet #3…).
Le démultiplexeur agira donc ainsi :
- tous les paquets valides reçus seront stockés ;
- après chaque réception, l’appel à process retournera les messages complets s’il y en a ;
- après la réception du message terminé par le paquet N, les paquets précédents, s’il y en a, seront défaussés.
Ceci sera une implémentation dite ordonnée non fiable : en supposant des paquets-messages, la réception des paquets #1, #2, #4, #3 dans cet ordre retournera les paquets #1, #2, #4 dans cet ordre et le paquet #3 sera ignoré puisque reçu après #4.
IV. Implémentation du multiplexeur▲
Commençons par le plus simple : le multiplexeur.
IV-A. Variables membres▲
Le multiplexeur aura besoin de deux variables membres : la liste des paquets en file d’envoi et un compteur pour savoir quel est l’identifiant à assigner au paquet suivant.
2.
3.
4.
5.
6.
7.
class
Multiplexer
{
…
private
:
std::
vector<
Packet>
mQueue;
Packet::
Id mNextId{
0
}
;
}
;
IV-B. void queue(std::vector<uint8_t>&& data);▲
La fonction queue permettra de mettre les données d’un message en file d’envoi, et de les découper au passage en plusieurs paquet-fragments si la quantité envoyée est plus grosse que la taille maximale autorisée pour un paquet.
IV-C. size_t serialize(uint8_t* buffer, const size_t buffersize);▲
La fonction serialize sera appelée lorsque l’on souhaite envoyer un datagramme afin d’y inclure nos paquets. Puisque notre implémentation est ordonnée non fiable, il suffira d’itérer sur la file et inclure les X premiers éléments jusqu’à remplir le tampon fourni. Une fois transmis, ils pourront être supprimés de la liste afin d’envoyer les suivants par la suite.
V. Implémentation du démultiplexeur▲
Le démultiplexeur aura pour responsabilité d’extraire les paquets reçus du datagramme, réassembler les messages fragmentés et défausser ce qui doit l’être afin de fournir à l’application ce qui a été défini plus haut : des messages ordonnés non fiables.
V-A. Variables membres▲
Pour remplir ces tâches, nous aurons besoin d’une liste des paquets reçus avant potentiel réassemblage ainsi que l’identifiant du paquet traité le plus récent afin de défausser les plus anciens et répondre à notre besoin d’implémentation ordonnée non fiable.
L’astuce consiste à maintenir notre liste de paquets triée de façon à simplifier son traitement par la suite.
V-B. void onDataReceived(const uint8_t* data, const size_t datasize);▲
Cette fonction sera le point d’entrée des données reçues. Il faudra ici séparer les paquets s’il y en a plusieurs dans notre tampon, puis traiter chaque paquet ainsi extrait pour s’assurer qu’il ne s’agit pas d’un doublon avant de l’insérer à la bonne place dans notre liste de paquets à traiter.
Le traitement est miroir à ce qui a été fait pour Multiplexer::
serialize.
Afin que le code soit plus clair, le traitement du paquet a été extrait du traitement du tampon dans sa propre fonction onPacketReceived.
V-C. std::vector<std::vector<uint8_t>> process();▲
Cette fonction retourne les messages complets récupérés depuis le dernier appel.
Il s’agit de traiter notre liste de paquets reçus, afin d’en extraire les éventuels messages complets pour les retourner à l’appelant. Puisque notre liste est ordonnée, il suffit d’itérer sur celle-ci afin de les extraire dans l’ordre, sans oublier de mettre à jour le paquet le plus récent reçu afin de ne pas accepter de paquets plus anciens lors des réceptions ultérieures.
Commençons par la partie simple : le cas où le message n’est pas découpé.
La partie non triviale maintenant : si le message est fragmenté en plusieurs paquets. Pas beaucoup plus compliqué, puisque notre file est ordonnée, il suffit de passer en revue les paquets suivants, jusqu’à trouver un paquet de type LastFragment et en s’assurant que leurs identifiants sont tous consécutifs.
J’ai choisi de faire ce travail en utilisant une fonction lambda qui modifie l’itérateur des paquets et retourne le tampon du message complété. Il est tout à fait possible de le faire via une autre fonction membre privée, ceci est au goût de chacun.
Après l’exécution de cette fonction, l’itérateur de parcours de la liste des paquets pointe vers le dernier paquet traité qui est le dernier fragment du message si le message est complété.
Si le message n’a pas été complété, il peut s’agir d’un fragment du message dont un paquet est manquant, d’un paquet non lié au message ou de la fin de la liste. Dans ce cas, on laisse la boucle continuer et gérer son cas lors de sa prochaine itération.
VI. Tests▲
Comme d’habitude, quelques tests ont été écrits pour vérifier le bon fonctionnement.
Récupérez le code source sous le tag V1.0.5 dans le dépôt Mercurial à l’adresse suivante.
Article précédent |
Article suivant |
---|---|
<< UDP – Créer son propre protocole par-dessus UDP | UDP – Envoi de paquets ordonné fiable >> |