Analysis of an algorithm catching elephants on the Internet

Abstract : 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.
Type de document :
Communication dans un congrès
Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.295-310, 2008, DMTCS Proceedings
Liste complète des métadonnées


https://hal.inria.fr/hal-01194674
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 7 septembre 2015 - 12:50:57
Dernière modification le : mercredi 10 mai 2017 - 17:41:12
Document(s) archivé(s) le : mardi 8 décembre 2015 - 11:27:20

Fichier

dmAI0119.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01194674, version 1

Citation

Yousra Chabchoub, Christine Fricker, Frédéric Meunier, Danielle Tibi. Analysis of an algorithm catching elephants on the Internet. Roesler, Uwe. Fifth Colloquium on Mathematics and Computer Science, 2008, Kiel, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science, pp.295-310, 2008, DMTCS Proceedings. <hal-01194674>

Partager

Métriques

Consultations de
la notice

411

Téléchargements du document

75