On 6/30/05, Ignatios Souvatzis <is@netbsd.org> wrote:
> On Thu, Jun 30, 2005 at 12:06:11PM +0200, Ivo Vachkov wrote:
> > 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:
> > >
> > > > 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 f=
act
> > > > I'm not approved by Google. Community interested ??? Or I could
> > > > probably do it for FreeBSD/OpenBSD.
> > >
> > > I'm interested in this, but you told very few details about your proj=
ect.
> > > 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.
> >
> > 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.
>=20
> The interesting idea is, what do you plan for a hash collision?

I think to "dig" in the theory about that :)=20

> And why any tree at all, and not using the hash as an index to an
> array?

Because using static hash array would consume too much memory in
kernel ... consider support for full BGP view with about 150k routes
... which sould be allocated for every device. While using dynamic
data structure it can expand only when needed.

>         -is
>=20


--=20
"UNIX is basically a simple operating system, but you have to be a
genius to understand the simplicity." Dennis Ritchie