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

Tue Sep 9 02:21:18 EDT 2008

Such algorithms are indeed used, as you can see at the IOS reference
for the "access-list compiled" command where the ACL is converted to a
data structure that is O(1).

I don't know which algorithm they use in IOS nowadays, but for a very
good reference on all of those algorithms (using RAM or CAM), I
recommend this paper:

"Survey and Taxonomy of Packet Classification Techniques" by David E. Taylor:
http://www.cse.seas.wustl.edu/Research/FileDownload.asp?334

Rubens

On Tue, Sep 9, 2008 at 2:07 AM, Alex Balashov <abalashov at evaristesys.com> wrote:
> Are you serious?
>
> Well, I unhappily and disappointedly stand corrected, then.  Indeed, Cisco
> documentation appears to confirm what you and Bill are saying.
>
> There are a variety of known algorithms for traversing hashed structures
> while taking order of precedence into account.  I am, quite frankly,
> astonished that they are not used, or that it takes some sort of ASIC or
> TCAM enhancement to make that happen.
>
>
>
> Adrian Chadd wrote:
>
>> Bill is practically right. The semantics for Cisco ACLs aren't "here's a
>> set
>> of IP ranges, apply this behaviour", they're a linear walk of rules from
>> top to bottom applying behaviour at each step. Collapsing that into the
>> smallest set of possible operations is -not- taught at first/second year
>> computer science. Eg:
>>
>> * permit ssh 1.2.3.0/24
>> * deny ssh 1.2.4.8/30
>> * permit ssh 1.2.0.0/16
>> * deny ssh 1.0.0.0/8
>>
>> Please yank the first year computer science curriculum bit which provides
>> the student with the clue required to algorithmically determine the
>> smallest
>> set of permit/deny's keeping the above semantics correct. Then do some
>> basic
>> analysis to find out what the resource bounds are on determining that.
>> Oh, then prove that you can evaluate it in "more or less O(1) time". Go
>> on,
>> I dare you :) (Note: I -think- the TCAM ACL rule programming in later
>> IOSes
>> can do that? Perhaps Rodney or someone else from Cisco can comment.. :)
>>
>> There's some rule folding (and compiling?) stuff that I've heard about in
>> later software-forwarding IOSes which attempt to mitigate this somewhat
>> but
>> I've never really sat down and (ab)used it.
>>
>> Now, I suggest you go back and read how iptables / ipfw / pf rules
>> are actually -parsed- and -handled- in the various *NIXes you speak of.
>> I've done this exercise and I'll give you a hint - rules are evaluated
>> much the same as they are on the Cisco, except in some cases the
>> evaluation
>> doesn't stop at first hit and there are other gotchas (like "match X goto
>> rule
>> Y"). Go figure out why.
>>
>> I'll give you an even bigger hint - the best way to get a speedup under
>> *NIX packet filters is to build "sets" of IP addresses to apply your
>> policies
>> rather than individual rules for each network you want to allow SSH for.
>> The difference between one rule w/ a 200,000 network IP set versus 200,000
>> entries is pretty staggering - and the latter depends on the rule
>> ordering.
>> Just like Bill said. :)
>>
>>
>>
>>
>> Adrian
>>
>> On Tue, Sep 09, 2008, Alex Balashov 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.
>>>
>>> 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
>>> _______________________________________________
>>> 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
> _______________________________________________
> 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/
>