Flow-based queuing of network traffic

• US 8,064,344 B2
• Filed: 02/16/2010
• Issued: 11/22/2011
• 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:
  US12/706,478
• Publication Number:
  US 20100150164A1
• Time in Patent Office: 644 Days
• Field of Search: None
• 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, comprising:

receiving, by a device, a packet;

identifying, by the device, a particular flow, of a plurality of flows, associated with the received packet,

where identifying the particular flow includes;

performing a function, based on information associated with the received packet, to obtain a value, and

identifying the particular flow based on the obtained value;

determining, by the device, whether a flow queue, of a plurality of flow queues, has been assigned to the particular flow associated with the received packet;

dynamically assigning, by the device, the particular flow to an available flow queue, of a plurality of available flow queues, when no flow queue has been assigned to the particular flow; and

enqueuing, by the device, the received packet into the available flow queue after the particular flow has been dynamically assigned to the available flow queue.

2. The method of claim 1, where the information associated with the received packet includes at least one of a source address, a destination address, a source port, a destination port, or a protocol identifier, and

where performing the function comprises:

performing a hashing function, based on the at least one of the source address, the destination address, the source port, the destination port, or the protocol identifier, to obtain the value.

3. The method of claim 1, further comprising:

determining that a flow queue, of the plurality of flow queues, associated with a flow queue identifier that corresponds to the obtained value, is in use;

performing, when the flow queue is in use and based on the information, a second, different function to obtain a second value; and

identifying the available flow queue based on the obtained second value.

4. The method of claim 1, further comprising:

receiving another packet associated with the particular flow; and

enqueuing the received other packet into the available flow queue.

5. The method of claim 1, where the received packet correspond to a first packet, the particular flow corresponds to a first flow, and the flow queue corresponds to a first flow queue,

the method further comprising:

identifying a second flow, of the plurality of flows, associated with a received second packet;

determining that a second flow queue, of the plurality of flow queues, has been previously assigned to the second flow;

determining whether the second flow queue has been reassigned to a third flow; and

determining, when the second flow queue has been reassigned to the third flow, whether the second flow queue is empty.

6. The method of claim 5, further comprising:

enqueueing the second packet, into the second flow queue, when the second flow queue is empty; and

enqueueing the second packet into a third flow queue, of the plurality of flow queues, when the second flow queue is not empty.

7. A system comprising:

one or more components, implemented at least partially in hardware, to;

receive information included in a packet;

identify a flow, of a plurality of flows, associated with the packet, based on the information,

where, when identifying the flow, the one or more components are to;

perform a function, based on the information, to obtain a value, and

identify the flow based on the obtained value;

determine whether a flow queue, of a plurality of flow queues, has been assigned to the flow associated with the packet;

dynamically assign the flow, associated with the packet, to an available flow queue, of a plurality of available flow queues, when no flow queue has been assigned to the flow; and

enqueue the packet into the available flow queue when the flow has been dynamically assigned to the available flow queue.

8. The system of claim 7, where the one or more components are further to:

determine that a particular flow queue, of the plurality of flow queues, has been previously assigned to the flow associated with the packet;

determine that the particular flow queue has been reassigned to a second flow; and

determine whether the particular flow queue is empty.

9. The system of claim 8, where the one or more components are further to:

determine that the particular flow queue is not empty, and

dynamically assign the flow to the available flow queue when the particular flow queue is not empty.

10. The system of claim 7, where the information included in the packet comprises information associated a header of the packet, and

where, when performing the function, the one or more components are to:

perform a hash function using the information associated with the header of the packet, and

identify the flow based on a hash value of the performed hash function,

where the obtained value includes the hash value.

11. The system of claim 10, where, when dynamically assigning the flow to the available flow queue, the one or more components are to:

set flow identification information, associated with the available flow queue, to the hash value.

12. The system of claim 7, where the one or more components are further to:

assign a weight to the available flow queue, the weight corresponding to a bandwidth allocated to the available flow queue, and

dequeue one or more packets from the available flow queue based on the weight.

13. The system of claim 7, where, when determining whether a flow queue has been assigned to the flow, the one or more components are to:

search a table for identification information of the flow,

where the table stores identification information, associated with flow queues, that correspond to identification information of flows that are associated with the flow queues.

14. A device comprising:

logic, implemented at least partially in hardware, to;

receive information associated with a header of a packet;

identify a flow, of a plurality of flows, associated with the packet, based on the information associated with the header of the packet,

where, when identifying the flow, the logic is to;

perform a function, based on the information associated with the header of the packet, to obtain a value, and

identifying the flow based on the obtained value;

determine whether a flow queue, of a plurality of flow queues, has been assigned to the flow associated with the packet;

assign the flow, associated with the packet, to an available flow queue, of a plurality of available flow queues, when no flow queue has been assigned to the flow; and

enqueue the packet into the available flow queue after the flow has been assigned to the available flow queue.

15. The device of claim 14, where, when performing the function, the logic is to:

perform a hash function using the information associated with the header of the packet, and

identify the flow based on a hash value of the performed hash function,

where the obtained value includes the hash value.

16. The device of claim 15, where, when determining whether a flow queue has been assigned to the flow, the logic is to:

search a table, that stores identification information of the plurality of flow queues, based on the hash value,

where the identification information, of one or more of the plurality of flow queues, corresponds to identification information of one or more respective flows, of the plurality of flows.

17. The device of claim 15, where, when dynamically assigning the flow to the available flow queue, the logic is to:

set flow identification information of the available flow queue to the hash value.

18. The device of claim 14, where the logic is further to:

receive at least one other packet associated with the flow; and

enqueue the at least one other packet into the available flow queue.

19. The device of claim 14, where the packet corresponds to a first packet, the flow corresponds to a first flow, and the flow queue corresponds to a first flow queue,

where the logic is further to:

identify a second flow, of the plurality of flows, associated with a received second packet,

determine that a second flow queue, of the plurality of flow queues, has been previously assigned to the second flow,

determine whether the second flow queue has been reassigned to a third flow,

determine whether the second flow queue is empty, when the flow queue is reassigned to the third flow, and

enqueue the second packet into a third flow queue, of the plurality of flow queues, when the second flow queue is not empty.