Back to results
US 2026/0254756 A1Published application
Cost-Based Selection of Cross-Field Summarization Labels
AssigneeArista Networks, Inc.
InventorsMuhammad Khalid YOUSUF, Ramakrishna PADUVALLI, Venkata Vyshnav LAGISETTY, Michael CHEN
Life of this patent
Estimating the term…
Abstract
Techniques for performing cost-based selection of cross-field summarization labels are provided. In certain embodiments, these techniques enable a network device to implement cross-field summarization in a manner that minimizes the number of ternary content-addressable memory (TCAM) entries needed for a traffic policy, specifically in cases where the network device's cross-field label lookup table cannot hold all of the cross-field summarization labels created for that policy.
Claims20
A method performed by a network device for executing cost-based selection of cross-field summarization labels for a traffic policy comprising a plurality of rules, the method comprising:
- for each rule in the plurality of rules:
- computing a cross-product of a plurality of field label sets corresponding to a plurality of field lists of the rule, each field label set including one or more field summarization labels assigned to one or more match patterns specified in a field list in the plurality of field lists, the computing of the cross-product resulting in a set of field label tuples;
- determining a first ternary content-addressable memory (TCAM) layout for a TCAM of the network device based on the set of field label tuples;
- determining a second TCAM layout for the TCAM based on a set of cross-field summarization labels associated with the rule;
- and
- computing a TCAM usage reduction cost for the rule based on the first TCAM layout and the second TCAM layout;
- ordering the plurality of rules from highest TCAM usage reduction cost to lowest TCAM usage reduction cost;
- and
- for each rule in the plurality of rules, in order:
- determining one or more entries to be programmed into a cross-field label lookup table for the set of cross-field summarization labels associated with the rule;
- checking whether the one or more entries fit in the cross-field label lookup table;
- and
- upon determining that the one or more entries fit in the cross-field label lookup table, programming the one or more entries into the cross-field label lookup table and marking the rule as using cross-field summarization.
10 more elements
A network device comprising:
- a central processing unit (CPU);
- a ternary content-addressable memory (TCAM);
- a cross-field label lookup table;
- and
- a memory having stored thereon program code for performing cost-based selection of cross-field summarization labels for a traffic policy comprising a plurality of rules, the program code causing the CPU to:
- for each rule in the plurality of rules:
- compute a cross-product of a plurality of field label sets corresponding to a plurality of field lists of the rule, each field label set including one or more field summarization labels assigned to one or more match patterns specified in a field list in the plurality of field lists, the computing of the cross-product resulting in a set of field label tuples;
- determine a first ternary TCAM layout for the TCAM based on the set of field label tuples;
- determine a second TCAM layout for the TCAM based on a set of cross-field summarization labels associated with the rule;
- and
- compute a TCAM usage reduction cost for the rule based on the first TCAM layout and the second TCAM layout;
- order the plurality of rules from highest TCAM usage reduction cost to lowest TCAM usage reduction cost;
- and
- for each rule in the plurality of rules, in order:
- determine one or more entries to be programmed into the cross-field label lookup table for the set of cross-field summarization labels associated with the rule;
- check whether the one or more entries fit in the cross-field label lookup table;
- and
- upon determining that the one or more entries fit in the cross-field label lookup table, program the one or more entries into the cross-field label lookup table and mark the rule as using cross-field summarization.
15 more elements
A method performed by a network device for executing cost-based selection of cross-field summarization labels for a traffic policy comprising a plurality of rules, the method comprising:
- for each rule in the plurality of rules:
- computing a cross-product of a plurality of field label sets corresponding to a plurality of field lists of the rule, each field label set including one or more field summarization labels assigned to one or more match patterns specified in a field list in the plurality of field lists, the computing of the cross-product resulting in a set of field label tuples;
- determining a first ternary content-addressable memory (TCAM) layout for a TCAM of the network device based on the set of field label tuples;
- determining a second TCAM layout for the TCAM based on a set of cross-field summarization labels associated with the rule;
- and
- computing a TCAM usage reduction cost for the rule based on the first TCAM layout and the second TCAM layout;
- ordering the plurality of rules from highest TCAM usage reduction cost to lowest TCAM usage reduction cost;
- and
- for each rule in the plurality of rules, in order:
- attempting to program one or more entries into a cross-field label lookup table for the set of cross-field summarization labels associated with the rule.
7 more elements
Dependencies are inferred from the claim text.