Ternary Content-Addressable Memory Assisted Packet Classification
AssigneeFuturewei Technologies, Inc.
InventorZixiong Wang
Life of this patent
Estimating the term…
Abstract
A method of packet classification implemented by a network router, the method comprising obtaining a packet whose header comprises a plurality of dimensional fields specified by a set of rules, matching one or more bits in at least two of the dimensional fields with a corresponding entry stored in a ternary content-addressable memory (TCAM), generating a hash key based on data associated with the corresponding entry in the TCAM, wherein the associated data is stored in at least one non-TCAM memory, searching, using the hash key, a multi-dimensional trie stored in the at least one non-TCAM memory, and mapping the packet to one or more of the set of rules based on the search.
Claims24
A method of packet classification implemented by a network router, the method comprising:
- obtaining a packet whose header comprises a plurality of dimensional fields specified by a set of rules;
- matching one or more bits in at least two of the dimensional fields with a corresponding entry stored in a ternary content-addressable memory (TCAM);
- generating a hash key based on data associated with the corresponding entry in the TCAM, wherein the associated data is stored in at least one non-TCAM memory;
- searching, using the hash key, a multi-dimensional trie stored in the at least one non-TCAM memory;
- and
- mapping the packet to one or more of the set of rules based on the search.
An apparatus comprising:
- a ternary content-addressable memory (TCAM) configured to store an entry for at least two of a plurality of dimensions specified by a set of rules;
- at least one non-TCAM memory configured to:
- store data associated with the entry in the TCAM;
- and
- a multi-dimensional trie for the at least two dimensions;
- a receiver configured to receive a packet comprising a plurality of fields in the plurality of dimensions;
- a processor that is coupled to the receiver, the TCAM, and the at least one non-TCAM memory and is configured to:
- match one or more bits in each of at least two of the fields with the entry;
- generate a hash key based on the data associated with the entry;
- search the multi-dimensional trie using the hash key;
- and
- map the packet to one or more rules in the set of rules based on the search.
A network router comprising:
- a ternary content-addressable memory (TCAM) configured to store a source address prefix and a destination address prefix;
- and
- a TCAM associated data (AD) table coupled to the TCAM and configured to store associated data for the source address prefix and the destination address prefix;
- a hashed subtrie table coupled to the TCAM AD table and configured to store a plurality of address prefixes represented by one or more subtries which belong to a multi-dimensional trie, wherein each subtrie is locatable by a hash key at least partially based on the associated data for each prefix stored in the TCAM;
- a product table coupled to the hashed subtrie table and configured to store pairs of labels assigned to the plurality of address prefixes;
- and
- a rule table coupled to the product table and configured to store rules each corresponding to a pair of labels in the product table.
Dependencies are inferred from the claim text.