Programming Question: Policy Based Routing

Claudio Jeker cjeker at diehard.n-r-g.com
Thu Dec 8 08:12:54 PST 2005


On Thu, Dec 08, 2005 at 01:15:04PM +0200, Ivo Vachkov wrote:
> > Normally it's the other way around.
> 
> So be it :)
> 
> My definition of Policy-Based Routing (PBR): ability make routing
> decision based on information other than destination IP address in the
> packet. In my project this "other" information includes source ip
> address, L4 protocol, tos, packet length.
> 
> Implementation:
> 
> Plan 1) This is complex standalone solution implemented entirely in
> the kernel, plus userland utilities (like the route command). Whole
> current routing engine will be changed. Instead of Patricia tree I
> implement a list of data structures, each one including special mask
> which identifies what field of the IP header are used to match the
> packet and an AVL tree to store routing information in it. Algorithm
> is simple:

An AVL tree is far from optimal for route lookups -- think about longest
prefix matches. It is even worse than a Patricia tree.
Also doing the packet classification as part of the route lookup is IMO a
bad idea. Also the linear list that needs to be traversed for every packet
is very expensive because you can only do one comparison at a time.

> Plan B) *Somehow very Linuxish* Using some sort of packet classifier
> (for example packet filter matching code) it marks the packet with a
> some user defined value. Example:
>     ipfw add mark 10 ip from 192.168.0.0/24 to 192.168.10.0/24
> and:
>     pbr_route add -mark 10 $gateway
> The kernel implementation should check for such marks on every packet
> and search them in a binary search tree (AVL probably).
> 
> That's it. Please, excuse my bad english and poor explanations. If you
> have any questions I'll try to explain better, probably using more
> examples.
> 

This is a better approach and much simpler. Pf and IPFW have a
powerful classifier and with tables, states, ...  it is possible to reduce
the classification time significantly.

-- 
:wq Claudio


More information about the freebsd-net mailing list