Quelle est la meilleure façon de mettre en œuvre correspondant pour ipv6 le plus ancien préfixe?

Question

Un magasin de routeur IPv6 un certain nombre de routes que les premiers n bits de l'adresse. En 2000, les chercheurs ont constaté que 14 longueurs de préfixe distinctes en 1500 routes ipv6. Les paquets entrants sont acheminés vers différents ports de sortie en fonction du match le plus long préfixe, donc si les 8 premiers bits de paquet x correspondent à une 8 route peu, mais les premiers 48 bits du même paquet correspondent à une route 48 bits alors le routeur doit choisir la itinéraire 48 bits.

Mon routeur est en train de traiter autant de paquets que la vitesse de recherche de mémoire dans la table de routage est un facteur limitant. Qu'est-ce qu'un bon algorithme pour trouver le plus long préfixe correspondant dans ma table de routage?

Answer 1

Utilisez un ou Trie radix-tree pour stocker les "préfixes standard". Un arbre suffixe / tableau est un inutile sur-tuer; ils sont utilisés pour trouver des correspondances entre infixes (en utilisant le fait que tout infix est un préfixe d'un suffixe, et si vous voulez trouver une correspondance entre plusieurs chaînes, les concaténer les uns aux autres), et non juste entre les préfixes.

Answer 2

J'ai trouvé un frais sur ce sujet appelé le plus long Prefix en utilisant Bloom filtres assortis .

Résumé: Nous présentons le premier algorithme que nous sommes conscients d'employer des filtres Bloom pour la correspondance la plus longue Prefix (LPM). L'algorithme effectue des requêtes parallèles sur les filtres Bloom, une structure de données efficace pour les requêtes d'adhésion, afin de déterminer l'appartenance de préfixe d'adresse dans des ensembles de préfixes classés par longueur de préfixe. Nous montrons que l'utilisation de cet algorithme pour LookUps de routage IP (Internet Protocol) des résultats dans un moteur de recherche offrant de meilleures performances et l'évolutivité que les approches fondées sur TCAM.

Leur idée de base est d'utiliser des filtres bloom stockés dans la SRAM intégrée d'un processeur (rapide) pour guider la table de lookups hachage préfixe dans la mémoire plus lente mais plus abondante. Pour le cas IPv4, ils affiner leur algorithme pour tenir compte du fait que la plupart des préfixes de tables de routage sont 24 bits. Pour IPv6 ils ont trouvé seulement 14 longueurs de préfixe unique en 1550 entrées BGP.

Answer 3

Je crois que la façon la plus efficace de calculer le plus long préfixe commun en général est un ou (exécution est linéaire à la longueur du préfixe après pré-traitement).

Answer 4

Avez-vous une mémoire de secours?

Faire une structure comme ceci:

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

Maintenant, vous pouvez faire des recherches comme ceci:

Node* table = root;
for (i=0; table != NULL; i++)
{
   node = table[address_byte[i]];
   table = node->table;
}
destination = node->port;