research-article

Feasibility of Longest Prefix Matching using Learned Index Structures

Authors:

Shunsuke Higuchi,

Junji Takemasa,

Atsushi Tagami,

Toru HasegawaAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 48, Issue 4

Pages 45 - 48

https://doi.org/10.1145/3466826.3466842

Published: 19 May 2021 Publication History

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.

References

[1]

H. Asai and Y. Ohara. Poptrie: A compressed trie with population count for fast and scalable software ip routing table lookup. In Proceedings of ACM SIGCOMM, Aug. 2015.

Digital Library

[2]

CAIDA. https://www.caida.org/home/.

[3]

H. J. Chao and B. Liu. High performance switches and routers. John Wiley & Sons, 2006.

Digital Library

[4]

M. Degermark et al. Small forwarding tables for fast routing lookups. In Proceedings of ACM SIGCOMM, pages 3--14, Sept. 1997.

Digital Library

[5]

S. Dharmapurikar et al. Longest prefix matching using bloom filters. IEEE/ACM Transactions on Networking, 14:397--409, Apr. 2006.

Digital Library

[6]

T. Kraska et al. The case for learned index structures. In Proceedings of ACM SIGMOD, June 2018.

Digital Library

[7]

D. R. Morrison. PATRICIA-practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM, pages 514--534, Oct. 1968.

Digital Library

[8]

S. Nilsson and G. Karlsson. IP-address lookup using LC-tries. IEEE Journal on Selected Areas in Communications, 17(6):1083--1092, June 1999.

Digital Library

[9]

C. Partridge et al. A 50-Gb/s IP router. IEEE/ACM Transactions on Networking, 6(3):237--248, June 1998.

Digital Library

[10]

A. Rashelbach et al. A computational approach to packet classification. In Proceedings of ACM SIGCOMM, Aug. 2020.

Digital Library

[11]

D. Shah and P. Gupta. Fast updating algorithms for TCAM. IEEE Micro, 21:36--47, Jan./Feb. 2001.

Digital Library

[12]

Y. Ueno et al. Spider: Parallelizing longest prefix matching with optimization for SIMD instructions. In Proceedings of IEEE NetSoft, Aug. 2020.

[13]

University of Oregon Route Views Project. http://www.routeviews.org/routeviews/.

[14]

M. Zec et al. DXR: towards a billion routing lookups per second in software. ACM SIGCOMM Computer Communication Review, 42(5):29--36, Sept. 2012.

Digital Library

[15]

B. Zhang et al. FIB aggregation. Internet-Draft draft-zhang-fibaggregation-02, Internet Engineering Task Force, Oct. 2009. Work in Progress.

Cited By

Zhang SQi JYao XBrinkmann A(2024)Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid ConstructionProceedings of the ACM on Management of Data10.1145/36549482:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654948
Korikawa TOki E(2022)Memory Network Architecture for Packet Processing in Functions VirtualizationIEEE Transactions on Network and Service Management10.1109/TNSM.2022.315909119:3(3304-3322)Online publication date: Sep-2022
https://doi.org/10.1109/TNSM.2022.3159091
Cong PZhang YLiu BWang WXiong ZXu K(2022)A&B: AI and Block-Based TCAM Entries Replacement Scheme for RoutersIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.319135140:9(2643-2661)Online publication date: Sep-2022
https://doi.org/10.1109/JSAC.2022.3191351
Show More Cited By

Recommendations

Longest prefix matching using bloom filters

We introduce the first algorithm that we are aware of to employ Bloom filters for longest prefix matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address ...
Longest prefix matching using bloom filters
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

We introduce the first algorithm that we are aware of to employ Bloom filters for Longest Prefix Matching (LPM). The algorithm performs parallel queries on Bloom filters, an efficient data structure for membership queries, in order to determine address ...
Demonstration of 100 Gbps optical packet switching using header processor based on 48-bit longest prefix matching

Wire-rate packet processing and its energy saving for over 100 Gbps speed of line are major issues to be resolved in optical packet switching (OPS) networks. For that purpose, we newly develop a high-speed, deterministic-latency electronic header ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 48, Issue 4

March 2021

66 pages

ISSN:0163-5999

DOI:10.1145/3466826

Editor:
Zhenhua Liu
Stony Brook University

Issue’s Table of Contents

Copyright © 2021 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2021

Published in SIGMETRICS Volume 48, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)3

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang SQi JYao XBrinkmann A(2024)Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid ConstructionProceedings of the ACM on Management of Data10.1145/36549482:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654948
Korikawa TOki E(2022)Memory Network Architecture for Packet Processing in Functions VirtualizationIEEE Transactions on Network and Service Management10.1109/TNSM.2022.315909119:3(3304-3322)Online publication date: Sep-2022
https://doi.org/10.1109/TNSM.2022.3159091
Cong PZhang YLiu BWang WXiong ZXu K(2022)A&B: AI and Block-Based TCAM Entries Replacement Scheme for RoutersIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.319135140:9(2643-2661)Online publication date: Sep-2022
https://doi.org/10.1109/JSAC.2022.3191351
Liu YWang HZhou KLi CWu R(2022)A survey on AI for storageCCF Transactions on High Performance Computing10.1007/s42514-022-00101-34:3(233-264)Online publication date: 23-May-2022
https://doi.org/10.1007/s42514-022-00101-3
Kraska T(2021)Towards instance-optimized data systemsProceedings of the VLDB Endowment10.14778/3476311.347639214:12(3222-3232)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.14778/3476311.3476392
Higuchi SKoizumi YTakemasa JTagami AHasegawa T(2021)Learned FIB: Fast IP Forwarding without Longest Prefix Matching2021 IEEE 29th International Conference on Network Protocols (ICNP)10.1109/ICNP52444.2021.9651956(1-11)Online publication date: 1-Nov-2021
https://doi.org/10.1109/ICNP52444.2021.9651956

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents