From owner-freebsd-net  Wed Oct  9 19:52:58 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 EFA3937B401; Wed,  9 Oct 2002 19:52:56 -0700 (PDT)
Received: from nuit.iteration.net (nuit.iteration.net [198.92.249.80])
	by mx1.FreeBSD.org (Postfix) with ESMTP
	id AF75743E65; Wed,  9 Oct 2002 19:52:56 -0700 (PDT)
	(envelope-from keichii@nuit.iteration.net)
Received: by nuit.iteration.net (Postfix, from userid 1001)
	id 30F9A11B641; Wed,  9 Oct 2002 19:47:30 -0700 (PDT)
Date: Wed, 9 Oct 2002 19:47:30 -0700
From: "Michael C. Wu" <keichii@iteration.net>
To: luigi@freebsd.org, darrenr@freebsd.org
Cc: freebsd-net@freebsd.org
Subject: DAWG for IPFW2/IPF
Message-ID: <20021010024730.GA25358@nuit.iteration.net>
Reply-To: "Michael C. Wu" <keichii@FreeBSD.org>
Mail-Followup-To: "Michael C. Wu" <keichii@iteration.net>,
	luigi@freebsd.org, darrenr@freebsd.org, freebsd-net@freebsd.org
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.3.28i
X-PGP-Fingerprint: 5025 F691 F943 8128 48A8  5025 77CE 29C5 8FA1 2E20
X-PGP-Key-ID: 0x8FA12E20
Sender: owner-freebsd-net@FreeBSD.ORG
Precedence: bulk
List-ID: <freebsd-net.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20freebsd-net>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20freebsd-net>
X-Loop: FreeBSD.org

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)

  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