Optimized back-to-back enqueue/dequeue via physical queue parallelism

• US 20050201398A1
• Filed: 12/22/2003
• Published: 09/15/2005
• Est. Priority Date: 12/22/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chandra, Prashant R., Kumar, Alok, Naik, Uday R., Varde, Ameya S.
• Granted Patent: US 7,336,675 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/6295 using multiple queues, one for each individual QoS, connection, flow or priority
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A method and apparatus to receive a plurality of packet from an inflow of a single packet flow. In response to receiving the plurality of packets, a plurality of packet pointers is enqueued into multiple physical queues. Each of the plurality of packet pointers designates one of the plurality of packets from the single packet flow. The plurality of packet pointers are dequeued from the multiple physical queues to transmit the plurality of packets along an outflow of the single packet flow.

Claims

1. A method, comprising:

receiving a plurality of packets from an inflow of a single packet flow;

enqueuing a plurality of packet pointers into multiple link lists, each one of the plurality of packet pointers designating one of the plurality of packets from the single packet flow; and

dequeuing the plurality of packet pointers from the multiple link lists to transmit the plurality of packets along an outflow of the single packet flow.

2. The method of claim 1 wherein enqueuing the plurality of packet pointers further comprises enqueuing the plurality of packet pointers into the multiple link lists using a round robin enqueuing scheme between the multiple link lists.

3. The method of claim 2 wherein dequeuing the plurality of packet pointers further comprises dequeuing the plurality of packet pointers from the multiple link lists in a same order as enqueuing the plurality of packet pointers into the multiple link lists.

4. The method of claim 1 wherein the multiple link lists comprise two link lists and wherein enqueuing the plurality of packet pointers into the multiple link lists further comprises alternating enqueues of each of the plurality of packet pointers between the two link lists.

5. The method of claim 4 wherein dequeuing the plurality of packet pointers from the two link lists further comprises alternating dequeues of each of the plurality of packet pointers from the two link lists in a same order as the alternating enqueues.

6. The method of claim 1, further comprising:

receiving multiple packet flows, each one of the multiple packet flows including a plurality of packets;

enqueuing a plurality of packet pointers for each of the multiple packet flows into multiple link lists, each one of the plurality of packet pointers designating one of the plurality of packets of each of the multiple packet flows; and

dequeuing the plurality of packet pointer for each of the multiple packet flows from each of the multiple link lists to transmit each of the plurality of packets along a corresponding outflow of each of the multiple packet flows.

7. The method of claim 6 wherein enqueuing the plurality of packet pointers for each of the multiple packet flows further comprises enqueuing each of the plurality of packet pointers into the multiple link lists according to the following relation,

PQ=(LQ×

N)+Qmult

wherein PQ represents a link list number of one of the multiple link lists, LQ represents a logical queue number corresponding to one of the multiple packet flows, N represents a number of the multiple link lists per each one of the multiple packet flows, and Qmult differentiates between each one of the multiple link lists of each of the multiple packet flows.

8. The method of claim 1 wherein the multiple link lists comprise multiple physical link lists having multiple link list elements, each link list element including one of the plurality of packet pointers and a next element pointer.

9. The method of claim 1 wherein the single packet flow comprises a single data packet flow along a network path.

10. A method, comprising:

receiving a plurality of packets from a packet inflow;

enqueuing the plurality of packets from the packet inflow into multiple physical queues; and

dequeuing the plurality of packets from the multiple physical queues to transmit the plurality of packets along a packet outflow.

11. The method of claim 10 wherein enqueuing the plurality of packets into the multiple physical queues comprises enqueuing the plurality of packets into the multiple physical queues using a round robin enqueuing scheme between the multiple physical queues.

12. The method of claim 11 wherein dequeuing the plurality of packets from the multiple physical queues comprises dequeuing the plurality of packets from the multiple physical queues in a same order as the plurality of packets were enqueued into the multiple physical queues.

13. The method of claim 10, further comprising:

receiving multiple pluralities of packets from corresponding multiple packet inflows;

enqueuing each of the multiple pluralities of data packets from the corresponding multiple packet inflows into corresponding multiple physical queues; and

dequeuing each of the multiple pluralities of packets from the corresponding multiple physical queues to transmit each of the multiple pluralities of packets along corresponding packet outflows.

14. The method of claim 13 wherein enqueuing each of the multiple pluralities of data packets comprises enqueuing each of the multiple pluralities of packets into the corresponding multiple physical queues according to the following relation,

PQ=(LQ×

N)+Qmult

wherein PQ represents a physical queue number of one of the corresponding multiple physical queues, LQ represents a logical queue number corresponding to one of the multiple packet inflows, N represents a number of the corresponding multiple physical queues per each of the multiple packet inflows, and Qmult differentiates between each one of the multiple physical queues of each of the multiple packet inflows.

15. A machine-accessible medium that provides instructions that, if executed by a machine, will cause the machine to perform operations comprising:

enqueuing a plurality of packet pointers into multiple physical queues, the plurality of packet pointers to each point to a memory location temporarily having stored therein one of a corresponding plurality of packets, the corresponding plurality of packets received from a packet flow via a first network link; and

dequeuing the plurality of packet pointers from the multiple physical queues to transmit the plurality of packets onto a second network link.

16. The machine-accessible medium of claim 15 wherein enqueuing the plurality of packet pointers into the multiple physical queues comprises enqueuing the plurality of packet pointers into the multiple physical queues using a round robin enqueuing scheme between the multiple physical queues.

17. The machine-accessible medium of claim 16 wherein dequeuing the plurality of packet pointers from the multiple physical queues comprises dequeuing the plurality of packet pointers from the multiple physical queues using a round robin dequeuing scheme between the multiple physical queues.

18. The machine-accessible medium of claim 15 wherein the dequeuing of the plurality of packet pointers from the multiple physical queues is executed in a same order as the enqueuing of the plurality of packet pointers.

19. The machine-accessible medium of claim 15, further providing instructions that, if executed by the machine, will cause the machine to perform operations, comprising:

enqueuing the plurality of packet pointers into the multiple physical queues for each of multiple packet flows, each of the plurality of packet pointers to point to one of the plurality of memory locations temporarily having stored therein one of the plurality of packets received from one of the multiple packet flows; and

dequeuing the plurality of packet pointers from the multiple physical queues for each of the multiple packet flows to transmit the plurality of packets of each of the multiple packet flows.

20. The machine-accessible medium of claim 19 wherein the multiple packet flows are all transmitted along multiple network links.

21. The machine-accessible medium of claim 15 wherein the multiple physical queues comprise multiple link lists.

22. The machine-accessible medium of claim 19 wherein enqueuing the plurality of packet pointers for each of the multiple packet flows further comprises enqueuing each of the plurality of packet pointers for each of the multiple packet flows into the multiple physical queues for each of the multiple packet flows according to the following relation,

PQ=(LQ×

N)+Qmult

wherein PQ represents a link list number of one of the multiple physical queues, LQ represents a logical queue number corresponding to one of the multiple packet flows, N represents a number of the multiple physical queues per each of the multiple packet flows, and Qmult differentiates between each one of the multiple physical queues of each of the multiple packet flows.

23. A router, comprising:

a first port to receive a plurality of packets of a packet flow;

a memory unit to temporarily queue the plurality of packets of the packet flow;

a queue manager to enqueue a plurality of packet pointers, each one of the plurality of packet pointers to point to one of the plurality of packets temporarily queued, the queue manager to enqueue the plurality of packet pointers into multiple link lists; and

a second port to transmit the plurality of packets thereon, each of the plurality of packets to be transmitted in response to the queue manager dequeuing one of the plurality of packet pointers.

24. The router of claim 23 wherein the queue manager is further to enqueue the plurality of packet pointers into the multiple link lists using a round robin enqueuing scheme between the multiple link lists.

25. The router of claim 24 wherein the queue manager is further to dequeue the plurality of packet pointers from the multiple link lists in a same order as enqueuing the plurality of packet pointers.

26. The router of claim 23 wherein the queue manager comprises hardware entity.

27. The router of claim 26 wherein the queue manager further comprises a software entity.

28. A system, comprising:

a plurality of optical routers, each of the plurality of optical routers comprising;

a first port to receive a plurality of packets of a packet flow;

a memory unit to temporarily queue the plurality of packets of the packet flow;

a queue manager to enqueue a plurality of packet pointers, each one of the plurality of packet pointers to point to one of the plurality of packets temporarily queued, the queue manager to enqueue the plurality of packet pointers into multiple physical queues; and

a second port to transmit the plurality of packets thereon, each of the plurality of packets to be transmitted in response to the queue manager dequeuing one of the plurality of packet pointers; and

a plurality of optical fibers to link the plurality of optical routers into a network, the first port and the second port of each of the plurality of routers each coupled to one of the plurality of optical fibers.

29. The system of claim 28 wherein the queue manager is further to enqueue the plurality of packet pointers into the multiple physical queues using a round robin enqueuing scheme between the multiple physical queues.

30. The system of claim 29 wherein the queue manager is further to dequeue the plurality of packet pointers from the multiple physical queues in a same order as enqueuing the plurality of packet pointers.