Data structure for longest-matching prefix searching and updating method for search table data structures

Abstract

In a system for finding output information such as an output link identification, by a longest-matching prefix search in response to a search key, only a search data structure comprising search tables is provided which is derived from a basic data structure comprising detailed prefix tables. The full basic data structure need not be maintained, but auxiliary information is provided in the search tables of the search data structure to enable reconstruction of relevant portions of the basic data structure when updates have to be made. In an updating procedure, first the relevant search tables are found and then reconverted to the associated prefix tables from which they were derived. Updating is performed on the reconstructed prefix tables which are then reconverted into search tables to be inserted into the search data structure, for replacing or supplementing search tables that required updating.

Dependencies are inferred from the claim text.