Programming Question: Policy Based Routing

Ivo Vachkov ivo.vachkov at gmail.com
Thu Dec 8 03:15:22 PST 2005


> 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:
- when user wants to add a rule:
    pbr_route add -source 192.168.0.0/24 -proto tcp $gateway
first thing is to create a generic route mask. This is a bit mask like this:
    source address        -> 1
    destination address -> 0
    protocol                    -> 1
    tos                            -> 0
    length                       -> 0
so, our mask is "10100". Then the kernel's list of routing structures
is checked for a structure with that mask. If not found, a new one is
created. When found/created a special hash function is used to compute
a hash value on the fields, the mask points (in the example - source
and protocol). This hash value and the $gateway form a node which is
inserted in the AVL tree.
- when a packet comes:
    since the data structures are sorted by their masks in a
descending order we have sorted list, most precise matching rules,
closest to the head of the list. When a packet is about to be routed,
for each of the data structures of the list, we apply the structure's
mask to find what combination of characteristics form the routing in
this structures. Then we compute the hash and search it in the AVL
tree. If we find it -> we find the $gateway where the packet should be
routed to.
There is one problem however. It is the netmask processing. In this
algorithm they're "included" really ugly :) For each structure with
source/destination/both type of rules i store one linked list with
netmasks only. When a packet processing comes to that structure it
enters a new loop -> for each netmask/pair of netmasks, apply the
netmask to the source/destination, then compute a hash value and
search it in the AVL tree.

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.

    Ivo Vachkov


More information about the freebsd-net mailing list