[Click] A fast IP lookup element

[Marko Zec]

Hi all,

A new IPv4 lookup element named DirectIPLookup is now in the Click CVS 
tree.  This is more or less a straightforward implementation of a 
longest prefix searching algorithm using two directly indexed tables 
proposed by Gupta, Lin, and McKeown in their '98 INFOCOM paper.

The algorithm is optimized for lookup speed at the expense of extensive 
RAM usage.  Worst-case lookup rates are determined primarily by the 
DRAM access and CPU cache line replacement latency; TLB misses most 
probably also play a certain role.  In a few tests I have measured 
something around 5.5 million lookups per second in average on a 800 MHz 
P-III, up to 6.7 MLPS on a 2.4 GHz Xeon box.  With localized traffic 
patterns one can expect the relevant parts of lookup tables to reside 
in the CPU cache most of the time, in which cases lookup times can 
converge to only a few clock cycles.

Another nice property of the direct lookup algorithm is that it allows 
for relatively fast incremental updating of lookup tables.  Inserting a 
route in a table already containing 100.000 prefixes lasts around 2 
microseconds in average, while removals can last two to three times 
longer.  Update latencies increase with wider prefix masks:  insertion 
or removal of a /8 prefix can last up to 2 milliseconds.  The element 
provides a set of standard handler hooks (add/remove/ctrl/table) for 
table manipulation, which can be used for interfacing with other 
software operating in the control plane (such as XORP).

That's it, hope it will be usefull...

Cheers,

Marko