From owner-freebsd-net@FreeBSD.ORG Thu Dec 8 11:15:21 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 C30CF16A41F for ; Thu, 8 Dec 2005 11:15:21 +0000 (GMT) (envelope-from ivo.vachkov@gmail.com) Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.198]) by mx1.FreeBSD.org (Postfix) with ESMTP id E13F343D6D for ; Thu, 8 Dec 2005 11:15:05 +0000 (GMT) (envelope-from ivo.vachkov@gmail.com) Received: by xproxy.gmail.com with SMTP id s9so401400wxc for ; Thu, 08 Dec 2005 03:15:04 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ON+CghYTW1JrgT3z0ebuR7YAU8dFFrVCnmoevNZdC5FZF14kGirU72hsBW4b01b67m58fO99anHVctpx3CzqzTv5OMVcfypK4t55zdET8nCI4Si6xcjkVbtGKKMhhfgHJEO8rq0vbhhSq4vV278siBZLz8rew3nLf1FyPLbH5/Y= Received: by 10.70.60.2 with SMTP id i2mr3714613wxa; Thu, 08 Dec 2005 03:15:04 -0800 (PST) Received: by 10.70.110.4 with HTTP; Thu, 8 Dec 2005 03:15:04 -0800 (PST) Message-ID: Date: Thu, 8 Dec 2005 13:15:04 +0200 From: Ivo Vachkov To: Andre Oppermann In-Reply-To: <4397A2D1.452F290A@freebsd.org> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline References: <4397A2D1.452F290A@freebsd.org> Cc: freebsd-net@freebsd.org 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 11:15:22 -0000 > 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