[AusNOG] Routing Table Question

[Andrew Fort]

On Thu, Sep 9, 2010 at 11:26 AM, Joshua Lehman <extractfx at gmail.com> wrote:
> Hi Noggers,
> Just having a debate which I hope that someone can clairfy for me.
>
> Do routers store the routing tables in order of longest mask to shortest
> based on longest mask matching? When I do a show ip route on a cisco router
> it does not appear that the list is any order.

Prefixes stored in the forwarding table are looked up using a b-tree
or (better) trie algorithm (in general).  That's for performance (a
naive trie will be able to lookup an IPv4 address in a max of 33
lookups (32 bits + 1 more deref for the leaf).  An n-way trie (e.g., a
16/8/8 way, as used in some routers), trades memory for lookup time,
and reduces the maximum number of lookups to 4 (3 + 1).  Neat.

But as for routes stored in a "routing table" (i.e., data used to
build a forwarding table), there's no requirement to store it in any
particular order.

> The other techs I work with are telling me that the tables are stored in
> memory and that they are not ordered as when you enter a new route it is
> just added to the list, and that trying to sort the table could cause the
> router to crash if it is large.

Partially true.  The route IS added to an optimised lookup table (the
trie), but it's not "sorting" upon insert (though it may need to
perform recalculation or optimisation activities on the trie, you
don't want to block lookups to the datastructure while this is
occuring, or you block packet forwarding.  You could use two tries,
and swap to looking them up in the "new" one atomically after a
routing table insert).

> Other person says that the router would proccess the rules in correct order,
> which would imply that there is some sort of linked list structure that
> indicates the order of the rules.
>
> It would seem logical to me that the rules would be sorted in some order but
> why does the show ip route not display this is in order and what abouts the
> other points regarding crashing the table when trying to sort a new entry?

It doesn't crash because that would just be poor code, wouldn't it?
:-).  This is why tries and related datastructures are used in IP
address lookup tables on routers.

Also, how do you know it's not displaying them in the order it stores
them internally?  It quite well could be.

For more info, you may like to read George Varghese's papers
(particularly the ones with Venkatachary Srinivasan), where they
describe a range of optimised trie-type datastructures used to power
router lookups.

Radia Perlman's book, 'Interconnections', has a section on routing
table lookups including a discussion of the Lulea sparse table
algorithm, another approach to the problem, as well as her own
(hardware accelerated) approach to the problem.

As for displaying them in "order", well, yes, sorting 180,000 routes
on a little CPU will take a little while.  Fairly sure they would be
displayed in the order that produces the fastest lookup; probably just
iterating over dereferenced values from the linked-list.

-a