More Web Proxy on the site http://driver.im/

research-article

Boosting FIB Caching Performance with Aggregation

Authors:

Garegin Grigoryan,

Minseok KwonAuthors Info & Claims

HPDC '20: Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing

Pages 221 - 232

https://doi.org/10.1145/3369583.3392682

Published: 23 June 2020 Publication History

Abstract

In the era of high-performance cloud computations, networks need to ensure fast packet forwarding. This task is carried by TCAM forwarding chips that perform line-rate Longest Prefix Matches in a Forwarding Information Base (FIB). However, with the increasing number of prefixes in IPv4 and IPv6 routing tables the price of TCAM increases as well. In this work, we present a novel FIB compression technique by adding an aggregation layer into a FIB caching architecture. In Combined FIB Caching and Aggregation (CFCA), cache-hit ratio is maximized up to 99.94% with only 2.50% entries of the FIB, while the churn in TCAM is reduced by more than 40% compared to low-churn FIB aggregation techniques.

Supplementary Material

MP4 File (3369583.3392682.mp4)

In the era of high-performance cloud computations, networks need to ensure fast packet forwarding. This task is carried by TCAM forwarding chips that perform line-rate Longest Prefix Matches in a Forwarding Information Base (FIB). However, with the increasing number of prefixes in IPv4 and IPv6 routing tables the price of TCAM increases as well. In this work, we present a novel FIB compression technique by adding an aggregation layer into a FIB caching architecture. In Combined FIB Caching and Aggregation (CFCA), cache-hit ratio is maximized up to 99.94% with only 2.50% entries of the FIB, while the churn in TCAM is reduced by more than 40% compared to low-churn FIB aggregation techniques.

Download
124.29 MB

References

[1]

2019. BGP routing table analysis reports. https://bgp.potaroo.net/.

[2]

2019. P4 Language Consortium. https://p4.org/

[3]

2019. Portable Switch Architecture (PSA). https://p4.org/p4-spec/docs/PSA.html

[4]

Advanced network technology center and University of Oregon. The RouteViews project. http://www.routeviews.org/. 2017.

[5]

Marcin Bienkowski, Jan Marcinkowski, Maciej Pacut, Stefan Schmid, and Aleksandra Spyra. 2017. Online tree caching. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, 329--338.

Digital Library

[6]

Marcin Bienkowski, Nadi Sarrar, Stefan Schmid, and Steve Uhlig. 2018. Online aggregation of the forwarding information base: accounting for locality and churn. IEEE/ACM Transactions on Networking, Vol. 26, 1 (2018), 591--604.

Digital Library

[7]

Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, and David Walker. 2014. P4: Programming protocol-independent packet processors. ACM SIGCOMM Computer Communication Review, Vol. 44, 3 (2014), 87--95.

Digital Library

[8]

Center for applied Internet data analysis. http://www.caida.org/home/. 2019.

[9]

Tzi-Cker Chiueh and Prashant Pradhan. 2000. Cache memory design for network processors. In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture. IEEE, 409--418.

[10]

Richard P Draves, Christopher King, Srinivasan Venkatachary, and Brian D Zill. 1999. Constructing optimal IP routing tables. In Proceedings of IEEE INFOCOM 1999, Vol. 1. IEEE, 88--97.

[11]

Kaustubh Gadkari, M Lawrence Weikum, Dan Massey, and Christos Papadopoulos. 2016. Pragmatic router FIB caching. Computer Communications, Vol. 84 (2016), 52--62.

Digital Library

[12]

Geoff Huston. BGP in 2019 -- the BGP table. https://blog.apnic.net/2020/01/14/bgp-in-2019-the-bgp-table/. 2020.

[13]

Kartik Gopalan and Tzi-cker Chiueh. 2002. Improving route lookup performance using network processor cache. In Proceedings of the 2002 ACM/IEEE Conference on Supercomputing. IEEE, 22--22.

Digital Library

[14]

Garegin Grigoryan and Yaoqing Liu. 2018. PFCA: a programmable fib caching architecture. In Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems. ACM, 97--103.

Digital Library

[15]

Garegin Grigoryan, Yaoqing Liu, Michael Leczinsky, and Jun Li. 2018. VeriTable: Fast Equivalence Verification of Multiple Large Forwarding Tables. In Proceedings of IEEE INFOCOM 2018. IEEE, 621--629.

[16]

Peng He, Wenyuan Zhang, Hongtao Guan, Kavé Salamatian, and Gaogang Xie. 2017. Partial order theory for fast tcam updates. IEEE/ACM Transactions on Networking, Vol. 26, 1 (2017), 217--230.

Digital Library

[17]

Raj Jain and Shawn Routhier. 1986. Packet trains--measurements and a new model for computer network traffic. IEEE Journal on Selected Areas inCommunications, Vol. 4, 6 (1986), 986--995.

Digital Library

[18]

Naga Katta, Omid Alipourfard, Jennifer Rexford, and David Walker. 2014. Infinite cacheflow in software-defined networks. Proceedings of the Third Workshop on Hot Topics in Software Defined Networking. ACM, 175--180.

Digital Library

[19]

Naga Katta, Omid Alipourfard, Jennifer Rexford, and David Walker. 2016. Cacheflow: Dependency-aware rule-caching for software-defined networks. In Proceedings of the Symposium on SDN Research. 1--12.

Digital Library

[20]

Changhoon Kim, Matthew Caesar, Alexandre Gerber, and Jennifer Rexford. 2009. Revisiting route caching: the world should be flat. In Proceedings of the International Conference on Passive and Active Network Measurement. Springer, 3--12.

[21]

Alex X Liu, Chad R Meiners, and Eric Torng. 2016. Packet classification using binary content addressable memory. IEEE/ACM Transactions on Networking, Vol. 24, 3 (2016), 1295--1307.

Digital Library

[22]

Yaoqing Liu and Garegin Grigoryan. 2018. Toward incremental FIB aggregation with quick selections (FAQS). In Proceedings of the 17th International Symposium on Network Computing and Applications. IEEE, 1--8.

[23]

Yaoqing Liu, Vince Lehman, and Lan Wang. 2015. Efficient FIB caching using minimal non-overlapping prefixes. Computer Networks, Vol. 83 (2015), 85--99.

Digital Library

[24]

Yaoqing Liu, Beichuan Zhang, and Lan Wang. 2013. FIFA: Fast incremental FIB aggregation. In Proceedings of IEEE INFOCOM 2013. IEEE, 1--9.

[25]

Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker, and Jonathan Turner. 2008. OpenFlow: enabling innovation in campus networks. ACM SIGCOMM Computer Communication Review, Vol. 38, 2 (2008), 69--74.

Digital Library

[26]

Xiaoqiao Meng, Zhiguo Xu, Beichuan Zhang, Geoff Huston, Songwu Lu, and Lixia Zhang. 2005. IPv4 address allocation and the BGP routing table evolution. ACM SIGCOMM Computer Communication Review, Vol. 35, 1 (2005), 71--80.

Digital Library

[27]

Mehrdad Moradi, Feng Qian, Qiang Xu, Z Morley Mao, Darrell Bethea, and Michael K Reiter. 2015. Caesar: High-speed and memory-efficient forwarding engine for future internet architecture. In Proceedings of the Symposium on Architectures for Networking and Communications Systems. IEEE, 171--182.

[28]

P. Lumbis, Y. Ramdoss, D. Miller. CAT 6500 and 7600 Series Routers and Switches TCAM Allocation Adjustment Procedures. https://www.cisco.com/c/en/us/support/docs/switches/catalyst-6500-series-switches/117712-problemsolution-cat6500-00.html. 2014.

[29]

Ori Rottenstreich and János Tapolcai. 2016. Optimal rule caching and lossy compression for longest prefix matching. IEEE/ACM Transactions on Networking, Vol. 25, 2 (2016), 864--878.

Digital Library

[30]

Nadi Sarrar, Steve Uhlig, Anja Feldmann, Rob Sherwood, and Xin Huang. 2012. Leveraging Zipf's law for traffic offloading. ACM SIGCOMM Computer Communication Review, Vol. 42, 1 (2012), 16--22.

Digital Library

[31]

Vibhaalakshmi Sivaraman, Srinivas Narayana, Ori Rottenstreich, S Muthukrishnan, and Jennifer Rexford. 2017. Heavy-hitter detection entirely in the data plane. Proceedings of the Symposium on SDN Research. ACM, 164--176.

Digital Library

[32]

The P4 language consortium. Compiler for PSA. https://github.com/p4lang/behavioral-model/issues/873. 2020.

[33]

The P4 language consortium. P4_1_6 language specification. https://p4lang.github.io/p4-spec/docs/P4--16-v1.0.0-spec.pdf. 2020.

[34]

The P4 language consortium. The BMv2 simple switch target. https://github.com/p4lang/behavioral-model/blob/master/docs/simple_switch.md. 2020.

[35]

Zahid Ullah, Manish K Jaiswal, and Ray CC Cheung. 2015. Z-TCAM: an SRAM-based architecture for TCAM. IEEE Transactions on Very Large Scale Integration Systems, Vol. 23, 2 (2015), 402--406.

Digital Library

[36]

Jun Xu, Mukesh Singhal, and Joanne Degroat. 2000. A novel cache architecture to support layer-four packet classification at memory access speeds. In Proceedings of IEEE INFOCOM 2000, Vol. 3. IEEE, 1445--1454.

[37]

Xiaoliang Zhao, Dante J Pacella, and Jason Schiller. 2010. Routing scalability: an operator's view. IEEE Journal on Selected Areas in Communications, Vol. 28, 8 (2010), 1262--1270.

Digital Library

Cited By

Gozlan IAvin CEinziger GScalosub G(2023)Go-to-Controller is Better: Efficient and Optimal LPM Caching with SplicingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35794417:1(1-33)Online publication date: 2-Mar-2023
https://doi.org/10.1145/3579441
Kim JKo MShin MKim J(2020)A Novel Prefix Cache with Two-Level Bloom Filters in IP Address LookupApplied Sciences10.3390/app1020719810:20(7198)Online publication date: 15-Oct-2020
https://doi.org/10.3390/app10207198

Index Terms

Boosting FIB Caching Performance with Aggregation
1. Networks
  1. Network architectures

Recommendations

PFCA: a programmable FIB caching architecture
ANCS '18: Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems

Ternary Content-Addressable Memory (TCAM) chips are used to store Forwarding Information Bases (FIB) in modern routers. TCAM provides next hop lookup for IP packets at the line-rate. However, TCAM is expensive and energy-consuming; in addition, the ...
Efficient FIB caching using minimal non-overlapping prefixes

The size of the global Routing Information Base (RIB) has been increasing at an alarming rate. This directly leads to the rapid growth of the global Forwarding Information Base (FIB) size, which raises serious concerns for ISPs as the FIB memory in line ...
Efficient FIB caching using minimal non-overlapping prefixes

The size of the global Routing Information Base (RIB) has been increasing at an alarming rate. As a direct effect, the size of the global Forwarding Information Base (FIB) has experienced rapid growth. This increase raises serious concerns for Internet ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HPDC '20: Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing

June 2020

246 pages

ISBN:9781450370523

DOI:10.1145/3369583

General Chairs:
Manish Parashar
Rutgers University, USA
,
Vladimir Vlassov
KTH Royal Institute of Technology, Stockholm, Sweden
,
Program Chairs:
David Irwin
University of Massachusetts Amherst, USA
,
Kathryn Mohror
Lawrence Livermore National Laboratory, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part 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 components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Arizona: University of Arizona
SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HPDC '20

Sponsor:

University of Arizona
SIGHPC
SIGARCH

HPDC '20: The 29th International Symposium on High-Performance Parallel and Distributed Computing

June 23 - 26, 2020

Stockholm, Sweden

Acceptance Rates

Overall Acceptance Rate 166 of 966 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
159
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gozlan IAvin CEinziger GScalosub G(2023)Go-to-Controller is Better: Efficient and Optimal LPM Caching with SplicingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35794417:1(1-33)Online publication date: 2-Mar-2023
https://doi.org/10.1145/3579441
Kim JKo MShin MKim J(2020)A Novel Prefix Cache with Two-Level Bloom Filters in IP Address LookupApplied Sciences10.3390/app1020719810:20(7198)Online publication date: 15-Oct-2020
https://doi.org/10.3390/app10207198

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 Table of Contents