Discussion :

[nscott32]

Bonjour,

Pour un projet (scolaire) d'application réseau en UDP, je dois attribuer un identifiant unique sur 8 octets à chaque message envoyé.
L'idée aurait été de ranger l'ip+port qui permet d'identifier un utilisateur unique, puis un identifiant de message, soit provenant d'un compteur, soit provenant du temps.

Une ip ça se range sur 4octets, donc il ne m'en reste déja plus que 4.
Pour le port, il doit être inférieur à 9999 pour le projet, et supérieur à 1024 pour éviter les well-known ports, cela fait donc une plage de 8975 soit 14bits (13.13).
Il me reste donc une plage de 18octets soit 262 144.
J'aimerais bien réduire la plage restante par exemple a 5octets au lieu de 5octets+6bits. Les fonction de hash standart envoie des données d'une taille variable vers une taille fixe avec une probabilité relativement faible de collision, elles ne conviennent pas dans mon cas car la taille d'arrivée est plus grande que celle que je demande (du moins celle que je connais).

Pensez-vous que cela est possible ?

[tbc92]

Donc, si j'ai bien compris, on t'a demandé d'écrire un certain nombre d'informations sur 64 bits (8 octets), et tu constates que 58 bits, c'est suffisant.

Parfait, Génial ! Dans les 6 bits restants, tu écris une série de 6 bits à 0 et voilà , ton problème est résolu. Et ces 6 bits non significatifs, tu peux les mettre où tu veux, au début, au milieu, à la fin ...

[nscott32]

Non c'est l'inverse !

J'aimerais obtenir quelque chose de relativement unique sur 8bits à partir de plus d'information, en fait idéalement pour obtenir un identifiant de message unique j'aimerais de quoi identifier l'utilisateur de manière unique, à savoir ip+port et après pour l'unicité du message l'heure par exemple. Mais cela ne rentre pas dans 8octets.
C'est là que je pense à générer un hash des informations, idéalement j'aurais aimé qu'un utilisateur puisse reconnaitre son message, donc hashé séparément ip+port et la composante d'intentification du message, mais je crois qu'il vaut mieux faire un hash de l'ensemble et oublier cette fonctionnalité.

[pseudocode]

Les fonction de hash standart envoie des données d'une taille variable vers une taille fixe avec une probabilité relativement faible de collision, elles ne conviennent pas dans mon cas car la taille d'arrivée est plus grande que celle que je demande (du moins celle que je connais).

Pour peu que ta fonction de hashage suive une distribution uniforme (ce qui est le cas pour la plupart de fonctions de hash habituelles), tu peux raccourcir le hash tout en gardant les propriétés de la fonction de hashage (faible probabilité de collision). Par exemple, tu peux prendre les 18 premiers bits sur un MD5 de 128 bits.

[nscott32]

Mais la probabilité de colision sera bien plus importante, car pour chaque hash sortie il y a 2^64 hash qui commencent par la même séquence de 8bit, multiptiplié par le nombre d'antécédent par hash ça fait gros !

[BufferBob]

salut,

Une ip ça se range sur 4octets, donc il ne m'en reste déja plus que 4.
Pour le port, il doit être inférieur à 9999 pour le projet, et supérieur à 1024 pour éviter les well-known ports, cela fait donc une plage de 8975 soit 14bits (13.13).

je sais pas si c'est envisageable, mais si tu sélectionnes ton port au dessus de 1807 au lieu de 1024 tu tombes le nombre de ports disponibles à 8192, tu gagnes 1 bit au détriment de 783 ports

Il me reste donc une plage de 18octets soit 262 144.

18 bits plutôt non ?

J'aimerais bien réduire la plage restante par exemple a 5octets au lieu de 5octets+6bits. Les fonction de hash standart envoie des données d'une taille variable vers une taille fixe avec une probabilité relativement faible de collision, elles ne conviennent pas dans mon cas car la taille d'arrivée est plus grande que celle que je demande (du moins celle que je connais).

là j'avoue j'ai rien compris de ce que tu as expliqué

Mais la probabilité de colision sera bien plus importante, car pour chaque hash sortie il y a 2^64 hash qui commencent par la même séquence de 8bit, multiptiplié par le nombre d'antécédent par hash ça fait gros !

oui mais en même temps si tu veux 0 collision t'auras pas tellement d'autre choix que de faire du 1 pour 1, après je sais pas si effectivement tronquer un hash comme ça est valide/fiable mais au pire tu pourrais envisager une fonction de hashage sur 64bits, qu'il s'agisse d'un CRC64 ou d'un Blowfish

mais je me pose d'autres questions, il est censé servir à quoi foncièrement ce hash, il doit permettre d'identifier chaque paquet ? ou juste une session ? dans un réseau local ? internet ? est-ce que par exemple chaque protagoniste doit pouvoir identifier chaque paquet ou est-ce que seul l'émetteur a besoin de tenir une liste de hash ?

[nscott32]

Ce que je disais c'est que md5 par exemple envoie sur une 128bit alors que moi j'en ai 64 de dispo donc cette fonction ne convient pas par exemple.

C'est pour un réseau sur une topologie en anneau, chaque message est envoyé à la personne suivante sur l'anneau et il fait le tour de l'anneau. Quand le message revient au destinataire il faut donc le supprimer. On attribue un identifiant unique au message de sorte qu'on puisse le reconnaitre s'il à déja été vu pour ne pas le retransmettre.
Une solution est de conservé la liste des messages vus, mais pour l'instant je m'intéresse à la possibilité de se reconnaitre propriétaire du message en regardant l'identifiant de message, c'est l'autre possibilité.

[pseudocode]

Mais la probabilité de colision sera bien plus importante, car pour chaque hash sortie il y a 2^64 hash qui commencent par la même séquence de 8bit, multiptiplié par le nombre d'antécédent par hash ça fait gros !

Ce que je voulais dire c'est que les valeur possibles du MD5 se répartissent uniformément sur les 128 bits (aka "Null hypothesis").
==> proba(bit0=1) = proba(bit0=0) = proba(bit1=1) = proba(bit1=0) = ... = proba(bit128=1) = 50%

Donc, si tu ne choisis que 18 bits, les valeur possibles se répartissent également uniformément sur les 18 bits.

Ca donne donc une fonction de hash sur 18 bits qui est aussi "bonne" que la fonction de hash originale sur 128 bits.
Bien sur, il y a 7 fois moins de bits et donc 7 fois plus de chance de collision. Mais pas plus que cela.

[dinobogan]

Tu ne donnes pas assez d'info sur le projet, alors je donne l'idée et tu pourras nous dire si c'est faisable ou pas :
je suppose qu'il y a un serveur central. Il va attribuer un numéro unique à chaque nouvel utilisateur. Il faut une borne maximum que tu peux fixer à 2 octet par exemple. Il reste donc 6 octets pour numéroter le message.
S'il n'y a pas de serveur central, explique ta typologie réseau.

Sinon, pour ta solution initiale, pourquoi 18 bits ne sont pas suffisants pour identifier un message d'un utilisateur ? Quel est la durée de vie d'un message ? Pour un utilisateur donné, combien de ces messages peuvent être vivant en même temps ?

[nscott32]

Oui si je ne donne pas plus d'infos sur le projet c'est que ma question porte sur les hash avant tout, mais je suis quand même obligé de donné un peu de contexte.

L'idée du projet c'est de faire des réseaux UDP en anneaux. On peut voir l'anneau comme une liste chainnée circulaire à sens unique. L'insertion sur un anneau se fait via un échange protocolaire tcp.
A la création d'un anneau une entité est seule sur l'anneau et peut donc s'envoyer des messages à elle même.
Les messages circulant sur l'anneau suive un protocole spécifique au projet et on une taille fixe de 512octets. Il y a des messages "protocolaires" envoyer automatiquement pour la vérification de l'intégrité de l'anneau, d'autres messages protocolaires, et en particulier des messages d'applications. Une application possible est le transfert de fichier, le destinataire est spécifier dans le message, ainsi que le nombre de message qui segmentent le fichier, etc...

Je pense au cas extrême en me dianst qu'une entité pourrait envoyer deux fichiers d'un taille très grande (plusieurs gigas) l'un après l'autre, le nombre de message requis est du même ordre que de la plage disponible dont on a parlé pour numéroté le message. Dans des cas extrême (mais possible) comme celui ci, on risque la collision.