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
Carian Protokol Internet (IP) yang cekap memori dengan kelajuan tinggi adalah penting untuk mencapai pemajuan paket berkelajuan pautan dalam penghala IP. Pertumbuhan pesat trafik Internet dan perkembangan teknologi pautan optik telah menjadikan carian IP sebagai hambatan prestasi utama dalam penghala teras. Dalam makalah ini, kami mencadangkan seni bina carian laluan IP baharu berdasarkan perkakasan yang dipanggil Prefix-Route Trie (PR-Trie), yang menyokong kedua-dua alamat IPv4 dan IPv6. Dalam PR-Trie, kami membangunkan struktur baru yang dipanggil Overlapping Hybrid Trie (OHT) untuk melaksanakan padanan awalan-terpanjang (LPM) yang pantas berdasarkan Multibit-Trie (MT) dan pertanyaan padanan tahap berasaskan cincang yang digunakan untuk mencapai hanya satu akses memori luar cip setiap carian. Selain itu, PR-Trie yang dicadangkan juga menyokong kemas kini tambahan yang pantas. Memandangkan kerumitan memori dalam skim carian IP berasaskan MT bergantung pada penyelesaian pembahagian tahap dan struktur data yang digunakan, kami membangunkan algoritma pengoptimuman yang dipanggil Pengoptimuman Pembahagian Awalan berasaskan Bitmap (BP2O). BP yang dicadangkan2O adalah berdasarkan carian heuristik menggunakan algoritma Ant Colony Optimization (ACO) untuk mengoptimumkan kecekapan memori. Keputusan percubaan menggunakan jadual penghalaan kehidupan sebenar membuktikan bahawa cadangan kami mempunyai kecekapan memori yang unggul. Analisis prestasi teori menunjukkan bahawa PR-Trie mengatasi algoritma carian IP berasaskan Trie klasik.
Yi ZHANG
Army Engineering University of PLA
Lufeng QIAO
Army Engineering University of PLA
Huali WANG
Army Engineering University of PLA
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Yi ZHANG, Lufeng QIAO, Huali WANG, "PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 4, pp. 509-522, April 2023, doi: 10.1587/transinf.2022EDP7088.
Abstract: Memory-efficient Internet Protocol (IP) lookup with high speed is essential to achieve link-speed packet forwarding in IP routers. The rapid growth of Internet traffic and the development of optical link technologies have made IP lookup a major performance bottleneck in core routers. In this paper, we propose a new IP route lookup architecture based on hardware called Prefix-Route Trie (PR-Trie), which supports both IPv4 and IPv6 addresses. In PR-Trie, we develop a novel structure called Overlapping Hybrid Trie (OHT) to perform fast longest-prefix-matching (LPM) based on Multibit-Trie (MT), and a hash-based level matching query used to achieve only one off-chip memory access per lookup. In addition, the proposed PR-Trie also supports fast incremental updates. Since the memory complexity in MT-based IP lookup schemes depends on the level-partitioning solution and the data structure used, we develop an optimization algorithm called Bitmap-based Prefix Partitioning Optimization (BP2O). The proposed BP2O is based on a heuristic search using Ant Colony Optimization (ACO) algorithms to optimize memory efficiency. Experimental results using real-life routing tables prove that our proposal has superior memory efficiency. Theoretical performance analyses show that PR-Trie outperforms the classical Trie-based IP lookup algorithms.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7088/_p
Salinan
@ARTICLE{e106-d_4_509,
author={Yi ZHANG, Lufeng QIAO, Huali WANG, },
journal={IEICE TRANSACTIONS on Information},
title={PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup},
year={2023},
volume={E106-D},
number={4},
pages={509-522},
abstract={Memory-efficient Internet Protocol (IP) lookup with high speed is essential to achieve link-speed packet forwarding in IP routers. The rapid growth of Internet traffic and the development of optical link technologies have made IP lookup a major performance bottleneck in core routers. In this paper, we propose a new IP route lookup architecture based on hardware called Prefix-Route Trie (PR-Trie), which supports both IPv4 and IPv6 addresses. In PR-Trie, we develop a novel structure called Overlapping Hybrid Trie (OHT) to perform fast longest-prefix-matching (LPM) based on Multibit-Trie (MT), and a hash-based level matching query used to achieve only one off-chip memory access per lookup. In addition, the proposed PR-Trie also supports fast incremental updates. Since the memory complexity in MT-based IP lookup schemes depends on the level-partitioning solution and the data structure used, we develop an optimization algorithm called Bitmap-based Prefix Partitioning Optimization (BP2O). The proposed BP2O is based on a heuristic search using Ant Colony Optimization (ACO) algorithms to optimize memory efficiency. Experimental results using real-life routing tables prove that our proposal has superior memory efficiency. Theoretical performance analyses show that PR-Trie outperforms the classical Trie-based IP lookup algorithms.},
keywords={},
doi={10.1587/transinf.2022EDP7088},
ISSN={1745-1361},
month={April},}
Salinan
TY - JOUR
TI - PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup
T2 - IEICE TRANSACTIONS on Information
SP - 509
EP - 522
AU - Yi ZHANG
AU - Lufeng QIAO
AU - Huali WANG
PY - 2023
DO - 10.1587/transinf.2022EDP7088
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2023
AB - Memory-efficient Internet Protocol (IP) lookup with high speed is essential to achieve link-speed packet forwarding in IP routers. The rapid growth of Internet traffic and the development of optical link technologies have made IP lookup a major performance bottleneck in core routers. In this paper, we propose a new IP route lookup architecture based on hardware called Prefix-Route Trie (PR-Trie), which supports both IPv4 and IPv6 addresses. In PR-Trie, we develop a novel structure called Overlapping Hybrid Trie (OHT) to perform fast longest-prefix-matching (LPM) based on Multibit-Trie (MT), and a hash-based level matching query used to achieve only one off-chip memory access per lookup. In addition, the proposed PR-Trie also supports fast incremental updates. Since the memory complexity in MT-based IP lookup schemes depends on the level-partitioning solution and the data structure used, we develop an optimization algorithm called Bitmap-based Prefix Partitioning Optimization (BP2O). The proposed BP2O is based on a heuristic search using Ant Colony Optimization (ACO) algorithms to optimize memory efficiency. Experimental results using real-life routing tables prove that our proposal has superior memory efficiency. Theoretical performance analyses show that PR-Trie outperforms the classical Trie-based IP lookup algorithms.
ER -