Re: merging forwarding & packet filtering?

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 18 Feb 2011, at 14:43 , David Young wrote:
> make a hairpin turn to go out interface B, instead.  Once I have set
> up the forwarding the way I like it, the kernel forwarding table does
> such light duty on these routers that you almost but not quite toss it
> out[1].

I'm not sure I have an opinion on the exact question you are asking but
I'm pretty sure the reason you don't find much use for the forwarding
table is that it is already underused, and that by itself is worth
fixing.  There are routes which the destination (or destination/source)
address in a packet must be matched against stored all over the network
stack in all kinds of data structures.  When a packet arrives at ip_input()
its destination is first looked up in a hash table to see if it is a local
address.  Then it is compared to addresses attached to the interface to
see if it is a local network broadcast address.  Then it is checked to
see if it is a multicast address, and if so it is looked up in one kind
of table to see if it needs to be forwarded, and then another kind of
table to see if it is something of local interest.  It is then checked
to see if it is addressed to the all-one's or all-zero's address.  If
it gets this far only then is it looked up in the forwarding table.  Oh,
and I forget that fast forwarding cache thing that it gets looked up in
first, before all the rest, the existence of which is an admission that
the rest of this is pretty crappy.  It looks at the same header fields
over and over and over again in so many ways.

All of this stuff that is matched against the packet's destination/source
addresses needs to be collected into just one (or maybe two, but no
more) data structure(s), so when a packet arrives you do just one
lookup that tells you what you are dealing with.  This is maximally efficient,
and leaves you with just one data structure to make SMP-safe and fast.
And if the lookup you need to do can be implemented by a simple prefix match
against an N-bit (64 bits for IPv4, 256 bits for IPv6) destination/source
key from the packet, as all of the operations described above and done in
so many ways can be, there are data structures for this which are fast,
incrementally updatable and needn't lock out readers during updates.  And,
as a side effect, makes it 100 or more lines of code in ip_input which
do exactly the same thing but divide the problem up into a bunch of
serially-executed special cases go away.

Beyond this, however, I'll just point out that my experience has been
that there is an impedance mismatch between the requirements of
standard routing protocols and what I'll call the "policy forwarding"
normally associated with filters.  The needs of standard routing protocols
(and I include ARP and ND among them) are fully met by a simple prefix
lookup, but all standard routing protocols learn their routes incrementally
and really want to modify them that way.  More than this, since the
things that standard routing protocols learn about are generated by
computers talking to computers, they can sometimes change frequently
(particularly if you have a lot of routes), so in general they want
relatively simple and uniform operations done in structure which can
be incrementally updated at low cost.

"policy forwarding", on the other hand, generally can't be done with
a simple prefix match, and if you need it to go fast then the best
structures seem to depend on knowing all the data in the filter and
compiling it to get the result you need, i.e. fast and incremental
updates are normally mutually exclusive.  In practice this is okay,
however, since the information on which "policy forwarding" is based
generally originates from a human somewhere (the filter which implements
the policy might be generated by an automaton, but a human is normally
the ultimate source), and tends to change closer to human time, so the
fact that an update might require considerable computing resources to
compile isn't a big problem in practice.

To keep both types of users well served the structures which implement
standard routing (which must be there) and "policy routing" are generally
kept separate, preserving the scalability of the former while avoiding
implementation constraints that might exist in the latter if it needs
to serve users which want to do frequent, incremental updates.  If you
think you have a structure which can serve both without penalizing
one or the other that is great, but in my experience there is no way
to make one thing do both really well.

Dennis Ferguson