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

[Alex Balashov]

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