Please use this identifier to cite or link to this item:
標題: TCAM-Based IP Address Lookup Using Longest Suffix Split
作者: Jhih-Yu Huang
Pi-Chung Wang
關鍵字: IP address lookup;ternary content addressable memory;longest prefix matching;virtual routers
Project: IEEE/ACM Transactions on Networking ( Volume: 26 , Issue: 2 , April 2018 )
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.
DOI: 10.1109/TNET.2018.2815999
Appears in Collections:資訊科學與工程學系所

Files in This Item:
File Description SizeFormat Existing users please Login
314.pdf2.89 MBAdobe PDFThis file is only available in the university internal network    Request a copy
Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.