La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup PR-Trie : un essai hybride avec un partitionnement de préfixe basé sur l'optimisation des colonies de fourmis pour une recherche de route IPv4/IPv6 économe en mémoire

Yi ZHANG, Lufeng QIAO, Huali WANG

  • Vues en texte intégral

    15

  • Citer

Résumé:

La recherche de protocole Internet (IP) économe en mémoire et à haute vitesse est essentielle pour obtenir un transfert de paquets à vitesse de liaison dans les routeurs IP. La croissance rapide du trafic Internet et le développement des technologies de liaison optique ont fait de la recherche IP un goulot d'étranglement majeur en termes de performances dans les routeurs principaux. Dans cet article, nous proposons une nouvelle architecture de recherche de route IP basée sur du matériel appelé Prefix-Route Trie (PR-Trie), qui prend en charge les adresses IPv4 et IPv6. Dans PR-Trie, nous développons une nouvelle structure appelée Overlapping Hybrid Trie (OHT) pour effectuer rapidement une correspondance de préfixe le plus long (LPM) basée sur Multibit-Trie (MT), et une requête de correspondance de niveau basée sur le hachage utilisée pour obtenir un seul accès à la mémoire hors puce par recherche. De plus, le PR-Trie proposé prend également en charge les mises à jour incrémentielles rapides. Étant donné que la complexité de la mémoire dans les schémas de recherche IP basés sur MT dépend de la solution de partitionnement de niveau et de la structure de données utilisée, nous développons un algorithme d'optimisation appelé Bitmap-based Prefix Partitioning Optimization (BP).2O). Le BP proposé2O est basé sur une recherche heuristique utilisant des algorithmes d’optimisation de colonies de fourmis (ACO) pour optimiser l’efficacité de la mémoire. Les résultats expérimentaux utilisant des tables de routage réelles prouvent que notre proposition a une efficacité de mémoire supérieure. Les analyses de performances théoriques montrent que PR-Trie surpasse les algorithmes de recherche IP classiques basés sur Trie.

Publication
IEICE TRANSACTIONS on Information Vol.E106-D No.4 pp.509-522
Date de publication
2023/04/01
Publicisé
2023/01/13
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2022EDP7088
Type de manuscrit
PAPER
Catégories
Système d'ordinateur

Auteurs

Yi ZHANG
  Army Engineering University of PLA
Lufeng QIAO
  Army Engineering University of PLA
Huali WANG
  Army Engineering University of PLA

Mots-clés

Table des matières