Packet classification using multiple processing units

Patent metadata

Field	Value
Publication number	US-9509809-B2
Application number	US-201414189264-A
Country	US
Kind code	B2
Filing date	Feb 25, 2014
Priority date	Feb 25, 2014
Publication date	Nov 29, 2016
Grant date	Nov 29, 2016

Abstract

A packet classification capability is presented herein. The packet classification capability enables improvements in packet classification via use of a combination of a primary processing unit and a secondary processing unit where the secondary processing unit is configured to perform packet classification functions in parallel based on distribution of packet classification information across processing blocks of the secondary processing unit. The processing blocks of the secondary processing unit may be supported using a set of processing elements, where each of the processing elements may include a shared memory, respectively. The secondary processing unit may be configured to use a linear search process, a tuple search process, a Bloom search process, or the like. The primary processing unit may be a Central Processing Unit (CPU) and the secondary processing unit may be a Graphics Processing Unit (GPU).

First claim

What is claimed is:

1. An apparatus, comprising:
a processing unit comprising a device memory and a set of processing elements, the device memory configured to store a set of packet classification information for a set of packet classification rules configured for use in classifying packets, the set of processing elements configured to support a set of processing blocks, the processing blocks having respective portions of the set of packet classification information assigned thereto, the processing unit configured to:
receive a set of tuples of a set of packets to be classified; and
determine, based on evaluation of the set of tuples by each of the processing blocks using the respective portions of the packet classification information assigned to the processing blocks, a set of matched packet classification rules matching the set of tuples of the packets to be classified.

2. The apparatus of claim 1 , wherein one of the processing blocks is configured to run on one of the processing elements, wherein the one of the processing elements comprises a shared memory, wherein the one of the processing blocks is configured to:
load, from the device memory into the shared memory of the one of the processing elements, at least a part of the respective portion of the set of packet classification information assigned to the one of the processing blocks.

3. The apparatus of claim 1 , wherein one of the processing blocks is configured to run on one of the processing elements, wherein the one of the processing elements comprises a shared memory, wherein the one of the processing blocks is configured to:
load, from the device memory into the shared memory of the one of the processing elements, a first part of the respective portion of the set of packet classification information assigned to the one of the processing blocks;
evaluate each of the tuples in the set of tuples based on the first part of the respective portion of the set of packet classification information;
load, from the device memory into the shared memory of the one of the processing elements, a second part of the respective portion of the set of packet classification information assigned to the one of the processing blocks; and
evaluate each of the tuples in the set of tuples based on the second part of the respective portion of the set of packet classification information.

4. The apparatus of claim 1 , wherein one of the processing blocks is configured to run on one of the processing elements, wherein the one of the processing elements comprises a shared memory, wherein the one of the processing blocks is configured to:
load, from the device memory into the shared memory of the one of the processing elements, a first subset of tuples from the set of tuples of the packets;
evaluate each of the tuples in the first subset of tuples based on the respective portion of the set of packet classification information assigned to the one of the processing blocks;
load, from the device memory into the shared memory of the one of the processing elements, a second subset of tuples from the set of tuples of the packets;
evaluate each of the tuples in the second subset of tuples based on the respective portion of the set of packet classification information assigned to the one of the processing blocks.

5. The apparatus of claim 1 , wherein one of the processing blocks is configured to run on one of the processing elements, wherein the one of the processing elements comprises a shared memory, wherein the one of the processing blocks comprises a processing thread configured to:
read one of the tuples of the set of tuples from the device memory of the processing element; and
evaluate the one of the tuples based on the respective portion of the set of packet classification information assigned to the one of the processing blocks.

6. The apparatus of claim 5 , wherein the one of the processing blocks is configured to:
based on a determination that the one of the tuples matches a packet classification rule in the respective portion of the set of packet classification information assigned to the one of the processing blocks, write an indication of the matched packet classification rule for the one of the tuples to the device memory for inclusion in the set of matched packet classification rules.

7. The apparatus of claim 5 , wherein the one of the processing elements is configured to:
based on a determination that the one of the tuples matches multiple packet classification rules in the respective portion of the set of packet classification information assigned to the one of the processing blocks:
identify a highest priority packet classification rule of the multiple packet classification rules; and
write an indication of the highest priority packet classification rule to the device memory for inclusion in the set of matched packet classification rules.

8. The apparatus of claim 5 , wherein the set of packet classification information comprises the set of packet classification rules, wherein the respective portion of the set of packet classification information assigned to the one of the processing blocks comprises a subset of packet classification rules from the set of packet classification rules.

9. The apparatus of claim 8 , wherein, to evaluate the one of the tuples, the processing thread is configured to:
determine, for each packet classification rule in the subset of packet classification rules, whether the one of the tuples matches the packet classification rule.

10. The apparatus of claim 5 , wherein the set of packet classification information comprises:
a class table from a set of class tables maintaining respective subsets of packet classification rules from the set of packet classification rules; and
a class mask, from a set of class masks associated with the set of class tables, that is configured for use with the class table.

11. The apparatus of claim 10 , wherein, to evaluate the one of the tuples, the processing thread is configured to:
determine a masked tuple for the one of the tuples based on the one of the tuples and the class mask; and
determine, based on the masked tuple, whether the one of the tuples matches one of the packet classification rules of the subset of packet classification rules in the class table.

12. The apparatus of claim 10 , wherein the class table is composed of a set of sub-tables based on hashing, wherein each of the sub-tables comprises a respective set of slots, wherein, to evaluate the one of the tuples, the processing thread is configured to:
perform a logical AND operation on the one of the tuples and the class mask to derive thereby a masked tuple;
for each sub-table in the set of sub-tables, compute a candidate slot for the masked tuple based on a hash function of the sub-table; and
compare a packet classification rule of the candidate slot with the masked tuple.

13. The apparatus of claim 12 , wherein the one of the processing blocks is configured to:
based on a determination that the packet classification rule of the candidate slot matches the masked tuple, identify the packet classification rule as a matching packet classification rule for the one of the tuples.

14. The apparatus of claim 5 , wherein the set of packet classification information comprises:
a class table from a set of class tables maintaining respective subsets of packet classification rules from the set of packet classification rules;
a class mask, from a set of class masks associated with the set of class tables, that is configured for use with the class table; and
a class table representation configured to represent the subset of packet classifi

Assignees

• Alcatel Lucent Usa Inc

Inventors

• Laufer Rafael P
• Varvello Matteo

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L69/22 Primary

  Parsing or analysis of headers · CPC title

• H04L45/7459

  using Bloom filters · CPC title