Dynamically-optimized hash-based packet classifier
AssigneeMellanox Technologies, Ltd.
InventorGuy Mittelman
Life of this patent
Estimating the term…
Abstract
A network element includes multiple ports and a packet classifier. The packet classifier is configured to receive rules and Rule Patterns (RPs), each RP corresponding to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset, to store in a RAM a grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith, to receive packets and match each packet to one or more of the rules by accessing the ERPs in the RAM, to determine counter values, each counter value corresponding to a respective RP and is indicative of a number of the received packets that match the RP, and to adaptively modify grouping of the RPs into the ERPs depending on the counter values.
Claims18
A network element, comprising:
- multiple ports, configured to transmit and receive packets over a network;
- a packet classifier, configured to:
- receive a corpus of rules and a plurality of Rule Patterns (RPs), wherein each RP corresponds to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset;
- define, in a Random-Access Memory (RAM), multiple memory regions that are read sequentially one after another;
- store, in the multiple memory regions, a first grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith, and each ERP including multiple RPs;
- receive packets, and match each packet to one or more of the rules by accessing the ERPs in the RAM;
- estimate, for each RP from among at least some of the RPs, a respective number of the received packets that match the RP;
- and
- adaptively modify (i) the first grouping of the RPs into the ERPs responsive to the estimated numbers of received packets of the RPs and (ii) allocation of the ERPs to the memory regions, by:
- building a new ERP from RPs having an estimated number of received packets that is greater than the estimated number of received packets of the ERPs in the first grouping;
- forming a second grouping of the RPs into ERPs, which includes the new ERP;
- sorting the ERPs of the second grouping according to accumulated numbers of the received packets that match the RPs in the ERP;
- and
- allocating subsets of the sorted ERPs, in descending order of the accumulated numbers of the received packets, to respective ones of the memory regions;
- and
- a packet handler, configured to apply actions to the packets depending on matching of the packets to the rules.
A method, comprising:
- in a network element that transmits and receives packets over a network, receiving a corpus of rules and a plurality of Rule Patterns (RPs), wherein each RP corresponds to a subset of the rules and specifies positions of unmasked packet-header bits to be matched by the rules in the subset;
- defining, in a Random-Access Memory (RAM), multiple memory regions that are read sequentially one after another;
- storing, in the multiple memory regions, a first grouping of the RPs into Extended RPs (ERPs), each ERP defining a superset of the unmasked bits in the RPs associated therewith, and each ERP including multiple RPs;
- receiving packets, and matching each packet to one or more of the rules by accessing the ERPs in the RAM;
- estimating, for each RP from among at least some of the RPs, a respective number of the received packets that match the RP;
- adaptively modifying (i) the first grouping of the RPs into the ERPs responsive to the estimated numbers of received packets of the RPs and (ii) allocation of the ERPs to the memory regions, by:
- building a new ERP from RPs having an estimated number of received packets that is greater than the estimated number of received packets of the ERPs in the first grouping;
- forming a second grouping of the RPs into ERPs, which includes the new ERP;
- sorting the ERPs of the second grouping according to accumulated numbers of the received packets that match the RPs in the ERP;
- and
- allocating subsets of the sorted ERPs, in descending order of the accumulated numbers of the received packets, to respective ones of the memory regions;
- and
- applying actions to the packets depending on matching of the packets to the rules.
Dependencies are inferred from the claim text.