Efficient probabilistic counting scheme for stream-expression cardinalities

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 (a) how many of the received data packets have been received by all of the nodes of the set or (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.

A digital data-storage medium encoding a machine-executable program of instructions for steps of a method of monitoring a network, the steps 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 (a) how many of the received data packets have been received by all of the nodes of the set or (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.