This in only a rough draft - Megan 04/13/92

Minutes from the Routing Table Lookup BOF,
Wednesday at 7:00

The purpose of the meeting was simply to discuss the various
known approaches to software-driven routing table lookup algorithms.
There is no intention to meet again, and no documentation is
expected.  Presentations were given by the following:

Paul Tsuchiya 		Cecilia Algorithm
Joel Halpern		Patricia Algorithm
Keith Sklower		Radix Algorithm (in Unix BSD)
Rob Coltun		Binary Search Algorithm
Fred Baker		16-wide Radix Algorithm
Dino Farinacci		Hash Algorithm

Very briefly, Cecilia, Patricia, Sklower Radix, and 16-wide radix
are all radix-type algorithms, meaning that they follow the search
tree by branching according to the value of certain bits of the "key" 
(the address being looked up).  The three former algorithms check
one bit at a time, while the 16-wide checks 4 bits at a time.
The three former algorithms can check bits in any order, while the
16-wide checks bits strictly MSB to LSB.

The Binary Search Algorithm does a greater than/less than compare
to determine how to traverse the search tree.  The Hash Algorithm
is not a tree-based search algorithm as the first 5 are, and won't
be further discussed in these minutes.

Of the 6 algorithms, only Cecilia and Patricia handle non-contiguous
masks efficiently (meaning, a tree of small size and depth).
Sklower's Radix handles non-contiguous masks, but at the expense of
a larger depth.  Cecilia has an efficient delete operation, whereas
Patricia does not.  Patricia uses roughly 1/2 the memory of Cecilia.
Note that in most router applications, a delete operation is not
that important because routes don't appear and then disappear
forever often.  Occasionally reforming the tree from scratch for the
purpose of garbage collection suffices.  All of the algorithms can
handle contiguous masks, but the hash algorithm performance decreases
as the number of different sized masks increases.

Of the first 5 algorithms, only the Binary Search is balanced.
However, note that this is only with respect to the number of elements
in the tree, not with respect to the frequency with which each
element is searched.  Usually the 16-wide Radix will have the
smallest depth, because it covers 4 bits with a single compare
rather than just 1.  However, since it goes strictly left to right,
if the left bits do not differ in any of the routing table entries,
the 16-wide Radix can be deeper than the first 4 algorithms.