Yousra Chabchoub ; Christine Fricker ; Frédéric Meunier ; Danielle Tibi - Analysis of an algorithm catching elephants on the Internet

dmtcs:3572 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3572
Analysis of an algorithm catching elephants on the InternetArticle

Authors: Yousra Chabchoub 1; Christine Fricker 1; Frédéric Meunier 2; Danielle Tibi 3

  • 1 Networks, Algorithms and Probabilities
  • 2 Laboratoire Ville, Mobilité, Transport
  • 3 Laboratoire de Probabilités et Modèles Aléatoires

The paper deals with the problem of catching the elephants in the Internet traffic. The aim is to investigate an algorithm proposed by Azzana based on a multistage Bloom filter, with a refreshment mechanism (called $\textit{shift}$ in the present paper), able to treat on-line a huge amount of flows with high traffic variations. An analysis of a simplified model estimates the number of false positives. Limit theorems for the Markov chain that describes the algorithm for large filters are rigorously obtained. The asymptotic behavior of the stochastic model is here deterministic. The limit has a nice formulation in terms of a $M/G/1/C$ queue, which is analytically tractable and which allows to tune the algorithm optimally.


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: attack detection,Bloom filter,coupon collector,elephants and mice,network mining,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 172 times.
This article's PDF has been downloaded 149 times.