[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
>rules

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 (10.0.0.0/24 is address 10.0.0.0 with netmask 255.255.255.0):

 Route        Nexthop
 10.0.0.0/16  A
 10.0.0.0/24  B
 10.0.2.0/24  C

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

The normal data structure for such lookups is a binary trie:
  http://www.nist.gov/dads/HTML/trie.html

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

 http://www.acm.org/sigcomm/sigcomm97/papers/p192.html
 http://www.acm.org/sigcomm/sigcomm97/papers/p182.html

Unfortunately I believe both these algorithms are patented.

Cheers,
	Mark

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





More information about the buug mailing list