Back to results
US 7,734,811 B2Granted
Multi-feature classification memory structure for associative matching
AssigneeCisco Technology, Inc.
InventorDavid R. Cheriton
Life of this patent
Estimating the term…
Abstract
The present invention describes a method and an apparatus of multi-feature lookup process using multi-feature classification memory (“CM”). In one embodiment of the present invention, the method defines various features, offered in the router, into a feature hierarchy. Individual associated CMs are merged into a combined associated multi-feature CM. The feature rules for packet processing are merged according to the feature hierarchy and the multi-feature CM is populated with the merged rules. The multi-feature CM includes combined packet-processing rules for multiple features. The multi-feature CM eliminates the need for individual associated CMs. The memory space in the multi-feature CM is shared by various feature rules.
Claims51
A method of processing a packet in a router comprising:
- creating a plurality of multi-feature packet processing rules, wherein
- said creating comprises, for each multi-feature packet processing rule of said multi-feature packet processing rules,
- forming said each multi-feature packet processing rule by merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature, and
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy;
- populating said plurality of multi-feature packet processing rules in a multi-feature classification memory;
- populating an associated content-addressable memory with a plurality of indices, wherein
- said indices are indices of said plurality of multi-feature packet processing rules in said multi-feature classification memory,
- said associated content-addressable memory and said multi-feature classification memory are associated with one another by virtue of said associated content-addressable memory being coupled to provide an index of said indices to said multi-feature classification memory, and
- each of said indices corresponds to at least one of said multi-feature packet processing rules;
- using said index to retrieve a multi-feature packet processing rule from said multi-feature classification memory;
- and
- processing said packet according to said multi-feature packet processing rule.
13 more elements
A method of processing a packet in a router comprising:
- identifying a classification of said packet in a content-addressable memory;
- causing said content-addressable memory to provide an index of a plurality of indices to a multi-feature classification memory, wherein said index corresponds to said classification;
- and
- locating a multi-feature packet processing rule in a multi-feature classification memory, wherein
- said multi-feature packet processing rule is created by
- forming said multi-feature packet processing rule by merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature,
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy,
- said locating uses said index, and
- said content-addressable memory and said multi-feature classification memory are coupled to one another by virtue of said content-addressable memory being coupled to provide said index to said multi-feature classification memory.
10 more elements
A packet processing rule lookup system for processing a packet in a router, comprising:
- a multi-feature classification memory, wherein
- said multi-feature classification memory is configured to store a plurality of multi-feature packet processing rules,
- each of said multi-feature packet processing rules comprises a merged set of features,
- said merged set of features comprise a plurality of features of a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- each said merged set of features is formed by merging features of said set of features according to said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature,
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy, and
- said each of said multi-feature packet processing rules is configured to allow said packet to be processed with regard to a set of said features corresponding to said each of said multi-feature packet processing rules;
- and
- a content-addressable memory coupled to said multi-feature classification memory, wherein
- said content-addressable memory is configured to store a plurality of indices, and
- each of said indices corresponds to at least one of said plurality of said multi-feature packet processing rules.
12 more elements
A network element comprising:
- means for creating a plurality of multi-feature packet processing rules, wherein
- said means for creating comprises, for each multi-feature packet processing rule of said multi-feature packet processing rules,
- means for forming said each multi-feature packet processing rule by merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature, and
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy, and
- means for populating said plurality of multi-feature packet processing rules in a multi-feature classification memory;
- means for populating an associated content-addressable memory with a plurality of indices, wherein
- said indices are indices of said plurality of multi-feature packet processing rules in said multi-feature classification memory,
- said associated content-addressable memory and said multi-feature classification memory are associated with one another by virtue of said associated content-addressable memory being coupled to provide an index of said indices to said multi-feature classification memory, and
- each of said indices corresponds to at least one of said multi-feature packet processing rules;
- means for using said index to retrieve a multi-feature packet processing rule from said multi-feature classification memory;
- and
- means for processing said packet according to said multi-feature packet processing rule.
13 more elements
A network element comprising:
- a content-addressable memory;
- means for identifying a classification of said packet in said content-addressable memory;
- means for causing said content-addressable memory to provide an index of a plurality of indices to a multi-feature classification memory, wherein said index corresponds to said classification;
- and
- means for locating a multi-feature packet processing rule in a multi-feature classification memory, wherein
- said means for locating comprises a means for forming said multi-feature packet processing rule,
- said means for forming comprises means for merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature,
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy,
- said means for locating is configured to use said index, and
- said content-addressable memory and said multi-feature classification memory are coupled to one another by virtue of said content-addressable memory being coupled to provide said index to said multi-feature classification memory.
11 more elements
A computer program product comprising:
- a set of instructions executable on a computer system, wherein
- said computer program product is configured to process a packet by virtue of said program product comprising said set of instructions, and
- said set of instructions is configured to
- create a plurality of multi-feature packet processing rules, wherein
- said set of instructions configured to create comprises a subset of instructions configured to, for each multi-feature packet processing rule of said multi-feature packet processing rules,
- form said each multi-feature packet processing rule by merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature, and
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy,
- populate a plurality of multi-feature packet processing rules in a multi-feature classification memory, and
- populate an associated content-addressable memory with a plurality of indices, wherein
- said indices are indices of said plurality of multi-feature packet processing rules in said multi-feature classification memory,
- said associated content-addressable memory and said multi-feature classification memory are associated with one another by virtue of said associated content-addressable memory being coupled to provide an index of said indices to said multi-feature classification memory, and
- each of said indices corresponds to at least one of said multi-feature packet processing rules:
- using said index to retrieve a multi-feature packet processing rule from said multi-feature classification memory, and
- processing said packet according to said multi-feature packet processing rule;
- and
- computer readable storage media, wherein said computer program product is encoded in said computer readable storage media.
17 more elements
A computer program product comprising:
- a set of instructions executable on a computer system, wherein
- said computer system comprises a content addressable memory,
- said computer program product is configured to process a packet by virtue of said program product comprising said set of instructions, and
- said set of instructions is configured to
- identify a classification of said packet in said content-addressable memory,
- causing said content-addressable memory to provide an index of a plurality of indices to a multi-feature classification memory, wherein said index corresponds to said classification, and
- locate a multi-feature packet processing rule in a multi-feature classification memory, wherein
- said multi-feature packet processing rule is created by
- forming said multi-feature packet processing rule by merging a plurality of features according to a feature hierarchy,
- each of said features is defined in said feature hierarchy,
- at least one of said features in said feature hierarchy comprise another of said features in said feature hierarchy,
- said at least one of said features in said feature hierarchy is a complex feature,
- said another of said features in said feature hierarchy is a simple feature,
- said at least one of said features in said feature hierarchy subsumes said another of said features in said feature hierarchy,
- said locating uses said index, and
- said content-addressable memory and said multi-feature classification memory are coupled to one another by virtue of said content-addressable memory being coupled to provide said index to said multi-feature classification memory;
- and
- computer readable storage media, wherein said computer program product is encoded in said computer readable storage media.
15 more elements
Dependencies are inferred from the claim text.