Optimized hash-based ACL lookup offload
AssigneeArista Networks, Inc.
InventorsHugh W. Holbrook, Francois Labonte
Life of this patent
Estimating the term…
Abstract
Described herein are various embodiments of a network element including an access control list processing module to process an access control list of the network element. In one embodiment, the access control list processing module converts the access control list into set of subsections of rules, where each rule of a subsection mutually exclusive of each other rule in the subsection. The network element may then make forwarding decisions for network data using the set of subsections of rules. In one embodiment, semantics preserving transformations can be applied to rules and data to enable more efficient processing of filtering or rules.
Claims42
A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform operations to convert an access control list into a set of subsections of access control entries, the operations comprising:
- receiving an access control list of access control entries, wherein each of the access control entries includes a network data characteristic and an action;
- converting a first portion of the access control list into a first set of subsections of rules, wherein each rule of a subsection is mutually exclusive of each other rule in the subsection to allow matching without ordering of the rules;
- storing a second portion of the access control list into an associative data structure including a set of entries, wherein each member of the set of entries has an associated mask and each associated mask of each member is different;
- and
- storing a description of each of the subsections in the first set of subsections of rules, wherein the descriptions and the first set of subsections of rules are used by the network element to make a packet processing decision for network data.
A method to convert an ordered access control list into a set of subsections of access control entries, the method comprising:
- receiving an access control list of access control entries, wherein each of the access control entries includes a network data characteristic and an action;
- converting a first portion of the access control list into a first set of subsections of rules, wherein each rule of a subsection is mutually exclusive of each other rule in the subsection to allow matching without ordering of the rules;
- storing a second portion of the access control list into an associative data structure including a set of entries, wherein each member of the set of entries has an associated mask and each associated mask of each member is different;
- and
- storing a description of each of the subsections in the first set of subsections of rules, wherein the descriptions and the first set of subsections of rules are used by the network element to make a packet processing decision for network data.
A network element including:
- non-associative memory;
- an access control list processing module to process an access control list associated with the network element, the access control list processing module to convert the access control list into multiple sets of subsections of rules, each rule of a subsection mutually exclusive of each other rule in the subsection to allow matching without ordering of the rules, and to store the subsections of rules in the non-associative memory;
- and
- packet processing logic to make packet processing decisions for network data received via a port of the network element using the set of subsections of rules, the packet processing logic to evaluate a first set of subsections of rules stored in one or more hash tables and a second set of subsections of rules in an associative data structure including a set of entries, wherein each member of the set of entries has an associated mask and each associated mask of each member is different.
A network processing system including:
- memory to store a processed access control list, the processed access control list including multiple sets of subsections of rules, each rule of a subsection mutually exclusive of each other rule in the subsection to allow matching without ordering of the rules;
- one or more hash tables to store hash values associated with one or more of the multiple sets of subsections of rules;
- one or more processors to apply a transformed access control list to network data within a network element, the processors including logic to load a description of a first subsection of the transformed access control list, evaluate each rule in the first subsection by performing a lookup in the hardware hash table using a hash of a masked flow label associated with the network data, load a description of a second subsection of the transformed access control list, and compare a matching rule result from the first subsection against a matching rule result from the second subsection;
- and
- logic to perform an action on a unit of network data based on a matching rule result from the first subsection or the second subsection.
Dependencies are inferred from the claim text.