Memory System for Optimized Search Access

摘要

A memory system and search method are provided for searching a multi-field longest prefix match (LPM) in a search term. The method provides a first LPM rule memory, where an LPM rule includes explicitly defined bit values in at least the n most significant bit (MSB) positions in a field of digital information, where n is an integer greater than or equal to 0. The method accepts a search term and compares at least a first field in the search term to subset rules structured in a sorted search tree for a first field organized as a LPM rule in the first LPM memory. When an explicit match is not found to the subset rules, the first field in the search term is compared to superset rules for the first field in the first LPM memory. As a final step, the method performs an instruction associated with a matching rule.

主权项

1. A memory system organized for optimized multi-field longest prefix match (LPM) search accessing, the system comprising:
a non-transitory first LPM rule memory, where an LPM rule includes explicitly defined bit values in at least the n most significant bit (MSB) positions in a field of digital information, where n is an integer greater than or equal to 0, the first LPM rule memory comprising:
subset rules structured in a sorted search tree for a first field organized as a LPM rule, where a subset rule is defined by a substring with at least one explicitly specified digital value that distinguishes the substring from every other rule substring in the first LPM memory; and,superset rules for the first field, where a superset rule is defined as a substring with a least one wildcard more than an associated subset rule, and having a digital value overlapping the associated subset rule digital value, where a wildcard may be any digital value.