IP Adressen matching

AVL Baum bietet sich an, noch schneller. is sicher auch nicht zu "fett" ...

lg

Ich würde mir eher Gedanken um das effiziente Abspeichern der IP-Adressen machen. Hier würde sich die Umrechnen der IP-Adresse auf einen Int sicher als nützlich erweisen.

Wegen der Angabe der Subnetmask würde ich mal davon ausgehen das auch Netzwerkbereiche angegeben werden können was das Ganze schon erschwert.

*hier stand blödsinn*

So hab mir das gerade nochmal überlegt, du könntest bei Bereichen die Netzwerk- und Broadcastadresse berechnen und diese wie folgt in einem Baum speichern.

Netzwerkadresse als Root, Broadcast als rechtes Kind
Wenn die Netzwerkadresse in das linke Kinder der Broadcastadresse geht darf die IP-Adresse den Service nutzen.

Zu Überlegen bleibt nur ob es Problem beim Balancieren des Baumes geben kann bzw wie die sich auf die Erkennung auswirken

auf den ersten blick schaut es aus als baust du eine firewall nach. warum nicht also eine firewall nehmen?

sonst kommt es sehr darauf an was du wirklich damit vor hast. ist das derart zeitkritisch? mein erster ansatz waere gewesen "das ganze" in python in ein tupel/eine list zu klatschen und dann einfach ein "in" darauf loszulassen. so viel overhead sehe ich nicht. python weisz im allgemeinen - meist besser - wie man sucht und sortiert. im schlimmsten fall kann man ja noch mit psycho tricksen. abspeichern wuerde ich IPv4 adressen als zahlenwert. das sollte dann auch beim subnet-maskiern hilfreich sein. so in die richtung:

shiftwidth = 24
number = 0
for part in ip.split("."):
    number += int(part) << shiftwidth
    shiftwidth -= 8

wie gesagt, ich habe keine ahnung was du wirklich damit tust, vielleicht zahlt es sich ja doch aus hand anzulegen.

Zitat von skinner33

Ich würde mir eher Gedanken um das effiziente Abspeichern der IP-Adressen machen. Hier würde sich die Umrechnen der IP-Adresse auf einen Int sicher als nützlich erweisen.

Umrechnen auf einen Int? Was umrechnen? Irgendwie Klar, dass man IP-Adressen in einem Int speichert, wenn man sie suchen und sortieren möchte, oder?

Zitat von davewood

mein Baum verändert sich zur Laufzeit nicht und wenn er von Beginn an balanciert ist gehts ja mit einem AVL Baum auch nicht schneller, oder versteh ich da was nicht?

Wenn sich der Baum zur Laufzeit nicht ändert, nur besser so. Trotzdem musst du den Baum mal initial einlesen, und da halt schaun dass er immer schön balanciert ist (im Gegensatz zum normalen Binärbaum), damit du mit "O log(n)" suchen kannst.

Zitat von Martinez

Irgendwie Klar, dass man IP-Adressen in einem Int speichert, wenn man sie suchen und sortieren möchte, oder?

Bei IPv6 ist mir das nicht so klar, muss ich zugeben.

Zitat

Trotzdem musst du den Baum mal initial einlesen, und da halt schaun dass er immer schön balanciert ist

Das wuerde der in Post #2 vorgeschlagene Algorithmus schoen gewaehrleisten, und das ohne den Aufwand einer korrekten AVL-Implementierung.

@plantschkuh: stimmt, sollt genauer lesen bevor ich poste.

:coolgrim:

Zitat von davewood

1) in ein Array packen
2) mit qsort sortieren
3) halbieren, einen Baum daraus machen, halbieren, ... dann is der Baum sortiert und ich kann schnell darin suchen

Dazu ist mir vorher eingefallen, dass das eigentlich eine ziemlich umstaendliche Art ist, eine Binaersuche zu implementieren Wenn du das sortierte Array hast, das sich nicht aendert, kannst du gleich auf die explizite Baumstruktur verzichten. Ersparnis: Zwei Pointer, was eventuell ein signifikanter Teil deines Speicherverbrauchs ist; somit koennte die Binaersuche wesentlich Cache-freundlicher sein, weil einfach mehr Eintraege auf einmal in den Cache passen. Preis: Einige Arithmetik-Befehle mehr. Was schneller ist, muesste man wohl ausprobieren.

Noch eine Ueberlegung zur Cache-Freundlichkeit, die bei diesem Beispiel glaub ich sehr relevant ist: Angenommen, der Baum ist hinreichend gross. Jede Suche wird die Wurzel besuchen; praktisch jede Suche wird eines der zwei Kinder der Wurzel besuchen; praktisch jede Suche wird eines der zwei Kinder von einem dieser Kinder besuchen. Wenn die Baumstruktur aber ganz simpel ueber ein sortiertes Array druebergestuelpt wird, dann sind diese sehr haeufig besuchten Knoten eben immer ziemlich weit von ihren Eltern entfernt, und zwar immer das eine links, das andere rechts. Damit wuerde ich erwarten, dass es staendig Cache Misses hagelt. Der Baum sollte wohl nach reiflicher Ueberlegung in Bloecken von Knoten angelegt werden, die die Lokalitaet der Zugriffe maximieren. Insbesondere sollten alle Knoten der obersten [tex='n'][/tex]

Schichten direkt nebeneinander stehen, Reihenfolge etwa wie durch eine Breitensuche, die auf eine passende Tiefe limitiert ist. Und die restlichen Teilbaeume in aehnlichen Bloecken ablegen, nicht den gesamten Baum in Breitensuchreihenfolge (das waere toedlich, wenn man zu den Blaettern hin kommt).

Man koennte sich auch ueberlegen, ob man was gewinnen kann, indem man Branches einspart. Naive Suchbaumsuche:

while (node != NULL && node->key != key) {
    if (node->key > key)
        node = node->left;
    else
        node = nore->right;
}

Das if geht mal nach links, mal nach rechts; die Branch Prediction duerfte sich damit ziemlich schwertun. Je nach Architektur koennte es ganz naiv ueberlegt einiges bringen, auf den Sprung zu verzichten:

while (node != NULL && node->key != key) {
    node = node->children[node->key < key];
}

Vielleicht ist das aber nur eine obskure Schreibweise, die gar nichts bringt. (Wenn doch, koennen ganz mutige auch noch die Schleife unrollen )

Ganz schliesslich sei noch auf den Splay Tree verwiesen. Der funktioniert aehnlich wie ein Cache: Wenn ein Knoten gesucht wurde, wird er zur Wurzel hin rotiert; wird er bald wieder gesucht, findet man ihn viel schneller. Koennte viel bringen, wenn dieselbe IP mehrmals kurz hintereinander gesucht werden soll. Wenn die Zugriffsmuster allerdings nicht so sind, kriegt man im Worst Case [tex='O(n)'][/tex]

-Suchverhalten, eine DoS-Attacke ist quasi vorprogrammiert.

Ich glaub, wenn du das schreiben würdest, könntens die Uhr vom Knight Rider als Server verwenden.

ich hab nur eine halbe minute rein geschaut, aber folgendes ist mir mal aufgefallen (weil ich beim atoi haengen geblieben bin):

char *part[3];
for(i = 0; i<(rc-1); i++) {
    part_start = ip_string + ovector[2+(i*2)];
    part_length = ovector[3+(i*2)] - ovector[2+(i*2)];
    sprintf(part, "%.*s", part_length, part_start);
    new_ip->addr.addr_b[3-i] = atoi(part);
}

atoi? das darfst du aber keinem sysprog-tutor zeigen atoi ist auf der blacklist => einreiseverbot ins sysprogland.
sprintf in ein array aus 3 char* ohne sie zu mallocn? uiuiui.

dass der code nicht wirklich C ist ist dir eh klar? durchs "make" laeuft er auch nicht sonderlich gut.

cfg.c:85:16: warning: unknown escape sequence '\.'
cfg.c:85:16: warning: unknown escape sequence '\.'
cfg.c:85:16: warning: unknown escape sequence '\.'
cfg.c: In function ‘char2ip’:
cfg.c:123: warning: assignment discards qualifiers from pointer target type
cfg.c:125: warning: passing argument 1 of ‘sprintf’ from incompatible pointer type
cfg.c:126: warning: passing argument 1 of ‘atoi’ from incompatible pointer type

also ich würde statt einen Baum einen Trie nehmen. mit 256 werten pro blatt

Bei IPv4 hat man max. 4 zugriffe auf den Speicher und kann mit spezialknoten ganze Subnetze abbilden.

Die Datenstrucktur müsste doch mit 200 Lines implementiert sein. Wahrscheinlich ist es durch Häufungen in Ipbereichen gar nicht so verschwenderisch, wie man vermuten könnte (müsste man sich statistisch ansehen)

Zitat von davewood

Code

snprintf(part, 3, "%.*s", part_length, part_start);

Ist part da noch immer als Array von Pointern deklariert?

Zitat

Wie ich die Fehlermeldung cfg.c:85:16: warning: unknown escape sequence '\.' wegbekomme weiß ich nciht, "\." ist die Escape Sequenz meiner Regexp.

Du musst einen doppelten Backslash nehmen.

Zitat

josef: ich brauch aber IPv6 auch und da will ich analoge Strukturen verwenden

Fuer IPv6 kannst du theoretisch einfach einen tieferen Trie nehmen. Ich persoenlich bin skeptisch bezueglich Platzverbrauch, aber ausprobieren waere sinnvoll.