Was ist die beste Art der Umsetzung longest-prefix-matching für ipv6?

Ipv6-router speichert eine Reihe von Routen, die als erste n bits der Adresse. Im Jahr 2000 fanden die Forscher nur 14 verschiedene Präfix-Länge in 1500 ipv6-Routen. Eingehende Pakete sind an unterschiedliche ausgehende ports, basierend auf der längsten Präfix-übereinstimmung, so dass, wenn die ersten 8 bit der Paket-x match ein 8-bit-route, aber die ersten 48 bits des gleichen Pakets entsprechen einem 48-bit-route dann den router, müssen Sie die 48-bit-route.

Mein router ist die Verarbeitung so viele Pakete, dass die Geschwindigkeit der memory lookup in der routing-Tabelle ist ein limitierender Faktor. Was ist ein guter Algorithmus zu finden, der längsten übereinstimmenden Präfix in meiner routing-Tabelle?

Ist der routing-Tabelle Konstante?
Nein, es werden von Zeit zu Zeit aktualisiert.
"Es gibt eine begrenzte Anzahl von standard-Präfix-Länge wahrscheinlich gefunden werden, in einer gegebenen routing-Tabelle. "Nein, das ist nicht wahr. Überprüfen Sie alle IPv6-looking glass und du wirst viele /30, /35, etc
Na wenigstens kann es nicht mehr als 128 :-0

InformationsquelleAutor joeforker | 2009-02-04

  1. 5

    Verwenden Sie entweder eine trie oder eine radix-Baum zum speichern der "standard" - Präfixe. Ein suffix-Baum/array ist eine unnötige over-kill; Sie werden verwendet, um übereinstimmungen zwischen infixes (unter Verwendung der Tatsache, dass jede infix ist ein Präfix eines suffix, und wenn Sie wollen, um eine übereinstimmung zu finden zwischen mehreren strings, verketten Sie Sie zu einer anderen), und das nicht nur zwischen den Präfixen.

    InformationsquelleAutor David Lehavi

  2. 2

    Fand ich eine cool Papier zu diesem Thema genannt Longest Prefix Matching mit Bloom-Filter.

    Beschreibung: stellen Wir die erste Algorithmus, den wir bewusst sind, zu beschäftigen Bloom-Filter für Longest Prefix Match (LPM). Der Algorithmus führt eine parallele Abfragen auf Bloom-filtern, einer effizienten Datenstruktur für die Mitgliedschaft Abfragen, um festzustellen, Adresse Präfix Mitgliedschaft in Sätze von Präfixen sortiert nach Präfix-Länge. Wir zeigen, dass die Verwendung dieses Algorithmus für Internet-Protokoll - (IP -) routing-lookups Ergebnisse in einer Suchmaschine eine bessere Leistung und Skalierbarkeit als die TCAM-basierte Ansätze.

    Ihre grundlegende Idee ist die Verwendung von bloom-filtern gespeichert, die in einem Prozessor des embedded-SRAM (fast) zu führen Präfix hash-Tabellen lookups in langsamer, aber mehr reichlich Speicher. Für die IPv4-Fall Sie optimieren Ihren Algorithmus für die Tatsache, dass die meisten der routing-Tabelle sind mit einem Präfix von 24 bit. Für IPv6-Sie fanden nur 14 eindeutiges Präfix-Länge in 1550 BGP-Einträge.

    InformationsquelleAutor joeforker

  3. 0

    Glaube ich, der effizienteste Weg, um die Berechnung der längsten gemeinsamen Präfix im Allgemeinen ist ein suffix-Baum oder eine suffix-array (Laufzeit ist linear in der Länge des Präfixes nach der Vorverarbeitung).

    InformationsquelleAutor Fabian Steeg

  4. 0

    Haben Sie einige freie Speicher?

    Machen eine Struktur wie diese:

    typedef struct node {
  struct node* table[256];
  Port_type port;
} Node;
Node* root[256];

    Können Sie jetzt tun, lookups so:

    Node* table = root;
for (i=0; table != NULL; i++)
{
   node = table[address_byte[i]];
   table = node->table;
}
destination = node->port;
    Sieht aus wie ein radix-tree.

    InformationsquelleAutor AShelly

Schreibe einen Kommentar