Cours programmation réseau en C++

UDP – Découpage et unification de paquets & création d’un protocole ordonné non fiable

Cet article présente comment découper un message en paquets pour l’envoi ainsi que la façon de reconstituer le message à la réception, dans le cadre de la création d’un protocole ordonné non fiable.

26 commentaires Donner une note  l'article (5) 

Article lu   fois.

L'auteur

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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 :

Structure de paquet
Sélectionnez
1.
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.

Interface du multiplexeur et démultiplexeur
Cacher/Afficher le codeSélectionnez
1.
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.

 
Cacher/Afficher le codeSélectionnez
1.
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.

Multiplexer::queue
Cacher/Afficher le codeSélectionnez

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.

Multiplexer::serialize
Cacher/Afficher le codeSélectionnez

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.

Demultiplexer::onDataReceived
Cacher/Afficher le codeSélectionnez

Afin que le code soit plus clair, le traitement du paquet a été extrait du traitement du tampon dans sa propre fonction onPacketReceived.

Demultiplexer::onPacketReceived
Cacher/Afficher le codeSélectionnez

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é.

Demultiplexer::process
Cacher/Afficher le codeSélectionnez

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.

Réassemblage de message fragmenté
Cacher/Afficher le codeSélectionnez

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.

PacketHandling_Test.hpp
Cacher/Afficher le codeSélectionnez

Récupérez le code source sous le tag V1.0.5 dans le dépôt Mercurial à l’adresse suivante.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2019 Cyrille (Bousk) Bousquet. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.