Optimal combination of sampled measurements

• US 20070016666A1
• Filed: 07/18/2006
• Published: 01/18/2007
• Est. Priority Date: 03/18/2001
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Duffield, Nicholas, Thorup, Mikkel, Lund, Carsten
• Granted Patent: US 7,536,455 B2
• Time in Patent Office: Days
• 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 a property of items, comprising:

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

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

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

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

e. determining a lower bound for a variance of each of the samples; and

f. combining the samples using a variance value for each sample that is equal to or larger than the lower bound for the variance for the said 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 distributions is obtained using a threshold sampling algorithm.

5. The method of claim 1 wherein at least one of said distributions is obtained using a priority sampling algorithm.

6. The method of claim 1 wherein at least one of said distributions is obtained using a parameter of the sampling algorithm

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

8. The method of claim 9 wherein the lower bound of the variance of a sample is obtained using information based on substantially all items including those outside the sample.

9. The method of claim 10 wherein the lower bound of the variance of a sample is obtained using information based on individual items that are part of the sample.

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

11. The method of claim 12 wherein the samples are obtained at different routers.

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

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

14. The method of claim 13 wherein the said property 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 comprising:

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

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

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

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

e. determining a lower bound for a variance of each of the samples; and

f. combining the samples using a variance value for each sample that is equal to or larger than the lower bound for the variance for the said sample.

16. The method of claim 15 wherein said items are packets that traverse a network

17. The method of claim 16 wherein the said property is the size of said packets.

18. The method of claim 17 wherein the lower bound of the variance of a sample is obtained using information based on substantially all items including those outside the sample.

19. The method of claim 17 wherein the lower bound of the variance of a sample is obtained using information based on individual items that are part of the sample.