Efficient probabilistic counting scheme for stream-expression cardinalities

1. A computer-implemented method of monitoring a network, comprising:

at each node of a fixed set, the computer constructing a corresponding vector of M components based on data packets received at the node during a time period, M being an integer greater than 1, the fixed set being formed of some nodes of the network; and

based on the constructed vectors, the computer estimating at least one of: (a) how many of the received data packets have been received by all of the nodes of the set and (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set;

wherein:

the constructing includes updating a component of the vector of one of the nodes in response to the one of the nodes receiving a data packet, the updating including selecting the component for updating by hashing a property of the data packet received by the one of the nodes; and

the hashing includes (i) mapping the property of the received data packet to a first element of a first hash function having a set of first elements and (ii) mapping the property of the received data packet to a second element of a second hash function having a set of second elements, wherein the property of the received data packet is a hash key used for both the first hash function and the second hash function.

2. The method of claim 1 , wherein the estimating estimates how many of the data packets have propagated to every node of the set.

3. The method of claim 1 , wherein the estimating estimates how many of the flows have data packets that have passed through all of the nodes of the set.

4. The method of claim 1 , wherein the updating further comprises determining a number to assign to the component for updating based on the property of the data packet received by the one of the nodes.

5. The method of claim 4 , wherein the constructing involves updating the number assigned to each component of one of the vectors by a process that changes the assigned number in a monotonic manner.

6. The method of claim 1 , wherein the estimating involves evaluating a correlation between the vectors.

7. The method of claim 1 , wherein each vector is generated using an algorithm employing a first hash function and a second hash function independent of the first hash function.

8. The method of claim 7 , wherein:

the first hash function maps an element of each data stream to a bucket of a hash array;

the second hash function maps the element of each data stream to a random number; and

for at least one component of a vector, the value of the bucket mapped in the first hash function is updated based on the random number mapped in the second hash function.

9. The method of claim 1 , wherein:

the computer estimates (a) how many of the received data packets have been received by all of the nodes of the set, and

the computer does not estimate (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set.

10. The method of claim 1 , wherein:

the computer estimates (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set, and

the computer does not estimate (a) how many of the received data packets have been received by all of the nodes of the set.

11. A network comprising:

a fixed set of nodes, each node configured to construct a corresponding vector of M components based on data packets received at the node during a time period, M being an integer greater than 1, the fixed set being formed of some nodes of the network; and

a server configured to (i) receive the constructed vectors from the nodes and (ii) based on the constructed vectors, estimate at least one of: (a) how many of the received data packets have been received by all of the nodes of the set and (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set;

wherein:

the constructing of the vector of M components includes updating a component of the vector of one of the nodes in response to the one of the nodes receiving a data packet, the updating including selecting the component for updating by hashing a property of the data packet received by the one of the nodes; and

the hashing includes (i) mapping the property of the received data packet to a first element of a first hash function having a set of first elements and (ii) mapping the property of the received data packet to a second element of a second hash function having a set of second elements, wherein the property of the received data packet is a hash key used for both the first hash function and the second hash function.

12. The network of claim 11 , wherein the estimation performed by the server estimates how many of the data packets have propagated to every node of the set.

13. The network of claim 11 , wherein the estimation performed by the server estimates how many of the flows have data packets that have passed through all of the nodes of the set.

14. The network of claim 11 , wherein the updating further comprises determining a number to assign to the component for updating based on the property of the data packet received by the one of the nodes.

15. The network of claim 14 , wherein the constructing of the vector of M components involves updating the number assigned to each component of one of the vectors by a process that changes the assigned number in a monotonic manner.

16. The network of claim 11 , wherein the estimating involves evaluating a correlation between the vectors.

17. The network of claim 11 , wherein each vector is generated using an algorithm employing a first hash function and a second hash function independent of the first hash function.

18. The network of claim 17 , wherein:

the first hash function maps an element of each data stream to a bucket of a hash array;

the second hash function maps the element of each data stream to a random number; and

for at least one component of a vector, the value of the bucket mapped in the first hash function is updated based on the random number mapped in the second hash function.

19. The network of claim 11 , wherein:

the server is configured to estimate (a) how many of the received data packets have been received by all of the nodes of the set, and

the server is not configured to estimate (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set.

20. The network of claim 11 , wherein:

the server is configured to estimate (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set, and

the server is not configured to estimate (a) how many of the received data packets have been received by all of the nodes of the set.

21. A non-transitory computer-readable storage medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to implement a method of monitoring a network, the method comprising:

at each node of a fixed set, constructing a corresponding vector of M components based on data packets received at the node during a time period, M being an integer greater than 1, the fixed set being formed of some nodes of the network; and

based on the constructed vectors, estimating at least one of: (a) how many of the received data packets have been received by all of the nodes of the set and (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set;

wherein:

the constructing includes updating a component of the vector of one of the nodes in response to the one of the nodes receiving a data packet, the updating including selecting the component for updating by hashing a property of the data packet received by the one of the nodes; and

the hashing includes (i) mapping the property of the received data packet to a first element of a first hash function having a set of first elements and (ii) mapping the property of the received data packet to a second element of a second hash function having a set of second elements, wherein the property of the received data packet is a hash key used for both the first hash function and the second hash function.

22. The non-transitory computer-readable storage medium of claim 9 , wherein the estimating estimates how many of the data packets have propagated to every node of the set.

23. The non-transitory computer-readable storage medium of claim 9 , wherein the estimating estimates how many of the flows have data packets that have passed through all of the nodes of the set.

24. The non-transitory computer-readable storage medium of claim 21 , wherein the updating further comprises determining a number to assign to the component for updating based on the property of the data packet received by the one of the nodes.

25. The non-transitory computer-readable storage medium of claim 24 , wherein the constructing involves updating the number assigned to each component of one of the vectors by a process that changes the assigned number in a monotonic manner.

26. The non-transitory computer-readable storage medium of claim 21 , wherein the estimating involves evaluating a correlation between the vectors.

27. The non-transitory computer-readable storage medium of claim 21 , wherein each vector is generated using an algorithm employing a first hash function and a second hash function independent of the first hash function.

28. The non-transitory computer-readable storage medium of claim 27 , wherein:

the first hash function maps an element of each data stream to a bucket of a hash array;

the second hash function maps the element of each data stream to a random number; and

for at least one component of a vector, the value of the bucket mapped in the first hash function is updated based on the random number mapped in the second hash function.

29. The non-transitory computer-readable storage medium of claim 21 , wherein:

the step of estimating comprises estimating (a) how many of the received data packets have been received by all of the nodes of the set, and

the step of estimating does not comprise estimating (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set.

30. The non-transitory computer-readable storage medium of claim 21 , wherein:

the step of estimating comprises estimating (b) how many flows of the received data packets have data packets that have passed through all of the nodes of the set, and

the step of estimating does not comprise estimating (a) how many of the received data packets have been received by all of the nodes of the set.