IP Lookup Table Design Using LC-Trie with Memory Constraint
Abstract: IP
address lookup is to determine the next hop destination of an incoming packet
in the router. The address lookup is a major bottleneck in high performance
router due to the increased routing table sizes, increased traffic, higher
speed links, and the migration to 128 bits IPv6 addresses. IP lookup time is
dependent on data structure of lookup table and search scheme.
In this paper, we propose a new approach to build a
lookup table that satisfies the memory constraint. The design of lookup table
is formulated as an optimization problem. The objective is to minimize average
depth from the root node for lookup. We assume that the frequencies with which
prefixes are accessed are known and the data structure is level compressed trie
with branching factor k at the root and binary at all other nodes. Thus,
the problem is to determine the branching factor k at the root node such
that the average depth is minimized. A heuristic procedure is proposed to solve
the problem. Experimental results show that the lookup table based on the
proposed heuristic has better average and the worst-case depth for lookup