Methods and apparatus for path selection within a network based on flow duration

• US 9,716,661 B2
• Filed: 05/11/2015
• Issued: 07/25/2017
• Est. Priority Date: 03/09/2011
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Aybay, Gunes
• Primary Examiner(s): Doan, Duyen
• Application Number:
  US14/708,650
• Publication Number:
  US 20150244633A1
• Time in Patent Office: 806 Days
• Field of Search: 709234, 370230
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/6295 using multiple queues, one for each individual QoS, connection, flow or priority

Abstract

In some embodiments, an apparatus includes a forwarding module that is configured to receive a group of first data packets. The forwarding module is configured to modify a data flow value in response to receiving each first data packet. The forwarding module is also configured to store each first data packet in a first output queue based on the data flow value not crossing a data flow threshold after being modified. Furthermore, the forwarding module is configured to receive a second data packet. The forwarding module is configured to modify the data flow value in response to receiving the second data packet, such that the data flow value crosses the data flow threshold. The forwarding module is configured to store the second data packet in a second output queue based on the data flow value having crossed the data flow threshold.

Claims

1. An apparatus, comprising:

a switching device including a memory and a processor operatively coupled to the memory, the processor configured to execute a flow module; and

the flow module configured to determine that a data flow identifier included in a data packet does not match an entry in a flow cache,

the flow module configured to determine, in response to the determination that the data flow identifier included in the data packet does not match an entry in the flow cache, that a first hash value based on a header portion of the data packet matches an entry in a first hash table,

the flow module configured to calculate, in response to the determination that the first hash value based on the header portion of the data packet matches an entry in the first hash table, a second hash value based on that header portion of the data packet,

the flow module configured to increment a data flow counter that is in the first hash table and that is associated with a first data flow when the second hash value matches an entry in a second hash table,

the flow module configured to define an entry and a data flow counter in the second hash table and that are both associated with a second data flow when the second hash value does not match an entry in the second hash table.

2. The apparatus of claim 1, wherein:

the data flow counter in the second hash table is a data packet counter,

when the second hash value does not match an entry in the second hash table, the data packet counter configured to be incremented in response to receiving the data packet.

3. The apparatus of claim 1, wherein:

the data flow counter in the first hash table is a data packet counter,

when the second hash value matches an entry in a second hash table, the data packet counter configured to be incremented in response to receiving the data packet.

4. The apparatus of claim 1, wherein:

the data flow counter in the second hash table is a data packet size counter,

when the second hash value does not match an entry in the second hash table, the data packet size counter configured to be incremented by an amount associated with a size of the data packet.

5. The apparatus of claim 1, wherein:

the data flow counter in the first hash table is a data packet size counter,

when the second hash value matches an entry in a second hash table, the data packet size counter configured to be incremented by an amount associated with a size of the data packet.

6. The apparatus of claim 1, wherein:

the data flow counter in the second hash table is a moving average bandwidth counter,

when the second hash value does not match an entry in the second hash table the moving average bandwidth counter configured to be modified based on a size of the data packet and an amount of time between receiving the data packet and receiving a previous most-recent data packet having a common source identifier and a common destination identifier with the data packet.

7. The apparatus of claim 1, wherein:

the data flow counter in the first hash table is a moving average bandwidth counter,

when the second hash value matches an entry in a second hash table the moving average bandwidth counter configured to be modified based on a size of the data packet and an amount of time between receiving the data packet and receiving a previous most-recent data packet having a common source identifier and a common destination identifier with the data packet.

8. The apparatus of claim 1, wherein:

the flow module is configured to modify the data flow counter in the first hash table by either increasing or decreasing a value the data flow counter in the first hash table; and

the flow module is configured to modify the data flow counter in the second hash table by either increasing or decreasing a value of the data flow counter in the second hash table.

10. The method of claim 8, further comprising:

modifying the data flow counter in the first hash table by either increasing or decreasing a value of the data flow counter in the first hash table; and

modifying the data flow counter in the second hash table by either increasing or decreasing a value of the data flow counter in the second hash table.

11. The method of claim 8, wherein:

the data flow counter in the second hash table is a data packet counter,

when the second hash value does not match an entry in the second hash table, the data packet counter configured to be incremented in response to receiving the data packet.

12. The method of claim 8, wherein,

the data flow counter in the first hash table is a data packet counter,

when the second hash value matches an entry in a second hash table, the data packet counter configured to be incremented in response to receiving the data packet.

13. The method of claim 8, wherein:

the data flow counter in the second hash table is a data packet size counter,

when the second hash value does not match an entry in the second hash table, the data packet size counter configured to be incremented by an amount associated with a size of the data packet.

14. The method of claim 8, wherein:

the data flow counter in the first hash table is a data packet size counter,

when the second hash value matches an entry in a second hash table, the data packet size counter configured to be incremented by an amount associated with a size of the data packet.

15. The method of claim 8, wherein:

the data flow counter in the second hash table is a moving average bandwidth counter,

when the second hash value does not match an entry in the second hash table the moving average bandwidth counter configured to be modified based on a size of the data packet and an amount of time between receiving the data packet and receiving a previous most-recent data packet having a common source identifier and a common destination identifier with the data packet.

9. A method, comprising:

determining that a data flow identifier included in a data packet does not match an entry in a flow cache,

determining, in response to the determination that the data flow identifier included in the data packet does not match an entry in the flow cache, that a first hash value based on a header portion of the data packet matches an entry in a first hash table,

calculating, in response to the determination that the first hash value based on the header portion of the data packet matches an entry in the first hash table, a second hash value based on that header portion of the data packet,

incrementing a data flow counter that is in the first hash table and that is associated with a first data flow when the second hash value matches an entry in a second hash table,

defining an entry as well as a data flow counter in the second hash table and that are both associated with a second data flow when the second hash value does not match an entry in the second hash table.

16. A non-transitory processor-readable medium storing code representing instructions to be executed by a processor, the code comprising code to cause the processor to:

determine that a data flow identifier included in a data packet does not match an entry that is associated with a data flow in a flow cache; and

when, based on the determination that the data flow identifier included in the data packet does not match an entry that is associated with the data flow in the flow cache, a first hash value based on a header portion of the data packet does not match an entry in a first hash table;

define an entry in the first hash table that is associated with the data flow;

define a data flow counter in the first hash table that is associated with the data flow;

define an entry in a second hash table that is associated with the data flow; and

increment the data flow counter in the first hash table.

17. The non-transitory processor-readable medium storing code representing instructions to be executed by a processor of claim 16, wherein the data packet is a first data packet, the code further comprising code:

determine that a data flow identifier included in a second data packet matches an entry that is associated with a data flow in a flow cache; and

incrementing a data flow counter in the flow cache.

18. The non-transitory processor-readable medium storing code representing instructions to be executed by a processor of claim 16, the code further comprising code to modify the data flow counter in the first hash table by either increasing or decreasing a value of the data flow counter in the first hash table.

19. The non-transitory processor-readable medium storing code representing instructions to be executed by a processor of claim 16, wherein:

the data flow counter in the first hash table is a data packet size counter,

the data packet size counter configured to be incremented by an amount associated with a size of the data packet.

20. The non-transitory processor-readable medium storing code representing instructions to be executed by a processor of claim 16, wherein:

the data flow counter in the first hash table is a moving average bandwidth counter,

the moving average bandwidth counter configured to be modified based on a size of the data packet and an amount of time between receiving the data packet and receiving a previous most-recent data packet having a common source identifier and a common destination identifier with the data packet.