Regarding Routing table in Linux kernel

Regarding Routing table in Linux kernel

[Ajith Adapa]

Hi,

I have few doubts regarding the routing table in linux kernel.

1. Why does the linux kernel use hashing table for storing routing
entries when there is patricia trie or radix tree which is more faster
than Hash table ?

2. Is there any way we can test the performance of an routing
algorithm before deploying in a real time scenario to check its
performance ? I would like to test one of my implementations to check
if there are any performance gains or not ?

Regards,
Ajith

Re: Regarding Routing table in Linux kernel

[Eric Dumazet]

Le dimanche 06 novembre 2011 à 12:43 +0530, Ajith Adapa a écrit :
> Hi,
> 
> I have few doubts regarding the routing table in linux kernel.
> 
> 1. Why does the linux kernel use hashing table for storing routing
> entries when there is patricia trie or radix tree which is more faster
> than Hash table ?
> 

I think you are mistaken. Routes are stored in a trie in recent kernels.

And route cache is scheduled to be removed at some point.

In normal situation, one hash lookup is the faster way to find a random
item, its a single memory cache line cost.


> 2. Is there any way we can test the performance of an routing
> algorithm before deploying in a real time scenario to check its
> performance ? I would like to test one of my implementations to check
> if there are any performance gains or not ?

Sorry there is no general answer. It all depends on your needs.

Re: Regarding Routing table in Linux kernel

[Ajith Adapa]

Thanks for the reply

>> 1. Why does the linux kernel use hashing table for storing routing
>> entries when there is patricia trie or radix tree which is more faster
>> than Hash table ?
>
> I think you are mistaken. Routes are stored in a trie in recent kernels.
>
> And route cache is scheduled to be removed at some point.
>
> In normal situation, one hash lookup is the faster way to find a random
> item, its a single memory cache line cost.

I will check it with the latest kernel. Actually I am just checking in
a 2.6.18 kernel.

>> 2. Is there any way we can test the performance of an routing
>> algorithm before deploying in a real time scenario to check its
>> performance ? I would like to test one of my implementations to check
>> if there are any performance gains or not ?
>
> Sorry there is no general answer. It all depends on your needs.

Hmm .. Seems there is no simple way for it other than trying out in
real time scenario :(

Re: Regarding Routing table in Linux kernel

[Eric Dumazet]

Le lundi 07 novembre 2011 à 09:52 +0530, Ajith Adapa a écrit :

> I will check it with the latest kernel. Actually I am just checking in
> a 2.6.18 kernel.
> 

2.6.18 is very old in this respect. Lot of things changed in recent
kernels in route cache handling. We no longer have long pauses because
of garbage collector runs.