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

[Alex Balashov]

Are you _sure_ that order is important in these ACLs?  I ask because I 
honestly don't know, so don't get me wrong.

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.

That's why such data gets stored in multidimensional and relational data 
structures:  things like binary trees (and their innumerable 
permutations), undirected string vector graphs for heavy lexical token 
matching, hash tables, and various relational mechanisms for forming 
bindings or indices from a quick and superficial glimpse at the data.

It's how every firewall/packet filtering engine (such as Linux 
netfilter, or the FreeBSD packet filter) is implemented, so packets are 
matched using a hashing strategy rather than linear, iterative comparisons.

What you appear to be suggesting in your dwelling upon the significance 
of rules being at the bottom or top of an access list definition would 
also imply that these basic algorithmic innovations and elements of the 
software engineering canon have somehow managed, with great finesse, to 
escape the notice of the people who wrote IOS.  I refuse to believe that.

bill fumerola wrote:

> [ reading through quickly, just some ACL pointers.. ]
> 
> On Mon, Sep 08, 2008 at 09:15:31PM +0100, Mateusz B?aszczyk wrote:
>> ! deny rogue IPs (it is interesting how many catches are here)
>> deny ip 10.0.0.0 .... any
>> deny ip 192... any
>> deny ip host 0.0.0.0 any
> 
> this breaks PMTUD. icmp messages from poorly addressed routers still
> need to get back to your hosts.
> 
>> etc....
>> ! deny spoofing us...
>> deny ip OURBLOCK1 any
>> deny ip OURBLOCK2 any
> 
> move to the top.
> 
>> ! pings and traceroute
>> permit icmp any any
> 
> either permit the specific ICMPs required for end to end communication
> to work and permit the rest after your anti-spoof, or just move this
> towards the top.
> 
>> permit udp any any range 32xxx 34xxx
> 
> rarely used, moved towards the bottom.
> 
>> ! transit providers
>> permit tcp host THEM1 host US1 eg bgp
>> permit tcp host THEM1 eq bgp host US1
>> ! Internet eXchanges - bgp/msdp
>> permit tcp THEM2 WCARD2 host US2  eg bgp
>> permit tcp THEM2 WCARD2 eq bgp host US2
>> deny ip any US1
>> deny ip any US2
> 
> rarely used, move towards bottom. consider removing the port-specific
> portions and see if you can get your ISP to use the TTL hack.
> 
>> ! some legacy stuff
>> permit ip any host XXX
> 
> move towards the top.
> 
>> ! deny access to infrastructure
>> deny ip any NETWORK_1
>> ...
>> deny ip any NETWORK_N
> 
> <hack>
> sometimes, you can null route these blocks and use policy route-maps
> that set next-hop for your local device and/or management networks
> that allow the forwarding plane take care of discarding these
> </hack>
> 
>> permit ip any any
> 
> and here's where the majority of your traffic matches - at the bottom.
> this will kill performance. consider the trade-off of adding a:
> 
> permit tcp any any established
> 
> towards the top of your config. that rule will catch the majority of
> most networks' traffic. your deny rules below will still prevent SYN
> packets from getting through to your infrastructure space. yes, your
> 'infrastructure' will be open to ACK floods and other such things, but
> you can deploy other measures to assist with that. for example: ACLs on
> the interfaces facing your management network instead.
> 
> also, if you run a service that represents the bulk of your traffic on
> that device, add a short-circuit rule for that service higher at the
> top, even if a rule with wider reach allows the same later.
> 
>> any significant advantage over entry-level 6500/7600?
> 
> 6500/7600 will be way less order dependent and you'll be able to have
> much longer ACLs. in my experience, on software platforms 99% of your
> traffic should either be permitted or denied in the first 5 or so rules
> or you're going to see serious performance problems.
> 
> consider using 'access-list compiled' if your platform/IOS support it.
> 
> distribute your ACLs as much as possible. take a multi layered approach.
> know your device's strengths and weaknesses when it comes to filtering
> and exploit those.
> 
> -- bill
> _______________________________________________
> 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/


-- 
Alex Balashov
Evariste Systems
Web    : http://www.evaristesys.com/
Tel    : (+1) (678) 954-0670
Direct : (+1) (678) 954-0671
Mobile : (+1) (706) 338-8599