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

research-article

Efficient FIB caching using minimal non-overlapping prefixes

Authors:

Syed Obaid Amin,

Lan WangAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 43, Issue 1

Pages 14 - 21

https://doi.org/10.1145/2427036.2427039

Published: 09 January 2013 Publication History

Abstract

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 cards is much more expensive than regular memory modules and it is very costly to increase this memory capacity frequently for all the routers in an ISP. One potential solution is to install only the most popular FIB entries into the fast memory (i.e., a FIB cache), while storing the complete FIB in slow memory. In this paper, we propose an effective FIB caching scheme that achieves a considerably higher hit ratio than previous approaches while preventing the cache-hiding problem. Our experimental results show that with only 20K prefixes in the cache (5.36% of the actual FIB size), the hit ratio of our scheme is higher than 99.95%. Our scheme can also handle cache misses, cache replacement and routing updates efficiently.

References

[1]

Advanced Network Technology Center at University of Oregon. The RouteViews project. http://www.routeviews.org/.

[2]

M. J. Akhbarizadeh and M. Nourani. Efficient prefix cache for network processors. In Proceedings of the High Performance Interconnects, 2004.

Digital Library

[3]

R. Draves, C. King, S. Venkatachary, and B. D. Zill. Constructing Optimal IP Routing Tables. In Proc. IEEE INFOCOM, 1999.

[4]

V. Fuller. Scaling Issues with Routing+Multihoming. http://www.vaf.net/~vaf/apricot-plenary.pdf, 1996.

[5]

K. Gadkari, D. Massey, and C. Papadopoulos. Dynamics of prefix usage at an edge router. In Proceedings of the 12th international conference on Passive and active measurement, PAM'11, 2011.

Digital Library

[6]

C. Kim, M. Caesar, A. Gerber, and J. Rexford. Revisiting route caching: The world should be flat. In Proceedings of the 10th International Conference on Passive and Active Network Measurement, PAM '09, 2009.

Digital Library

[7]

T. Li. Preliminary Recommendation for a Routing Architecture. RFC 6115, 2011.

[8]

H. Liu. Routing prefix caching in network processor design. In in Tenth International Conference on Computer Communications and Networks, 2001.

[9]

Y. Liu, X. Zhao, K. Nam, L. Wang, and B. Zhang. Incremental forwarding table aggregation. In Proc. IEEE Globecom, 2010.

[10]

D. Meyer, L. Zhang, and K. Fall. Report from the IAB Workshop on Routing and Addressing. RFC 4984, 2007.

[11]

D. R. Morrison. PATRICIA-practical algorithm to retrieve information coded in alphanumeric. J. ACM, 15(4):514--534, Oct. 1968.

Digital Library

[12]

J. Rexford, J. Wang, Z. Xiao, and Y. Zhang. BGP routing stability of popular destinations. In Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, IMW'02, 2002.

Digital Library

[13]

G. Trotter. Terminology for Forwarding Information Base (FIB) based Router Performance. RFC 3222, 2001.

Digital Library

[14]

Z. A. Uzmi, M. Nebel, A. Tariq, S. Jawad, R. Chen, A. Shaikh, J. Wang, and P. Francis. SMALTA: practical and near-optimal FIB aggregation. In Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies, CoNEXT '11, 2011.

Digital Library

[15]

W. Zhang, J. Bi, J. Wu, and B. Zhang. Catching popular prefixes at as border routers with a prediction based method. Comput. Netw., 56(4):1486--1502, Mar. 2012.

Digital Library

[16]

X. Zhao, Y. Liu, L. Wang, and B. Zhang. On the Aggregatability of Router Forwarding Tables. In Proc. IEEE INFOCOM, 2010.

Digital Library

[17]

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

Digital Library

Cited By

Ma ZLi TXu ZFonseca NZhu Z(2024)SFCache: Hybrid NF Synthesization in Runtime With Rule-Caching in Programmable SwitchesIEEE Transactions on Network and Service Management10.1109/TNSM.2024.339014021:4(4613-4624)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3390140
Rottenstreich OKulik AJoshi ARexford JRetvari GMenasche D(2022)Data Plane Cooperative Caching With DependenciesIEEE Transactions on Network and Service Management10.1109/TNSM.2021.313227519:3(2092-2106)Online publication date: Sep-2022
https://doi.org/10.1109/TNSM.2021.3132275
Wang WWang JYang XYang L(2022)Cache Dependent Rules With Size-Limited Flow Table in Software-Defined Networking2022 IEEE Smartworld, Ubiquitous Intelligence & Computing, Scalable Computing & Communications, Digital Twin, Privacy Computing, Metaverse, Autonomous & Trusted Vehicles (SmartWorld/UIC/ScalCom/DigitalTwin/PriComp/Meta)10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356(1736-1741)Online publication date: Dec-2022
https://doi.org/10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356
Show More Cited By

Index Terms

Efficient FIB caching using minimal non-overlapping prefixes
1. Hardware
  1. Communication hardware, interfaces and storage
2. Networks

Recommendations

Boosting FIB Caching Performance with Aggregation
HPDC '20: Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing

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 ...
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. 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 SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 43, Issue 1

January 2013

55 pages

ISSN:0146-4833

DOI:10.1145/2427036

Issue’s Table of Contents

Copyright © 2013 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 January 2013

Published in SIGCOMM-CCR Volume 43, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
179
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ma ZLi TXu ZFonseca NZhu Z(2024)SFCache: Hybrid NF Synthesization in Runtime With Rule-Caching in Programmable SwitchesIEEE Transactions on Network and Service Management10.1109/TNSM.2024.339014021:4(4613-4624)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3390140
Rottenstreich OKulik AJoshi ARexford JRetvari GMenasche D(2022)Data Plane Cooperative Caching With DependenciesIEEE Transactions on Network and Service Management10.1109/TNSM.2021.313227519:3(2092-2106)Online publication date: Sep-2022
https://doi.org/10.1109/TNSM.2021.3132275
Wang WWang JYang XYang L(2022)Cache Dependent Rules With Size-Limited Flow Table in Software-Defined Networking2022 IEEE Smartworld, Ubiquitous Intelligence & Computing, Scalable Computing & Communications, Digital Twin, Privacy Computing, Metaverse, Autonomous & Trusted Vehicles (SmartWorld/UIC/ScalCom/DigitalTwin/PriComp/Meta)10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356(1736-1741)Online publication date: Dec-2022
https://doi.org/10.1109/SmartWorld-UIC-ATC-ScalCom-DigitalTwin-PriComp-Metaverse56740.2022.00356
Gao PXu YChao H(2021)OVS-CAB: Efficient rule-caching for Open vSwitch hardware offloadingComputer Networks10.1016/j.comnet.2021.107844188(107844)Online publication date: Apr-2021
https://doi.org/10.1016/j.comnet.2021.107844
Dey PYuksel M(2020)An Economic Analysis of Cloud-Assisted Routing for Wider Area SDNIEEE Transactions on Network and Service Management10.1109/TNSM.2019.294703017:1(445-458)Online publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1109/TNSM.2019.2947030
Rottenstreich OKulik AJoshi ARexford JRetvari GMenasche D(2020)Cooperative Rule Caching for SDN Switches2020 IEEE 9th International Conference on Cloud Networking (CloudNet)10.1109/CloudNet51028.2020.9335795(1-7)Online publication date: 9-Nov-2020
https://doi.org/10.1109/CloudNet51028.2020.9335795
Yang SBai LCui LMing ZWu YYu SShen HPan Y(2020)An efficient pipeline processing scheme for programming Protocol-independent Packet ProcessorsJournal of Network and Computer Applications10.1016/j.jnca.2020.102806(102806)Online publication date: Sep-2020
https://doi.org/10.1016/j.jnca.2020.102806
Liu YGrigoryan GLi JSun GTauber T(2020)VeriTableComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2019.106981168:COnline publication date: 26-Feb-2020
https://dl.acm.org/doi/10.1016/j.comnet.2019.106981
Csikor LDivakaran DKang MKőrösi ASonkoly BHaja DPezaros DSchmid SRétvári GMohaisen AZhang Z(2019)Tuple space explosionProceedings of the 15th International Conference on Emerging Networking Experiments And Technologies10.1145/3359989.3365431(292-304)Online publication date: 3-Dec-2019
https://dl.acm.org/doi/10.1145/3359989.3365431
Ascigil ORene SPsaras IPavlou GYeh EOran D(2018)On-demand routing for scalable name-based forwardingProceedings of the 5th ACM Conference on Information-Centric Networking10.1145/3267955.3267968(67-76)Online publication date: 21-Sep-2018
https://dl.acm.org/doi/10.1145/3267955.3267968
Show More Cited By

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