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 fact
> > > 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 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. 
> 
> 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=TCP 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.

The interesting idea is, what do you plan for a hash collision?

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

	-is