tc filtering vs iptables

tc filtering vs iptables

[jamal]

Harald or anyone from the netfilter devel cabal: 

I am trying to do a performance comparison for basic stateless
firewalling using tc and iptables. I want to provide a fair analysis
but dont know how well to optimize iptables. I know you can use chains
but not sure what the best way to approach it in this case. I will
describe what i am trying to do in English and someone please help
provide it in iptables-speak:

I want to be able to have many hosts[1] accessing a web server at
TCP port 80. The return path is asymetric so wont go via same box.
In this case clearly the ephemeral src port will vary as will the src IP
but nothing else.
Anything that doesnt match gets dropped i.e thats the default rule.

Let me know how to create proper chains for a range of hosts
{1,2,8, 64,256,4096,8192,16384,32768,64K} 

cheers,
jamal

Re: tc filtering vs iptables

[Henrik Nordstrom]

On Fri, 27 Aug 2004, jamal wrote:

> Let me know how to create proper chains for a range of hosts
> {1,2,8, 64,256,4096,8192,16384,32768,64K}

For very many unique hosts in iptables it is better to use an ippool for 
matching the source IP, or to look into using hipac.

ippool has the benefit that it allows you to create a group of hosts where 
the lookup is relatively fast to determine if the IP is among those hosts 
or not.

The benefit of hipac is that any kind of lookup is fast with no need to 
arrange the ruleset in a special mannner.

Regards
Henrik

Re: tc filtering vs iptables

[jamal]

On Fri, 2004-08-27 at 11:54, Henrik Nordstrom wrote:
> On Fri, 27 Aug 2004, jamal wrote:
> 
> > Let me know how to create proper chains for a range of hosts
> > {1,2,8, 64,256,4096,8192,16384,32768,64K}
> 
> For very many unique hosts in iptables it is better to use an ippool for 
> matching the source IP, or to look into using hipac.

Both of them seem to be a hassle for what i need (and given the time i
have). hipac seems to be a 2.4.x thing and pool requires me to recompile
a few things (while docs look scarce). I dont have much time to get this
done by - when i have more time in the future i could do it.

Any recommendation of how i should arrange the chains?

cheers,
jamal

Re: tc filtering vs iptables

[Bill Rugolsky Jr.]

On Fri, Aug 27, 2004 at 02:45:24PM -0400, jamal wrote:
> Both of them seem to be a hassle for what i need (and given the time i
> have). hipac seems to be a 2.4.x thing and pool requires me to recompile
> a few things (while docs look scarce). I dont have much time to get this
> done by - when i have more time in the future i could do it.
> 
> Any recommendation of how i should arrange the chains?
 
PATRICIA tree?  Calculate the internal CIDR address/prefixes and branch
on them.

Regards,

	Bill Rugolsky

Re: tc filtering vs iptables

[jamal]

On Fri, 2004-08-27 at 16:11, Bill Rugolsky Jr. wrote:
> On Fri, Aug 27, 2004 at 02:45:24PM -0400, jamal wrote:
> > Both of them seem to be a hassle for what i need (and given the time i
> > have). hipac seems to be a 2.4.x thing and pool requires me to recompile
> > a few things (while docs look scarce). I dont have much time to get this
> > done by - when i have more time in the future i could do it.
> > 
> > Any recommendation of how i should arrange the chains?
>  
> PATRICIA tree?  Calculate the internal CIDR address/prefixes and branch
> on them.

Can you emulate a patricia tree out of chains?
Heres what i have now (posted earlier):

What a painful experience it is to install large rules.
about 20 minutes to install 16K rules. Not sure if this is
even worth pursuing anymore

---------------
256 chains:  subnet_0 .. subnet_255

In each chain, there are 256 rules specifying a host in each 
(.0 ....255).

This creates a maximum of 65536 rules with hosts from 10.1.0.0 to 
10.1.255.255.

The lookup on the rules is done only on the IPs at the end.
I am being a little unfair to tc u32 which looks up the rcp src ports as
well in the rules - hopefully, this will  compensate for lack of
iptables optimization skills on my part.
----------------

cheers,
jamal

Re: tc filtering vs iptables

[KOVACS Krisztian]

  Hi,

On Fri, Aug 27, 2004 at 04:27:54PM -0400, jamal wrote:
> What a painful experience it is to install large rules.
> about 20 minutes to install 16K rules. Not sure if this is
> even worth pursuing anymore

  You're using the 'iptables' command, I guess. Probably you should try
iptables-restore, it is definitely _the_ tool you'll need when installing
large rulesets.

-- 
 KOVACS Krisztian

Re: tc filtering vs iptables

[jamal]

On Fri, 2004-08-27 at 16:42, KOVACS Krisztian wrote:
>   Hi,
> 
> On Fri, Aug 27, 2004 at 04:27:54PM -0400, jamal wrote:
> > What a painful experience it is to install large rules.
> > about 20 minutes to install 16K rules. Not sure if this is
> > even worth pursuing anymore
> 
>   You're using the 'iptables' command, I guess. Probably you should try
> iptables-restore, it is definitely _the_ tool you'll need when installing
> large rulesets.

One of my tests is to add and delete a rule while traffic is running
(and 16K rules are already installed).
I cant use restore in that case unfortunately -  getting
some very odd behavior just adding and deleting the rule. 

cheers,
jamal
 

Re: tc filtering vs iptables

[Henrik Nordstrom]

On Fri, 27 Aug 2004, jamal wrote:

> What a painful experience it is to install large rules.
> about 20 minutes to install 16K rules. Not sure if this is
> even worth pursuing anymore

Make sure to use iptables-restore for this, not iptables.

Regards
Henrik

Re: tc filtering vs iptables

[Henrik Nordstrom]

On Fri, 27 Aug 2004, jamal wrote:

> Can you emulate a patricia tree out of chains?

Yes, sort of.

If you like chains are just nodes with a list of branches or terminal 
leaves (the rules).

What you can't have in iptables is the prefix compression used in 
patricia, or at least not to the same level. You can still compress if 
your rules are based on multiple "dimensions" of the packet address space 
(i.e. source, destination, port).

But seriously speaking, if you are looking into ruleset requiring this 
amount of address information I stronly suspect ippool (or it's successor 
ipset) is the best tool for the job, allowing you to quickly group similar 
things together.  Only if you need to assign unique classification to each 
individual flow do you need a rule for each. But then again I do not have 
the full picture of the type of packet classification you are trying to 
accomplish.

Regards
Henrik

Re: tc filtering vs iptables

[jamal]

On Fri, 2004-08-27 at 20:00, Henrik Nordstrom wrote:
> On Fri, 27 Aug 2004, jamal wrote:
> 
> > Can you emulate a patricia tree out of chains?
> 
> Yes, sort of.
> 
> If you like chains are just nodes with a list of branches or terminal 
> leaves (the rules).
> 
> What you can't have in iptables is the prefix compression used in 
> patricia, or at least not to the same level. You can still compress if 
> your rules are based on multiple "dimensions" of the packet address space 
> (i.e. source, destination, port).

Thats what i wanted to do. I still have one more opportunity to re-run
tests before i close it for now.

> But seriously speaking, if you are looking into ruleset requiring this 
> amount of address information I stronly suspect ippool (or it's successor 
> ipset) is the best tool for the job, allowing you to quickly group similar 
> things together.  Only if you need to assign unique classification to each 
> individual flow do you need a rule for each. But then again I do not have 
> the full picture of the type of packet classification you are trying to 
> accomplish.

My goal end goal is to test a _huge_ number of rules with iptables
and u32. huge is probably an exageration here since 64K is the max i
test.

To simplify things i selected the following:
A single web server (TCP port 80) connected to by upto 64K different
clients. 
The reason i chose this simple setup is because i can plot its lookups
easily and write simple scripts to install rules.
So end goal: stash many rules in both u32 and iptables and check
results.
In this example setup src IP and src TCP port are always looked up in
the case of u32 and only when a match happens are the packets let
through - by default they are dropped. In the case of iptables, only the
src IP is looked up (didnt wanna add any overhead).
Of course these are cooked tests - so i dont bother looking up either
dst IP or dst port. So neither u32 nor iptables do that.

Does that make sense?

Next step: Since i can optimize u32 (didnt try too hard) - figured i
need to be fair to iptables hence my posting here.

Traffic runs in a sort of DOS mode. i.e for all users you send one
packet and wait until everyone has sent one before your turn again
(round robin). The overall packets are sent at wire rate 64 byte
packets. If there was one user that would be 1.48Million packets per
second. If there were 148 users each would be sending 10Kpps.
All the above is designed to test worst case scenario.

Next phase of the test:
While all that traffic is being sent add then delete a totaly unrelated
rule. Two metrics:
1) what packet rates are observed during add/del?
2) how many times/sec can you do this? (essentially this could be used
to simulate opening and closing peepholes maybe even in a midcom kind
environment)

I will present my results at SUCON.

cheers,
jamal

Re: tc filtering vs iptables

[Henrik Nordstrom]

On Sat, 27 Aug 2004, jamal wrote:

> A single web server (TCP port 80) connected to by upto 64K different
> clients.
> The reason i chose this simple setup is because i can plot its lookups
> easily and write simple scripts to install rules.
> So end goal: stash many rules in both u32 and iptables and check
> results.

This test case is an exact match for using ippool/ipset. You then stash 
all the client IP addresses into the pool and use a single iptable rule 
with very good performance mostly independent on the number of IP 
addresses.

iptables -d ip.of.web.server -p tcp --dport -m pool --srcpool webserver -j ACCEPT
iptables -d ip.of.web.server -p tcp --dport -m pool -j REJECT

> In this example setup src IP and src TCP port are always looked up in
> the case of u32 and only when a match happens are the packets let
> through - by default they are dropped. In the case of iptables, only the
> src IP is looked up (didnt wanna add any overhead).

The overhead of looking up the destination ip and tcp port is minimal. Can 
easily be done at the head of your lookup tree

iptables -d ip.of.web.server -p tcp --dport 80 -j WEBSERVER

then have the match tree for the client source IP addresses in WEBSERVER. 
Remember to terminate each subchain with a REJECT/DROP in case there is no 
match.

> While all that traffic is being sent add then delete a totaly unrelated
> rule. Two metrics:
> 1) what packet rates are observed during add/del?

With iptables there should not be much difference, except that the higher 
the packet load the slower the change take.

If you use ippool then the overhead of this operation is considerably 
less.

> 2) how many times/sec can you do this? (essentially this could be used
> to simulate opening and closing peepholes maybe even in a midcom kind
> environment)
>
> I will present my results at SUCON.

Looking forward to see your results.



How do you optimize this kind of lookups using u32?


Regards
Henrik

Re: tc filtering vs iptables

[jamal]

On Sat, 2004-08-28 at 03:08, Henrik Nordstrom wrote:
> On Sat, 27 Aug 2004, jamal wrote:
> 
> > A single web server (TCP port 80) connected to by upto 64K different
> > clients.
> > The reason i chose this simple setup is because i can plot its lookups
> > easily and write simple scripts to install rules.
> > So end goal: stash many rules in both u32 and iptables and check
> > results.
> 
> This test case is an exact match for using ippool/ipset. You then stash 
> all the client IP addresses into the pool and use a single iptable rule 
> with very good performance mostly independent on the number of IP 
> addresses.
> 
> iptables -d ip.of.web.server -p tcp --dport -m pool --srcpool webserver -j ACCEPT
> iptables -d ip.of.web.server -p tcp --dport -m pool -j REJECT

Ok, I will try this if i get the chance.
Again my point is that the above is not a proper test for what i want to
do. Primary goal is to have many many rules. 
As an example if i decided to vary something else in the header
which pool doesnt understand it will render it useless or i will have to
go and hack it to make it understand (ex offset 43 byte 1). My criteria
is not to be restricted like that. However, if this is something that
will give you really good results i would like to see the best i can get
out of iptables.

> > In this example setup src IP and src TCP port are always looked up in
> > the case of u32 and only when a match happens are the packets let
> > through - by default they are dropped. In the case of iptables, only the
> > src IP is looked up (didnt wanna add any overhead).
> 
> The overhead of looking up the destination ip and tcp port is minimal. Can 
> easily be done at the head of your lookup tree
> 
> iptables -d ip.of.web.server -p tcp --dport 80 -j WEBSERVER
> 
> then have the match tree for the client source IP addresses in WEBSERVER. 
> Remember to terminate each subchain with a REJECT/DROP in case there is no 
> match.
> 

I dont think the overhead of it will add a noticeable difference. So for
my tests i dont care. I may at some point add it when i have time later.
Theres less than 10 memory access and the computes are not the issue
since CPU is not my problem from what i gathered.

> > While all that traffic is being sent add then delete a totaly unrelated
> > rule. Two metrics:
> > 1) what packet rates are observed during add/del?
> 
> With iptables there should not be much difference, except that the higher 
> the packet load the slower the change take.

Actually its quiet noticeable.
At 4096 users (accept rules) inserted:
input 1.48Mps(eth0) --> accept rules --> 190Kpps, avg latency 12.4 ms
Start adding deleting a unused rule. 
output goes to 104Kpps, latency 23ms. And the add del/rate does not
exceed 5/sec.
Its almost unusable at 16384 rules so i didnt bother even recording
results. 

> If you use ippool then the overhead of this operation is considerably 
> less.

I hope to try this at some point.

> > 2) how many times/sec can you do this? (essentially this could be used
> > to simulate opening and closing peepholes maybe even in a midcom kind
> > environment)
> >
> > I will present my results at SUCON.
> 
> Looking forward to see your results.
> 
> 
> 
> How do you optimize this kind of lookups using u32?


u32 can have similar "chains" concept but the path selection of the next
chain is based on a hash that you define. The overall effect compared
to iptables is that even if you have similar jumps, u32 wuill end up
having less rules.
Like i said not a lot of effort was made in the case of u32 given
attempts to try and attempt to have a fair analysis. 
What would have been nice is for you guys to come up with the rules
for iptables - then i wouldnt have felt guilty optimizing u32 ;->

cheers,
jamal

Re: tc filtering vs iptables

[Henrik Nordstrom]

On Fri, 27 Aug 2004, Jamal Hadi Salim wrote:

> On Fri, 2004-08-27 at 14:45, jamal wrote:
>
>> Any recommendation of how i should arrange the chains?
>
> Ok, how does this sound:
>
> 256 chains:  subnet_0 .. subnet_255
>
> In each chain, there are 256 rules specifying a host in each
> (.0 ....255).
>
> This creates a maximum of 65536 rules with hosts from 10.1.0.0 to
> 10.1.255.255.

If you have the need of individually classifying all IP addresses in a 
whole 'B' network I would probably split it on a more granular level to 
keep the number of rules down to 16 or so per chain, this gives a worst 
case of 16 + 16 + 16 + 16 lookups which is a bit better than 256 + 256, 
and use ranges where possible to further cut down the number of rules.

How would this look like with the u32 thing in tc?

I think I have lost some of the picture of the classification you are 
trying to accomplish. Can you please describe it again?

Regards
Henrik