From owner-freebsd-net@FreeBSD.ORG Thu Dec 8 12:06:37 2005 Return-Path: X-Original-To: freebsd-net@freebsd.org Delivered-To: freebsd-net@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id D3E7916A41F; Thu, 8 Dec 2005 12:06:37 +0000 (GMT) (envelope-from baldur@foo.is) Received: from gremlin.foo.is (gremlin.foo.is [194.105.250.10]) by mx1.FreeBSD.org (Postfix) with ESMTP id BAE2A43D90; Thu, 8 Dec 2005 12:06:16 +0000 (GMT) (envelope-from baldur@foo.is) Received: from 127.0.0.1 (unknown [127.0.0.1]) by injector.foo.is (Postfix) with SMTP id C7AA02842B; Thu, 8 Dec 2005 12:06:09 +0000 (GMT) Received: by gremlin.foo.is (Postfix, from userid 1000) id A41AA28427; Thu, 8 Dec 2005 12:06:05 +0000 (GMT) Date: Thu, 8 Dec 2005 12:06:05 +0000 From: Baldur Gislason To: Ivo Vachkov Message-ID: <20051208120605.GC779@gremlin.foo.is> References: <4397A2D1.452F290A@freebsd.org> In-Reply-To: User-Agent: Mutt/1.4.2.1i X-Spam-Checker-Version: SpamAssassin 3.0.4 (2005-06-05) on gremlin.foo.is X-Spam-Level: X-Spam-Status: No, score=-5.9 required=6.0 tests=ALL_TRUSTED,BAYES_00 autolearn=ham version=3.0.4 X-Sanitizer: Foo MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Disposition: inline Cc: freebsd-net@freebsd.org, Andre Oppermann Subject: Re: Programming Question: Policy Based Routing X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 08 Dec 2005 12:06:38 -0000 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" >