Binned duration flow tracking
AssigneeAlcatel Lucent
InventorBradley James Whitehead
Life of this patent
Estimating the term…
Abstract
Binned Duration Flow Tracking (BDFT) method tracks the duration of packet flows in a resource limited environment by storing packets identifying the beginning and the end of a flow in bins, with each bin covering an independent and arbitrary length of time. Bins are “aged” periodically, based on the range of time which the bin covers. A query as to the flow duration returns the bin number which that flow is in; the bin number is then translated into a range of time. Each bin is a counting bloom filter. The size of the bloom filters, range of the count, and number of hashes used are all parameters of the algorithm which affect memory usage, processing required, and accuracy.
Claims20
A system for measuring a duration of a packet flow of interest in a communication network, comprising:
- a flow descriptor unit for calculating a unique flow descriptor for said packet flow;
- a plurality of timers;
- a plurality of bins, each bin of the plurality of bins connected to a respective timer of the plurality of timers, the plurality of bins covering contiguous time ranges, each bin for keeping said unique flow descriptor until a respective time range expires;
- a bin access interface for storing said unique flow descriptor in a youngest bin on receipt of a flow beginning packet, and removing the unique flow descriptor from a current bin where said unique flow descriptor is currently located, on receipt of a flow ending packet;
- and
- a bin controller for moving the unique flow descriptor from a certain bin to a next, older bin when the respective timer for the certain bin has expired.
A method for measuring a duration of a packet flow of interest in a communication network, comprising:
- calculating a unique flow descriptor from a flow beginning packet;
- storing said unique flow descriptor into a youngest bin of a plurality of bins, covering contiguous time ranges, wherein each bin is connected to a respective timer;
- progressing said unique flow descriptor through said bins from a current bin BinX to a next bin BinX+1 as the respective timers for the bins expire;
- and
- determining the duration of said packet flow based on an identifier X of a bin that currently stores said unique flow descriptor, wherein the identifier X initially has a value of 1.
A method for measuring a duration of a packet flow of interest in a communication network, comprising:
- detecting a flow beginning packet indicating the beginning of said packet flow;
- and
- calculating a unique flow descriptor for said packet flow;
- storing said unique flow descriptor in a youngest bin of a plurality of bins, covering contiguous time ranges, each bin connected to a respective timer and keeping said unique flow descriptor until the respective timer expires;
- moving the unique flow descriptor from a younger bin to a next, older bin when the respective timer for said younger bin expires;
- removing the unique flow descriptor from a current bin where said unique flow descriptor is currently located, on receipt of a flow ending packet;
- and
- determining the duration of said packet flow based on the time range of said current bin.
Dependencies are inferred from the claim text.