Routing on Longest-Matching Prefixes

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.