increase the number of routing tables

Hey folks,

To my limited knowledge, Linux currently supports 256 (255?) routing
tables defined in /etc/iproute2/rt_tables.

Is there a way to increase this number to something much larger? Are
there performance/scalability concerns there? I am trying to have
customized routing table for each IP address (using "ip rule add from
xxx table yyy"). I am not sure exactly how many IPs I'll handle, but
certainly more than 255...

Thanks.
-Simon

Le samedi 28 janvier 2012 à 21:20 -0500, Simon Chen a écrit :

Hey folks,

To my limited knowledge, Linux currently supports 256 (255?) routing
tables defined in /etc/iproute2/rt_tables.

Is there a way to increase this number to something much larger? Are
there performance/scalability concerns there? I am trying to have
customized routing table for each IP address (using "ip rule add from
xxx table yyy"). I am not sure exactly how many IPs I'll handle, but
certainly more than 255...

Its is possible, but probably not scalable.

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

The limit being ~32768 rules

# ip rule
0:	from all lookup local 
32763:	from all to 1.2.3.7 lookup test3000 
32766:	from all lookup main 
32767:	from all lookup default 

# cat /etc/iproute2/rt_tables
#
# reserved values
#
255	local
254	main
253	default
0	unspec
#
# local
#
#1	inr.ruhep

3000 test3000

# ip route list table 3000
1.2.3.4 dev eth0  scope link 

On 01/28/2012 06:41 PM, Eric Dumazet wrote:

Le samedi 28 janvier 2012 à 21:20 -0500, Simon Chen a écrit :

quoted

Hey folks,

To my limited knowledge, Linux currently supports 256 (255?) routing
tables defined in /etc/iproute2/rt_tables.

Is there a way to increase this number to something much larger? Are
there performance/scalability concerns there? I am trying to have
customized routing table for each IP address (using "ip rule add from
xxx table yyy"). I am not sure exactly how many IPs I'll handle, but
certainly more than 255...

Its is possible, but probably not scalable.

I've run with a few thousand routing tables and probably 5000 or so
rules.  It seems to run OK....

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

For every packet, or maybe just until conn-track gets an entry
for the connection?

Thanks,
Ben


-- 
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com

Thanks...

Here says 252 routing tables top... maybe that's too old:
http://linux-ip.net/html/routing-tables.html

I wonder if we can use a trie-tree for "ip rule" - linear evaluation
does not sound too good. But I'll be using a ton of iptables rules as
well, and I believe those are linear evaluation too :-(

On Sat, Jan 28, 2012 at 9:46 PM, Ben Greear [off-list ref] wrote:

On 01/28/2012 06:41 PM, Eric Dumazet wrote:

quoted

Le samedi 28 janvier 2012 à 21:20 -0500, Simon Chen a écrit :

quoted

Hey folks,

To my limited knowledge, Linux currently supports 256 (255?) routing
tables defined in /etc/iproute2/rt_tables.

Is there a way to increase this number to something much larger? Are
there performance/scalability concerns there? I am trying to have
customized routing table for each IP address (using "ip rule add from
xxx table yyy"). I am not sure exactly how many IPs I'll handle, but
certainly more than 255...

Its is possible, but probably not scalable.

I've run with a few thousand routing tables and probably 5000 or so
rules.  It seems to run OK....

quoted

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

For every packet, or maybe just until conn-track gets an entry
for the connection?

Thanks,
Ben


--
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com

On 01/28/2012 08:20 PM, Simon Chen wrote:

Thanks...

Here says 252 routing tables top... maybe that's too old:
http://linux-ip.net/html/routing-tables.html

I wonder if we can use a trie-tree for "ip rule" - linear evaluation
does not sound too good. But I'll be using a ton of iptables rules as
well, and I believe those are linear evaluation too :-(

At least some rules apply only to packets entering certain
interfaces.  It seems we could have per-interface rule collections
in those cases so that only a few rules would be searched each time.

What type of rules are you planning to use?

Thanks,
Ben

-- 
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com

From: Ben Greear <redacted>
Date: Sat, 28 Jan 2012 18:46:01 -0800

On 01/28/2012 06:41 PM, Eric Dumazet wrote:

quoted

Its is possible, but probably not scalable.

I've run with a few thousand routing tables and probably 5000 or so
rules.  It seems to run OK....

quoted

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

For every packet, or maybe just until conn-track gets an entry
for the connection?

When the routing cache is removed, using a huge number of rules is not
going to be something you want to do any more because the rule table
will be inspected on every route lookup.

From: Simon Chen <redacted>
Date: Sat, 28 Jan 2012 23:20:33 -0500

I wonder if we can use a trie-tree for "ip rule" - linear evaluation
does not sound too good. But I'll be using a ton of iptables rules as
well, and I believe those are linear evaluation too :-(

You cannot use a trie because the rules are defined to be evaluated
in the order they were added to the kernel, it is the same problem
that basic firewall rule tables have.

On Sun, Jan 29, 2012 at 03:41:27AM +0100, Eric Dumazet wrote:

Le samedi 28 janvier 2012 à 21:20 -0500, Simon Chen a écrit :

quoted

Hey folks,

To my limited knowledge, Linux currently supports 256 (255?) routing
tables defined in /etc/iproute2/rt_tables.

Is there a way to increase this number to something much larger? Are
there performance/scalability concerns there? I am trying to have
customized routing table for each IP address (using "ip rule add from
xxx table yyy"). I am not sure exactly how many IPs I'll handle, but
certainly more than 255...

Its is possible, but probably not scalable.

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

The limit being ~32768 rules

# ip rule
0:	from all lookup local 
32763:	from all to 1.2.3.7 lookup test3000 
32766:	from all lookup main 
32767:	from all lookup default 

I've run into these scalability issues a while ago which is
why I've added the goto action allowing to build a tree like
structures:

0:	from all lookup local 
10:     from eth0 goto 4000
[possibly thousands of rules]
3999:   from all goto 32763
4000:   from all to 1.1.1.1 lookup foo
[...]
32763:	from all to 1.2.3.7 lookup test3000 
32766:	from all lookup main 
32767:	from all lookup default 

Le lundi 30 janvier 2012 à 07:25 -0500, Thomas Graf a écrit :

I've run into these scalability issues a while ago which is
why I've added the goto action allowing to build a tree like
structures:

0:	from all lookup local 
10:     from eth0 goto 4000
[possibly thousands of rules]
3999:   from all goto 32763
4000:   from all to 1.1.1.1 lookup foo
[...]
32763:	from all to 1.2.3.7 lookup test3000 
32766:	from all lookup main 
32767:	from all lookup default 

Indeed, but make sure to use a recent kernel (3.2) so that Yan Zheng and
Gao Feng fixes are in :)

commit afaef734e5f0 (fib_rules: fix unresolved_rules counting)
commit 561dac2d410f (fib:fix BUG_ON in fib_nl_newrule when add new fib
rule)

commit ebb9fed2def (fib: fix fib_nl_newrule())

On 01/29/2012 01:01 PM, David Miller wrote:

From: Ben Greear<redacted>
Date: Sat, 28 Jan 2012 18:46:01 -0800

quoted

On 01/28/2012 06:41 PM, Eric Dumazet wrote:

quoted

Its is possible, but probably not scalable.

I've run with a few thousand routing tables and probably 5000 or so
rules.  It seems to run OK....

quoted

You really should not have too many "ip rule" entries, since they are
evaluated linearly.

For every packet, or maybe just until conn-track gets an entry
for the connection?

When the routing cache is removed, using a huge number of rules is not
going to be something you want to do any more because the rule table
will be inspected on every route lookup.

Well, that sounds like a reason to keep the routing cache around,
even if it isn't used by default, perhaps.

Thanks,
Ben

-- 
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com

From: Ben Greear <redacted>
Date: Mon, 30 Jan 2012 09:26:25 -0800

Well, that sounds like a reason to keep the routing cache around,
even if it isn't used by default, perhaps.

The routing cache is fundamentally DoS'able and this problem
is independent of the routing rule issues being discussed here.

Therefore it will be removed, and if people want routing rule
performance to be better in the regime they better start
thinking about how to do that (without reintroducing the
DoS issue) now.

Basically I am trying to build a NATter with multiple uplinks...

I have a ton of private IPs behind the NATter, and I need to NAT a
private IP into different uplinks based on the destination prefix.
Think about choosing a specific ISP for a certain destination.

Therefore I'll need to maintain a per-IP routing table to make sure
the outgoing packet goes to the right uplink, and then use
iptables-rules to translate into the proper public IP.

-Simon

On Sun, Jan 29, 2012 at 2:26 PM, Ben Greear [off-list ref] wrote:

On 01/28/2012 08:20 PM, Simon Chen wrote:

quoted

Thanks...

Here says 252 routing tables top... maybe that's too old:
http://linux-ip.net/html/routing-tables.html

I wonder if we can use a trie-tree for "ip rule" - linear evaluation
does not sound too good. But I'll be using a ton of iptables rules as
well, and I believe those are linear evaluation too :-(

At least some rules apply only to packets entering certain
interfaces.  It seems we could have per-interface rule collections
in those cases so that only a few rules would be searched each time.

What type of rules are you planning to use?


Thanks,
Ben

--
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com