Fast address look-up for Internet routers
Stefan Nilsson and Gunnar Karlsson
We consider the problem of organizing address tables for
internet routers to enable fast searching.
Our proposal is to build an efficient, compact and
easily searchable implementation of an IP routing table
by using an LC-trie, a trie structure with
combined path and level compression.
A node in the trie can be coded in only four bytes and
the size of the main search structure
never exceeds 500 kB
for the tables in the US core routers.
We present a software implementation that can sustain
approximately half a million lookups per second
on a 133 MHz Pentium personal computer,
and two million lookups per second on a more powerful
SUN Sparc Ultra II workstation.
In Proc.
IFIP 4th International Conference on Broadband Communications,
pp. 11-22, 1998.
Complete text:
ps,
pdf
Code
|