I. Identifier un datagramme▲
Puisque UDP n’est pas un protocole fiable, chaque datagramme envoyé peut être perdu en route. Ou arriver en plusieurs exemplaires. Il nous faut donc un moyen d’identifier les datagrammes afin que le receveur soit capable de décider si oui ou non il accepte de les traiter.
Afin de pouvoir identifier nos datagrammes, il suffira d’ajouter un identifiant unique à chacun. Un tel identifiant sera simplement un entier non signé, que l’on incrémentera de 1 à chaque envoi et commençant à 0.
Une structure de datagramme prend alors forme, composée d’un en-tête suivi des données :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#pragma once
#include <cstdint>
#include <array>
namespace Bousk
{
namespace UDP
{
struct Datagram
{
using ID = ???;
static constexpr size_t BufferMaxSize = 1400;
static constexpr size_t DataMaxSize = BufferMaxSize - sizeof(ID);
ID id;
std::array<uint8_t, DataMaxSize> data;
};
}
}
Bien que pouvant théoriquement atteindre 1500 o, la taille d’un datagramme sera limitée à 1400 o afin d’être sûr qu’aucun routeur ne rejette le paquet pour cause de surpoids.
L’identifiant étant un entier non signé, le choix se fera entre uint8_t, uint16_t, uint32_t ou uint64_t.
II. Taille de l’identifiant▲
Afin de déterminer une taille correcte, il faut avoir une meilleure idée de la quantité de datagrammes que l’on souhaite échanger.
Imaginons envoyer 10 datagrammes par seconde avec un identifiant codé sur 8 bits. L’identifiant sera réinitialisé après la valeur 255, qui sera atteinte en 25,5 s.
Si l’on envoie maintenant 30 datagrammes par seconde, la réinitialisation se produit après seulement 8,5 s.
Voici un tableau récapitulatif afin d’y voir plus clair :
| Datagrammes/s | Taille de l'identifiant | Temps avant réinitialisation (s) | Temps avant réinitialisation (mn) |
| 10 | 8 | 25,50 | 0,43 |
| 16 | 6553,50 | 109,23 | |
| 32 | 429496729,50 | 7158278,83 | |
| 64 | 1844674407370960000,00 | 30744573456182600,00 | |
| 20 | 8 | 12,75 | 0,21 |
| 16 | 3276,75 | 54,61 | |
| 32 | 214748364,75 | 3579139,41 | |
| 64 | 922337203685478000,00 | 15372286728091300,00 | |
| 30 | 8 | 8,50 | 0,14 |
| 16 | 2184,50 | 36,41 | |
| 32 | 143165576,50 | 2386092,94 | |
| 64 | 614891469123652000,00 | 10248191152060900,00 |
II-A. Durée de vie d’un datagramme sur le réseau▲
Afin de pouvoir déterminer une taille d’identifiant correcte, il faut prendre connaissance d’un nouveau paramètre : la durée de vie d’un datagramme sur le réseau.
Cette durée de vie, Time To Live en anglais ou plus communément TTL, est un paramètre de l’en-tête IP. Il s’agissait à l’origine d’une durée en secondes, mais la très grande majorité des routeurs aujourd’hui utilisent ce champ comme nombre de sauts si bien qu’il a été renommé Hop Limit (pour limite du nombre de sauts) dans l’en-tête IPv6.
Ce champ est présent afin qu’un paquet IP ne puisse vivre indéfiniment sur le réseau et que le matériel finisse par le défausser. Chaque routeur, lors de la réception d’un paquet, décrémente la valeur du champ. Si le champ vaut maintenant 0, le paquet n’est pas retransmis.
Bien que l’on puisse modifier la valeur dans notre programme, on s’intéressera à la valeur de configuration par défaut des machines, puisque nous ne pouvons pas réécrire le programme de toutes les machines à travers le monde :
| OS/Device | Version | TTL | OS/Device | Version | TTL | OS/Device | Version | TTL | ||
| AIX | 30 | OS/2 | TCP/IP 3.0 | 64 | VMS/UCX | 128 | ||||
| DEC Pathworks | V5 | 30 | OSF/1 | V3.2A | 30 | Windows | for Workgroups | 32 | ||
| FreeBSD | 2.1R | 64 | Solaris | 2.x | 255 | Windows | 95 | 32 | ||
| HP-UX | 9.0x | 30 | Stratus | TCP_OS (14.2-) | 30 | Windows | NT 3.51 | 32 | ||
| HP-UX | 10.01 | 64 | Stratus | TCP_OS (14.3+) | 64 | Windows | NT 4.0 | 128 | ||
| Irix | 5.3 | 60 | Stratus | STCP | 60 | Windows | NT 4.0 SP5- | 32 | ||
| Irix | 6.x | 60 | SunOS | 4.1.3/4.1.4 | 60 | Windows | NT 4.0 SP6+ | 128 | ||
| Linux | 64 | Ultrix | V4.1/V4.2A | 30 | Windows | 2000 pro | 128 | |||
| MacOS/MacTCP | 2.0.x | 60 | VMS/Multinet | 64 | Windows | Server 2003 | 128 | |||
| MacOS/MacTCP | X (10.5.6) | 64 | VMS/TCPware | 64 | Windows | XP | 128 | |||
| Netgear FVG318 | 64 | VMS/Wollongong | 1.1.1.1 | 30 |
Sources : http://www.binbert.com/blog/2009/12/default-time-to-live-ttl-values/ & http://www.map.meteoswiss.ch/map-doc/ftp-probleme.htm
Avec ce tableau, on peut avoir une idée grossière de la durée de vie maximum d’un datagramme, et surtout avec quel délai maximum un paquet peut arriver. Ceci afin de déterminer une durée nécessaire avant qu’un identifiant soit réinitialisé et réutilisé, pour éviter qu’un datagramme très en retard soit incorrectement accepté comme nouveau et non pour ce qu’il est réellement : très en retard.
II-B. Définir la taille de l’identifiant▲
Pour les raisons vues dans le paragraphe précédent, la valeur de 16 bits est particulièrement intéressante : un identifiant de 8 bits se réinitialise bien trop vite, en moins de 10 secondes à 30 datagrammes/s tandis qu’à 16 bits pour l’identifiant, la réinitialisation se produit toutes les 30 minutes à 30 datagrammes/s, et 10 minutes pour 100 datagrammes/s.
Inutile d’utiliser plus de mémoire (qui est précieuse puisque limitée dans un datagramme) pour cette information : ce sera donc un uint16_t.
Si votre débit est limité et très bas, la valeur de 8 bits pourrait devenir utilisable.
À l’opposé, je ne vois absolument aucune nécessité de passer à un identifiant sur 32 bits.
Si vous souhaitez optimiser la mémoire, des valeurs intermédiaires peuvent être explorées : 12, 13, 14, 15 bits, qui entraînerait une réinitialisation pour un débit de 30 datagrammes/s respectivement après 136,5 s, 273 s, 546 s et 1092 s. Cependant, encoder une telle valeur proprement requiert quelques astuces, donc à mon avis le jeu en vaut rarement la chandelle.
Pour tester aisément des valeurs de votre choix, voici ma feuille de calculs.
II-C. Vérifier qu’un identifiant est plus récent▲
Nos identifiants seront donc toutes les valeurs possibles d’un uint16_t, soit [0, 65535].
Et bien sûr leur ordre va croissant : 0 < 1 < 2 < … < 65535. Mais lors de la réinitialisation 0 doit être identifié comme plus récent que 65535.
Il existe une astuce assez simple pour détecter ce cas, en utilisant de simples opérations arithmétiques :
- Si A > B et A – B est plutôt petit, alors A est plus récent que B ;
- Exemple : A = 5 ; B = 1 ; A – B = 5 – 1 = 4 : 5 plus récent que 1.
- Si A < B et B – A est plutôt élevé, alors A est plus récent que B ;
- Exemple : A = 3 ; B = 65533 ; B – A = 65533 – 3 = 65530 : 3 plus récent que 65533.
L’astuce est de définir ce qui est plutôt petit ou élevé, en fonction de l’intervalle de valeurs possibles et du dépassement (ou overflow). En particulier, il est intéressant d’utiliser la valeur médiane de l’intervalle des valeurs de l’identifiant, un uint16_t dans notre cas : 65535 / 2 = 32767.
Ce qui nous permet d’écrire le code suivant afin de vérifier qu’un identifiant est plus récent qu’un autre :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
#pragma once
#include <cstdint>
namespace Bousk
{
namespace Utils
{
bool IsSequenceNewer(uint16_t sNew, uint16_t sLast);
uint16_t SequenceDiff(uint16_t sNew, uint16_t sLast);
}
}
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
#include "Utils.hpp"
#include <numeric>
namespace Bousk
{
namespace Utils
{
bool IsSequenceNewer(uint16_t sNew, uint16_t sLast)
{
if (sNew == sLast)
return false;
return (sNew > sLast && sNew - sLast <= std::numeric_limits<uint16_t>::max() / 2) // cas simple : 4 > 2
|| (sNew < sLast && sLast - sNew > std::numeric_limits<uint16_t>::max() / 2); // dépassement : 2 > 65534
}
Uint16_t SequenceDiff(uint16_t sNew, uint16_t sLast)
{
if (sNew == sLast)
return 0;
assert(IsSequenceNewer(sNew, sLast)); //!< S’ils ne sont pas dans le bon ordre le diff n’a pas beaucoup de sens et n’est pas permis
if (sNew > sLast && sNew - sLast <= std::numeric_limits<uint16_t>::max() / 2)
return sNew - sLast;
//!< dépassement
return (std::numeric_limits<uint16_t>::max() - sLast) + sNew + 1; //!< +1 pour compter le 0 : si sLast == sMax && sNew == 0, la difference est 1
}
}
}
Au passage, l’ajout d’une fonction pour récupérer l’écart entre deux identifiants se révélera être utile plus tard.
III. Informer l’autre machine de ce que nous avons reçu▲
Un client peut déterminer localement s’il lui manque un datagramme ou des données, mais la clé du protocole est d’informer la machine distante de ce que nous avons reçu, et surtout de ce que nous n’avons pas reçu, afin qu’elle agisse en conséquence.
À cette fin, dans notre unité d’échange qui est le datagramme, ajoutons un nouveau champ ack, qui sera l’acquittement du datagramme le plus récent reçu et sera donc un uint16_t.
III-A. Un acquittement c’est bien, deux c’est mieux.▲
Vous vous serez peut-être déjà fait la réflexion : un acquittement par datagramme, est-ce suffisant pour acquitter tous les datagrammes ?
Un seul acquittement est définitivement trop faible : si les deux parties de la connexion ne vont pas à la même vitesse, des acquittements seront forcément manqués. Ajoutez à ça les pertes inhérentes à l’utilisation d’UDP, acquitter tous les datagrammes devient alors impossible de cette manière.
III-B. 17, 33 ou 65 acquittements▲
Avec l’astuce que je vais vous présenter, on va pouvoir intégrer jusque 65 acquittements par datagramme. Et ceci n’est en rien une limite absolue, mais sera plus que largement suffisant pour des besoins généraux.
L’astuce consiste à ce que tous ces acquittements soient relatifs au plus récent, et plus précisément qu’ils soient tous les précédents du plus récent. Permettant ainsi de les écrire sur un champ de bits. Ainsi 64 acquittements seront encodés dans un seul et unique uint64_t tel que le premier bit représente l’acquittement ack-1, le deuxième bit représente l’acquittement ack-2, etc. Jusqu’au 64e bit qui représente l’acquittement ack-64.
Ainsi avec 65 acquittements par datagramme, nous devrions être en mesure d’en acquitter un maximum, voire quasiment tous. Le seul moyen de ne pas être acquitté serait que les 64 datagrammes suivants un identifiant donné n’acquittent pas l’identifiant en question. Dans ce dernier cas, il est plutôt sûr et légitime de marquer un tel identifiant comme perdu.
Vous l’aurez compris : quand un identifiant est acquitté, nous avons la certitude qu’il a été reçu, alors qu’il y a une chance, même si très faible, qu’un identifiant acquitté ne soit pas notifié en tant que tel à l’autre partie de la connexion.
Il ne faut pas s’inquiéter pour autant : les pertes font partie du jeu d’utiliser UDP et il convient de s’en accommoder. L’extrême redondance de ce système limite très fortement ce résultat : il faudrait qu’un datagramme soit reçu très désordonné et en retard pour que cela se produise.
III-C. Mise à jour de l’en-tête▲
Afin de transférer cette information entre les machines, elle sera incluse dans l’en-tête de chaque datagramme.
Puisque nous commençons à avoir plusieurs informations, il est temps de créer une structure dédiée.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
#pragma once
#include <cstdint>
#include <array>
namespace Bousk
{
namespace UDP
{
struct Datagram
{
using ID = uint16_t;
struct Header
{
ID id;
ID ack;
uint64_t previousAcks;
};
static constexpr size_t BufferMaxSize = 1400;
static constexpr size_t DataMaxSize = BufferMaxSize - sizeof(Header);
Header header;
std::array<uint8_t, DataMaxSize> data;
};
}
}
IV. Vérifier qu’un identifiant est nouveau▲
Nous pouvons déterminer qu’un identifiant est plus récent, mais dans certains cas il peut être intéressant d’accepter des données plus anciennes, si le datagramme est reçu désordonné mais contient des données d’une autre nature qui nous intéressent.
Par exemple si je viens de recevoir le datagramme #3 qui contient la dernière position du personnage, puis je reçois le datagramme #2 qui contient une mise à jour de certaines caractéristiques : le #2 est tout autant intéressant à traiter, bien qu’il soit plus ancien que #3 – tant qu’il ne s’agit pas d’un doublon.
L’idée est d’avoir un tampon circulaire, ou une liste glissante, afin de pouvoir identifier les nouveaux paquets désordonnés et les traiter également : l’intérêt des données qu’il contient reviendra à l’application et non à la couche réseau1.
Ce traitement sera réalisé par un gestionnaire d’acquittements, qui sera une classe AckHandler, qui permettra de contrôler qu’un identifiant reçu n’est pas trop ancien et surtout qu’il est unique afin de valider son traitement. Puisque nous pouvons identifier ces deux fonctionnalités, il est également assez aisé de détecter les identifiants manqués qui seront décrétés perdus par la couche réseau.
Une telle classe aura cette interface :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
#pragma once
#include <cstdint>
#include <vector>
namespace Bousk
{
namespace UDP
{
class AckHandler
{
public:
AckHandler() = default;
AckHandler(const AckHandler&) = default;
AckHandler& operator=(const AckHandler&) = default;
AckHandler(AckHandler&&) = default;
AckHandler& operator=(AckHandler&&) = default;
~AckHandler() = default;
void update(uint16_t newAck, uint64_t previousAcks, bool trackLoss = false);
bool isAcked(uint16_t ack) const;
bool isNewlyAcked(uint16_t ack) const;
uint16_t lastAck() const;
uint64_t previousAcksMask() const;
std::vector<uint16_t> getNewAcks() const;
std::vector<uint16_t>&& loss();
};
}
}
Cette classe aura pour principal objectif de permettre le suivi des acquittements. Elle nous permettra donc de connaître l’acquittement le plus récent, mais également de connaître les acquittements précédents sous forme d’un masque que nous pourrons utiliser pour notre en-tête de datagramme.
La méthode clé sera update qui, à partir d’un identifiant d’acquittement et un masque des acquittements précédents, mettra à jour son état interne.
Puisque cette classe a une parfaite connaissance du suivi des acquittements, elle sera aussi capable de repérer ceux qui ont été perdus. J’en profite donc pour intégrer cette information également via le dernier paramètre de la fonction update qui permet de choisir d’identifier les pertes ou non et la fonction loss qui permet de récupérer les identifiants non acquittés et désormais hors de la plage de suivi (plus ancien que l’acquittement le plus récent - 64). Comme l’indique sa signature, loss déplace cette information vers l’appelant, il s’agira donc des acquittements perdus depuis le dernier appel à loss.
Ensuite, il suffit d’appeler les méthodes isAcked pour vérifier qu’un identifiant spécifique a été acquitté, ou isNewlyAcked pour vérifier qu’un identifiant spécifique a été acquitté lors du dernier appel à update.
IV-A. Membres et initialisation de AckHandler▲
Au niveau des membres, nous avons besoin :
- du dernier acquittement ;
- des acquittements précédents ;
- des nouveaux acquittements ;
- des acquittements perdus.
Donnons un type à chacun afin d’avoir toutes nos données :
2.
3.
4.
5.
uint16_t mLastAck{ -1 };
uint64_t mPreviousAcks{ -1 };
uint64_t mNewAcks{ 0 };
std::vector<uint16_t> mLoss;
bool mLastAckIsNew{ false };
mLastAck servira pour l’acquittement le plus récent tandis que mPreviousAcks sera le masque des acquittements précédents qui aura le fonctionnement décrit plus haut.
Pour l’information nouvellement acquittée, nous aurons mNewAcks qui sera le masque des acquittements précédents nouvellement acquittés, et mLastAckIsNew qui sera l’information relative au dernier acquittement.
Je fais la part belle aux entiers et masques parce que les manipulations internes seront principalement et quasi uniquement de la manipulation de bits, des décalages et des masques. Seule la fonction getNewAcks retourne des identifiants et transformera le champ de bits en identifiants.
Vous pouvez si vous le souhaitez utiliser std::bitset, seulement cette classe semble avoir des lacunes de performances (au moins sur certaines plateformes), et vu la facilité de manipuler nos champs de bits, autant l’écrire correctement.
IV-A-1. Gérer les champs de bits▲
Les champs de bits internes auront les propriétés suivantes :
- un bit à 1 signifie un acquittement reçu, 0 l’identifiant n’a pas encore été acquitté ;
- ils seront utilisés en Endianness-agnostique ;
- les bits seront lus de droite à gauche ;
- le premier bit (bit #0, le plus à droite) représente l’identifiant précédent directement du dernier acquittement, le dernier bit (#63) sera l’identifiant dernier acquittement – 64.
Ceci permettra d’utiliser nos uint64_t comme fenêtres glissantes d’acquittements.
IV-A-2. Quelques fonctions utilitaires▲
Afin de manipuler aisément nos champs de bits, quelques fonctions utilitaires se montrent particulièrement intéressantes :
2.
3.
4.
5.
6.
7.
8.
9.
10.
inline void SetBit(uint64_t& bitfield, uint8_t n);
inline void UnsetBit(uint64_t& bitfield, uint8_t n);
inline bool HasBit(uint64_t bitfield, uint8_t n);
template<class INTEGER>
struct Bit {};
template<>
struct Bit<uint64_t> {
static constexpr uint64_t Right = 0b0000000000000000000000000000000000000000000000000000000000000001;
};
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
void SetBit(uint64_t& bitfield, const uint8_t n)
{
assert(n < 64);
bitfield |= (Bit<uint64_t>::Right << n);
}
void UnsetBit(uint64_t& bitfield, const uint8_t n)
{
assert(n < 64);
bitfield &= (~(Bit<uint64_t>::Right << n));
}
bool HasBit(uint64_t bitfield, const uint8_t n)
{
assert(n < 64);
return (bitfield & (Bit<uint64_t>::Right << n)) != 0;
}
Je ne fournis qu’une version pour un uint64_t parce que c’est le seul type avec lequel j’utilise ceci pour l’instant, mais les versions pour d’autres tailles d’entier sont possibles et très simples à écrire.
On pourrait penser la structure permettant d’avoir le bit le plus à droite superflue, mais si la machine cible n’est pas en Big-Endian, la représentation de 1 en mémoire n’est pas du tout 0x00000001. Par exemple, en Little-Endian, 1 serait représenté en mémoire par 0x01000000 soit le 8e bit en partant de la gauche à 1. Ceci entraînerait des erreurs dans le reste des opérations puisque notre champ de bits n’est pas en représentation locale mais agnostique.
IV-B. Implémentation de la fonction update▲
Cette fonction étant la clé de voûte du système, prenez le temps nécessaire pour l’implémenter correctement et vous assurer de son bon comportement.
Elle devra mettre à jour l’acquittement le plus récent, les acquittements précédents, les nouveaux acquittements ainsi que les acquittements ratés et désormais hors de notre portée si nécessaire.
IV-B-1. Réacquittement d’un identifiant▲
Commençons par le plus simple, la réception d’un duplicata du dernier acquittement :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
#include "UDP/AckHandler.hpp"
namespace Bousk
{
namespace UDP
{
void AckHandler::update(uint16_t newAck, uint64_t previousAcks, bool trackLoss /*= false*/)
{
mLastAckIsNew = false;
if (newAck == mLastAck)
{
//!< Doublon du dernier acquittement, mais le masque peut contenir de nouvelles informations
mNewAcks = (mPreviousAcks & previousAcks) ^ previousAcks;
mPreviousAcks |= previousAcks;
}
}
}
}
Si l’acquittement est un doublon, on se contente de marquer les nouveaux acquittements et mettre à jour les masques.
IV-B-2. Acquittement d’un identifiant plus récent▲
La seconde étape sera la réception d’un acquittement plus récent, ce qui entraîne de multiples traitements :
- il faut vérifier si des acquittements en queue de masque sont manquants pour les marquer perdus ;
- décaler correctement les masques afin qu’ils restent cohérents ;
- si le saut est important s’assurer de marquer correctement comme perdus les acquittements ratés et irrécupérables ;
- sinon, introduire le précédent acquittement dans le masque décalé.
En déroulant l’algorithme ci-dessus, on parvient à cette implémentation :
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
namespace Bousk
{
namespace UDP
{
void AckHandler::update(uint16_t newAck, uint64_t previousAcks, bool trackLoss /*= false*/)
{
…
else if (Utils::IsSequenceNewer(newAck, mLastAck))
{
//!< Acquittement plus récent, vérifier les pertes, etc.
const auto diff = Utils::SequenceDiff(newAck, mLastAck);
const auto gap = diff - 1;
//!< Nombre de bits à décaler du masque
const auto bitsToShift = std::min(diff, static_cast<uint16_t>(64));
if (trackLoss)
{
for (uint32_t i = 0; i < bitsToShift; ++i)
{
const auto packetDiffWithLastAck = 64 - i;
const auto bitInPreviousMask = packetDiffWithLastAck - 1;
if (!Utils::HasBit(mPreviousAcks, bitInPreviousMask))
{
//!< Cet identifiant n’a pas été acquitté et est maintenant hors bornes : marquer comme perdu
const uint16_t packetid = mLastAck - packetDiffWithLastAck;
mLoss.push_back(packetid);
}
}
}
//!< Décaller le masque vers la gauche : supprimer les paquets les plus anciens du masque
mPreviousAcks <<= bitsToShift;
if (gap >= 64)
{
//!< Il s’agit d’un saut qui supprime entièrement le masque
mPreviousAcks = mNewAcks = 0;
//!< Vérifier chaque identifiant du masque pour marquer comme perdus les non-acquittés
if (trackLoss)
{
for (uint32_t p = 64; p < gap; ++p)
{
const uint16_t packetid = mLastAck + (p - 64) + 1;
mLoss.push_back(packetid);
}
}
}
else
{
//!< Marquer l’ancien acquittement comme acquitté dans le masque décalé
Utils::SetBit(mPreviousAcks, gap);
}
mLastAck = newAck;
mLastAckIsNew = true;
mNewAcks = (mPreviousAcks & previousAcks) ^ previousAcks;
mPreviousAcks |= previousAcks;
}
}
}
}
IV-B-3. Acquittement d’un identifiant non-nouveau▲
Enfin il reste un troisième et dernier cas à traiter, celui où l’acquittement reçu n’est pas nouveau, mais suffisamment récent pour être d’intérêt puisqu’il pourrait contenir des acquittements à prendre en compte.
Un tel acquittement est digne d’intérêt s’il n’est pas plus vieux que la borne inférieure du masque actuel, auquel cas on l’alignera avec le masque actuel afin de réaliser les mêmes opérations pour en extraire les nouveaux acquittements.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
namespace Bousk
{
namespace UDP
{
void AckHandler::update(uint16_t newAck, uint64_t previousAcks, bool trackLoss /*= false*/)
{
…
else
{
//!< Il s’agit d’un vieil acquittement, s’il n’est pas trop dépassé il peut contenir des informations intéressantes
const auto diff = Utils::SequenceDiff(mLastAck, newAck);
if (diff <= 64)
{
//!< Aligner le masque reçu avec notre masque actuel
previousAcks <<= diff;
//!< Insérer l’acquittement dans le masque
const auto ackBitInMask = diff - 1;
Utils::SetBit(previousAcks, ackBitInMask);
//!< Puis mise à jour des acquittements
mNewAcks = (mPreviousAcks & previousAcks) ^ previousAcks;
mPreviousAcks |= previousAcks;
}
else
{
//!< Acquittement plus vieux que la borne inférieure du masque actuel, on l’ignore
}
}
}
}
}
Nous voilà donc avec la totalité de la gestion des acquittements. Notre classe sait reconnaître les acquittements plus récents ainsi que les identifiants acquittés lors du dernier appel à update et les identifiants perdus car non acquittés.
Nous pouvons désormais grâce à cet objet identifier les doublons, traiter de manière unique chaque identifiant et être informé quand un identifiant a été perdu. Appliquer ceci aux identifiants de datagramme et nous sommes en mesure de connaître lesquels ont été reçus, et lesquels probablement pas. Il s’agit d’un élément clé de la réussite de tout protocole, et de celui que nous bâtissons en particulier.
IV-C. Implémentation des autres fonctions▲
Maintenant que le plus dur est fait, mettons en place l’interface pour consulter l’état de notre gestionnaire d’acquittement.
IV-C-1. Vérifier un acquittement▲
La première fonction proposée permet de vérifier qu’un identifiant a été acquitté.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
namespace Bousk
{
namespace UDP
{
bool AckHandler::isAcked(uint16_t ack) const
{
if (ack == mLastAck)
return true;
if (Utils::IsSequenceNewer(ack, mLastAck))
return false;
const auto diff = Utils::SequenceDiff(mLastAck, ack);
if (diff > 64)
return false;
const uint8_t bitPosition = static_cast<uint8_t>(diff - 1);
return Utils::HasBit(mPreviousAcks, bitPosition);
}
}
}
La seule complexité ici est de traiter correctement et dans le bon ordre les bits du masque.
Puisque nos acquittements sont sur une fenêtre glissante, l’historique complet n’est pas disponible – et il n’aurait de toute façon aucune utilité pratique.
Seuls les 65 derniers identifiants peuvent être ainsi demandés et ont du sens pour notre utilisation. C’est-à-dire qu’une fois l’identifiant 65 acquitté, vous n’avez plus aucune information concernant l’identifiant 0.
Si par hasard vous utilisez cette classe pour votre propre besoin et souhaitez conserver cette information, il vous faudra enregistrer au fur et à mesure les identifiants nouvellement acquittés et perdus.
IV-C-2. Vérifier qu’un acquittement est nouveau▲
La deuxième fonctionnalité proposée permet de savoir si un identifiant a été acquitté lors du dernier appel à update.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
namespace Bousk
{
namespace UDP
{
bool AckHandler::isNewlyAcked(uint16_t ack) const
{
if (ack == mLastAck)
return mLastAckIsNew;
if (Utils::IsSequenceNewer(ack, mLastAck))
return false;
const auto diff = Utils::SequenceDiff(mLastAck, ack);
if (diff > 64)
return false;
const uint8_t bitPosition = static_cast<uint8_t>(diff - 1);
return Utils::HasBit(mNewAcks, bitPosition);
}
}
}
Ici aussi, faites attention à traiter correctement les bits et le tour est joué.
IV-C-3. Récupérer les identifiants nouvellement acquittés▲
La troisième et dernière fonction permet de récupérer une liste d’identifiants nouvellement acquittés lors du dernier appel à update.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
namespace Bousk
{
namespace UDP
{
std::vector<uint16_t> AckHandler::getNewAcks() const
{
std::vector<uint16_t> newAcks;
newAcks.reserve(65);
for (uint8_t i = 64; i != 0; --i)
{
const uint8_t bitToCheck = i - 1;
if (Utils::HasBit(mNewAcks, bitToCheck))
{
const uint16_t id = mLastAck - i;
newAcks.push_back(id);
}
}
if (mLastAckIsNew)
newAcks.push_back(mLastAck);
return newAcks;
}
}
}
Remarquez les indices de la boucle : je parcours mon champ de bits dans l’ordre inverse pour pouvoir retourner les identifiants dans l’ordre du plus ancien au plus récent.
V. Conclusion▲
Grâce à cette classe vous pouvez facilement suivre des identifiants qui s’incrémentent, vous assurer de ne pas traiter de doublons ou de données trop anciennes et gérer correctement la réinitialisation lorsque l’identifiant atteint la valeur maximale.
Son utilisation première sera le suivi des datagrammes afin de les acquitter et faire parvenir cette information à la machine distante.
Parmi les évolutions possibles et relativement aisées, la taille du masque peut être modifiée ainsi que la taille des identifiants. Vous pouvez par exemple les passer en paramètres template. Ceci fera l’objet d’un futur article si le besoin se présente.
| Article précédent | |
|---|---|
| << UDP – Introduction et premiers pas | S’assurer du bon fonctionnement de son code >> |
1 : il peut s’agir d’une optimisation intéressante que d’ajouter une telle responsabilité à votre moteur réseau, si vous savez exactement comment les données sont utilisées par l’application hôte. Dans le cadre du cours il s’agit d’écrire un moteur réseau, et des briques logicielles, (ré)utilisables dans de nombreux cas. Si vous souhaitez personnaliser le moteur, libre à chacun d’adapter son implémentation selon ses besoins. Plus de détails à ce sujet dans un prochain article.