linux 2.4 routing algorithm?

linux 2.4 routing algorithm?

[Kristen Carlson]

Hello,
I'm trying to understand the routing algorithm for linux 2.4.  I thought
it would use a longest prefix match due to some documentation I had googled,
but the code in route.c looks like a hash.  I probably just don't understand
how lpm would be coded in practice.  Am I looking in the right place?  Can
someone give me a clue about how this works?

Thanks,
Kristen

-- 
WWXD (What Would Xena Do?) 

Re: linux 2.4 routing algorithm?

[David S. Miller]

On Wed, 17 Sep 2003 16:47:53 -0700
Kristen Carlson <kristenc@cs.pdx.edu> wrote:

> I'm trying to understand the routing algorithm for linux 2.4.  I thought
> it would use a longest prefix match due to some documentation I had googled,
> but the code in route.c looks like a hash.  I probably just don't understand
> how lpm would be coded in practice.  Am I looking in the right place?  Can
> someone give me a clue about how this works?

route.c is the routing cache, it caches prefix based lookup results
so that a direct hash based lookup can be used for subsequent lookups
on the same exact key.

The prefix based lookup occurs in fib_hash.c, it uses 32+1 hash tables
to implement the prefix based lookup, one for each bit in the IPV4 address
plus an extra for "default" routes requiring matching of no bits.  The
hash tables are lookup up from most specific to least specific so that
we truly get a longest matching prefix lookup.

Any time the routing tables are changed, the routing cache in route.c
is flushed completely.