Feasibility of Longest Prefix Matching using Learned Index Structures
- 17 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 48 (4), 45-48
- https://doi.org/10.1145/3466826.3466842
Abstract
This paper revisits longest prefix matching in IP packet forwarding because an emerging data structure, learned index, is recently presented. A learned index uses machine learning to associate key-value pairs in a key-value store. The fundamental idea to apply a learned index to an FIB is to simplify the complex longest prefix matching operation to a nearest address search operation. The size of the proposed FIB is less than half of an existing trie-based FIB while it achieves the computation speed nearly equal to the trie-based FIB. Moreover, the computation speed of the proposal is independent of the length of IP prefixes, unlike trie-based FIBs.Keywords
This publication has 11 references indexed in Scilit:
- A Computational Approach to Packet ClassificationPublished by Association for Computing Machinery (ACM) ,2020
- The Case for Learned Index StructuresPublished by Association for Computing Machinery (ACM) ,2018
- PoptrieACM SIGCOMM Computer Communication Review, 2015
- DXRACM SIGCOMM Computer Communication Review, 2012
- Longest prefix matching using bloom filtersIEEE/ACM Transactions on Networking, 2006
- Fast updating algorithms for TCAMIEEE Micro, 2001
- IP-address lookup using LC-triesIEEE Journal on Selected Areas in Communications, 1999
- A 50-Gb/s IP routerIEEE/ACM Transactions on Networking, 1998
- Small forwarding tables for fast routing lookupsACM SIGCOMM Computer Communication Review, 1997
- PATRICIA—Practical Algorithm To Retrieve Information Coded in AlphanumericJournal of the ACM, 1968