System and method of processing packet classification with range sets

Patent metadata

Field	Value
Publication number	US-2021044521-A1
Application number	US-202016986982-A
Country	US
Kind code	A1
Filing date	Aug 6, 2020
Priority date	Aug 7, 2019
Publication date	Feb 11, 2021
Grant date	—

Abstract

A method and apparatus of a network element that processes network data using a transformed packet classification list in a network element is described. A network element receives a packet classification list and transforms a first set of the plurality of range sets corresponding to a first one of the two or more types of packet characteristics into a first set of range labels. In addition, the network element transforms a second set of the plurality of range sets corresponding to a second one of the two or more types of packet characteristics into a second set of range labels. The network element may create a set of combination labels. The network element further processes network data by performing a first lookup to derive a first combination packet label, performing a second lookup of at least the first combination packet label, and applying a rule resulting from the second lookup to the network data.

First claim

What is claimed is:

1 . A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform operations to process network data using a transformed packet classification list, the operations comprising:
receiving a packet classification list that includes a plurality of range sets for two or more types of packet characteristics, wherein each of the plurality of range sets is set of one or more numerical ranges for a packet characteristic; transforming a first set of the plurality of range sets corresponding to a first one of the two or more types of packet characteristics into a first set of range labels; transforming a second set of the plurality of range sets corresponding to a second one of the two or more types of packet characteristics into a second set of range labels; creating a set of combination labels from the first and second set of range labels, wherein each of the combination labels in the set of combination labels is derived from one of the range labels in the first set of range labels and one of the range labels in the second set of range labels; storing the set of combination labels in a first lookup table, wherein each of the entries in the first lookup table includes one of the first range labels, one of the second range labels and a resulting combination label; and processing network data by,
performing a first lookup in the first lookup table to derive a first combination packet label,
performing a second lookup of at least the first combination packet label in a second lookup table, and
applying a rule resulting from the second lookup to the network data.

2 . The non-transitory machine-readable medium of claim 1 , wherein the receiving of the packet classification list comprises:
receiving a user configuration; and transforming that user configuration into a set of rules and the plurality of range sets, wherein each range in the plurality of range sets is associated with a rule from the set of rules.

3 . The non-transitory machine-readable medium of claim 1 , further comprising:
transforming one of the plurality of range sets into a new range set that includes non-overlapping ranges by splitting a member range of the one of the plurality of ranges into two or more non-overlapping ranges.

4 . The non-transitory machine-readable medium of claim 1 , wherein
a first label associated with the first type of packet characteristic is associated with a first set of rules, and a second label associated with the second type of packet characteristic is associated the first set of rules, a third label associated with the first type of packet characteristic is associated with a second set of rules, and a fourth label associated with the second type of packet characteristic is also associated the second set of rules, and wherein a first combination label derived from the combination of the first label and the second label is equal to a second combination label derived from the combination of the third label and the fourth label.

5 . The non-transitory machine-readable medium of claim 1 , wherein the transformation to one or more of the first and second set of range labels comprises:
associating with a first range, an indication of a subset of a set of rules that that the first range belongs to.

6 . The non-transitory machine-readable medium of claim 1 , wherein a second range of a first range set of the plurality of range sets is nested within the first range of the first range set, and an indication of the rules that the second range belongs to includes a subset of a set of rules that the first range belongs to.

7 . The non-transitory machine-readable medium of claim 1 , wherein one of the plurality of range sets includes an except element that subtracts a numerical range of the packet characteristic from that range-set.

8 . The non-transitory machine-readable medium of claim 1 , wherein a first range is designated as a negative range within a first range set and an indication of the set of range sets that the first range belongs to does not include the first range set.

9 . The non-transitory machine-readable medium of claim 1 , further comprising:
determining that a second range is nested within the first range using a data structure; and storing an indication of the subset of the set of ranges associated with the first and second ranges.

10 . The non-transitory machine-readable medium of claim 1 , further comprising:
matching a rule with one of the combination labels in the set of combination labels when another one of the combination labels in the set of combination labels is a possible match.

11 . The non-transitory machine-readable medium of claim 1 , wherein one of the plurality of range sets is associated with multiple range labels.

12 . The non-transitory machine-readable medium of claim 1 , wherein one of the plurality of range sets is associated with multiple combination labels.

13 . A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform operations to process network data using a transformed packet classification list, the operations comprising:
receiving the network data having a plurality of packet characteristics; retrieving the plurality of packet characteristics; transforming a subset of the plurality of packet characteristics by performing a first lookup of the subset of the plurality of packet characteristics; performing a second lookup using the transformed subset of the plurality of packet characteristics in a lookup table that stores the transformed packet classification list as set of labels that are each derived from at least two types of the packet characteristics, wherein the second lookup returns a rule associated with the subset of packet characteristics; and processing the network data using the rule.

14 . A method to process network data using a transformed packet classification list, the method comprising:
receiving a packet classification list that includes a plurality of range sets for two or more types of packet characteristics, wherein each of the plurality of range sets is set of one or more numerical ranges for a packet characteristic; transforming a first set of the plurality of range sets corresponding to a first one of the two or more types of packet characteristics into a first set of range labels; transforming a second set of the plurality of range sets corresponding to a first one of the two or more types of packet characteristics into a second set of range labels; creating a set of combination labels from the first and second set of range labels, wherein each of the combination labels in the set of combination labels is derived from one of the range labels in the first set of range labels and one of the range labels in the second set of range labels; storing the set of combination labels in a first lookup table, herein each of the entries in the first lookup table includes one of the first range labels, one of the second range labels and a resulting combination label; and processing network data by,
performing a first lookup in the first lookup table to derive a first combination packet label
performing a second lookup of at least the first combination packet label in a second lookup table, and
applying a rule resulting from the second lookup to the network data.

15 . The method of claim 14 , wherein the receiving of the packet classification list comprises:
receiving a user configuration; and transforming that user configuration into a set of rules and the plurality of range

Assignees

• Arista Networks Inc

Inventors

• Holbrook Hugh W
• Labonte Francois
• Paduvalli Ramakrishna Shivaramaiah
• Zong Xuanran

Classifications

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• H04L45/7452

  Multiple parallel or consecutive lookup operations (lookup operation involving Bloom filters H04L45/7459) · CPC title

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/507 Primary

  Label distribution · CPC title

• H04L47/2441

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title