tsuchiya@thumper.bellcore.com (Paul Tsuchiya) (06/29/91)
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