On 6/30/05, Pavel Cahyna <pavel.cahyna@st.mff.cuni.cz> wrote:
> On Sun, 26 Jun 2005 01:39:50 +0200, Ivo Vachkov wrote:
>=20
> > Hi all,
> >
> > I just want to ask will there be some to work on Policy Routing for
> > NetBSD because I really want to work on that project, despite the fact
> > I'm not approved by Google. Community interested ??? Or I could
> > probably do it for FreeBSD/OpenBSD.
>=20
> I'm interested in this, but you told very few details about your project.
> How will the rules for your policy routing look like? You mentioned
> extending struct rtentry. How will the routing table look like then?
> Currently it is a tree which looks up routes according to destination
> address. I don't see how it would use additional criteria like source
> address or TOS.

Let start with some thoughts. Currently we have only 1 type of routing
rules - routes to destination. And we have Radix Tree to seach in. If
you try to add second type of rules you must start with a whole new
structure to represent them - probably another tree. And so on for
every new type of routing rules. Well, assuming that was "easy" part
we're now facing the "hard" part - how to decide where to route packet
if it maches entries in both (or more) trees. No simple answer ...
This is somehow close to Linux implementation with multiple tables ...

But this is not the best solution according to me.=20

Learning from BSD code (and some proffesional experience) I think
there is better solution to implement policy routing. For example we
have following scenario:

route add -dst 192.168.0.0/24 -src 192.168.1.0/24 -proto tcp
172.16.0.1 (route all packets to 192.168.0.0/24 comming from
192.168.1.0/24 with L4 proto=3DTCP over 172.16.0.1).

The problem is obvious - kernel should examine each packet's src, dst
and proto over some structures.
And here come the solution - we should use ONLY ONE !!! This is the
only way to keep current routing performance.

Next problem: How to represent many, many different combinations of
routing rules in a common manner ???
And the answer - HASHING !!! :)

Using the route command before kernel gets following info:
- dst - 192.168.0.0/24
- src - 192.168.1.0/24
- TOS - any
- L4 Proto - TCP (6)
- Length - any

Now we use some hash function over all these values and get unique
value for that routing entry that corresponds to gateway 172.16.0.1.
We use this pair (hash value <-> gateway address) as key <-> value in
RADIX or AVL tree.

On each outgoing packet we calculate it's hash over the IP Header
fields, search that value in the table (tree) and route it over the
gateway for that hash. If we meet "no match", we (the kernel) use
default route.

This is the main idea. I know some parts are not explained clearly,
but I'm in a middle of some term exams, not much time to "polish" the
algorithm :) Basicly, there will be overhead in the routing code, but
it'll depend on the speed of the hash function.

> Linux seems to have the routing table mostly unmodified, but there can be
> multiple such tables and a system of rules then determine which one will
> be used. Isn't this an easier alternative to extending the routing table
> itself? (see www.lartc.org)
>
> Bye     Pavel
>=20
>=20
--=20
"UNIX is basically a simple operating system, but you have to be a
genius to understand the simplicity." Dennis Ritchie