A data streaming algorithm for estimating entropies of od flows
Lists
Only you see this
Abstract
Entropy has recently gained considerable significance as an important metric for network measurement. Previous research has shown its utility in clustering traffic and detecting traffic anomalies. While measuring the entropy of the traffic observed at a single point has already been studied, an interesting open problem is to measure the entropy of the traffic between every origin-destination pair. In this paper, we propose the first solution to this challenging problem. Our sketch builds upon and extends the Lp sketch of Indyk with significant additional innovations. We present calculations showing that our data streaming algorithm is feasible for high link speeds using commodity CPU/memory at a reasonable cost. Our algorithm is shown to be very accurate in practice via simulations, using traffic traces collected at a tier-1 ISP backbone link.
BibTeX
@inproceedings{zhao2007data,
author = {Haiquan Chuck Zhao and Ashwin Lall and Mitsunori Ogihara and Oliver Spatscheck and Jia Wang and Jun Jim Xu},
title = {{A data streaming algorithm for estimating entropies of od flows}},
booktitle = {Internet Measurement Conference},
year = {2007},
url = {https://openreview.net/forum?id=lOE-ySmw4vm},
}Loading related content...