Optimal combination of sampled measurements

• US 7,536,455 B2
• Filed: 07/18/2006
• Issued: 05/19/2009
• Est. Priority Date: 03/18/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Thorup, Mikkel, Lund, Carsten, Duffield, Nicholas G.
• Primary Examiner(s): Eng; David Y
• Application Number:
  US11/488,874
• Publication Number:
  US 20070016666A1
• Time in Patent Office: 1,036 Days
• Field of Search: 709/223
• 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:

a. obtaining a first sample of said objects based on a first sampling distribution;

b. obtaining a first estimate of said attribute based on said first sample;

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

d. obtaining a second estimate of said attribute based on said second sample;

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

f. 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 lower 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 1 wherein the first and second samples are obtained using different sampling algorithms.

4. The method of claim 1 wherein at least one of:

said first sampling distribution or said second sampling distribution is obtained using a threshold sampling algorithm.

5. The method of claim 1 wherein at least one of:

said first sampling distribution or said second sampling distribution is obtained using a priority sampling algorithm.

6. The method of claim 4 wherein at least one of:

said first sampling distribution or said second sampling distribution is obtained using a parameter of the threshold sampling algorithm.

7. The method of claim 6 wherein said parameter is a value of a sampling threshold.

8. The method of claim 1 wherein the lower 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.

9. The method of claim 1 wherein the lower 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.

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

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

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

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

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

15. A computer readable medium contained stored instructions which when executed on a computer causes the computer to perform a method of estimating an attribute of objects comprising:

a. obtaining a first sample of said objects based on a first sampling distribution;

b. obtaining a first estimate of said attribute based on said first sample;

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

d. obtaining a second estimate of said attribute based on said second sample;

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

f. 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 lower bound for the variance for the first sample and second sample.

16. The computer readable medium of claim 15 wherein said objects are packets that traverse a network.

17. The computer readable medium of claim 16 wherein said attribute is the size of said packets.

18. The computer readable medium of claim 15 wherein the lower 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.

19. The method computer readable medium of claim 15 wherein the lower 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.