Methods and apparatus to bound network traffic estimation error for multistage measurement sampling and aggregation

An article of manufacture storing machine readable instructions which, when executed, cause a machine to:

• determine a hierarchical sampling topology representative of multiple data sampling and aggregation stages, the hierarchical sampling topology comprising a plurality of nodes connected by a plurality of edges, each node corresponding to at least one of a data source and a data aggregation operation, and each edge corresponding to a data sampling operation characterized by a generalized sampling threshold determined from a sampling probability function also characterizing the data sampling operation;
• select a first generalized sampling threshold from a set of generalized sampling thresholds associated with a respective set of edges originating at a respective set of descendent nodes of a target node undergoing network traffic estimation;
• and
• transform a measured sample of network traffic associated with the target node into a confidence interval for a network traffic estimate associated with the target node using the first generalized sampling threshold and an error parameter.

A network traffic estimation device configured to determine a confidence interval characterizing a network traffic estimate, the device comprising:

• a sampling topology configuration unit to determine a hierarchical sampling topology representative of multiple data sampling and aggregation stages, the hierarchical sampling topology comprising a plurality of nodes connected by a plurality of edges, each node corresponding to at least one of a data source and a data aggregation operation, and each edge corresponding to a data sampling operation characterized by a generalized sampling threshold determined from a sampling probability function also characterizing the data sampling operation;
• a measurement sampler to sample network traffic at a particular network location represented by a target node in the hierarchical sampling topology;
• and
• a confidence interval estimator to transform a measured sample of network traffic into a confidence interval for a network traffic estimate associated with the particular network location using an error parameter and a first generalized sampling threshold selected from a set of generalized sampling thresholds associated with a respective set of edges originating at a respective set of descendent nodes of the target node.