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.

[dinobogan]

Comment fait un nouveau client pour intégrer l'anneau ? Il contacte le créateur de l'anneau ?
Si oui, alors le créateur de l'anneau peut donner un nouveau numéro unique au nouveau client. Chaque client est identifié par ce numéro unique au lieu de son adresse IP+port.
Tu peux stocker ce numéro unique sur 3 octets ce qui permet d'avoir à chaque instant un maximum de plus de 16 millions de clients. Il te reste 5 octets pour l'identification du message.

Tu voudrais un identifiant de message sur environ 5 octets. Ca me parait trop. En effet, 1000 milliards de paquets en transit pour un seul client est beaucoup trop élevé sur un réseau, peut importe sa typologie. En plus, selon le mode de transfert, les messages arrivent probablement dans le désordre et il faut les réordonner. La solution IP+port et 18 bits pour le numéro de message me semblent largement suffisant.

[nscott32]

L'insertion se fait à partir de n'importe quelle entité sur le réseau.
Il faudrait limiter le traffic sur le réseau alors ?

[dinobogan]

Il faudrait limiter le traffic sur le réseau alors ?

Non, il ne faut pas voir ça comme une limite technique. 260.000 messages à chaque instant pour un émetteur donné est largement assez.
Il "suffirait" d'ajouter un message protocolaire signifiant que le numérotage redémarre à zéro et l'envoyeur attend un "ok message reçu, remet à zéro" de la part du receveur. Du point de vue de l'émetteur et du receveur, il y aurait un flux continue d'information en transit, peu importe la taille du fichier à transférer.

[nscott32]

Oui mais si un message numéro 0 par exemple n'a pas encore fait le tour de l'anneau et que le compteur a eu le temps de revenir à 0, deux messages avec le numéro 0 vont circulé est le deuxième sera considéré comme déja vu par les entité donc ne sera pas retransmis.

[dinobogan]

Oui mais si un message numéro 0 par exemple n'a pas encore fait le tour de l'anneau et que le compteur a eu le temps de revenir à 0, deux messages avec le numéro 0 vont circulé est le deuxième sera considéré comme déja vu par les entité donc ne sera pas retransmis.

Pour toi, une entité est une machine intermédiaire entre l'émetteur et le receveur ?
Comme déjà dit dans un message précédent, tu n'expliques pas grand chose...
Que contient un message ? adresse émetteur, identifiant message et adresse receveur. J'ai bon ?
Lorsqu'une entité reçoit un message, si l'identifiant receveur ne lui correspond pas alors elle retransmet le message. Par contre, si l'identifiant émetteur ou récepteur lui correspond, alors elle ne retransmet pas.

Pour la remise à zéro, tu utilises un message "protocolaire" comme tu les appelles. Avant de redémarrer la numérotation à zéro, l'émetteur transmet un message de protocole interne avertissant que la remise à zéro est imminente et attend l'accord du receveur.

Une idée me vient à l'instant : la numérotation du message est universelle, peu importe l'adresse de l'émetteur et du receveur ? Ou alors la numérotation est spécifique à un émetteur ou receveur ?

[nscott32]

Une entité est une machine sur l'anneau.
Un message est formé par les champs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

<TYPE> <IDM> <CONTENU>

Le type est sur 4 octets, l'id sur 8 octets, le contenu prend le reste (il y à des espaces entre les champs).
Les messages passent par toute les entité (retransmis par les entités), une entité qui a déja vu un message ne le retransmet pas.
C'est aux entités de savoir comment elles doivent traiter le message.

On ne peut pas se servir de messages protocolaires pour les identifiants de message car tout les message du protocole doivent posséder un identifiant unique.

[dinobogan]

Une entité est une machine sur l'anneau.
Un message est formé par les champs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

<TYPE> <IDM> <CONTENU>

Le type est sur 4 octets, l'id sur 8 octets, le contenu prend le reste (il y à des espaces entre les champs).

TYPE est ce qui identifie un message normal d'un message "protocolaire" ?
L'id ne contient que l'adresse du destinataire ?
Un message ne contient pas l'id de l'émetteur ?

Les messages passent par toute les entité (retransmis par les entités), une entité qui a déja vu un message ne le retransmet pas.

Un message déjà vu est un ensemble (TYPE, IDM) déjà reçu ? Une entité ne peut pas stocker tous les couples (TYPE, IDM) qu'elle a rerouté. Cela va poser 2 problèmes : 1) le volume va vite devenir gigantesque et 2) la recherche dans ce volume lorsqu'un nouveau message est à rerouter va prendre trop de temps.

C'est aux entités de savoir comment elles doivent traiter le message.

C'est-à-dire ? Tu gères uniquement le protocole et pas le code des entités ?

On ne peut pas se servir de messages protocolaires pour les identifiants de message car tout les message du protocole doivent posséder un identifiant unique.

Je ne comprends pas. Cela signifie qu'un message protocolaire ne possède pas l'adresse de l'entité réceptrice ? C'est toujours une même entité (peut-être l'entité "serveur") qui envoie les messages protocolaires ?

[nscott32]

Puisque c'est vraiment le sujet qui t'intéresse : https://www.irif.univ-paris-diderot....seaux-2016.pdf

[dinobogan]

Je pense que tu t'es mélangé les pinceaux sur les différents champs d'un message et sur le principe de ne pas transmettre de nouveau un message déjà transmis.
"idm" est un identifiant unique à une entité. Il n'y a pas de lien avec un numéro de message.
Lorsqu'une entité envoie un message, elle place son idm, toujours le même quelque soit le message. Lorsqu'elle reçoit un message avec son "idm", elle ne le transmet pas.
Pour transférer un fichier, le numéro du message est indiqué dans le contenu du message. C'est le principe d'encapsulation ou couche réseau.

Donc pour ton "idm", il suffit d'y placer l'adresse IP et le numéro de port de l'entité, c'est tout. Ton numéro devient unique pour l'anneau.

[nscott32]

Non non en faite idm c'est pour IDentifiant de Message.
L'idée d'inclure un indentifiant d'utilisateur c'est parce qu'il n'y a pas moyen de partager un systême de gestion des identifiants de message entre les entitées, donc il faudrait que chaque entitées ai son propre gestionnaire d'identifiant. Mais cela peut poser conflit di deux entitées produisent des identifiants identiques, donc il faudrait inclure un identifiant d'entité, d'où l'ip+le port.