Quel est un bon moyen de détecter un wrap-around dans un compteur de messages de largeur fixe?

Question

J'écris une application client pour communiquer avec un programme serveur via UDP. Le client effectue périodiquement des demandes de données et doit utiliser la réponse du serveur la plus récente. Le message de demande a un champ de compteur non signé de 16 bits qui est répercuté par le serveur afin que je puisse jumeler les demandes avec les réponses du serveur. Comme c'est le protocole UDP, je dois gérer le cas où les réponses du serveur arrivent en désordre (ou n'arrivent pas du tout). Naïvement, cela signifie se tenir au plus haut compteur de messages vu jusqu'ici et laisser tomber n'importe quel message entrant avec un nombre inférieur. Mais cela échouera dès que nous passerons à 65535 messages et que le compteur reviendra à zéro. Existe-t-il un bon moyen de détecter (avec une probabilité raisonnable) que, par exemple, le message 5 vient effectivement après le message 65 000?

Le langage d'implémentation est C++.

Answer 1

Si je comprends bien les choses, vous pourrez peut-être utiliser des fenêtres, si ce n'est déjà fait. C'est-à-dire, n'acceptez pas un message qui est en dehors de votre fenêtre. Par exemple, si votre compteur est à 1000, vous pouvez limiter votre plage d'ID de compteur entrant que vous accepterez à 1000 ... 1031 inclus. Ainsi, tout ce qui se trouve en dehors de cette plage est trop important pour vous (vous obligeant à initier un protocole de renvoi). Une fois que vous obtenez 1000, votre limite supérieure ira à 1032. Puis, une fois que vous aurez votre compteur de limite inférieure de 1001, votre limite supérieure sera 1033, et ainsi de suite. Ce que vous vous retrouvez avec une fenêtre coulissante.

Si un tel scénario est acceptable, alors tout ce que vous devez vérifier est que votre ID de compteur entrant est dans votre fenêtre acceptée. Ce sera un sous-ensemble du compteur 16 bits, de sorte que vous pouvez tester ...

incomingCounterID - lowerLimitCount < windowSize

Tant que vous traitez avec des variables non signées, vous devriez être bien.

Espérons que cela aide (et a du sens).

Answer 2

je pourrais avoir le client, sauf deux choses:

• un message interne 32 bits non signé contre
• une liste de requêtes serveur en attente

A chaque demande, le client incrémente son compteur interne et l'enregistre dans la liste. Dans le message de requête, il met le compteur à ce numéro modulo 65536. Lorsqu'un message de réponse arrive, le client parcourt sa liste de demandes en attente pour un numéro correspondant modulo 65536. Si ce numéro interne est supérieur au plus haut jusqu'à présent, le message est accepté. Cela retarde le problème global à environ 4 milliards. Pseudocode suit ci-dessous.

unsigned long internalCounter = 0; 
unsigned long highestSoFar = 0; 

// On message send... 
++internalCounter; 
message.counter = internalCounter % 65536; 
pendingList.push_back(internalCounter); 

// On message receive... 
for (i = pendingList.begin(); i != pendingList.end(); ++i) 
{ 
    if (*i % 65536 == message.counter && *i > highestSoFar) 
    { 
     highestSoFar = *i; 
     pendingList.remove(i); 
     process(message); 
     break; 
    } 
} 

Answer 3

Ceci est la plupart du temps d'une combinaison de ce qui a été dit, alors ne me choisit pas comme la réponse, mais comme vous le savez

1. ce que vous avez demandé (la demande et le numéro de demande)

2. ce que vous avez obtenu

3. combien de temps il a été depuis que vous avez une folle demande

4. quelle réponse à une demande particulière devrait ressembler à

vous devriez être en mesure d'obtenir un système assez bonne passe.

De l'auteur demande/réponse côté preneur:

1. Ne jamais accepter une réponse pour une demande, vous ne l'avez pas fait ou fait si longtemps que vous le considérer vieux. Les données dans une telle réponse devraient être abandonnées. Acceptez uniquement la première réponse d'une demande attendue et marquez le numéro de la demande comme non-attendu lors de l'acceptation. (handler (* f)() est un bon moyen de l'implémenter)

2. Chaque fois qu'une réponse est reçue, vous devez enregistrer l'heure actuelle associée à ce numéro de demande pour vous aider lorsque vous commencez à recycler les numéros de demande. Cela devrait être fait pour les réponses acceptées et non acceptées (celles qui ont été supprimées en 1).

3. N'acceptez pas les réponses qui ne sont pas des données légales pour la demande faite. Si une telle réponse est reçue, supprimez-la et si vous pouvez déterminer que faire la demande réelle qui est censée utiliser à nouveau ce code de demande ne causera pas de mauvais effets secondaires sur l'autre machine, vous pouvez répéter la requête avec une nouvelle requête code (s'il y en a qui sont intacts depuis assez longtemps - voir 4) et marquez le code de demande plus ancien comme n'étant pas prévu.

4. Choisissez vos numéros de demande de ceux que vous n'avez pas vu de réponses sur le plus long temps. Si le code de requête utilisé le moins récemment est trop jeune, connectez-vous à l'événement, mais essayez de continuer à travailler. Traiter tous les numéros de demande inutilisés comme ayant été utilisés il y a longtemps. Affichez votre code d'écoute de réponse avant votre demande d'envoi de code afin qu'il puisse voir s'il y a d'anciennes réponses qui arrivent dans la pipe depuis la dernière exécution de ce programme.

Sur le preneur demande/réponse côté du fabricant:

1. Si une demande est faite avec un numéro de demande que vous travaillez déjà sur une réponse pour enregistrer l'événement et le seul service de la nouvelle réponse.

Cela devrait fonctionner correctement, sauf si vous envoyez un très grand nombre de demandes très rapidement. Cela ne suppose pas qu'il y ait quelqu'un sur le réseau qui veut faire de mauvaises choses. Il serait trivial d'implémenter un déni de service (DOS) sur cette configuration.

Answer 4

La manière habituelle de gérer ceci est de faire une soustraction modulo.Le numéro de séquence a est après le numéro de séquence b si & seulement si (a - b) % 65536 est supérieur à (b - a) % 65536.

Pour votre exemple, (65000 - 5) % 65536 est 64995 et (5 - 65000) % 65536 est 541, donc le numéro de séquence 5 est après le numéro de séquence 65000.

Answer 5

Votre problème a été répondu il y a longtemps RFC1982 qui dit que si vous avez le numéro de série non signé i1 et i2, le test approprié est

i1 est inférieure à i2 si i1 <> i2, et

(i1 < i2 and (i2 - i1) < 2^(SERIAL_BITS - 1)) or 
    (i1 > i2 and (i1 - i2) > 2^(SERIAL_BITS - 1)) 

(ou utiliser leur inverse supérieur à essai)

32 bits non signé, 2^(SERIAL_BITS - 1) = 2^31 = x80000000