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

[Matt Carter]

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

in regards to shortcut ACL's i seriously doubt any time in the near future IOS is going to help you in this regard.

do some netflow analysis and work out your traffic mix, look at your security requirements and develop an ACL that encompasses both considerations.