TY - GEN
T1 - Parallel-search trie-based scheme for fast IP lookup
AU - Rojas-Cessa, Roberto
AU - Ramesh, Lakshmi
AU - Ziqian, Dong
AU - Lin, Cai
AU - Ansari, Nirwan
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2007
Y1 - 2007
N2 - As data rates in the Internet increase, the Internet Protocol (IP) address lookup is required to be resolved in shorter resolution times. IP address lookup involves finding the longest matching prefix from a database of prefixes that better matches the destination address of a packet. The fastest IP-address lookup solutions are based on ternary content addressable memories (TCAMs), which can resolve the IP lookup in one memory-access time. However, TCAMs have a high power consumption and large complexity that may limit their scalability and storage capacity. An alternative is to use random access memory (RAM) that stores a forwarding table in a trie form. Proposed trie-based solutions for IP lookup require three or more memory-access times in the worst-case scenario. This makes them unattractive despite their reduced power consumption. In this paper, we propose a flexible and fast trie-based IP-lookup algorithm where parallel searching is performed. This algorithm performs lookup in two memoryaccess times whith a feasible amount of memory or three memory access times with reduced memory.
AB - As data rates in the Internet increase, the Internet Protocol (IP) address lookup is required to be resolved in shorter resolution times. IP address lookup involves finding the longest matching prefix from a database of prefixes that better matches the destination address of a packet. The fastest IP-address lookup solutions are based on ternary content addressable memories (TCAMs), which can resolve the IP lookup in one memory-access time. However, TCAMs have a high power consumption and large complexity that may limit their scalability and storage capacity. An alternative is to use random access memory (RAM) that stores a forwarding table in a trie form. Proposed trie-based solutions for IP lookup require three or more memory-access times in the worst-case scenario. This makes them unattractive despite their reduced power consumption. In this paper, we propose a flexible and fast trie-based IP-lookup algorithm where parallel searching is performed. This algorithm performs lookup in two memoryaccess times whith a feasible amount of memory or three memory access times with reduced memory.
KW - Hashing
KW - Parallel search
KW - Prefix expansion
KW - RAM based
KW - Trie search
UR - http://www.scopus.com/inward/record.url?scp=39349101634&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=39349101634&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2007.47
DO - 10.1109/GLOCOM.2007.47
M3 - Conference contribution
AN - SCOPUS:39349101634
SN - 1424410436
SN - 9781424410439
T3 - GLOBECOM - IEEE Global Telecommunications Conference
SP - 210
EP - 214
BT - IEEE GLOBECOM 2007 - 2007 IEEE Global Telecommunications Conference, Proceedings
T2 - 50th Annual IEEE Global Telecommunications Conference, GLOBECOM 2007
Y2 - 26 November 2007 through 30 November 2007
ER -