From owner-freebsd-net Wed Oct 9 20:37:53 2002 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 23A4837B411; Wed, 9 Oct 2002 20:37:50 -0700 (PDT) Received: from carp.icir.org (carp.icir.org [192.150.187.71]) by mx1.FreeBSD.org (Postfix) with ESMTP id 933BE43E4A; Wed, 9 Oct 2002 20:37:50 -0700 (PDT) (envelope-from rizzo@carp.icir.org) Received: from carp.icir.org (localhost [127.0.0.1]) by carp.icir.org (8.12.3/8.12.3) with ESMTP id g9A3boO2056145; Wed, 9 Oct 2002 20:37:50 -0700 (PDT) (envelope-from rizzo@carp.icir.org) Received: (from rizzo@localhost) by carp.icir.org (8.12.3/8.12.3/Submit) id g9A3bo8k056144; Wed, 9 Oct 2002 20:37:50 -0700 (PDT) (envelope-from rizzo) Date: Wed, 9 Oct 2002 20:37:50 -0700 From: Luigi Rizzo To: "Michael C. Wu" Cc: darrenr@FreeBSD.ORG, freebsd-net@FreeBSD.ORG Subject: Re: DAWG for IPFW2/IPF Message-ID: <20021009203750.A55843@carp.icir.org> References: <20021010024730.GA25358@nuit.iteration.net> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <20021010024730.GA25358@nuit.iteration.net>; from keichii@iteration.net on Wed, Oct 09, 2002 at 07:47:30PM -0700 Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.org On Wed, Oct 09, 2002 at 07:47:30PM -0700, Michael C. Wu wrote: > Hi Luigi and Darren, > > Regarding IPFW2 and IPF, do you have plans on implementing a DAWG algorithm > for the pattern matching? (Directed Acyclic Word Graphs) my quick answer is no -- it might be interesting stuff, but have too much stuff on my plate... cheers luigi > http://citeseer.nj.nec.com/crochemore99fast.html > > It is a new algorithm that does super fast multiple stream/pattern > matching in a given n-length string within O(n) . > The traditional fastest Knuth algorithm only does > two streams, while DAWG's do multiple streams. We use it in > Bioinformatics research to match DNA sequences. However, I know > for a fact that applying DAWG's to router/firewall situations > would be very appropriate. > > Forgive my not knowing about our regex(3) implementation, > what algorithm exactly does our regex(3) do/use? > > I was thinking that we may possibly add kernel/userland libraries > for a DAWG regex. And I am willing to do the work. > > What do you think? Does anyone else have thoughts about this? > > Thanks, > Michael > > To Unsubscribe: send mail to majordomo@FreeBSD.org > with "unsubscribe freebsd-net" in the body of the message To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message