Receive-side scaling in a computer system using sub-queues assigned to processing cores

• US 9,639,403 B2
• Filed: 03/15/2013
• Issued: 05/02/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Ribbon Communications Operating Company, Inc. (Ribbon Communications, Inc.)
• Original Assignee: Genband US LLC (Ribbon Communications, Inc.)
• Inventors: Peters, Matthew Lorne
• Primary Examiner(s): Savla, Arpan P.
• Application Number:
  US13/833,049
• Publication Number:
  US 20140281349A1
• Time in Patent Office: 1,509 Days
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/548 Queue
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A system, method, and computer program product are provided for receiving an incoming data stream. The system comprises a multi-core processor with a memory unit that is configured to include a circular queue that receives a data stream. The circular queue is divided into a plurality of sub-queues determined as a multiple of the number of processing cores, and each sub-queue is assigned to one processing core such that as data is received into a region covered by a particular sub-queue, the processing core assigned to the particular sub-queue processes the data. The system is also configured to update a head pointer and a tail pointer of the circular queue. The head pointer is updated as data is received into the circular queue and the tail pointer is updated by a particular processing core as it processes data in its assigned sub-queue.

Claims

1. A computer system configured to receive an incoming data stream, the system comprising:

a multi-core processor;

a memory unit at least partially configured in a circular queue that receives a data stream, wherein the circular queue is divided into a plurality of sub-queues, each sub-queue corresponding to a different memory region, and wherein each memory region is assigned to a different processing core of the multicore processor such that as data is read from a particular memory region covered by a particular sub-queue, the processing core assigned to the particular memory region processes the data, the processing core being assigned to the particular memory region before the data is received into the circular queue;

wherein a head pointer of the circular queue is updated as data is received into the circular queue and a tail pointer of the circular queue is updated by the particular processing core assigned to the memory region at which the tail pointer is currently located as the particular processing core processes data from the memory region at which the tail pointer is currently located.

2. The system of claim 1, wherein the circular queue is divided into a plurality of sub-queues based on a multiple of the number of processing cores.

3. The system of claim 1, further comprising a memory location configured to store at least a receive token and a dispatch token, wherein the receive token is used to determine whether the particular processing core can process data in its assigned sub-queue, and wherein the dispatch token is used to determine whether the particular processing core can pass processed data in its assigned sub-queue to a work queue for further processing.

4. The system of claim 3, wherein the data in each sub-queue is hashed when its assigned processing core is in possession of the receive token.

5. The system of claim 1, wherein an assigned processing core hashes the data in its assigned sub-queue as the tail pointer moves through its assigned sub-queue.

6. The system of claim 1, wherein a processing core assigned to a particular sub-queue is configured to update the tail pointer to point to a next subsequent sub-queue after a plurality of sub-queues have been processed by their respectively assigned processing cores.

7. The system of claim 1, wherein the circular queue is configured to receive data from an operatively coupled network interface device, and wherein the network interface device updates the head pointer of the circular queue based on the amount of received data.

8. The system of claim 1, wherein each processing core is configured to process data in a work queue when the tail pointer is not pointing to an assigned sub-queue.

9. The system of claim 1, wherein the number of sub-queues is adjusted based on the rate at which data is received into the circular queue.

10. A computer-implemented method for receiving an incoming data stream comprising:

dividing a circular queue in a memory unit into multiple sub-queues, each sub-queue including an equal portion of the circular queue, and wherein each of the sub-queues are sequentially assigned to a different one of a plurality of processing cores;

receiving the data stream into the circular queue, wherein a head pointer indicating the front of the queue is updated based on an amount of data received into the queue;

as data is received in the circular queue;

determining whether a tail pointer of the circular queue is within a region of a particular sub-queue;

in response to determining that the tail pointer is within the region, retrieving the data in the particular sub-queue, wherein the data is retrieved by the processing core assigned to a particular sub-queue, the processing core being assigned to the particular sub-queue before the data is received into the circular queue;

updating the tail pointer with the particular processing core assigned to the region at which the tail pointer is currently located; and

notifying a processing core assigned to a next subsequent sub-queue that retrieving of the data in the particular sub-queue is complete.

11. The method of claim 10, wherein the data comprises packets.

12. The method of claim 10, further comprising:

maintaining a receive token that is used to determine whether a particular processing core can process data in its assigned sub-queue.

13. The method of claim 12, wherein the data in each sub-queue is hashed when its assigned processing core is in possession of the receive token.

14. The method of claim 10, further comprising:

maintaining a dispatch token that is used to determine whether the particular processing core can pass processed data in its assigned sub-queue to a work queue for further processing.

15. The method of claim 10, wherein processing the data in the particular sub-queue includes hashing the data.

16. The method of claim 10, wherein notifying the processing core assigned to the next subsequent sub-queue includes updating the tail pointer to point to the next subsequent sub-queue after a plurality of sub-queues have been processed by their respectively assigned processing cores.

17. The method of claim 10, wherein notifying the processing core assigned to the next subsequent sub-queue includes updating the tail pointer to point to the next subsequent sub-queue after the data in the particular sub-queue is processed.

18. The method of claim 10, wherein the number of sub-queues is adjusted based on the rate at which data is received into the circular queue.

19. A computer program product having a non-transitory computer readable medium tangibly recording computer program logic for processing and incoming data stream, the computer program product comprising:

code for dividing a circular queue in a memory unit into multiple sub-queues, each sub-queue including an equal portion of the circular queue, wherein the number of sub-queues is related to a number of processing cores in a computer processor coupled to the memory unit, and wherein the sub-queues are sequentially assigned to the processing cores;

code for receiving the data stream into the circular queue, wherein a head pointer indicating the front of the queue is updated based on the amount of data received into the queue;

as data is received in the circular queue;

code for determining whether a tail pointer of the circular queue is within a region of a particular sub-queue;

code for retrieving data in the particular sub-queue after determining that the tail pointer is within the region, wherein the data is retrieved by the processing core assigned to the particular sub-queue, the processing core being assigned to the particular sub-queue before the data is received into the circular queue;

code for updating the tail pointer with the particular processing core assigned to the region at which the tail pointer is currently located;

code for notifying a processing core assigned to a next subsequent sub-queue that retrieving of the data in the particular sub-queue is complete.

20. The computer program product of claim 19 further comprising code to update the tail pointer after data in a plurality of sub-queues has been processed.