Methods and Systems for Estimating Entropy
First Claim
Patent Images
1. A method for estimating entropy, comprising:
- setting an allowable error to deciding a sample number according to a total of packets in a stream data;
randomly sampling a plurality of locations in the stream data;
applying to a count sketch algorithm to each packet for performing the count and update;
applying the counter sketch algorithm to the each packet for performing the query according to flow IDs of the plurality of locations;
recording each query result of the each packet onto an entropy table;
obtaining an average of a counter used in each same row in the entropy table;
selecting a median to be an estimation value from the averages; and
obtaining an estimation entropy value according to the estimation value.
1 Assignment
0 Petitions
Accused Products
Abstract
It is a challenge task to conduct Entropy computation on the attributes of packet header in high-speed networks. Motivated by Ashwin Lall et al., we present a stream-based scheme to estimate to the entropy norm based on Count Sketch algorithm. The system is implemented on a NetFPGA-10G platform. It is capable of processing IP packets and computing the entropy in 30 Gbps line rate.
-
Citations
20 Claims
-
1. A method for estimating entropy, comprising:
-
setting an allowable error to deciding a sample number according to a total of packets in a stream data; randomly sampling a plurality of locations in the stream data; applying to a count sketch algorithm to each packet for performing the count and update; applying the counter sketch algorithm to the each packet for performing the query according to flow IDs of the plurality of locations; recording each query result of the each packet onto an entropy table; obtaining an average of a counter used in each same row in the entropy table; selecting a median to be an estimation value from the averages; and obtaining an estimation entropy value according to the estimation value. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for estimating entropy, comprising:
-
a measuring module, setting an allowable error to deciding a sample number according to a total of packets in a stream data; a sampling module, coupled to the measuring module, randomly sampling a plurality of locations in the stream data; a calculation and update module, coupled to the sampling module, applying to a count sketch algorithm to each packet for performing the count and update; a query module, coupled to the calculation and update module, applying the counter sketch algorithm to the each packet for performing the query according to flow IDs of the plurality of locations; and a storage module, coupled to the query module and the calculation and update module, obtaining an average of a counter used in each same row in the entropy table, and selecting a median to be an estimation value from the averages, and obtaining an estimation entropy value according to the estimation value. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. The method for estimating entropy, comprising:
-
applying a data streaming algorithm for estimating entropy for deciding a sampling number and randomly sampling a plurality of locations in a stream data; and applying a count sketch algorithm to obtain a estimation entropy value. - View Dependent Claims (16, 17, 18, 19)
-
-
20. The method for estimating entropy, wherein the plurality of locations is an array having g×
- z locations, and the entropy table is an array table, wherein the g and z are selected by a equation, and the equation is as follows;
- z locations, and the entropy table is an array table, wherein the g and z are selected by a equation, and the equation is as follows;
Specification