[buug] Theorizing data structures behind unix utilities

Mark Handley mjh at icir.org
Fri Jun 7 12:30:04 PDT 2002

>> >    I propose we continue along this vein...by
>> > theorizing the data structures behind "ipchains".
>OK...here's my guess:
>1)  IPChains nas 3 types of rules.  We need a place to
>hold the rules and a fast way to find out which rules
>are applicable:
>name: input chains
>type: hashtable
>holds: Network Number -> rule number
>purpose: matches incoming IP to applicable input chain

In most cases where you're matching IP addresses (firewalls, routing
tables, etc), it's hard to use hash tables.  The reason is that you
normally want "longest prefix match" to apply, and you specify the
routes or filters in terms of address and prefix.

For example, if I have a routing table, I might have the following
route entries ( is address with netmask

 Route        Nexthop  A  B  C

In this case the packets for would get nexthop B, packets for would get nexthop A, and packets for would get
nexthop C.

The normal data structure for such lookups is a binary trie:

There's been a lot of research on fast route lookup algorithms.  Two
good papers on faster route lookups are:


Unfortunately I believe both these algorithms are patented.


XORP: eXtensible Open Router Platform, http://www.xorp.org

More information about the buug mailing list