Your browser does not support JavaScript!

access icon free Hardware-assisted estimation of entropy norm for high-speed network traffic

The computation of the entropy of a high-speed data stream in a one-pass fashion is crucial to many network security applications. Motivated by the work of Lall et al., this study examines the design trade-off of processing speed and accuracy for estimating the entropy norm. The proposed scheme leverages the Count Sketch with constant memory access on counter update and point query operations. With a bounded relative error and a constant memory access cycle, the design can process incoming traffic with a throughput of 30 Gbit/s.


    1. 1)
      • 5. Lall, A., Sekar, V., Ogihara, M., Xu, J.J., Zhang, H.: ‘Data streaming algorithms for estimating entropy of network traffic’. ACM SIGMETRICS, 2006, pp. 145156.
    2. 2)
      • 1. Lakhina, A., Crovella, M., Diot, C.: ‘Mining anomalies using traffic feature distributions’. Proc. 2005 Conf. Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM '05, ACM, New York, NY, USA, 2005, pp. 217228.
    3. 3)
      • 11. CAIDA: ‘The CAIDA UCSD anonymized internet traces 2012 equinix-sanjose.dira.20120119-130000.utc.anon.pcap.gz’, 2012.
    4. 4)
    5. 5)
      • 2. Nychis, G., Sekar, V., Andersen, D.G., Kim, H., Zhang, H.: ‘An empirical evaluation of entropy-based traffic anomaly detection’. Proc. 8th ACM SIGCOMM Conf. Internet Measurement, ACM, Vouliagmeni, Greece, 2008, pp. 151156.
    6. 6)
      • 9. Alon, N., Matias, Y., Szegedy, M.: ‘The space complexity of approximating the frequency moments’. Proc. 28th Annual ACM Symp. Theory of Computing, STOC'96, New York, NY, USA, 1996, pp. 2029.
    7. 7)
      • 8. Chakrabarti, A., Do Ba, K., Muthukrishnan, S.: ‘Estimating entropy and entropy norm on data streams’. Proc. 23rd Annual Conf. Theoretical Aspects of Computer Science, STACS'06, Berlin, Heidelberg, 2006, pp. 196205.
    8. 8)
      • 3. Bartos, V., Zadnik, M., Cejka, T.: ‘Nemea: framework for stream-wise analysis of network traffic’. CESNET Technical Report, 2013.
    9. 9)
    10. 10)
      • 4. Sekar, V., Reiter, M.K., Zhang, H.: ‘A case for a RISC architecture for network flow monitoring’. Technical Report, CMU-CS-09-125.
    11. 11)
      • 10. Cormode, G.: ‘MassDAL public code bank: Sketches, frequent items, changes (Deltoids)’, Massive Data Analysis Lab..

Related content

This is a required field
Please enter a valid email address