increase the number of routing tables

increase the number of routing tables

[Simon Chen]

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

increase the number of routing tables

[Simon Chen]

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

Re: increase the number of routing tables

[Eric Dumazet]

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 

Re: increase the number of routing tables

[Ben Greear]

On 01/28/2012 06:41 PM, Eric Dumazet wrote:
> 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.

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 <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: increase the number of routing tables

[Simon Chen]

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 <greearb@candelatech.com> wrote:
> On 01/28/2012 06:41 PM, Eric Dumazet wrote:
>>
>> 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.
>
>
> 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 <greearb@candelatech.com>
> Candela Technologies Inc  http://www.candelatech.com

Re: increase the number of routing tables

[Jan Engelhardt]

On Sunday 2012-01-29 03:23, Simon Chen wrote:

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

There are 2147483647.

Re: increase the number of routing tables

[Ben Greear]

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 <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: increase the number of routing tables

[David Miller]

From: Ben Greear <greearb@candelatech.com>
Date: Sat, 28 Jan 2012 18:46:01 -0800

> On 01/28/2012 06:41 PM, Eric Dumazet wrote:
>> 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?

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.

Re: increase the number of routing tables

[David Miller]

From: Simon Chen <simonchennj@gmail.com>
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.

Re: increase the number of routing tables

[Ed W]

On 29/01/2012 11:50, Jan Engelhardt wrote:
> On Sunday 2012-01-29 03:23, Simon Chen wrote:
>
>> Hey folks,
>>
>> To my limited knowledge, Linux currently supports 256 (255?) routing
>> tables defined in /etc/iproute2/rt_tables.
> There are 2147483647.
>

Any reason why it's not an unsigned 32bit int? (surely there is a corner 
case where this is useful...)

Ed W

Re: increase the number of routing tables

[Stephen Hemminger]

On Sun, 29 Jan 2012 23:24:27 +0000
Ed W <lists@wildgooses.com> wrote:

> On 29/01/2012 11:50, Jan Engelhardt wrote:
> > On Sunday 2012-01-29 03:23, Simon Chen wrote:
> >
> >> Hey folks,
> >>
> >> To my limited knowledge, Linux currently supports 256 (255?) routing
> >> tables defined in /etc/iproute2/rt_tables.
> > There are 2147483647.
> >
> 
> Any reason why it's not an unsigned 32bit int? (surely there is a corner 
> case where this is useful...)
> 
> Ed W

The 8 bit value is enshrined in the API for 'struct rtmsg' and therefore
increasing it would break existing applications. 

Re: increase the number of routing tables

[Jan Engelhardt]

On Monday 2012-01-30 01:31, Stephen Hemminger wrote:

>On Sun, 29 Jan 2012 23:24:27 +0000
>Ed W <lists@wildgooses.com> wrote:
>
>> On 29/01/2012 11:50, Jan Engelhardt wrote:
>> > On Sunday 2012-01-29 03:23, Simon Chen wrote:
>> >
>> >> Hey folks,
>> >>
>> >> To my limited knowledge, Linux currently supports 256 (255?) routing
>> >> tables defined in /etc/iproute2/rt_tables.
>> > There are 2147483647.
>> >
>> 
>> Any reason why it's not an unsigned 32bit int? (surely there is a corner 
>> case where this is useful...)
>> 
>> Ed W
>
>The 8 bit value is enshrined in the API for 'struct rtmsg' and therefore
>increasing it would break existing applications. 

Actually, what Ed (and me too) was wondering about was:

why does `ip route show table $[0x80000000]` not print an empty table, 
i.e. where is it that some code uses int/s32 during parsing of 
the argument and/or the RTA_TABLE attribute?

Re: increase the number of routing tables

[Thomas Graf]

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

Re: increase the number of routing tables

[Eric Dumazet]

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())

Re: increase the number of routing tables

[Stephen Hemminger]

On Mon, 30 Jan 2012 03:02:35 +0100 (CET)
Jan Engelhardt <jengelh@medozas.de> wrote:

> On Monday 2012-01-30 01:31, Stephen Hemminger wrote:
> 
> >On Sun, 29 Jan 2012 23:24:27 +0000
> >Ed W <lists@wildgooses.com> wrote:
> >
> >> On 29/01/2012 11:50, Jan Engelhardt wrote:
> >> > On Sunday 2012-01-29 03:23, Simon Chen wrote:
> >> >
> >> >> Hey folks,
> >> >>
> >> >> To my limited knowledge, Linux currently supports 256 (255?) routing
> >> >> tables defined in /etc/iproute2/rt_tables.
> >> > There are 2147483647.
> >> >
> >> 
> >> Any reason why it's not an unsigned 32bit int? (surely there is a corner 
> >> case where this is useful...)
> >> 
> >> Ed W
> >
> >The 8 bit value is enshrined in the API for 'struct rtmsg' and therefore
> >increasing it would break existing applications. 
> 
> Actually, what Ed (and me too) was wondering about was:
> 
> why does `ip route show table $[0x80000000]` not print an empty table, 
> i.e. where is it that some code uses int/s32 during parsing of 
> the argument and/or the RTA_TABLE attribute?

There are lots of places internally in ip utilities that use u32
for route table. But the route input/output message format is still limited
to 8 bits.

Re: increase the number of routing tables

[Ben Greear]

On 01/29/2012 01:01 PM, David Miller wrote:
> From: Ben Greear<greearb@candelatech.com>
> Date: Sat, 28 Jan 2012 18:46:01 -0800
>
>> On 01/28/2012 06:41 PM, Eric Dumazet wrote:
>>> 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?
>
> 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 <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: increase the number of routing tables

[David Miller]

From: Ben Greear <greearb@candelatech.com>
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.

Re: increase the number of routing tables

[Jan Engelhardt]

On Monday 2012-01-30 17:14, Stephen Hemminger wrote:

>> >> > There are 2147483647.
>> >> 
>> >> Any reason why it's not an unsigned 32bit int? (surely there is a corner 
>> >> case where this is useful...)
>> >
>> >The 8 bit value is enshrined in the API for 'struct rtmsg' and therefore
>> >increasing it would break existing applications. 
>> 
>> Actually, what Ed (and me too) was wondering about was:
>> 
>> why does `ip route show table $[0x80000000]` not print an empty table, 
>> i.e. where is it that some code uses int/s32 during parsing of 
>> the argument and/or the RTA_TABLE attribute?
>
>There are lots of places internally in ip utilities that use u32
>for route table. But the route input/output message format is still limited
>to 8 bits.

But then, adding a rule to table 258 would make it show up in table 2 as 
well, which is not the case.

Re: increase the number of routing tables

[Stephen Hemminger]

On Mon, 30 Jan 2012 19:57:20 +0100 (CET)
Jan Engelhardt <jengelh@medozas.de> wrote:

> On Monday 2012-01-30 17:14, Stephen Hemminger wrote:
> 
> >> >> > There are 2147483647.
> >> >> 
> >> >> Any reason why it's not an unsigned 32bit int? (surely there is a corner 
> >> >> case where this is useful...)
> >> >
> >> >The 8 bit value is enshrined in the API for 'struct rtmsg' and therefore
> >> >increasing it would break existing applications. 
> >> 
> >> Actually, what Ed (and me too) was wondering about was:
> >> 
> >> why does `ip route show table $[0x80000000]` not print an empty table, 
> >> i.e. where is it that some code uses int/s32 during parsing of 
> >> the argument and/or the RTA_TABLE attribute?
> >
> >There are lots of places internally in ip utilities that use u32
> >for route table. But the route input/output message format is still limited
> >to 8 bits.
> 
> But then, adding a rule to table 258 would make it show up in table 2 as 
> well, which is not the case.

Ok, drilling deeper, overlooked the extended table support.
Tables >= 256 are handled by setting rtm_table to RT_TABLE_UNSPEC and
sending a RTA_TABLE attribute.
Therefore it has worked for quite a while.

But, I also see code in other utilities (like net-snmp and quagga)
which don't know about how to handle tables other than main. But
that is a different issue.

Re: increase the number of routing tables

[Simon Chen]

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 <greearb@candelatech.com> wrote:
> 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 <greearb@candelatech.com>
> Candela Technologies Inc  http://www.candelatech.com