[AusNOG] Routing Table Question

[Lincoln Dale]

On 09/09/2010, at 11:26 AM, Joshua Lehman wrote:

> 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.

the order shown in "show routing" or "show ip route" is platform specific.  even on two different cisco routers and indeed even two different software releases for the same model router you may get a different order.
the output will show the route table in the order in which it is stored in memory - which may be a trie structure (http://en.wikipedia.org/wiki/Trie).

note that the routing table (RIB aka Routing Information Base) is different to the forwarding table (FIB aka Forwarding Information Base).
again, depending on the router platform there may even be multiple FIBs, e.g. software (control plane) view of it, and then the hardware (data plane) view of it, depending on exactly how the router platform works.

>  
> 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.

not quite true, although in a simplistic manner i guess its sort of right.
if you are 'displaying' something that is organic and can change then locks are needed to prevent pointers changing and causing corruption.

its sort of easier to just do a linear walk through all of the blocks because order does not matter in any "show" output.
but again, its platform and s/w version specific.

>  
> 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.

one could never implement a RIB using a linked-list due to its O(n) worst case searching characteristics.


cheers,

lincoln.