Optimal combination of sampled measurements

• US 8,028,055 B2
• Filed: 11/17/2008
• Issued: 09/27/2011
• Est. Priority Date: 03/18/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Thorup, Mikkel, Lund, Carsten, Duffield, Nicholas G.
• Primary Examiner(s): Eng; David
• Application Number:
  US12/272,712
• Publication Number:
  US 20090161570A1
• Time in Patent Office: 1,044 Days
• Field of Search: 709/223, 370/229, 370/232, 370/235, 705/30, 705/35
• US Class Current: 709/223
• CPC Class Codes: H04L 12/14 Charging , metering or billing arrangements for data wireline or wireless communications
• CPC Class Codes: H04L 12/1428 Invoice generation, e.g. customization, lay-out, database processing, algorithms for calculating the bill or formatting invoices as WWW pages invoicing in general G06Q30/04
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/5009 Determining service level performance parameters or violations of service level contracts, e.g. violations of agreed response time or mean time between failures [MTBF]
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

Two regularized estimators that avoid the pathologies associated with variance estimation are disclosed. The regularized variance estimator adds a contribution to estimated variance representing the likely error, and hence ameliorates the pathologies of estimating small variances while at the same time allowing more reliable estimates to be balanced in the convex combination estimator. The bounded variance estimator employs an upper bound to the variance which avoids estimation pathologies when sampling probabilities are very small.

Claims

1. A method of estimating an attribute of objects, comprising:

obtaining a first sample of the objects based on a first sampling distribution;

obtaining a first estimate of the attribute based on the first sample;

obtaining a second sample of the objects based on a second sampling distribution, where the second sampling distribution is different from the first sampling distribution;

obtaining a second estimate of the attribute based on the second sample;

determining a bound for a variance based upon each of the first sample and the second sample; and

combining the first sample and the second sample using a variance value for each one of the first sample and the second sample that is equal to or larger than the bound for the variance for the first sample and second sample.

2. The method of claim 1, wherein the first and second samples are obtained at different locations.

3. The method of claim 2, wherein the first and second samples are obtained at different router interfaces.

4. The method of claim 2, wherein the first and second samples are obtained at different routers.

5. The method of claim 2, wherein the first and second samples are obtained at different network ingress/egress interfaces.

6. The method of claim 1, wherein the first and second samples are obtained using different sampling algorithms.

7. The method of claim 1, wherein the first sampling distribution is obtained using a threshold sampling algorithm.

8. The method of claim 7, wherein the first sampling distribution is obtained using a parameter of the threshold sampling algorithm.

9. The method of claim 8, wherein the parameter is a value of a sampling threshold.

10. The method of claim 1, wherein the first sampling distribution is obtained using a priority sampling algorithm.

11. The method of claim 1, wherein the bound of the variance of each of the first sample and the second sample is obtained using information based on substantially all objects including those outside the first sample and the second sample, respectively.

12. The method of claim 1, wherein the bound of the variance of each of the first sample and the second sample is obtained using information based on individual objects that are part of the first sample and the second sample, respectively.

13. The method of claim 1, wherein the objects are packets that traverse a network.

14. The method of claim 13, wherein the attribute is the size of the packets.

15. The method of claim 1, wherein the second sampling distribution is obtained using a threshold sampling algorithm.

16. A computer readable medium containing stored instructions which when executed on a computer causes the computer to perform a method comprising:

obtaining a first sample of the objects based on a first sampling distribution;

obtaining a first estimate of the attribute based on the first sample;

obtaining a second sample of the objects based on a second sampling distribution, where the second sampling distribution is different from the first sampling distribution;

obtaining a second estimate of the attribute based on the second sample;

determining a bound for a variance based upon each of the first sample and the second sample; and

combining the first sample and the second sample using a variance value for each one of the first sample and the second sample that is equal to or larger than the bound for the variance for the first sample and second sample.

17. The computer readable medium of claim 16, wherein the objects are packets that traverse a network.

18. The computer readable medium of claim 17, wherein the attribute is the size of the packets.

19. The computer readable medium of claim 16, wherein the bound of the variance of each of the first sample and the second sample is obtained using information based on substantially all objects including those outside the first sample and the second sample, respectively.

20. The computer readable medium of claim 16, wherein the bound of the variance of each of the first sample and the second sample is obtained using information based on individual objects that are part of the first sample and the second sample, respectively.