Methods and apparatus for retaining packet order in systems utilizing multiple transmit queues

• US 7,039,061 B2
• Filed: 09/25/2001
• Issued: 05/02/2006
• Est. Priority Date: 09/25/2001
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Connor, Patrick L., Minnick, Linden
• Primary Examiner(s): Phan, Man U.
• Application Number:
  US09/963,284
• Publication Number:
  US 20030058876A1
• Time in Patent Office: 1,680 Days
• Field of Search: 370429-432, 370229-230, 370389-395, 370413-428, 709213-223, 709230-250
• US Class Current: 370/429
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 47/41 by acting on aggregated flows or links
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority

Abstract

Methods, apparatus, and articles of manufacture for retaining packet order in multiprocessor systems utilizing multiple transmit queues are disclosed herein. Embodiments of the present invention define multiple transmit queues for a given priority level of packets to enable the multiprocessor system to process and queue packets of equal priority in different transmit queues. Queuing packets of equal priority in different transmit queues minimizes processor time spent attempting to acquire queue-specific resources associated with one particular transmit queue. In addition, embodiments of the present invention provide an assignment mechanism to ensure that packets corresponding to a common flow are queued in the same transmit queue in order to eliminate, to the extent possible, out-or-order packets, which many times results in lost packets and a reduction in realized network throughput.

Claims

1. A method, comprising:

defining at least two transmit queues for a priority level group;

receiving at least two transmit requests substantially simultaneously; and

wherein, if the at least two transmit requests correspond to packets from separate flows, the packets having a priority designation corresponding to the priority level group, then processing the at least two transmit requests substantially in parallel and queuing the packets separately in the at least two transmit queues;

wherein, if the at least two transmit requests correspond to packets from a common flow, then processing the at least two transmit requests substantially in series and queuing the packets together in one of the at least two transmit queues.

2. The method of claim 1, wherein the priority level group corresponds to at least one communication protocol priority level.

3. The method of claim 1, wherein the priority level group comprises a single priority level.

4. The method of claim 1, wherein the priority level group comprises two or more priority levels.

5. A method, comprising:

defining at least two transmit queues to correspond to at least one priority level

receiving at least two transmit requests at a send packet function of a device driver substantially simultaneously, the at least two transmit requests corresponding to at least two packets;

assigning each of the at least two packets to a queue group in response to a priority designation, the queue group comprising the at least two transmit queues corresponding to the at least one priority level;

assigning each of the at least two packets to one of the at least two transmit queues in response to a flow characteristic; and

wherein, if the at least two packets correspond to different queue assignments, then processing the at least two transmit requests substantially in parallel and queuing the at least two packets separately in the at least two transmit queues;

wherein assigning each of the at least two packets to one of the at least two transmit queues comprises correlating an output generated by an algorithm with a defined value associated uniquely with each of the at least two transmit queues.

6. The method of claim 5, wherein the priority designation corresponds to a communication protocol priority level.

7. The method of claim 5, wherein the flow characteristic comprises at least a portion of a destination address associated with each of the at least two packets.

8. The method of claim 5, wherein assigning each of the at least two packets to a queue group comprises correlating the priority designation with at least one priority level associated uniquely with the queue group.

9. The method of claim 5, wherein the algorithm comprises a hashing algorithm.

10. An apparatus, comprising:

a plurality of processors; and

a memory, coupled to the plurality of processors, to store a plurality of instructions, the memory configured to provide at least two transmit queues accessible by the communications interface, and wherein execution of the instructions by the plurality of processors causes the apparatus to;

define the at least two transmit queues for a priority level group;

receive, substantially simultaneously, a plurality of transmit requests at the plurality of processors, each of the transmit requests corresponding to a packet having a priority designation and a flow characteristic; and

process the two or more transmit requests substantially in series and queue the packets together in one of the at least two transmit queues in response to a determination that the packets have equivalent flow characteristics;

wherein, if two or more of the plurality of transmit requests correspond to packets having distinct flow characteristics, the packets having a priority designation corresponding to the priority level group, then process the two or more of the plurality of transmit requests substantially in parallel and queue the packets separately in the at least two transmit queues.

11. The apparatus of claim 10, wherein the priority level group corresponds to at least one communication protocol priority level.

12. The apparatus of claim 10, wherein the priority level group comprises a single priority level.

13. The apparatus of claim 10, wherein the priority level group comprises two or more priority levels.

14. The apparatus of claim 10, wherein the priority designation corresponds to a communication protocol priority level.

15. The apparatus of claim 10, wherein the flow characteristic comprises at least a portion of a destination address associated with each packet.

16. An article of manufacture, comprising:

a machine-readable medium that provides instructions, which, when executed by a machine, cause the machine to;

define at least two transmit queues for a priority level group;

receive at least two transmit requests substantially simultaneously; and

process the at least two transmit requests substantially in series and queue the packets together in one of the at least two transmit queues in response to a determination that the at least two transmit requests correspond to packets from a common flow;

wherein, if the at least two transmit requests correspond to packets from separate flows, the packets having a priority designation corresponding to the priority level group, then processing the at least two transmit requests substantially in parallel and queuing the packets separately in the at least two transmit queues.

17. The article of manufacture of claim 16, wherein the priority level group corresponds to at least one communication protocol priority level.

18. The article of manufacture of claim 16, wherein the priority level group comprises a single priority level.

19. The article of manufacture of claim 16, wherein the priority level group comprises two or more priority levels.

20. An article of manufacture, comprising:

a machine-readable medium that provides instructions, which, when executed by a machine, cause the machine to;

define at least two transmit queues to correspond to at least one priority level;

receive at least two transmit requests at a send packet function of a device driver substantially simultaneously, the at least two transmit requests corresponding to at least two packets;

assign each of the at least two packets to a queue group in response to a priority designation, the queue group comprising the at least two transmit queues corresponding to the at least one priority level;

assign each of the at least two packets to one of the at least two transmit queues in response to a flow characteristic; and

wherein, if the at least two packets correspond to different queue assignments, then process the at least two transmit requests substantially in parallel and queue the at least two packets separately in the at least two transmit queues;

wherein assigning each of the at least two packets to one of the at least two transmit queues comprises correlating an output generated by an algorithm with a defined value associated uniquely with each of the at least two transmit queues.

21. The article of manufacture of claim 20, wherein the priority designation corresponds to a communication protocol priority level.

22. The article of manufacture of claim 20, wherein the flow characteristic comprises at least a portion of a destination address associated with each of the at least two packets.

23. The article of manufacture of claim 20, wherein assigning each of the at least two packets to a queue group comprises correlating the priority designation with at least one priority level associated uniquely with the queue group.

24. The article of manufacture of claim 20, wherein the algorithm comprises a hashing algorithm.