Adrian Chadd wrote:
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 :)
You're right - point definitely taken. :)
Without wanting to get into a discussion about the relative merits of
sundry CS curricula: I didn't mean that the solution to this exact
problem, or close variants of it, are taught in introductory CS. What I
meant was more that the underlying, formal methodological intuitions are
taught, or at least should be taught, as far as I know, as a key
pedagogical point.
In other words, it ought to occur to someone doing this type of
implementation that subjecting thousands to tens of thousands of packets
per second to one or more sets of linear evaluations of arbitrary size
is going to be murderously inefficient, and that a different approach
should be taken.
I don't know a lot about the hardware anatomy of a lot of these devices,
and especially the ASIC-assisted software components. But I do know
their overall processing power is not typically very much, in the grand
scheme of things, as compared to commodity PC hardware, so if they are
handling some of the PPS loads we're discussing every day, then surely
the data structures in which these endless webs of ACLs are stored and
which are traversed when matching ACL criteria are not simple, naive
linear lists. I haven't done a detailed study, of course, and that
seems impossible to do without some access to IOS internals, but from an
intuitive perspective as a systems developer it seems computationally
impossible.
Of course, the fact that I, personally, find something counterintuitive
is no testament of any scientific credibility to its impossibility or
nonexistence. :)
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 know how they are parsed and evaluated from a superficial perspective.
Our observational language and our ontology about these rules is
founded to a great extent on the linear form and order of precedence
that those rules take in the user interface and the state machine that
is described to us.
What I was taking for granted is that in the back end of the packet
filter, implemented inside the cavernous interior of the kernel beyond
the reach of various APIs, libraries and state databases, these rules
take a very different form than what is handed to the user or accessor
in the representational realm. It seems fairly obvious that there must
be some very erudite, learned hashing or tree-building going on.
-- Alex
--
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@puck.nether.net
https://puck.nether.net/mailman/listinfo/cisco-nsp
archive at http://puck.nether.net/pipermail/cisco-nsp/
