[c-nsp] NPE G1, CEF and ACLs and high CPU

[Kristian Larsson]

On Tue, Sep 09, 2008 at 04:04:46AM -0400, Alex Balashov wrote:
> Just to be clear, in case it isn't, I was not referring to how the ACLs are 
> organised from the user perspective, presentation-wise, but rather I was 
> surprised that they are not all put into an optimised data structure on the 
> back side by IOS by default so that matching can happen with somewhere 
> between O(1) and O(n) performance.
> 
> Thank you all for the enlightenment on compiled/turbo ACLs.
> 
> It makes me wonder whether the reason why routers are generally considered 
> a poorer solution for extensive ACL duty than PIXs or ASAs. Does the PIX 
> use compiled ACLs by default?  Or perhaps there is some sort of extremely 
> helpful ACIC-driven optimisation that they provide?

Cisco IOS (without the firewall feature set)
doesn't really support stateful firewalls, but is 
rather a fixed set of filters applied to packets.
PIX / ASA does stateful packet inspection and some
other mumbo jumbo that security people like to
have. I think that would be the #1 reason of why
one would choose a PIX over an IOS device.

I have no clue whether they're actually faster or
not at filtering packets.

  -K


>>> Are you _sure_ that order is important in these ACLs?  I ask because I
>>> honestly don't know, so don't get me wrong.
>> yes it is.. i have seen software based platforms knock 10-20% cpu off by 
>> reworking very poorly laid out ACL's in a "top down" fashion.
>>> It just seems rather unlikely.  Organising data like that into
>>> structures where matching and access can happen at more or less an O(1)
>>> formal computational complexity is a basic skill that is taught at the
>>> beginning of any undergraduate curriculum in computer science.
>>> Students
>>> are taught to understand that large amounts of random (non-sorted) data
>>> cannot be stored in a linear structure, and that even linear structures
>>> with comparatively few elements (such as an access list) can be very
>>> slow if the lookup is repeated with very great frequency.
>> aren't we doing some kind of eval on our current lists before applying a 
>> new one? like i'm thinking
>> 1) fire up the ACL leave it running for a while, look at the number of 
>> hits per ACL entry, and rework the ACL such that the maximum number of 
>> hits is at the top.
>> 2) shortcut ACL's as bill mentioned
>> eg, consider the following ACL
>> 5 deny udp host
>> 10 deny udp host
>> 20 deny udp host
>> 25 permit ip any
>> presume that 60% of your traffic is TCP. all of this traffic is having to 
>> drop through 3 denies before it gets permitted. you could save a 
>> significant amount of processing by simply putting
>> 1 permit tcp
>> 5 deny udp host
>> 10 deny udp host
>> 20 deny udp host
>> 25 permit ip any
>> sure, you are doubling up in what is permitted because the TCP would have 
>> hit the permit ip any at the bottom anyway, but you are saving a 
>> considerable amount of processing by having 60% of your traffic match the 
>> first ACL entry. sure, oversimplified, but if you can't permit tcp 
>> outright, consider a permit established before you start denying other tcp 
>> bits and pieces, because more often than not the majority of traffic being 
>> forwarded is established.
>> so in regards to having IOS reorganise the ACL for you that would have to 
>> make the assumption that the IOS has the capability to work out what is 
>> the ACL entries that are getting the most matches, in order to reorganise 
>> them, it isnt going to be able to predict this for you.
> 
> 
> -- 
> Alex Balashov
> Evariste Systems
> Web    : http://www.evaristesys.com/
> Tel    : (+1) (678) 954-0670
> Direct : (+1) (678) 954-0671
> Mobile : (+1) (706) 338-8599
> _______________________________________________
> cisco-nsp mailing list  cisco-nsp at puck.nether.net
> https://puck.nether.net/mailman/listinfo/cisco-nsp
> archive at http://puck.nether.net/pipermail/cisco-nsp/

-- 
Kristian Larsson                                        KLL-RIPE
Network Engineer / Internet Core        Tele2 / SWIPnet [AS1257]
+46 704 910401			              kll at spritelink.net