Algorithm for long-lived large flow identification

摘要

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.

主权项

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; anda 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.