From owner-freebsd-net@FreeBSD.ORG Thu Dec 8 16:12:54 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 CFFBC16A423 for ; Thu, 8 Dec 2005 16:12:54 +0000 (GMT) (envelope-from cjeker@diehard.n-r-g.com) Received: from diehard.n-r-g.com (diehard.n-r-g.com [62.48.3.9]) by mx1.FreeBSD.org (Postfix) with ESMTP id DA83943D4C for ; Thu, 8 Dec 2005 16:12:42 +0000 (GMT) (envelope-from cjeker@diehard.n-r-g.com) Received: (qmail 31093 invoked by uid 1001); 8 Dec 2005 16:12:45 -0000 Date: Thu, 8 Dec 2005 17:12:23 +0100 From: Claudio Jeker To: freebsd-net@freebsd.org Message-ID: <20051208161245.GB19179@diehard.n-r-g.com> Mail-Followup-To: Claudio Jeker , freebsd-net@freebsd.org References: <4397A2D1.452F290A@freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.8i 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 16:12:54 -0000 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