Methods and Systems for Estimating Entropy

• US 20160191918A1
• Filed: 03/06/2015
• Published: 06/30/2016
• Est. Priority Date: 12/31/2014
• Status: Active Grant

• Current Assignee: Chung-Yuan Christian University
• Original Assignee: Chung-Yuan Christian University
• Inventors: Lai, Yu-Kuen, Wellem, Theophilus, Yu, Hui-Ping
• Granted Patent: US 9,781,427 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 63/14 for detecting or protecting against malicious traffic
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/164 Feedback from the receiver or from the transmission channel
• CPC Class Codes: H04N 19/166 concerning the amount of transmission errors, e.g. bit error rate [BER]
• CPC Class Codes: H04N 19/19 using optimisation based on Lagrange multipliers
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

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.

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.

2. The method for estimating entropy according to claim 1, wherein the plurality of locations is an array having g×

z locations.

3. The method for estimating entropy according to claim 2, wherein the g and z are selected according to an equation as follow:

4. The method for estimating entropy according to claim 1, wherein the entropy table is an array table.

5. The method for estimating entropy according to claim 1, wherein the step of obtaining an average of a counter used in each same row in the entropy table, further comprising:

obtaining a calculation value by calculating the counter value used in the each same row in the entropy table according to a equation; and

obtaining the average of the counter of each row according to the calculation value.

6. The method for estimating entropy according to claim 5, wherein the equation is represents as follows:

X=m(c log(c)−

(c−

1)log(c−

1)).

7. The method for estimating entropy according to claim 1, wherein the step of obtaining an estimation entropy value according to the estimation value, further comprises:

substituting the estimation value into a equation to obtain a estimation entropy value, and wherein the equation being represented as follow,

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.

9. The system for estimating entropy according to claim 8, wherein the plurality of locations is an array having g×

z locations.

10. The system for estimating entropy according to claim 9, wherein the g and z are selected according to an equation as follow:

11. The system for estimating entropy according to claim 8, wherein the entropy table is an array table.

12. The system for estimating entropy according to claim 8, wherein the calculation and update module obtains a calculation value by calculating the counter value used in the each same row in the entropy table according to a equation, and obtains the average of the counter of each row according to the calculation value.

13. The system for estimating entropy according to claim 12, wherein the equation is represented as follow:

X=m(c log(c)−

(c−

1)log(c−

1)).

14. The system for estimating entropy according to claim 8, wherein the calculation and update module substitutes the estimation value into a equation to obtain a estimation entropy value, and wherein the equation being represented as follow,

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.

16. The method for estimating entropy according to claim 15, wherein the data streaming algorithm for estimating entropy further comprises:

setting an allowable error to deciding the sample number according to a total of packets in a stream data, and randomly sampling a plurality of locations in the stream data.

17. The method for estimating entropy according to claim 15, wherein the count sketch algorithm further comprises:

applying to a count sketch algorithm to each packet for performing the count and update, and 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, and obtaining an average of a counter used in each same row in the entropy table, and obtaining a calculation value by calculating the counter value used in the each same row in the entropy table according to a equation so as to obtain the average of the counter of each row according to the calculation value; and

selecting a median to be an estimation value from the averages, and obtaining an estimation entropy value according to the estimation value.

18. The method for estimating entropy according to claim 17, wherein the equation is represented as follow:

X=m(c log(c)−

(c−

1)log(c−

1)).

19. The method for estimating entropy according to claim 17, wherein the estimation value is substituted into a equation to obtain a estimation entropy value, and wherein the equation being represented as follow,

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;