Prefix optimizations for a network search engine

摘要

A network router comprising at least one index table operable to store encoded values of a function associated with an input source address in at least two locations. The encoded values are obtained by hashing the input source address such that all the encoded values must be used to recover the function. At least one filtering table is provided that is operable to store prefixes of at least two different lengths, the prefixes corresponding to network addresses. The filtering table is indexed by entries in said index table. At least one result table is provided. The result table is operable to be indexed by entries in said index table. The result table stores destination addresses. At least one record in the filtering table has a prefix length field that is operable to store a prefix length of a prefix stored in said at least one record.