Routing on Longest-Matching Prefixes

Copyright [©] (1996) by IEEE. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distrubuted for profit. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.

This article describes the {\em Dynamic Prefix Tries% \footnote{{\em trie\/} as in re{\em trie\/}val.}\/} - a novel data structure with algorithms for insertion, deletion and retrieval to build and maintain a dynamic database of binary keys of arbitrary length. These tries extend the concepts of compact digital (Patricia) tries to support the storage of prefixes and to guarantee retrieval times at most li near in the length of the input key irrespective of the trie size, even when search ing for longest-matching prefixes. The new design permits very efficient, simple and non-recursive implementation s of small code size and minimal storage requirements. Insert and delete operati ons have strictly local effects, and their particular sequence is irrelevant for the structure of the resulting trie, thus maintaining at all times the desired storage and computational efficiency. The algorithms have been successfully employed in experimental communication systems and products for a variety of networking functions such as address resolution, maintenance and verification of access control lists, and high-performance routing tables in operating system kernels. \begin{keywords} Trie, binary trie, Patricia trie, dynamic prefix trie, DP-Trie, routing table, address prefixes, longest matching prefix, searches, pattern matching , dictionary, address resolution, access control lists.

By: Willibald Doeringer, Guenter Karjoth and Mehdi Nassehi

Published in: IEEE/ACM Transactions on Networking, volume 4, (no 1), pages 86-97 in 1996

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .