PACKET FLOW CLASSIFICATION

• US 20150341473A1
• Filed: 05/23/2014
• Published: 11/26/2015
• Est. Priority Date: 05/23/2014
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Venkatesan, Namakkal N., Laurent, Pierre, Dumitrescu, Cristian Florin F., Richardson, Bruce
• Granted Patent: US 9,769,290 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Technologies for packet flow classification on a computing device include a hash table including a plurality of hash table buckets in which each hash table bucket maps a plurality of keys to corresponding traffic flows. The computing device performs packet flow classification on received data packets, where the packet flow classification includes a plurality of sequential classification stages and fetch classification operations and non-fetch classification operations are performed in each classification stage. The fetch classification operations include to prefetch a key of a first received data packet based on a set of packet fields of the first received data packet for use during a subsequent classification stage, prefetch a hash table bucket from the hash table based on a key signature of the prefetched key for use during another subsequent classification stage, and prefetch a traffic flow to be applied to the first received data packet based on the prefetched hash table bucket and the prefetched key. The computing device handles processing of received data packets such that a fetch classification operation is performed by the flow classification module on the first received data packet while a non-fetch classification operation is performed by the flow classification module on a second received data packet.

Claims

1. A computing device for packet flow classification, the computing device comprising:

a memory to store a hash table including a plurality of hash table buckets, each hash table bucket mapping a plurality of keys to corresponding traffic flows;

a flow classification module to perform packet flow classification on received data packets, the packet flow classification comprising a plurality of sequential classification stages, wherein fetch classification operations and non-fetch classification operations are performed in each classification stage, and wherein the fetch classification operations include to (i) prefetch a key of a first received data packet based on a set of packet fields of the first received data packet for use during a subsequent classification stage, (ii) prefetch a hash table bucket from the hash table based on a key signature of the prefetched key for use during another subsequent classification stage, and (iii) prefetch a traffic flow to be applied to the first received data packet based on the prefetched hash table bucket and the prefetched key; and

an execution interlacing module to handle processing of received data packets such that a fetch classification operation is performed by the flow classification module on the first received data packet while a non-fetch classification operation is performed by the flow classification module on a second received data packet.

2. The computing device of claim 1, further comprising a packet receiving module to receive a set of data packets including the received data packets for packet flow classification.

3. The computing device of claim 2, wherein the flow classification module is further to determine whether the set of received data packets meets a threshold number of data packets;

and

wherein to prefetch the key comprises to prefetch the key in response to a determination that the set of received data packets meets the threshold number.

4. The computing device of claim 1, wherein the non-fetch classification operations include to apply a hash function to the prefetched key to determine the key signature.

5. The computing device of claim 1, wherein the non-fetch classification operations include apply the key signature to the hash table to identify the hash table bucket, each hash table bucket being identifiable by a corresponding key signature.

6. The computing device of claim 1, wherein the non-fetch classification operations include to compare the prefetched key to the plurality of keys of the prefetched hash table bucket to identify a matching key;

and

wherein to prefetch the traffic flow comprises to prefetch the traffic flow mapped to the matching key.

7. The computing device of claim 1, wherein to prefetch the key comprises to store the key in one of L1 or L2 cache of the computing device.

8. The computing device of claim 1, wherein to prefetch the key comprises to prefetch a first key of the first received data packet based on a set of packet fields of the first received data packet;

wherein to prefetch the hash table bucket comprises to prefetch a first hash table bucket based on a key signature of the first prefetched key;

wherein the fetch operations include to prefetch a second key of a second received data packet based on a set of packet fields of the second received data packet, the first and second received data packets being received in a same set of received data packets; and

wherein the non-fetch operations include to identify a second hash table bucket based on a key signature of the second prefetched key while prefetching the first key.

9. The computing device of claim 8, wherein to:

prefetch the first key comprises to prefetch the first key with a first execution unit of the computing device; and

identify the second hash table bucket comprises to identify the second hash table bucket with a second execution of the computing device different from the first execution unit.

10. The computing device of claim 1, wherein the flow classification module is to perform packet flow classification on the received data packets in pairs of data packets.

11. The computing device of claim 1, wherein the flow classification module is to perform packet flow classification on the received data packets without executing a branch instruction.

12. The computing device of claim 1, wherein each hash table bucket comprises a data structure for storing keys of configurable data sizes.

13. The computing device of claim 1, wherein each hash table bucket comprises a data structure for storing only keys that are one of 8-bytes or 16-bytes in size.

14. The computing device of claim 1, wherein the non-fetch classification operations include to determine a memory location of a bucket key in the hash table bucket based on a signature of the prefetched key;

and

wherein the fetch classification operations include to prefetch the bucket key from the determined memory location.

15. The computing device of claim 14, wherein the non-fetch classification operations include to (i) compare the prefetched key to the prefetched bucket key (ii) identify a traffic flow mapped to the prefetched bucket key in response to a match between the prefetched key and the prefetched bucket key;

and

wherein to prefetch the traffic flow comprises to prefetch the identified traffic flow.

16. One or more machine-readable storage media comprising a plurality of instructions stored thereon that, in response to execution by a computing device, cause the computing device to:

perform packet flow classification on received data packets, the packet flow classification comprising a plurality of sequential classification stages, wherein fetch classification operations and non-fetch classification operations are performed in each classification stage, and wherein to perform the packet flow classification comprises to;

prefetch a key of a first received data packet based on a set of packet fields of the first received data packet for use during a subsequent stage of packet flow classification while a non-fetch classification operation is performed on another received data packet;

prefetch a hash table bucket based on a key signature of the prefetched key for use during another subsequent classification stage while a non-fetch classification operation is performed on another received data packet, the hash table bucket being prefetched from a plurality of hash table buckets of a hash table, and each hash table bucket mapping a plurality of keys to corresponding traffic flows; and

prefetch a traffic flow to be applied to the first received data packet based on the prefetched hash table bucket and the prefetched key.

17. The one or more machine-readable storage media of claim 16, wherein to perform the packet flow classification further comprises to compare the prefetched key to the plurality of keys of the prefetched hash table bucket to identify a matching key;

and

wherein to prefetch the traffic flow comprises to prefetch the traffic flow mapped to the matching key.

18. The one or more machine-readable storage media of claim 16, wherein to prefetch the key comprises to store the key in one of L1 or L2 cache of the computing device.

19. The one or more machine-readable storage media of claim 16, wherein to:

prefetch the key comprises to prefetch a first key of the first received data packet based on a set of packet fields of the first received data packet; and

prefetch the hash table bucket comprises to prefetch a first hash table bucket based on a key signature of the first prefetched key; and

wherein to perform the packet flow classification further comprises to;

prefetch a second key of a second received data packet based on a set of packet fields of the second received data packet, the first and second received data packets being received in a same set of received data packets; and

identify a second hash table bucket based on a key signature of the second prefetched key while prefetching the first key.

20. The one or more machine-readable storage media of claim 19, wherein to:

prefetch the first key comprises to prefetch the first key with a first execution unit of the computing device; and

identify the second hash table bucket comprises to identify the second hash table bucket with a second execution of the computing device different from the first execution unit.

21. A method for classifying data packet flow by a computing device, the method comprising:

performing packet flow classification on received data packets, the packet flow classification comprising a plurality of sequential classification stages, wherein fetch classification operations and non-fetch classification operations are performed in each classification stage, and wherein performing the packet flow classification comprises;

prefetching, by the computing device, a key of a first received data packet based on a set of packet fields of the first received data packet for use during a subsequent stage of packet flow classification while a non-fetch classification operation is performed on another received data packet;

prefetching, by the computing device, a hash table bucket based on a key signature of the prefetched key for use during another subsequent classification stage while a non-fetch classification operation is performed on another received data packet, the hash table bucket being prefetched from a plurality of hash table buckets of a hash table, and each hash table bucket mapping a plurality of keys to corresponding traffic flows; and

prefetching, by the computing device, a traffic flow to be applied to the first received data packet based on the prefetched hash table bucket and the prefetched key.

22. The method of claim 21, wherein performing the packet flow classification further comprises comparing, by the computing device, the prefetched key to the plurality of keys of the prefetched hash table bucket to identify a matching key;

and

wherein prefetching the traffic flow comprises prefetching the traffic flow mapped to the matching key.

23. The method of claim 21, wherein prefetching the key comprises storing the key in one of L1 or L2 cache of the computing device.

24. The method of claim 21, wherein:

prefetching the key comprises prefetching a first key of the first received data packet based on a set of packet fields of the first received data packet; and

prefetching the hash table bucket comprises prefetching a first hash table bucket based on a key signature of the first prefetched key; and

wherein performing the packet flow classification further comprises;

prefetching, by the computing device, a second key of a second received data packet based on a set of packet fields of the second received data packet, the first and second received data packets being received in a same set of received data packets; and

identifying, by the computing device, a second hash table bucket based on a key signature of the second prefetched key while prefetching the first key.

25. The method of claim 24, wherein:

prefetching the first key comprises prefetching the first key with a first execution unit of the computing device; and

identifying the second hash table bucket comprises identifying the second hash table bucket with a second execution of the computing device different from the first execution unit.