Efficient probabilistic counting scheme for stream-expression cardinalities
US8400933B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 28, 2008 |
| Grant date | Mar 19, 2013 |
| Priority date | — |
| Expiry date | Apr 28, 2028 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L43/026
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
In one embodiment, a method of monitoring a network. The method includes, 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 how many of the received data packets have been received by all of the nodes of the set or estimating how many flows of the received data packets have data packets that have passed through all of the nodes of the set. 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 includes selecting the component for updating by hashing a property of the data packet received by the one of the nodes.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.