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

[Alex Balashov]

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?

Matt Carter wrote:

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