Load balancing the servicing of received packets

• US 7,076,545 B2
• Filed: 07/31/2002
• Issued: 07/11/2006
• Est. Priority Date: 07/31/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: DiMambro, Francesco R.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): NGUYEN, VAN KIM T
• Application Number:
  US10/210,487
• Publication Number:
  US 20040024873A1
• Time in Patent Office: 1,441 Days
• Field of Search: 709/223, 709/225, 709/249, 709/250, 710 52- 54, 710 55- 60
• US Class Current: 709/223
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1027 Persistence of sessions during load balancing

Abstract

A system and method for distributing a portion of the processing of a received packet among a plurality of service threads. When an ISR or similar process retrieves a packet from a communication interface via a receive descriptor ring, it places the packet on one of a plurality of service queues. Each queue has an associated service thread or process that initiates upper layer protocol processing for queued packets. The ISR may select a particular service queue based on the packet'"'"'s communication flow or connection. Alternatively, the ISR may use a processor identifier provided by the communication interface to select a queue (e.g., in a multi-processor computer system). Or, other information provided by the interface may be used.

Claims

1. A method of load balancing the processing of packets received at a computer system, comprising:

maintaining a plurality of queues, wherein each said queue is serviced by a separate service process configured to facilitate the processing of a packet in accordance with one or more communication protocols;

receiving packets at a communication interface of a computer system, wherein the communication interface is configured to place the packets onto a descriptor ring; and

executing a single interrupt service routine configured to;

receive the packets from the descriptor ring;

replace descriptor ring buffers in which the packets were received;

distribute the packets among the queues; and

signal the service process associated with each queue into which a packet was distributed.

2. The method of claim 1, further comprising:

executing a first service process associated with a first queue to;

retrieve a first packet from the first queue; and

initiate processing of the first packet in accordance with a communication protocol according to which the first packet was formatted.

3. The method of claim 2, wherein said executing a first service process associated with a first queue is performed during the same time said executing a single interrupt service routine is performed.

4. The method of claim 2, wherein the communication protocol is one of IP (Internet Protocol) and TCP (Transport Control Protocol).

5. The method of claim 1, wherein:

the computer system comprises multiple processors; and

each of the multiple processors is configured to execute one or more of the service processes.

6. The method of claim 1, further comprising:

for each packet, receiving a corresponding flow identifier from the communication interface;

wherein the flow identifier is configured to identify a communication flow comprising the packet; and

wherein said distributing the packets comprises selecting a queue associated with the flow identifier.

7. The method of claim 6, wherein said selecting a queue comprises hashing the flow identifier and using the resulting hash to identify a queue.

8. The method of claim 6, wherein said selecting a queue comprises computing a modulo of the flow identifier over the number of queues.

9. The method of claim 1, further comprising:

for each packet, receiving a corresponding processor identifier from the communication interface;

wherein the processor identifier is configured to identify a processor of the computer system; and

wherein said distributing the packets comprises selecting a queue associated with the processor identifier.

10. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of load balancing the processing of packets received at a computer system, the method comprising:

maintaining a plurality of queues, wherein each said queue is serviced by a separate service process configured to facilitate the processing of a packet in accordance with one or more communication protocols;

receiving packets at a communication interface of a computer system, wherein the communication interface is configured to place the packets onto a descriptor ring; and

executing a single interrupt service routine configured to;

receive the packets from the descriptor ring;

replace descriptor ring buffers in which the packet were received;

distribute the packets among the queues; and

signal the service process associated with each queue into which a packet was distributed.

11. A method of processing a received packet, comprising:

receiving a first packet at a communication interface of a multi-processor computer system;

executing an interrupt service routine to;

retrieve the first packet from a receive descriptor ring buffer;

replace the receive descriptor ring buffer;

place the first packet onto one of a plurality of service queues; and

signal a first service process associated with the selected service queue; and

executing said first service process to;

retrieve the first packet from the service queue; and

facilitate processing of the first packet through an upper layer communication protocol.

12. The method of claim 11, further comprising:

receiving a second packet at the communication interface;

executing the interrupt service routine to;

retrieve the second packet from the receive descriptor ring buffer;

place the second packet into a second service queue; and

signal a second service process associated with the second service queue; and

executing said second service process to facilitate processing of the second packet.

13. The method of claim 12, wherein:

the interrupt service routine retrieves the second packet from the receive descriptor ring at the same time the service process facilitates processing of the first packet through an upper layer communication protocol.

14. The method of claim 12, wherein:

said executing said second service process occurs during the same time said executing said first service process occurs.

15. The method of claim 11, wherein the number of service queues is proportional to the number of processors in the computer system.

16. The method of claim 11, wherein the number of service processes equals the number of service queues, and each service process is configured to retrieve packets from only one service queue.

17. The method of claim 11, wherein said placing the packet onto one of a plurality of service queues comprises:

receiving from the communication interface a processor identifier configured to identify one of the multiple processors; and

identifying a service queue associated with said processor identifier.

18. The method of claim 11, wherein said placing the packet onto one of a plurality of service queues comprises:

receiving from the communication interface a flow identifier configured to identify a communication flow comprising the packet; and

identifying a service queue associated with said flow identifier.

19. The method of claim 18, wherein said identifying a service queue comprises computing a hash of said flow identifier.

20. The method of claim 18, wherein said identifying a service queue comprises computing a modulo of said flow identifier over the number of service queues.

21. The method of claim 11, wherein said signalling a service process associated with the selected service queue comprises:

waking the service process.

22. The method of claim 11, wherein said facilitating processing of the packet through an upper layer communication protocol comprises:

processing the packet in accordance with a communication protocol according to which the packet was formatted.

23. The method of claim 22, wherein the communication protocol is one of IP (Internet Protocol) and TCP (Transport Control Protocol).

24. The method of claim 11, wherein said facilitating processing of the packet through an upper layer communication protocol comprises:

submitting the packet to be processed in accordance with a communication protocol according to which the packet was formatted.

25. A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of processing a received packet, the method comprising:

receiving a first packet at a communication interface of a multi-processor computer system;

executing an interrupt service routine to;

retrieve the first packet from a receive descriptor ring buffer;

replace the buffer;

place the first packet onto one of a plurality of service queues; and

signal a first service process associated with the selected service queue; and

executing said first service process to;

retrieve the first packet from the service queue; and

facilitate processing of the first packet through an upper layer communication protocol.

26. A computer system, comprising:

multiple processors;

a communication interface configured to receive a packet from a communication link;

a plurality of service queues;

an interrupt process configured to;

receive the packet from the communication interface;

select a first service queue from the plurality of service queues; and

place the packet into the first service queue; and

a first service process, distinct from the interrupt process, wherein said first service process is configured to remove the packet from the first service queue and initiate processing of the packet through one or more communication protocols.

27. The computer system of claim 26, wherein the number of service queues is equal to the number of processors.

28. The computer system of claim 26, wherein the number of service queues is proportional to the number of processors.

29. The computer system of claim 26, further comprising a plurality of service processes, including the first service process;

wherein the number of service processes is equal to the number of service queues.

30. The computer system of claim 26, further comprising:

a receive descriptor ring;

wherein the communication interface is configured to place the received packet onto the receive descriptor ring; and

the interrupt process is configured to retrieve the packet from the receive descriptor ring in response to an interrupt from the communication interface.

31. The computer system of claim 26, wherein the interrupt process selects one of the service queues by:

receiving an identifier from the communication interface; and

identifying a service queue associated with the identifier.

32. The computer system of claim 26, wherein the interrupt process selects one of the service queues by:

receiving from the communication interface, with the packet, a flow identifier configured to identify a communication flow comprising the packet; and

identifying a service queue associated with the flow identifier.

33. The computer system of claim 32, wherein said identifying comprises hashing the flow identifier.

34. The computer system of claim 32, wherein said identifying comprises calculating the modulo of the flow identifier over the number of service queues.

35. The computer system of claim 26, wherein the interrupt process selects one of the service queues by:

receiving from the communication interface, with the packet, a processor identifier configured to identify one of the multiple processors; and

identifying a service queue associated with the processor identifier.

36. The computer system of claim 26, wherein:

said first service process associated with said first service queue is configured to block when said first service queue is empty;

the interrupt process is configured to signal said first service process when the first packet is placed onto said first service queue; and

in response to said signal, said first service process awakes and removes the first packet from said first service queue.