research-article

Guarantee IP lookup performance with FIB explosion

Authors:

Laurent MathyAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 44, Issue 4

Pages 39 - 50

https://doi.org/10.1145/2740070.2626297

Published: 17 August 2014 Publication History

Abstract

The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both requirements at the same time. In this paper, we first propose SAIL, a Splitting Approach to IP Lookup. One splitting is along the dimension of the lookup process, namely finding the prefix length and finding the next hop, and another splitting is along the dimension of prefix length, namely IP lookup on prefixes of length less than or equal to 24 and IP lookup on prefixes of length longer than 24. Second, we propose a suite of algorithms for IP lookup based on our SAIL framework. Third, we implemented our algorithms on four platforms: CPU, FPGA, GPU, and many-core. We conducted extensive experiments to evaluate our algorithms using real FIBs and real traffic from a major ISP in China. Experimental results show that our SAIL algorithms are several times or even two orders of magnitude faster than well known IP lookup algorithms.

References

[1]

FPGA data sheet {on line}. Available: http://www.xilinx.com.

[2]

Quagga routing suite {on line}. Available: http://www.nongnu.org/quagga/.

[3]

RIPE network coordination centre {on line}. Available: http://www.ripe.net.

[4]

SAIL webpage. http://fi.ict.ac.cn/firg.php?n=PublicationsAmpTalks. OpenSource.

[5]

Tilera datasheet {on line}. Available: http://www.tilera.com/sites/default/files/productbriefs/TILE-Gx8036PB033-02web.pdf.

[6]

K. Adam and M. Michael. Less hashing, same performance: Building a better bloom filter. In Algorithms--ESA 2006, pages 456--467. Springer, 2006.

Digital Library

[7]

P. Derek, L. Ziyan, and P. Hang. IP address lookup using bit-shuffled trie. IEEE Computer Communications, 2014.

[8]

S. Devavrat and G. Pankaj. Fast incremental updates on ternary-cams for routing lookups and packet classification. In Proc. Hot Interconnects, 2000.

[9]

W. Feng and H. Mounir. Matching the speed gap between sram and dram. In Proc. IEEE HSPR, pages 104--109, 2008.

[10]

B. Florin, T. Dean, R. Grigore, and S. Sumeet. A tree based router search engine architecture with single port memories. In Proc. IEEE ISCA, 2005.

Digital Library

[11]

Z. Francis, N. Girija, and B. Anindya. Coolcams: Power-efficient tcams for forwarding engines. In Proc. IEEE INFOCOM, pages 42--52, 2003.

[12]

R. Gabor, T. Janos, A. Korosi, A. Majdan, and Z. Heszberger. Compressing IP forwarding tables: Towards entropy bounds and beyond. In Proc. ACM SIGCOMM, 2013.

Digital Library

[13]

P. Gupta, S. Lin, and N. McKeown. Routing lookups in hardware at memory access speeds. In Proc. IEEE INFOCOM, pages 1240--1247, 1998.

[14]

F. Hamid, Z. M. Saheb, and S. Masoud. A novel reconfigurable hardware architecture for IP address lookup. In Proc. ACM/IEEE ANCS, pages 81--90, 2005.

Digital Library

[15]

S. Haoyu, K. Murali, H. Fang, and L. TV. Scalable IP lookups using shape graphs. In Proc. ACM/IEEE ICNP, pages 73--82, 2009.

Digital Library

[16]

L. Hoang, J. Weirong, and P. V. K. A sram-based architecture for trie-based IP lookup using fpga. In Proc. IEEE FCCM, pages 33--42, 2008.

Digital Library

[17]

L. Hyesook, Y. Changhoon, and S. Earl. Priority tries for IP address lookup. IEEE Transactions on Computers, 59(6):784--794, 2010.

Digital Library

[18]

F. Jing and R. Jennifer. Efficient IP-address lookup with a shared forwarding table for multiple virtual routers. In Proc. ACM CoNEXT. ACM, 2008.

Digital Library

[19]

Z. Kai, H. Chengchen, L. Hongbin, and L. Bin. A tcam-based distributed parallel IP lookup scheme and performance analysis. IEEE/ACM Transactions on Networking, 14(4):863--875, 2006.

Digital Library

[20]

S. Keith. A tree-based packet routing table for berkeley unix. In USENIX Winter, pages 93--99, 1991.

[21]

L. Layong, X. Gaogang, S. Kave, U. Steve, M. Laurent, and X. Yingke. A trie merging approach with incremental updates for virtual routers. In Proc. IEEE INFOCOM, pages 1222--1230, 2013.

[22]

H. Lim, K. Lim, N. Lee, and K.-H. Park. On adding bloom filters to longest prefix matching algorithms. IEEE Transactions on Computers (TC), 63(2):411--423, 2014.

Digital Library

[23]

M. Mahmoud and M. Massato. A new hardware algorithm for fast IP routing targeting programmable routers. In Network control and engineering for Qos, security and mobility II, pages 164--179. Springer, 2003.

Digital Library

[24]

W. Marcel, V. George, T. Jon, and P. Bernhard. Scalable high speed IP routing lookups. In Proc. ACM SIGCOMM, 1997.

Digital Library

[25]

Z. Marko, R. Luigi, and M. Miljenko. Dxr: towards a billion routing lookups per second in software. ACM SIGCOMM Computer Communication Review, 42(5):29--36, 2012.

Digital Library

[26]

B. Masanori and C. H. Jonathan. Flashtrie: hash-based prefix-compressed trie for IP route lookup beyond 100gbps. In Proc. IEEE INFOCOM, 2010.

Digital Library

[27]

R. Miguel, B. Ernst, and D. Walid. Survey and taxonomy of IP address lookup algorithms. Network, IEEE, 15(2), 2001.

Digital Library

[28]

D. Mikael, B. Andrej, C. Svante, and P. Stephen. Small forwarding tables for fast routing lookups. In Proc. ACM SIGCOMM, pages 3--14, 1997.

Digital Library

[29]

A. Mohammad, N. Mehrdad, P. Rina, and S. Samar. A tcam-based parallel architecture for high-speed packet forwarding. IEEE Transactions on Computers, 56(1):58--72, 2007.

Digital Library

[30]

NVIDIA Corporation. NVIDIA CUDA C Best Practices Guide, Version 5.0, Oct. 2012.

[31]

C. Pierluigi, D. Leandro, and G. Roberto. IP address lookupmade fast and simple. In Algorithms-ESA'99, pages 65--76. Springer, 1999.

Digital Library

[32]

W. Priyank, S. Subhash, and V. George. Multiway range trees: scalable IP lookup with fast updates. Computer Networks, 44(3):289--303, 2004.

Digital Library

[33]

S. Rama, F. Natsuhiko, A. Srinivas, and S. Arun. Scalable, memory efficient, high-speed IP lookup algorithms. IEEE/ACM Transactions on Networking, 13(4):802--812, 2005.

Digital Library

[34]

P. Rina and S. Samar. Reducing tcam power consumption and increasing throughput. In Proc. High Performance Interconnects, pages 107--112, 2002.

Digital Library

[35]

H. Sangjin, J. Keon, P. KyoungSoo, and M. Sue. Packetshader: a gpu-accelerated software router. In Proc. ACM SIGCOMM, pages 195--206, 2010.

Digital Library

[36]

D. Sarang, K. Praveen, and T. D. E. Longest prefix matching using bloom filters. In Proc. ACM SIGCOMM, pages 201--212, 2003.

Digital Library

[37]

H. Song, M. Kodialam, F. Hao, and T. Lakshman. Building scalable virtual routers with trie braiding. In Proc. IEEE INFOCOM, 2010.

Digital Library

[38]

N. Stefan and K. Gunnar. IP-address lookup using lc-tries. Selected Areas in Communications, IEEE Journal on, 17(6):1083--1092, 1999.

Digital Library

[39]

S. Venkatachary and V. George. Fast address lookups using controlled prefix expansion. ACM TOCS, 17(1):1--40, 1999.

Digital Library

[40]

E. Will, V. George, and D. Zubin. Tree bitmap: hardware/software IP lookups with incremental updates. ACM SIGCOMM Computer Communication Review, 34(2):97--122, 2004.

Digital Library

[41]

T. Yang, Z. Mi, R. Duan, X. Guo, J. Lu, S. Zhang, X. Sun, and B. Liu. An ultra-fast universal incremental update algorithm for trie-based routing lookup. In Proc. ACM/IEEE ICNP, 2012.

Digital Library

[42]

J. Zhao, X. Zhang, X. Wang, and X. Xue. Achieving O(1) IP lookup on gpu-based software routers. In ACM SIGCOMM Computer Communication Review, volume 40, pages 429--430. ACM, 2010.

Digital Library

Cited By

(2022)ReferencesNetwork Algorithmics10.1016/B978-0-12-809927-8.00028-2(541-557)Online publication date: 2022
https://doi.org/10.1016/B978-0-12-809927-8.00028-2
Varghese GXu J(2022)Prefix-match lookupsNetwork Algorithmics10.1016/B978-0-12-809927-8.00018-X(249-294)Online publication date: 2022
https://doi.org/10.1016/B978-0-12-809927-8.00018-X
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
Show More Cited By

Index Terms

Guarantee IP lookup performance with FIB explosion
1. Networks
  1. Network components
    1. Intermediate nodes
      1. Routers
  2. Network types

Recommendations

Guarantee IP lookup performance with FIB explosion
SIGCOMM '14: Proceedings of the 2014 ACM conference on SIGCOMM

The Forwarding Information Base (FIB) of backbone routers has been rapidly growing in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time and on-chip memory usage. However, no prior IP lookup algorithm achieves both ...
Constant IP Lookup With FIB Explosion

With the fast development of Internet, the forwarding tables in backbone routers have been growing fast in size. An ideal IP lookup algorithm should achieve constant, yet small, IP lookup time, and on-chip memory usage. However, no prior IP lookup ...
Achieving O(1) IP lookup on GPU-based software routers
SIGCOMM '10: Proceedings of the ACM SIGCOMM 2010 conference

IP address lookup is a challenging problem due to the increasing routing table size, and higher line rate. This paper investigates a new way to build an efficient IP lookup scheme using graphics processor units(GPU). Our contribution here is to design a ...

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 44, Issue 4

SIGCOMM'14

October 2014

672 pages

ISSN:0146-4833

DOI:10.1145/2740070

Editors:
Konstantina Papagiannaki
Telefonica Research, Barcelona, Spain
,
Katerina Argyraki
EPFL, Switzerland
,
Hitesh Ballani
Microsoft Research Cambridge, UK
,
Fabián Bustamante
Northwestern University, USA
,
Joseph Camp
SMU, USA
,
Augustin Chaintreau
Columbia University, USA
,
Phillipa Gill
Stony Brook University, USA
,
Marco Mellia
Politecnico di Torino, Italy
,
Bhaskaran Raman
IIT Bombay, India
,
Joel Sommers
Colgate University, USA
,
Aline Carneiro Viana
INRIA, France

Issue’s Table of Contents

SIGCOMM '14: Proceedings of the 2014 ACM conference on SIGCOMM
August 2014
662 pages
ISBN:9781450328364
DOI:10.1145/2619239
General Chairs:
Fabián E. Bustamante
Northwestern University, USA
,
Y. Charlie Hu
Purdue University, USA
,
Program Chairs:
Arvind Krishnamurthy
University of Washington, USA
,
Sylvia Ratnasamy
University of California, Berkeley, USA

Copyright © 2014 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: 17 August 2014

Published in SIGCOMM-CCR Volume 44, Issue 4

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

74
Total Citations
View Citations
2,608
Total Downloads

Downloads (Last 12 months)177
Downloads (Last 6 weeks)32

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2022)ReferencesNetwork Algorithmics10.1016/B978-0-12-809927-8.00028-2(541-557)Online publication date: 2022
https://doi.org/10.1016/B978-0-12-809927-8.00028-2
Varghese GXu J(2022)Prefix-match lookupsNetwork Algorithmics10.1016/B978-0-12-809927-8.00018-X(249-294)Online publication date: 2022
https://doi.org/10.1016/B978-0-12-809927-8.00018-X
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
Tian XZhao H(2020)Constant-Weight Group Coded Bloom Filter for Multiple-Set Membership QueriesThe 10th International Conference on Computer Engineering and Networks10.1007/978-981-15-8462-6_83(723-730)Online publication date: 6-Oct-2020
https://doi.org/10.1007/978-981-15-8462-6_83
LI JHAN BSUN ZLI TWANG X(2019)Exploiting Packet-Level Parallelism of Packet Parsing for FPGA-Based SwitchesIEICE Transactions on Communications10.1587/transcom.2018EBP3333E102.B:9(1862-1874)Online publication date: 1-Sep-2019
https://doi.org/10.1587/transcom.2018EBP3333
Yang TGao SSun ZWang YShen YLi X(2019)Diamond Sketch: Accurate Per-flow Measurement for Big Streaming DataIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2019.292377230:12(2650-2662)Online publication date: 1-Dec-2019
https://doi.org/10.1109/TPDS.2019.2923772
Ghasemi CYousefi HShin KZhang B(2019)On the Granularity of Trie-Based Data Structures for Name Lookups and UpdatesIEEE/ACM Transactions on Networking10.1109/TNET.2019.290148727:2(777-789)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1109/TNET.2019.2901487
Asai H(2019)Deep Pipelining: Efficient Pipelining of Network Function Chains with Coroutines2019 IEEE Conference on Network Softwarization (NetSoft)10.1109/NETSOFT.2019.8806673(324-332)Online publication date: Jun-2019
https://doi.org/10.1109/NETSOFT.2019.8806673
Islam MKhan J(2019)SAIL Based FIB Lookup in a Programmable Pipeline Based Linux Router2019 IEEE 20th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2019.8808129(1-8)Online publication date: May-2019
https://doi.org/10.1109/HPSR.2019.8808129
Liu LHu JYan YGao SYang TLi X(2019)Longest Prefix Matching with Pruning2019 IEEE 20th International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR.2019.8808125(1-6)Online publication date: May-2019
https://doi.org/10.1109/HPSR.2019.8808125
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