Programming Question: Policy Based Routing

G Bryant bsd at roamingsolutions.net
Thu Dec 8 21:48:04 PST 2005


   Ivo Vachkov wrote:

2005/12/8, Claudio Jeker [1]<cjeker at diehard.n-r-g.com>:


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.


I am aware that this part sux :) That's why I'm asking for other
people's opinions.



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.



   I am currently using a solution with 5.4 where different packets get
   routed out different routes.
   I'm using IPFW and according to protocol or source IP (but IPWF can
   recognise any IP header criteria you like), I then FWD the packets to
   the specific gateway required.
   For this solution to work, you need to make all the gateways available
   from a single external NIC (or multiple NIC's that have been
   ng_hook'd).
   Let me know if you would like an example ipfw script.

However this binds the code with some external software. Further more,
what should i use to "mark" packets originating from the host ... at
some point it get too complex to configure, many rules should be to
written just to get it working ...



--
:wq Claudio
_______________________________________________
[2]freebsd-net at freebsd.org mailing list
[3]http://lists.freebsd.org/mailman/listinfo/freebsd-net
To unsubscribe, send any mail to [4]"freebsd-net-unsubscribe at freebsd.org"



_______________________________________________
[5]freebsd-net at freebsd.org mailing list
[6]http://lists.freebsd.org/mailman/listinfo/freebsd-net
To unsubscribe, send any mail to [7]"freebsd-net-unsubscribe at freebsd.org"

References

   1. mailto:cjeker at diehard.n-r-g.com
   2. mailto:freebsd-net at freebsd.org
   3. http://lists.freebsd.org/mailman/listinfo/freebsd-net
   4. mailto:freebsd-net-unsubscribe at freebsd.org
   5. mailto:freebsd-net at freebsd.org
   6. http://lists.freebsd.org/mailman/listinfo/freebsd-net
   7. mailto:freebsd-net-unsubscribe at freebsd.org


More information about the freebsd-net mailing list