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 <[EMAIL PROTECTED]> 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 [email protected] >>>> 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 [email protected] >>> 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 [email protected] > https://puck.nether.net/mailman/listinfo/cisco-nsp > archive at http://puck.nether.net/pipermail/cisco-nsp/ > _______________________________________________ cisco-nsp mailing list [email protected] https://puck.nether.net/mailman/listinfo/cisco-nsp archive at http://puck.nether.net/pipermail/cisco-nsp/
