Flow-based queuing of network traffic

• US 7,701,849 B1
• Filed: 06/23/2006
• Issued: 04/20/2010
• Est. Priority Date: 06/23/2006
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Ma, Qingming
• Primary Examiner(s): Pham; Chi H.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US11/426,124
• Time in Patent Office: 1,397 Days
• Field of Search: 370/471
• US Class Current: 370/230
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• 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 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3045 Virtual queuing

Abstract

A method is provided for queuing packets. A packet may be received and its flow identified. It may then be determined whether a flow queue has been assigned to the identified flow. The identified flow may be dynamically assigning to an available flow queue when it is determined that a flow queue has not been assigned to the identified flow. The packet may be enqueued into the available flow queue.

Claims

1. A method for queuing packets, comprising:

receiving a packet;

identifying a flow associated with the packet;

determining whether a flow queue has been assigned to the identified flow;

dynamically assigning the identified flow to an available flow queue when it is determined that the flow queue has not been assigned to the identified flow; and

enqueuing the packet into the available flow queue,

where the available flow queue is selected from a pool of available flow queues, and

where the pool of available flow queues is equal to a maximum number of packets capable of simultaneous processing.

2. The method of claim 1, where identifying the flow associated with the packet further comprises:

identifying flow information from a header associated with the packet; and

identifying the flow associated with the packet based on the identified flow information.

3. The method of claim 2, where the flow information includes the packet'"'"'s source address, destination address, source port, destination port, and protocol identifier.

4. The method of claim 1, where the dynamically assigning the identified flow to the available flow queue, further comprises:

identifying an available queue having no active packets; and

assigning a flow identifier associated with the identified flow to the available queue.

5. The method of claim 4, where the determining whether the flow queue has been assigned to the identified flow, further comprises:

determining whether a flow queue identifier has been assigned to the identified flow, where the flow queue identifier comprises a pointer to the assigned flow queue.

6. The method of claim 5, further comprising:

determining whether the flow identifier associated with the identified flow queue matches the flow identifier of the flow associated with the packet;

determining whether the identified flow queue is empty when it is determined that the flow identifier associated with the identified flow queue does not match the flow identifier of the flow associated with the packet; and

enqueuing the packet into the identified flow queue when it is determined that the identified flow queue is empty.

7. The method of claim 6, further comprising:

assigning the flow identifier associated with the identified flow queue to the flow identifier associated with the identified flow.

8. The method of claim 6, further comprising:

dynamically assigning the identified flow to the available flow queue when it is determined that the flow identifier associated with the identified flow queue does not match the flow identifier of the flow associated with the packet and that the identified flow queue is not empty; and

enqueuing the packet into the available flow queue.

9. The method of claim 1, further comprising:

maintaining a flow table that maps identified flows and flow queue identifiers; and

determining whether the flow queue has been assigned to the identified flow based on entries in the flow table.

10. A network device comprising:

an input interface configured to receive a data unit;

an interface configured to forward the data unit to another network device;

a plurality of flow queues, associated with the interface, configured to store data units or pointers to the data units, each of the plurality of flow queues being dynamically assigned to flows associated with the data unit; and

a scheduler component configured to;

identify a flow associated with the data unit;

determine whether the flow associated with the data unit has been assigned to a flow queue in the plurality of flow queues;

dynamically assign the flow associated with the data unit to an available flow queue when it is determined that the flow associated with the data unit has not been assigned to the flow queue in the plurality of flow queues;

store the data unit in the available flow queue;

determine whether a flow identifier associated with the flow queue matches a flow identifier associated with the flow when it is determined that the flow associated with the data unit has been assigned to the flow queue in the plurality of flow queues; and

store the data unit in the flow queue when it is determined that a flow identifier, associated with the flow queue, matches the flow identifier associated with the flow.

11. The network device of claim 10, where the scheduler component is further configured to:

determine whether the flow queue is empty when it is determined that a flow identifier associated with the flow queue does not match the flow identifier associated with the flow;

reassign the flow queue to the flow when it is determined that the flow queue is empty; and

store the data unit in the flow queue.

12. The network device of claim 11, where the scheduler component is further configured to:

identify the available flow queue from among the plurality of flow queues when it is determined that the flow queue is not empty;

assign the flow queue to the available flow; and

store the data unit in the available flow queue.

13. The network device of claim 12, where, when identifying the available flow queue from among the plurality of flow queues, the scheduler component is configured to:

perform a first hashing operation on a flow identifier associated with the flow to generate a flow queue identifier;

determine whether the flow queue associated with the flow queue identifier is available; and

perform a second hashing operation on the flow identifier associated with the flow to generate a second flow queue identifier.

14. The network device of claim 13, where the second hashing operation is different than the first hashing operation.

15. The network device of claim 10, where the network device is a router.

16. A network device comprising:

logic, implemented in hardware, configured to;

maintain a flow table including flow information for each of a plurality of flow, where the flow information for each flow includes a flow identifier, and a flow queue identifier;

receive a packet;

identify the flow identifier associated with the packet;

determine whether the flow information associated with the flow identifier includes the flow queue identifier;

identify an available flow queue from a pool of flow queues when it is determined that the flow information associated with the flow identifier does not include the flow queue identifier,

where the pool of flow queues includes a number of flow queues equal to a maximum number of simultaneously processed packets;

add the flow queue identifier associated with the available flow queue to the flow information associated with the flow identifier;

assign the flow identifier to the available flow queue; and

enqueue the packet in the available flow queue.

17. The network device of claim 16, where the logic is further configured to:

determine whether the flow queue associated with the flow queue identifier remains associated with the flow; and

enqueue the packet in the flow queue when it is determined that the flow queue identifier remains associated with the flow.

18. The network device of claim 17, where the logic configured to determine whether the flow queue associated with the flow queue identifier remains associated with the flow further comprises:

logic configured to determine whether a flow identifier associated with the flow queue matches the flow identifier associated with the packet.

19. The network device of claim 17, further comprising logic configured to:

determine whether the flow queue is empty when the flow queue associated with the flow queue identifier is no longer associated with the flow;

identify the available flow queue from the pool of flow queues when it is determined that the flow queue is not empty;

add the flow queue identifier associated with the available flow queue to the flow information associated with the flow identifier;

assign the flow identifier to the available flow queue; and

enqueue the packet in the available flow queue.

20. A method for queuing packets, comprising:

receiving a packet;

identifying a flow associated with the packet;

determining whether a flow queue has been assigned to the identified flow;

dynamically assigning the identified flow to an available flow queue when it is determined that the flow queue has not been assigned to the identified flow; and

enqueuing the packet into the available flow queue,

where the available flow queue is selected from a pool of available flow queues, and

where the pool of available flow queues is equal to a maximum number of queue slots.

21. The method of claim 20, where identifying the flow associated with the packet further comprises:

identifying flow information from a header associated with the packet; and

identifying the flow associated with the packet based on the identified flow information.

22. The method of claim 20, further comprising:

maintaining a flow table that maps identified flows and flow queue identifiers; and

determining whether the flow queue has been assigned to the identified flow based on entries in the flow table.