Newsgroups: comp.archives
Path: utzoo!utgpu!news-server.csri.toronto.edu!ox.com!msen.com!emv
From: tsuchiya@thumper.bellcore.com (Paul Tsuchiya)
Subject: [ietf] new routing table lookup algorithm
Message-ID: <1991Jun29.042500.25735@ox.com>
Followup-To: list.ietf
Sender: emv@msen.com (Edward Vielmetti, MSEN)
Reply-To: tsuchiya@thumper.bellcore.com (Paul Tsuchiya)
Organization: OTA Limited Partnership
References: <9106262053.AA21895@chiya.bellcore.com>
X-Original-Date: Wed, 26 Jun 91 16:53:55 -0400
Date: Sat, 29 Jun 1991 04:25:00 GMT
Approved: emv@msen.com (Edward Vielmetti, MSEN)
X-Original-Newsgroups: list.ietf
Lines: 60

Archive-name: internet/route/cecilia/1991-06-26
Archive: thumper.bellcore.com:/pub/cecilia.tar.Z [128.96.41.1]
Original-posting-by: tsuchiya@thumper.bellcore.com (Paul Tsuchiya)
Original-subject: new routing table lookup algorithm
Reposted-by: emv@msen.com (Edward Vielmetti, MSEN)



Hi gang,

I have written a new routing table lookup algorithm in the
spirit of patricia.  It is in the spirit of
patricia in the sense that it is a binary
search, and in that it can bounce around the
word being searched rather than just work left
to right.  I call it cecilia.

As such, it works with non-contiguous masks
in their full generality (including the "non-decidable"
case where there is not a single bit that can be
used to distinguish a group of entries, but
instead different pairs of entries use different
bits).

The reason I wrote the algorithm is as follows:
I wanted a search algorithm for use with my
Nat (Network address translator) box.  Of course,
it had to deal with non-contiguous masks (I couldn't
show my face in public if I implemented something that
couldn't work with non-contiguous masks).  I
started to use Joel Halpern's patricia code, but
realized that Nat does a LOT of delete operations,
and patricia doesn't have a delete operation.

So, cecilia has a delete operation.  Its other
advantages over patricia are that it can deal with
the non-decidable case, whereas patricia doesn't,
and that it probably produces on average a slightly
shallower tree, although I haven't done the 
measurements to show this for sure.

Anybody who wants to play with cecilia can anonymous
ftp over a tarfile that contains the code and
a short and roughly written overview of the algorithm
and how it is different from patricia.  I have
exercised the code pretty thoroughly on my kampai
simulator, so its pretty well flushed out.  I hope
to do more exercising soon, plus the comparisons
with patricia.

You can get it on thumper.bellcore.com, in directory
pub.  It is in the file cecilia.tar.Z.

PT

-- MSEN Archive Service file verification
thumper.bellcore.com
-rw-rw-rw-  1  4172     4172        37417 Jun 26 20:38 /pub/cecilia.tar.Z
found cecilia ok
thumper.bellcore.com:/pub/cecilia.tar.Z