Rate detection, or incoming event stream intensity measuring in the decay model

Introduction

Heavy hitter detection problem

Problem classification

  • Threshold-t. The flows having a rate higher than a given fraction t of the rate of total incoming traffic are to be recognized.
  • Top-k. For a given number k, the the highest k rate flows are to be selected.
  • The flows having a rate higher than a given absolute value.

Target architecture

Problem parameters

  • The absolute value of the flow rate, which is considered dangerous. The problem is to identify such flows.
  • The size of the key which identifies the event type. For instance, if the packets with the same source IP address are declared to be the same, then the key is defined as the 4-bytes value src.ip. In this implementation, as in many other algorithms, key values are stored in some table, so the key size affects memory costs.
  • A method for calculating the rate of a single flow from the timestamps of events belonging to the same type. In essence, this is an algorithmic definition of what is the rate of the flow. In this case, an exponential moving average is calculated, which has a single parameter — the typical time τ, during which the weight of the event after its arrival is taken into account.

Solution accuracy

Overheads

Methods for estimating the rate of the event flow

Methods of multiple flows accounting

  • Packet sampling
  • Space saving algorithm
  • HashParallel
  • HashPipe
  • Count-min sketch

Problem formalization

  • Counting the number of events:
  • Counting the number of events taking the weight into account:
  • Calculation of exponential moving average (EMA) with the β parameter. Here the counter s = (v, t) stores two values: the current value of the EMA and the time of the last update.

The decay model

“v” value for different flows

Counter update

Rate definition

r- and r+ function graphs for τ = 15

Applicability limitations of the decay model

Multiple flows accounting algorithms

Decay model features

Numerical implementation of the decay-based count

Update value operation

Calculating Rτ: FPU

Calculating Rτ: table implementation

ρ function graph

Results and Conclusion

  1. Naive implementation of EMA;
  2. Decay-based model with FPU calculations, i.e. with exp() and log() functions calls from standard math library;
  3. Decay-based model implemented via table.

Acknowledgements

--

--

--

DDoS Attacks Mitigation and Continuous Availability

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Practical Machine Learning with Keras

Battle of the Deep Learning frameworks — Part I: 2017, even more frameworks and interfaces

Machine Learning Engineer Intern at Jumio/Master student at Mila

AI, ML, DL and Everything in Between

How should I build a Residual Block?

Frequent Category Imputation (Missing Data Imputation Technique)

Understanding of K-Nearest Neighbours

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Qrator Labs

Qrator Labs

DDoS Attacks Mitigation and Continuous Availability

More from Medium

Using Depth First Search to Determine if a Graph Contains a Cycle

Min-Max Normalization

Comprehensive Overview of AlexNet Architecture

Understanding bias and variance trade-off