LOGLOG counting for the estimation of IP traffic

Olivier Gandouet 1, 2 Alain Jean-Marie 3, 1
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
3 APR - Algorithmes et Performance des Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper, we discuss the problem of estimating the number of "elephants'' in a stream of IP packets. First, the problem is formulated in the context of multisets. Next, we explore some of the theoretical space complexity of this problem, and it is shown that it cannot be solved with less than $\Omega (n)$ units of memory in general, $n$ being the number of different elements in the multiset. Finally, we describe an algorithm, based on Durand-Flajolet's LOGLOG algorithm coupled with a thinning of the packet stream, which returns an estimator of the number of elephants using a small amount of memory. This algorithm allows a good estimation for particular families of random multiset. The mean and variance of this estimator are computed. The algorithm is then tested on synthetic data.
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.119-128, 2006, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184707
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:07:09
Dernière modification le : jeudi 11 janvier 2018 - 17:00:43
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:09:55

Fichier

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

Identifiants

  • HAL Id : hal-01184707, version 1

Citation

Olivier Gandouet, Alain Jean-Marie. LOGLOG counting for the estimation of IP traffic. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.119-128, 2006, DMTCS Proceedings. 〈hal-01184707〉

Partager

Métriques

Consultations de la notice

337

Téléchargements de fichiers

88