Tracking network-data flows
AssigneeAlcatel Lucent
InventorsAiyou Chen, Jin Cao, Li Li
Life of this patent
Estimating the term…
Abstract
A network-equipment-implemented method and apparatus for tracking durations of flows received at a network node in consecutive intervals utilizes two counting bloom filters in ping-pong operation to reduce memory and processing. Identifiers for flows that exceed a predetermined duration or number of intervals are stored in a long-duration flow-identifier table. Hash functions used within the counting bloom filters and optionally used in the long-duration flow-identifier table are chosen to minimize the probability of false positives in the detection of long-duration flows. In some embodiments, flows are sampled to conserve memory and processing resources at the risk of missing detection of some long-duration flows.
Claims20
A network-equipment-implemented method for monitoring network-data flows at a node in a communication network, the method comprising:
- (a) receiving a network-data flow at the node in a current time interval;
- (b) determining a previous duration estimate for the network-data flow as a function of values stored in a first counting bloom filter associated with a previous time interval;
- (c) storing, in a second counting bloom filter associated with the current time interval, a new count that is a function of the previous duration estimate;
- and
- (d) storing, in a flow-identifier data structure, an identifier for the network-data flow, as a function of the new count, wherein the new count for a counter in the second counting bloom filter represents a possible duration for a network-data flow that hashes to the counter.
Apparatus for monitoring durations of one or more data flows in a communication network, the apparatus comprising:
- a previous bloom filter (i) associated with a previous time interval and (ii) having (1) a previous set of hash functions and (2) an array of counters storing previous counter values;
- and
- a current bloom filter (i) associated with a current time interval and (ii) having (1) a current set of hash functions and (2) an array of counters storing current counter values, wherein:
- for at least one packet of each data flow received in the current time interval, the current counter value for each counter hashed to by applying the current set of hash functions to the data flow is updated based on (i) the current counter value and (ii) a previous duration estimate for the data flow derived from the previous bloom filter;
- and
- the current counter value for a counter in the current bloom filter represents a possible duration for a data flow that hashes to the counter.
Apparatus for monitoring durations of one or more data flows in a communication network, the apparatus comprising:
- a previous bloom filter (i) associated with a previous time interval and (ii) having (1) a previous set of hash functions and (2) an array of counters storing previous counter values;
- and
- a current bloom filter (i) associated with a current time interval and (ii) having (1) a current set of hash functions and (2) an array of counters storing current counter values, wherein:
- for at least one packet of each data flow received in the current time interval, the current counter value for each counter hashed to by applying the current set of hash functions to the data flow is updated based on (i) the current counter value and (ii) a previous duration estimate for the data flow derived from the previous bloom filter;
- the previous duration estimate for the data flow is based on a minimum of the previous counter values in counters hashed to by applying the previous set of hash functions to the data flow;
- and
- the current counter value for each hashed-to counter for the data flow is based on a maximum of (i) the current counter value and (ii) an incremented value of the previous duration estimate for the data flow.
Dependencies are inferred from the claim text.