Fast Prefix Deletion for Parallel TCAM-Based IP Address Lookup (병렬 TCAM 기반의 IP 주소 검색에서 신속한 프리픽스 삭제)

Jinsoo Kim (김진수); Junghwan Kim (김정환)

Fast Prefix Deletion for Parallel TCAM-Based IP Address Lookup

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2010, 15(12), pp.93-100
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

Jinsoo Kim ¹, Junghwan Kim ¹

¹건국대학교

Accredited

ABSTRACT

In this paper, we propose a technique which makes it faster to delete prefixes in an IP address lookup architecture based on parallel TCAMs. In previous deletion schemes, more than one memory movement is needed for the prefix ordering and keeping the available memory space consecutive. For deletion, our scheme stores the address of the deleted prefix in a stack implemented by SRAM instead of actual movement in TCAM. Since SRAM has very short latency compared to TCAM, the proposed scheme can accomplish fast updating. From the experiment with the real forwarding table and update trace, we evaluate the performance of our scheme in terms of the memory access time for the prefix insertion and deletion. The experiment result also shows good performance with considerably small size of stack.

KEYWORDS

IP 주소 검색(IP address lookup), 신속한 프리픽스 삭제(fast prefix deletion), 병렬 TCAM(parallel TCAM)

Citation status

* References for papers published after 2023 are currently being built.

[other] V. Fuller / 1993 / Classless Inter-Domain Routing (CIDR): An Address Assignment and Aggregation Strategy / RFC 1519

[journal] Mi. A. Ruiz-Sanchez / 2001 / Survey and Taxonomy of IP Address Lookup Algorithms / IEEE Network

[book] H.J.Chao / 2007 / High Performance Switches and Routers / Wiley Interscience

[confproc] A.J.McAuley / 1993 / Fast Routing Table Lookup using CAMs / Proc.of INFOCOM : 1382~1391

[confproc] M.Kobayashi / 2000 / A Longest Prefix Match Search Engine for Multi-Gigabit IP Processing / Proc.of 2000 International Conf.on Communications : 1360~1364

[journal] D.Shah / 2001 / Fast Updating Algorithm for TCAMs / IEEE Micro 21(2) : 36~47

[journal] Y.-M. Hsiao / 2009 / A Fast Update Scheme for TCAM-Based IPv6 Routing Lookup Architecture / Proc.of 15th Asia-Pacific conference on Communications, : 779~789

[journal] J. Kim / 2008 / An Efficient IP Lookup Architecture with Fast Update Using Single-Match TCAMs / Proc. of WWIC 5031 : 104~114

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

[journal] B.Agrawal / 2008 / Ternary CAM Power and Delay Model:Extensions and Uses / IEEE Tr.on Very Large Scale Integration(VLSI)Systems 16 : 554~564

[report] N. P. Jouppi / 2001 / Cacti 3.0: An Integrated Cache Timing, Power and Area Model / Technical Report Western Research Lab (WRL) Research Report

[web] / http://www.hpl.hp.com/research/cacti/ / http://www.hpl.hp.com/research/cacti/

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65