Algorithm for long-lived large flow identification

• US 9,306,794 B2
• Filed: 03/12/2013
• Issued: 04/05/2016
• Est. Priority Date: 11/02/2012
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Brocade Communications Systems, Inc. (Broadcom, Inc.)
• Inventors: Kirshnan, Ram, Terry, John
• Primary Examiner(s): Hsu, Alpus H
• Assistant Examiner(s): Thai, Camquyen
• Application Number:
  US13/797,169
• Publication Number:
  US 20140126393A1
• Time in Patent Office: 1,120 Days
• Field of Search: 709/223, 709/232, 709/238, 711/216, 713/201, 704/10, 370/230, 370/235, 370/392
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/062 related to network traffic
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A mechanism for identifying long-lived large flows in a communication network is disclosed in which packets transmitted through ports of a switching device or router are continuously examined. As new flows are recognized, their flow definition information is processed through a hashing table that uses a predetermined number of hash stages each having a pre-selected number of hash buckets. Each hash bucket has a counter that is incremented each time flow definition information ends up in the bucket. At the same time as counters are incremented, they are compared against a threshold number. If the bucket counters for all the hash stages exceed this threshold number, the flow is identified as a long-lived large flow and stored as such in a flow table.

Claims

1. A hash engine for identifying long-lived large flows comprising:

a plurality of hashing stages for receiving a flow key associated with a flow, wherein each hashing stage includes;

a hash function that generates an n bit output from the flow key;

a plurality of hash buckets, wherein each hash bucket includes a counter providing a hash counter value, wherein one of the hash buckets is selected based on the n bit output, wherein n is an integer greater than 1; and

a comparator coupled to each of the hash buckets such that the comparator compares the hash counter value of the selected hash bucket with a predetermined threshold to determine if the hash counter value of the selected hash bucket exceeds the predetermined threshold; and

wherein a logic operation is performed on the result from all comparators of the hashing stages to identify the flow as a long-lived large flow if the hash counter values for all of the selected hash buckets exceed the predetermined threshold.

2. The hash engine of claim 1, wherein the hash counter value of the selected hash bucket is incremented when the hash function maps the flow key to the selected hash bucket.

3. The hash engine of claim 2, wherein the hash counter value of the selected hash bucket is compared by the comparator after being incremented.

4. The hash engine of claim 1, wherein each hashing stage receives and processes the same flow key.

5. The hash engine of claim 1, wherein at least some of hash functions within the hashing stages implement different hash function within each hashing stage performs.

6. The hash engine of claim 1, wherein the number of hash buckets within each hash stage is 2n.

7. A network device comprising:

an input port for receiving frame flows;

a packet processing circuitry coupled to the input port for processing the received flows, the packet processing circuitry comprising;

a memory for storing information related to identified long-lived large flows; and

a hash engine comprising;

a plurality of hashing stages for processing a flow key associated with the received flow, wherein each hashing includes;

a hash function that generates an n bit output based on the flow key;

a plurality of hash buckets, wherein each bucket includes a counter that provides a hash counter value, wherein at least one of the hash buckets is selected by the n bit output, wherein n is an integer and greater than 1; and

a comparator coupled to each of the hash buckets such that the comparator compares the hash counter value of the at least one selected hash bucket with a predetermined threshold to determine if the hash counter value of the at least one selected hash bucket exceeds the predetermined threshold; and

wherein a logic operation is performed on the result from all comparators of the hashing stages to identify the received flow as a long-lived large flow if the hash counter values for all of the at least one selected hash buckets exceed the predetermined threshold.

8. The network device of claim 7, wherein each the hash counter value of the at least one selected hash bucket is incremented when the hash function maps the flow key to the at least one selected hash bucket.

9. The network device of claim 8, wherein the hash counter value of the at least one selected hash bucket is compared by the comparator after being incremented.

10. The network device of claim 7, wherein the memory includes a flow table for storing flow entries for each identified long-lived large flow.

11. The network device of claim 10, wherein each flow entry has an associated counter.

12. The network device of claim 10, wherein the flow key is sent to the hash engine when the flow table is unable to identify the received flow as the long-lived large flow.

13. The network device of claim 7, wherein each hashing stage receives and processes the same flow key.

14. The network device of claim 7, wherein each hash function of each hashing stage is different.

15. The network device of claim 7, wherein the number of hash buckets within each hash stage is 2n.

16. A method for identifying long-lived large flows comprising:

receiving a flow key associated with a flow;

inputting the flow key in a plurality of hashing stages, wherein each hashing stage performs a hash function to generate an n bit output using the flow key;

for each hashing stage, selecting a hash bucket from a plurality of hash buckets based on the n bit output, wherein each hash bucket includes a counter that provides a hash counter value, wherein n is an integer and greater than 1;

for each hashing stage, comparing the hash counter value of the selected hash bucket with a predetermined threshold to determine if the hash counter value of the selected hash bucket exceeds the predetermined threshold; and

identifying the flow as a long-lived large flow if the hash counter values of all of the selected hash buckets exceed the predetermined threshold.

17. The method of claim 16, further comprising incrementing each hash counter value of the selected hash bucket when the hash function maps the flow key to the selected hash bucket.

18. The method of claim 17, wherein the hash counter value of the selected hash bucket is compared after being incremented.

19. The method of claim 16, wherein each hashing stage receives and processes the same flow key.

20. The method of claim 16, wherein each hashing stage performs a different hash function.

21. The method of claim 16, wherein the number of hash buckets within each hash stage is 2n.