PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup

Yi ZHANG; Lufeng QIAO; Huali WANG

doi:10.1587/transinf.2022EDP7088

PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route Lookup

Yi ZHANG, Lufeng QIAO, Huali WANG

Full Text Views

15

Cite this

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 (BP²O). The proposed BP²O 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

IP route lookup, longest prefix matching, Multibit-Trie, prefix partitioning, Ant Colony Optimization

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 (BP²O). The proposed BP²O 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 (BP²O). The proposed BP²O 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 (BP²O). The proposed BP²O 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 -