FIB LPM algorithm

FIB LPM algorithm

[Tobias DiPasquale]

Hello all,

I was wondering if someone could point me to a discussion of what LPM
algorithm the Linux routing FIB uses? Is it detailed in the code
somewhere, or online, or in a book? I have perused the code somewhat
and it appears that it makes use of hash tables to store the FIB(s?),
but I can't seem to find the actual LPM operation used. Any help would
be appreciated. Thanks.

--
Tobias DiPasquale
[ 0x63626367545440676d61696c2e636f6d ]

Re: FIB LPM algorithm

[Antony Stone]

On Monday 07 June 2004 12:23 pm, Tobias DiPasquale wrote:

> Hello all,
>
> I was wondering if someone could point me to a discussion of what LPM
> algorithm the Linux routing FIB uses?

Er, what do LPM and FIB mean please?   I think I know netfilter quite well, 
and I've not come across these abbreviations so far...

Antony.

-- 
"I estimate there's a world market for about five computers."

 - Thomas J Watson, Chairman of IBM

                                                     Please reply to the list;
                                                           please don't CC me.

Re: FIB LPM algorithm

[alex]

> On Monday 07 June 2004 12:23 pm, Tobias DiPasquale wrote:
> 
> > Hello all,
> >
> > I was wondering if someone could point me to a discussion of what LPM
> > algorithm the Linux routing FIB uses?
> 
> Er, what do LPM and FIB mean please?  I think I know netfilter quite
> well, and I've not come across these abbreviations so far...
Longest Prefix Match and Forwarding Information Base.

To answer your question: Linux has routing cache which stores complete 
5-tuples. If it is not found in cache, it is looked up in the FIB which is 
stored as 33 hashes (based on netmask size). Hashes are looked up from the 
/32 back to /0.

Yes, it is extremely inefficient ;)

-alex

Re: FIB LPM algorithm

[Tobias DiPasquale]

On Mon, 7 Jun 2004 13:02:15 +0100, Antony Stone
<antony@soft-solutions.co.uk> wrote:
> Er, what do LPM and FIB mean please?   I think I know netfilter quite well,
> and I've not come across these abbreviations so far...

LPM = Longest Prefix Match, the algorithm used to match an IP to a
particular route based on the route's destination network spefication.

FIB = Forwarding Information Base, the data structure used by the
kernel to hold packet routing information.

There are 3 or 4 files in net/ipv4/ devoted entirely to the FIB (which
are called in route.c in the same subdir). Thinking more about this,
though, it was probably a mistake posting this to the netfilter
list... it seems more of a question that should be asked of the
linux-net list.

As well, I just found a small section on the FIB in Chapter 18 of
Understanding the Linux Kernel (2nd Edition) but its not really as
specific as I would like with respect to the exact LPM algorithm used.

I will repost my original message to linux-net but will also be
amenable to any direction that may come from this list, as well.
Thanks again :)

--
Tobias DiPasquale
[ 0x63626367545440676d61696c2e636f6d ]