IEICE TRANSACTIONS on Information
PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E106-D No.4 pp.509-522
- Publication Date
- 2023/04/01
- Publicized
- 2023/01/13
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2022EDP7088
- Type of Manuscript
- PAPER
- Category
- Computer System
Authors
Yi ZHANG
Army Engineering University of PLA
Lufeng QIAO
Army Engineering University of PLA
Huali WANG
Army Engineering University of PLA
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
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
Copy
@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},}
Copy
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 -
English
