LARTC - Jun 2006 - Advanced routing routing table limits and rule design

I am trying to determine how to best increase the number of routing
tables available in linux 2.6 to more than 255.  I realize this involves
increasing the storage of some messages to and from the kernel in
addition to kernel changes (from browsing the code), and was hopeful
that someone might know what the correct solution would be or could
point me in the right direction (like existing patches or a highlevel of
what I need to change in the code).

Additionally, I was curious how the ip *rule* system works in regards to
matching -- is it a linear search or optimized in some way.  Basically
what I''m asking is if adding rules to a machine adds time to the whole
system passing over various rules that don''t match.

This all comes down to a seutp I have that has a lot of routing tables
and at least one or two rules to get into each routing table.  I don''t
want to increase the number of routing tables if also increasing the
number of rules on the box is going to do more harm than good.

Wayne

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Greetings Wayne,

 : I am trying to determine how to best increase the number of 
 : routing tables available in linux 2.6 to more than 255. 

You are in good company.  The question seems to come up with some 
frequency [0]...I''m beginning to think that it needs to be an FAQ.

 : I realize this involves increasing the storage of some messages 
 : to and from the kernel in addition to kernel changes (from 
 : browsing the code), and was hopeful that someone might know what 
 : the correct solution would be or could point me in the right 
 : direction (like existing patches or a highlevel of what I need to 
 : change in the code).

Sadly, I haven''t heard of anybody yet having done this, although one 
of the key developers of the kernel VLAN code (Ben Greear) has 
recently requested development on this point [1].

 : Additionally, I was curious how the ip *rule* system works in 
 : regards to matching -- is it a linear search or optimized in some 
 : way.  Basically what I''m asking is if adding rules to a machine 
 : adds time to the whole system passing over various rules that 
 : don''t match.

While I''m not certain of this, I believe that any route lookup which 
fails the routing cache (you do know about the routing cache, right) 
will traverse the rule policy database in a linear fashion.  (Sorry, 
don''t know which part of the kernel C to examine.)

 : This all comes down to a seutp I have that has a lot of routing 
 : tables and at least one or two rules to get into each routing 
 : table.  I don''t want to increase the number of routing tables if 
 : also increasing the number of rules on the box is going to do 
 : more harm than good.

I am not aware of any performance comparisons of typically routing 
configurations against "full" RPDBs.  It seems like you''d get
some
benefit from your own sort of least recently used (LRU) sort before 
inserting rules into the RPDB, though.

I hope somebody else out there will comment on:

  - whether s/he is working on patches which would support up to 
    2 ** 16 routing tables (as opposed to 2 ** 8).
  - performance metrics/routing comparison, Linux with one routing 
    table and a given load as against Linux with RPDB + many
    routing tables

Good luck in getting your answer(s), Wayne,

- -Martin

 [0] http://oss.sgi.com/archives/netdev/2005-08/msg00163.html
     http://mailman.ds9a.nl/pipermail/lartc/2001q2/001073.html
     http://mailman.ds9a.nl/pipermail/lartc/2004q1/011670.html
     http://mailman.ds9a.nl/pipermail/lartc/2004q4/014125.html
     http://mailman.ds9a.nl/pipermail/lartc/2005q4/017094.html
 [1] http://marc.theaimsgroup.com/?l=linux-netdev&m=115029279428349&w=4

- -- 
Martin A. Brown
http://linux-ip.net/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: For info see http://quantumlab.net/pine_privacy_guard/

iD8DBQFEpYiSki79Zb8hnmwRAhGpAJ0aLU24s0US28hd+gamGFpnbtRfIgCfRUqY
aE+XF2YAIPKHKJykfLCOwNM=G6vh
-----END PGP SIGNATURE-----

Good morning LARTC and, specifically, Wayne,

 :  : I am trying to determine how to best increase the number of 
 :  : routing tables available in linux 2.6 to more than 255. 
 : 
 : You are in good company.  The question seems to come up with some 
 : frequency [0]...I''m beginning to think that it needs to be an 
 : FAQ.

Perhaps this will no longer be an FAQ.  Since I just answered this 
question late last week, and my answer is now "wrong", I thought I 
would post a followup message.

 : Sadly, I haven''t heard of anybody yet having done this, although 
 : one of the key developers of the kernel VLAN code (Ben Greear) 
 : has recently requested development on this point [1].

Just today, Patrick McHardy has posted a set of patches [0] [1] 
which accommodate the desire for more routing tables.

Good luck and enjoy!

-Martin

 [0] http://marc.theaimsgroup.com/?t=115191334700002&r=1&w=2
 [1] http://marc.theaimsgroup.com/?l=linux-netdev&m=115191325909208&w=2
     http://marc.theaimsgroup.com/?l=linux-netdev&m=115191325901440&w=2
     http://marc.theaimsgroup.com/?l=linux-netdev&m=115191326012390&w=2
     http://marc.theaimsgroup.com/?l=linux-netdev&m=115191325901420&w=2
     http://marc.theaimsgroup.com/?l=linux-netdev&m=115191325911007&w=2

-- 
Martin A. Brown
http://linux-ip.net/