Hash-Funktion für src dest ip + port

Die Primzahl wird verwendet, weil, wenn ein Wert mit einer Primzahl multipliziert wird, er tendenziell eine höhere Wahrscheinlichkeit hat, einzigartig zu bleiben, wenn sich andere ähnliche Operationen darüber aufaddieren. Der spezifische Wert 59 kann willkürlich gewählt worden sein oder er kann beabsichtigt sein. Es ist schwer zu sagen. Es ist möglich, dass 59 tendenziell eine bessere Verteilung von Werten basierend auf den wahrscheinlichsten Inputs generiert.

Die Verschiebung um 16 ist möglicherweise darauf zurückzuführen, dass die Ports auf den Bereich 2 ^ 16 beschränkt sind. Die Funktion scheint den Quellport in den höheren Teil des Bitfelds zu verschieben, während der Zielport im unteren Teil verbleibt. Ich denke, das kann in meinem nächsten Absatz weiter erklärt werden.

Ein anderer Grund, warum die Multiplikation stattfindet (und das gilt auch für die Schiebeoperation), ist, weil sie die assoziative Natur der Hash-Funktion aufschlüsselt. Denken Sie daran, XOR ist assoziativ, so dass die IPs src = 192.168.1.1 und dst = 192.168.1.254 auf den gleichen Wert wie src = 192.168.1.254 und dst = 192.168.1.1 (getauscht) würden, wenn die Multiplikation nicht vorhanden wäre.

Untersuchen Sie die Ausgabe der Funktion auf gleichmäßige Verteilung. Wenn Sie es nicht mögen, stecken Sie verschiedene Primzahlen ein, bis Sie eine Distribution erhalten, die Ihnen gefällt. Hashing kann eine sehr dunkle Kunst ohne "richtige" Antwort sein.

Ich persönlich denke, dass es besser wäre, wenn Sie die vier IP-Bytes als unsigned long lesen, was Ihnen eine ungefähre Zahl im Bereich von 0 - 2 ^ 32-1 geben würde. Dann ermitteln Sie, wie viele Datenflüsse Sie gleichzeitig aktiv haben möchten, und das wäre Ihre Indextabellengröße.

Nehmen Sie 2000 zum Beispiel. Das bedeutet, dass Sie 2 ^ 32 Zahlen auf ungefähr 2 ^ 11 Indices abbilden wollen (um Informationen fließen zu lassen). Das wird nicht funktionieren, weil Hashing fast nie funktioniert, wenn gefüllt zu 100% und sogar 90% schwierig sein kann. Die Verwendung einer Indextabelle, die nur zu 50% (4000 indeces) oder gar zu 25% (8000) gefüllt ist, ist mit den heutigen Erinnerungen keine große Sache.

Die genaue Größe der Indextabelle sollte eine ungerade Anzahl von Stellen und vorzugsweise eine Primzahl sein. Dies liegt daran, dass Sie höchstwahrscheinlich eine Überlaufbehandlung benötigen, um Kollisionen zu behandeln (zwei oder mehr IP-Nummern, die nach dem Hash-Punkt auf dieselbe Position in der Indextabelle verweisen) - die Sie erhalten. Die Überlaufbehandlung sollte eine andere Primzahl als die Indextabellengröße sein. All diese Primzahlen! Was ist mit ihnen überhaupt?

Ich werde mit einem Beispiel (in C) veranschaulichen:

...

füllt die Tabelle der idxjmp-Positionen anfänglich mit einer UNUSED-Markierung (-1). Halten Sie eine DELETED-Markierung bereit (-2).

Ihre IP-Nummer wird in das System eingegeben und Sie suchen nach ihrem Flow-Datensatz (möglicherweise oder auch nicht):

Der UNUSED dient als Markierung, dass dieser Index nie benutzt wurde und dass die Suche aufhören sollte. Der DELETED dient als Markierung dafür, dass dieser Index nicht mehr verwendet wurde. Das bedeutet, dass die Suche fortgesetzt werden muss.

Das war, als du versucht hast, etwas zu tun. Sie erhalten einen NULL zurück von get, also müssen Sie einen Put machen, den Sie beginnen, indem Sie die erste Indexposition finden, die UNUSED oder DELETED enthält. Ersetzen Sie diesen Wert durch einen Index für die erste / nächste freie Zeile in der Tabelle flow_record. Markieren Sie die Zeile als in_use. Setzen Sie die ursprüngliche IP-Nummer in das ip-Member der Zeile flow_record.

Dies ist eine sehr einfache - aber sehr effektive - Möglichkeit, einen Hash-Mechanismus zu konstruieren. Praktisch jede Optimierung in Form von speziellen Funktionen, die nach dem Scheitern dieser oder jener Funktion verwendet werden sollen, erhöht die Effektivität des Hashing.

Die Verwendung von Primzahlen stellt sicher, dass - im schlimmsten Fall, wenn alle Indexstandorte belegt sind - der Mechanismus jeden einzelnen Ort testet. Um dies zu illustrieren: Angenommen, Idxsiz ist durch ovfjmp ganzzahlig teilbar: Sie werden nicht viel Überlauf haben, um davon zu sprechen. 35 und 7 werden dazu führen, dass die Positionen 0,7,14,21 und 28 getestet werden, bevor der Index auf 0 springt, wobei der While-Test die Suche stoppt.

---------------------- OOPS!

Ich habe verpasst, dass Sie auch die Portnummer haben wollten. Angenommen, IP V4 bedeutet 6 Byte Adresse. Lesen Sie dies als vorzeichenlose 64-Bit-Ganzzahl und löschen Sie die oberen 16 Bits / 2 Bytes. Dann machst du die Modulo-Berechnung.

Brian Gideon fasst es ziemlich zusammen; die Multiplikation und die Verschiebung sind als Symmetriebrecher gedacht. Das fängt also den hypothetischen Fall ein, dass Maschine A an Maschine B telnet und umgekehrt und sie wählen zufällig die gleiche flüchtige Portnummer. Nicht sehr häufig, aber nicht unmöglich. Ein großer Teil des 5-Tupels ist ziemlich konstant: Das Protokoll kommt von einer sehr kleinen Domäne und ebenso die Hälfte von {Adresse, Portnummer}.

Unter der Annahme einer Primzahl-Hashtabelle könnte die magische Konstante 59 durch jede Primzahl, IMO, ersetzt werden. Der (Port & lt; & lt; 16) könnte auch durch eine andere Verschiebung ersetzt werden, solange keine Bits abfallen oder sogar durch einen (port * some_other_prime) -Begriff.

Für eine Potenz von zwei Größen sollten alle (minus eins) Mitglieder des 5-Tupels mit einem (anderen) Primfaktor multipliziert werden. (Früher, als die Teilung teuer war, wäre das eine Option gewesen)