Donc, je regarde différentes fonctions de hachage à utiliser pour le hachage A 4 tuple IP et le port pour identifier les flux.
Un que j'ai rencontré était maintenant Pour la vie de moi, je ne peux pas expliquer le principal utilisé (59). Pourquoi pas 31, puis pourquoi aller gâcher en multipliant le sport par une puissance de 2.
Y a-t-il une meilleure fonction de hachage à utiliser pour les adresses IP?
4 Réponses :
Examinez la sortie de la fonction pour une distribution uniforme. Si vous ne l'aimez pas, branchez des nombres premiers différents jusqu'à ce que vous ayez une distribution que vous aimez. Le hachage peut être un art très sombre sans réponse «droite».
Ouais. Très probablement, cette fonction particulière résulte de tester de nombreuses fonctions différentes sur les données de test et de voir ce qui a donné le meilleur comportement.
Le numéro principal est utilisé car une seule valeur est multipliée par un nombre premier, il a tendance à avoir une probabilité plus élevée de rester unique lorsque d'autres opérations similaires sont accumulées de dessus. La valeur spécifique 59 peut avoir été choisie arbitrairement ou qu'elle peut être intentionnelle. Il est difficile de dire. Il est possible que 59 avaient tendance à générer une meilleure répartition des valeurs basées sur les intrants les plus probables.
Le changement de 16 peut être parce que les ports sont limités à la plage 2 ^ 16. La fonction semble déplacer le port source dans la partie supérieure du champ Bitfield tout en laissant le port de destination dans la partie inférieure. Je pense que cela peut être expliqué plus loin dans mon prochain paragraphe.
Une autre raison pour laquelle la multiplication a lieu (et cela est vrai de l'opération de changement de vitesse) est donc parce qu'il décompose la nature associative de la fonction de hachage. N'oubliez pas que XOR est associative de sorte que les IPS SRC = 192.168.1.1 et DST = 192.168.1.254 Le hachage de la même valeur que SRC = 192.168.1.254 et DST = 192.168.1.1 (échangé) si la multiplication n'était pas là.
Alors, pourquoi ne pas multiplier chaque adresse IP avec le premier au lieu de la source.
La fonction Hash serait encore associative car (a * p) ^ (b * p) = (b * p) ^ (a * p) . Bien qu'il soit courant de voir deux numéros de coprime travaillant en tandem pour faire quelque chose de similaire.
Personnellement, je pense que vous feriez mieux de lire les quatre octets IP comme un peu signé long, ce qui vous donnerait un nombre à peu près compris entre 0 et 2 ^ 32-1. Ensuite, vous déterminez combien de flux que vous souhaitez avoir actifs à une fois et ce serait votre taille de table d'index.
Prendre 2000 par exemple. Cela signifie que vous souhaitez mapper 2 ^ 32 numéros sur environ 2 ^ 11 indeces (pour les informations d'écoulement). Cela ne fonctionnera pas car le hachage ne fonctionne presque jamais s'il est rempli à 100% et même 90% peut être difficile. En utilisant une table d'index que vous ne remplissez que 50% (4000 indeces) ou même 25% (8000) n'est pas une grosse affaire avec les mémoires d'aujourd'hui. P>
La taille exacte de la table d'index devrait être un nombre inégal de emplacements et de préférence un nombre premier. En effet, vous aurez probablement besoin d'avoir une manipulation de débordement pour gérer les collisions (deux ou plusieurs numéros de propriété intellectuelle après le point de hachage au même emplacement dans la table d'index) - que vous obtiendrez. La manipulation des débordements doit être un autre nombre de premier choix que la taille de la table d'index. Tous ces nombres premiers! Qu'est-ce qui est avec eux quand même? P>
Je vais illustrer avec un exemple (en C): p> ... p> Initialement Remplissez la table des positions IDXJMP avec un marquage inutilisé (-1). Avoir un marquage supprimé prêt (-2). P> Votre numéro IP entre dans le système et que vous recherchez son enregistrement de flux (peut ou non exister): P> stoppos = ip % idxsiz; /* modulo (division) just this once */
i = stoppos;
do
{
if (index[i] == UNUSED) return NULL;
if (index[i] != DELETED)
{
flowrecptr = &flow_record[index[i]];
if (!flowrecptr->in_use) {/* hash table is broken */}
if (flowrecptr->ip == ip) return flowrecptr;
}
i += ovfjmp;
if (i >= idxsiz) i -= idxsiz;
}
while (i != stoppos);
return NULL;
Brian Gideon résume beaucoup beaucoup; La multiplication et le décalage sont conçus comme un disjoncteur de symétrie. Cela attire donc le cas hypothétique de la machine un telNetting à la machine B et inversement et ils ont choisi le même portnum éphémère. Pas très courant, mais pas impossible. Une grande partie du 5-tuple est assez constante: le protocole provient d'un très petit domaine, de même que la moitié de {adresse, portnum}.
En supposant une haquetable de grande taille, la constante magique 59 pourrait être remplacée par n'importe quel prime, imo. Le (port << 16) pourrait également être remplacé par un autre décalage, tant qu'aucun bits ne tombe ou même par un terme (port * quelque_other_prime).
Pour une haquetable de la taille d'une puissance de deux, tous (moins un) membres de la 5 tuple devraient être multipliés par un (différent) Prime. (Dans les vieux jours, lorsque la division était chère qui aurait été une option)