Geodesic
LOGLOG counting for the estimation of IP traffic
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2006_special_252_a27,
     author = {Gandouet, Olivier and Jean-Marie, Alain},
     title = {LOGLOG counting for the estimation of {IP} traffic},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities},
     year = {2006},
     doi = {10.46298/dmtcs.3503},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3503/}
}
TY  - JOUR
AU  - Gandouet, Olivier
AU  - Jean-Marie, Alain
TI  - LOGLOG counting for the estimation of IP traffic
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3503/
DO  - 10.46298/dmtcs.3503
LA  - en
ID  - DMTCS_2006_special_252_a27
ER  - 
%0 Journal Article
%A Gandouet, Olivier
%A Jean-Marie, Alain
%T LOGLOG counting for the estimation of IP traffic
%J Discrete mathematics & theoretical computer science
%D 2006
%V DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3503/
%R 10.46298/dmtcs.3503
%G en
%F DMTCS_2006_special_252_a27
Gandouet, Olivier; Jean-Marie, Alain. LOGLOG counting for the estimation of IP traffic. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006). doi : 10.46298/dmtcs.3503. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3503/

Cité par Sources :