Date: Thu, 8 Dec 2005 12:06:05 +0000 From: Baldur Gislason <baldur@foo.is> To: Ivo Vachkov <ivo.vachkov@gmail.com> Cc: freebsd-net@freebsd.org, Andre Oppermann <andre@freebsd.org> Subject: Re: Programming Question: Policy Based Routing Message-ID: <20051208120605.GC779@gremlin.foo.is> In-Reply-To: <f85d6aa70512080315k7861b9f8w@mail.gmail.com> References: <f85d6aa70512071854h1b41f10o@mail.gmail.com> <4397A2D1.452F290A@freebsd.org> <f85d6aa70512080315k7861b9f8w@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
You know you can do policy routing with IPFW. ipfw add fwd 172.20.0.1 ip from 172.20.0.0/24 to not 172.20.0.0/24 for example. Baldur 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: > - 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 > _______________________________________________ > freebsd-net@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-net > To unsubscribe, send any mail to "freebsd-net-unsubscribe@freebsd.org" >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20051208120605.GC779>