research-article

TCAM-Based IP Address Lookup Using Longest Suffix Split

Authors:

Pi-Chung WangAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 26, Issue 2

Pages 976 - 989

https://doi.org/10.1109/TNET.2018.2815999

Published: 01 April 2018 Publication History

Abstract

Ternary content addressable memory TCAM plays an important role in modern routers due to its capability of performing fast IP address lookup. However, it is expensive, space limited, and a major source of power consumption in a router. In addition, because TCAM only reports the first matching entry, updating TCAM entries would be slow due to necessary entry reordering. In this paper, we present a trie-based algorithm, longest suffix split, to reduce the number of TCAM entries for IP address lookup. The algorithm divides route prefixes into two portions, subprefix and suffix. The route prefixes with the same subprefix and similar suffix portions can then be represented by one TCAM entry and one SRAM entry. Each SRAM entry stores one of two succinct data structures, depending on the threshold number of similar suffixes. The experimental results show that our scheme can reduce 50% to 95% TCAM entries for the original routing tables. Our scheme also supports incremental updates. Because the drawbacks of TCAM are related to the number of required entries, our scheme significantly improves the feasibility of TCAM-based IP address lookup. While network virtualization may store multiple forwarding information bases in a router, the number of supported virtual routers can be increased by our scheme.

References

[1]

T. B. Mishra and S. Sahni, "PETCAM--A power efficient TCAM architecture for forwarding tables," IEEE Trans. Comput., vol. 61, no. 1, pp. 3-17, Jan. 2012.

Digital Library

[2]

L. Luo et al., "Towards TCAM-based scalable virtual routers," in Proc. 8th ACM CoNEXT, 2012, pp. 73-84.

Digital Library

[3]

J. Baliga, R. Ayre, K. Hinton, and R. S. Tucker, "Photonic switching and the energy bottleneck," in Proc. Photon. Switching, Aug. 2007, pp. 125-126.

[4]

O. Rottenstreich, R. Cohen, D. Raz, and I. Keslassy, "Exact worst case TCAM rule expansion," IEEE Trans. Comput., vol. 62, no. 6, pp. 1127-1140, Jun. 2013.

Digital Library

[5]

K. Kunlap. (2006). Cooling Audit for Identifying Potential Cooling Problems in Data Centers. [Online]. Available: http://www.apcmedia.com/salestools/VAVR-5UGVCN/VAVR-5UGVCN_R3_EN.pdf

[6]

H. Liu, "Routing table compaction in ternary CAM," IEEE Micro, vol. 22, no. 1, pp. 58-64, Jan. 2002.

Digital Library

[7]

R. K. Brayton, A. L. Sangiovanni-Vincentelli, C. T. McMullen, and G. D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis. Boston, MA, USA: Springer, 1984.

Digital Library

[8]

V. C. Ravikumar and R. Mahapatra, "TCAM architecture for IP lookup using prefix properties," IEEE Micro, vol. 24, no. 2, pp. 60-69, Mar./Apr. 2004.

Digital Library

[9]

V. C. Ravikumar, R. N. Mahapatra, and L. N. Bhuyan, "EaseCAM: An energy and storage efficient TCAM-based router architecture for IP lookup," IEEE Trans. Comput., vol. 54, no. 5, pp. 521-533, May 2005.

Digital Library

[10]

T. Yang et al., "Virtual routing tables polymerization for lookup and update," in Proc. 20th IEEE ICNP, Oct./Nov. 2012, pp. 1-2.

Digital Library

[11]

Future Networks: Objectives and Design Goals, document Rec. Y.3001, ITU-T, 2011.

[12]

S. Su et al., "Energy-aware virtual network embedding," IEEE/ACM Trans. Netw., vol. 22, no. 5, pp. 1607-1620, Oct. 2014.

Digital Library

[13]

V. Eramo, E. Miucci, and M. Ammar, "Study of migration policies in energy-aware virtual router networks," IEEE Commun. Lett., vol. 18, no. 11, pp. 1919-1922, Nov. 2014.

[14]

X. Zhao, Y. Liu, L. Wang, and B. Zhang, "On the aggregatability of router forwarding tables," in Proc. IEEE INFOCOM, Mar. 2010, pp. 1-9.

Digital Library

[15]

R. P. Draves, C. King, S. Venkatachary, and B. D. Zill, "Constructing optimal IP routing tables," in Proc. IEEE INFOCOM, Mar. 1999, pp. 88-97.

[16]

T. Yang et al., "Approaching optimal compression with fast update for large scale routing tables," in Proc. IEEE 20th IWQoS, Jun. 2012, pp. 1-9.

Digital Library

[17]

M. Bienkowski, N. Sarrar, S. Schmid, and S. Uhlig, "Competitive FIB aggregation without update churn," in Proc. IEEE 34th ICDCS, Jun./Jul. 2014, pp. 607-616.

Digital Library

[18]

N. Sarrar, R. Wuttke, S. Schmid, M. Bienkowski, and S. Uhlig, "Leveraging locality for FIB aggregation," in Proc. IEEE GLOBECOM, Dec. 2014, pp. 1930-1935.

[19]

V. Srinivasan and G. Varghese, "Fast address lookups using controlled prefix expansion," ACM Trans. Comput. Syst., vol. 17, no. 1, pp. 1-40, 1999.

Digital Library

[20]

S. Nilsson and G. Karlsson, "IP-address lookup using LC-tries," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1083-1092, Jun. 1999.

Digital Library

[21]

P. Gupta, S. Lin, and N. McKeown, "Routing lookups in hardware at memory access speeds," in Proc. IEEE INFOCOM, Mar./Apr. 1998, pp. 1240-1247.

[22]

B. Lampson, V. Srinivasan, and G. Varghese, "IP lookups using multiway and multicolumn search," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 324-334, Jun. 1999.

Digital Library

[23]

M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, "Scalable high speed ip routing lookups," in Proc. ACM SIGCOMM, 1997, pp. 25-36.

Digital Library

[24]

N.-F. Huang and S.-M. Zhao, "A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers," IEEE J. Sel. Areas Commun., vol. 17, no. 6, pp. 1093-1104, Jun. 1999.

Digital Library

[25]

H. Lim and J. H. Mun, "NXG06-1: An efficient IP address lookup algorithm using a priority trie," in Proc. IEEE GLOBECOM, Nov./Dec. 2006, pp. 1-5.

[26]

M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, "Small forwarding tables for fast routing lookups," in Proc. ACM SIGCOMM, 1997, pp. 3-14.

Digital Library

[27]

K. Huang, G. Xie, Y. Li, and A. X. Liu, "Offset addressing approach to memory-efficient IP address lookup," in Proc. IEEE INFOCOM, Apr. 2011, pp. 306-310.

[28]

N.-F. Tzeng, "Routing table partitioning for speedy packet lookups in scalable routers," IEEE Trans. Parallel Distrib. Syst., vol. 17, no. 5, pp. 481-494, May 2006.

Digital Library

[29]

S. Dharmapurikar, P. Krishnamurthy, and D. E. Taylor, "Longest prefix matching using bloom filters," in Proc. ACM SIGCOMM, 2003, pp. 201-212.

Digital Library

[30]

F. Pong and N. F. Tzeng, "SUSE: Superior storage-efficiency for routing tables through prefix transformation and aggregation," IEEE/ACM Trans. Netw., vol. 18, no. 1, pp. 81-94, Feb. 2010.

Digital Library

[31]

M. Zec, L. Rizzo, and M. Mikuc, "DXR: Towards a billion routing lookups per second in software," ACM SIGCOMM Comput. Commun. Rev., vol. 42, no. 5, pp. 29-36, Sep. 2012.

Digital Library

[32]

T. Yang et al., "Guarantee IP lookup performance with FIB explosion," ACM SIGCOMM Comput. Commun. Rev., vol. 44, no. 4, pp. 39-50, Aug. 2014.

Digital Library

[33]

H. Yu, "A memory- and time-efficient on-chip TCAM minimizer for IP lookup," in Proc. DATE, Mar. 2010, pp. 926-931.

Digital Library

[34]

K. Zheng, C. Hu, H. Lu, and B. Liu, "A TCAM-based distributed parallel IP lookup scheme and performance analysis," IEEE/ACM Trans. Netw., vol. 14, no. 4, pp. 863-875, Aug. 2006.

Digital Library

[35]

T. Yang et al., "CLUE: Achieving fast update over compressed table for parallel lookup with reduced dynamic redundancy," in Proc. IEEE ICDCS, Jun. 2012, pp. 678-687.

Digital Library

[36]

W. Lu and S. Sahni, "Low-power TCAMs for very large forwarding tables," IEEE/ACM Trans. Netw., vol. 18, no. 3, pp. 948-959, Jun. 2010.

Digital Library

[37]

T. B. Mishra and S. Sahni, "DUOS-Simple dual TCAM architecture for routing tables with incremental update," in Proc. IEEE ISCC, Jun. 2010, pp. 503-508.

Digital Library

[38]

F. Zane, G. Narlikar, and A. Basu, "CoolCAMs: Power-efficient TCAMs for forwarding engines," in Proc. IEEE INFOCOM, Mar./Apr. 2003, pp. 42-52.

[39]

M. J. Akhbarizadeh, M. Nourani, R. Panigrahy, and S. Sharma, "A TCAM-based parallel architecture for high-speed packet forwarding," IEEE Trans. Comput., vol. 56, no. 1, pp. 58-72, Jan. 2007.

Digital Library

[40]

J. Fu and J. Rexford, "Efficient IP-address lookup with a shared forwarding table for multiple virtual routers," in Proc. ACM CoNEXT, 2008, Art. no. 21.

Digital Library

[41]

H. Song, M. Kodialam, F. Hao, and T. V. Lakshman, "Efficient trie braiding in scalable virtual routers," IEEE/ACM Trans. Netw., vol. 20, no. 5, pp. 1489-1500, Oct. 2012.

Digital Library

[42]

T. Ganegedara, W. Jiang, and V. K. Prasanna, "Multiroot: Towards memory-efficient router virtualization," in Proc. IEEE ICC, Jun. 2011, pp. 1-5.

[43]

Y. Zhou, Y. Li, D. Jin, L. Su, L. Zeng, and H. F. Rashvand, "Trie shifting scheme with depth adjusting for multiple virtual routers," IET Commun., vol. 6, no. 12, pp. 1716-1723, Aug. 2012.

[44]

H. Le, T. Ganegedara, and V. K. Prasanna, "Memory-efficient and scalable virtual routers using FPGA," in Proc. 19th ACM/SIGDA, 2011, pp. 257-266.

Digital Library

[45]

L. Luo et al., "A trie merging approach with incremental updates for virtual routers," in Proc. IEEE INFOCOM, Apr. 2013, pp. 1222-1230.

[46]

L. Luo, G. Xie, Y. Xie, L. Mathy, and K. Salamatian, "A hybrid hardware architecture for high-speed IP lookups and fast route updates," IEEE/ACM Trans. Netw., vol. 22, no. 3, pp. 957-969, Jun. 2014.

Digital Library

[47]

D. Shah and P. Gupta, "Fast updating algorithms for TCAM," IEEE Micro, vol. 21, no. 1, pp. 36-47, Jan. 2001.

Digital Library

[48]

Advanced Network Technology Center. (Dec. 2013). Route Views Project. [Online]. Available: http://www.routeviews.org/.

Cited By

Ashraf MHuang CKhalid SRana AAhmad MRaza U(2022)Dynamic Naming Scheme and Lookup Method Based on Trie for Vehicular Named Data NetworkWireless Communications & Mobile Computing10.1155/2022/65395322022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/6539532
Liu SLuo WZhou XJia YChen ZJiang S(2021)An Efficient Addressing Scheme for Flexible IP AddressProceedings of the 2021 2nd International Conference on Control, Robotics and Intelligent System10.1145/3483845.3483865(111-116)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3483845.3483865
Chowdhury ZResch SCilasun HZhao ZZabihi MSapatnekar SWang JKarpuzcu UChen YZhirnov VSasan ASavidis I(2021)CAMeleonProceedings of the 2021 Great Lakes Symposium on VLSI10.1145/3453688.3461507(57-63)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3453688.3461507
Show More Cited By

Recommendations

An On-Chip IP Address Lookup Algorithm

This paper proposes a new data compression algorithm to store the routing table in a tree structure using very little memory. This data structure is tailored to a hardware design reference model presented in this paper. By exploiting the low memory ...
High-speed IP address lookup using balanced multi-way trees

Rapid growth of the Internet traffic requires more bandwidth and high-speed packet processing in the Internet routers. As one of the major packet processing performed in routers, address lookup determines an output port using the destination IP address ...
A longest prefix first search tree for IP lookup

The IP lookup mechanism is a key issue, in the design of IP routers. IP lookup is an important action in a router, which finds the next hop of each incoming packet with a longest-prefix-match address in the routing table. This work places the routing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 26, Issue 2

April 2018

377 pages

ISSN:1063-6692

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 April 2018

Published in TON Volume 26, Issue 2

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
76
Total Downloads

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

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ashraf MHuang CKhalid SRana AAhmad MRaza U(2022)Dynamic Naming Scheme and Lookup Method Based on Trie for Vehicular Named Data NetworkWireless Communications & Mobile Computing10.1155/2022/65395322022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/6539532
Liu SLuo WZhou XJia YChen ZJiang S(2021)An Efficient Addressing Scheme for Flexible IP AddressProceedings of the 2021 2nd International Conference on Control, Robotics and Intelligent System10.1145/3483845.3483865(111-116)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3483845.3483865
Chowdhury ZResch SCilasun HZhao ZZabihi MSapatnekar SWang JKarpuzcu UChen YZhirnov VSasan ASavidis I(2021)CAMeleonProceedings of the 2021 Great Lakes Symposium on VLSI10.1145/3453688.3461507(57-63)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3453688.3461507
Sun B(2019)An Improved PLC-Trie Based Routing Table Design for Variable Length IP Address LookupProceedings of the 14th International Conference on Future Internet Technologies10.1145/3341188.3341189(1-8)Online publication date: 7-Aug-2019
https://dl.acm.org/doi/10.1145/3341188.3341189
Ullah IUllah ZAfzaal ULee J(2019)DURE: An Energy- and Resource-Efficient TCAM Architecture for FPGAs With Dynamic UpdatesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2019.290410527:6(1298-1307)Online publication date: 20-May-2019
https://dl.acm.org/doi/10.1109/TVLSI.2019.2904105

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents