Size-dependent sampling for managing a data network

• US 20020188710A1
• Filed: 01/24/2002
• Published: 12/12/2002
• Est. Priority Date: 03/18/2001
• Status: Abandoned Application

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Thorup, Mikkel, Lund, Carsten, Duffield, Nicholas G.
• Application Number:
  US10/056,682
• Publication Number:
  US 20020188710A1
• Time in Patent Office: Days
• US Class Current: 709/223
• 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/024 by adaptive sampling
• CPC Class Codes: H04L 43/026 using flow identification

Abstract

The present invention provides a method for sampling data flows in a data network in order to estimate a total data volume in the network. Sampling the data flows in the data network reduces the network resources that must be expended by the network to support the associated activity. The present invention enables the service provider of the data network to control sampled volumes in relation to the desired accuracy. The control can be either static or can be dynamic for cases in which the data volumes are changing as a function of time.

Claims

1. A method for managing a data network, comprising the steps of:

(a) receiving an object, wherein the object is characterized by at least one attribute and wherein the object comprises at least one data element;

(b) determining whether to sample the object in accordance with a probabilistic parameter;

(c) sampling the object in response to step (b); and

(d) processing the sample in response to step (c).

2. The method of claim 1, wherein the probabilistic parameter is determined from a cost function.

3. The method of claim 2, wherein the cost function relates a network resource to a quality of measurements.

4. The method of claim 3, wherein the network resource corresponds to a sampling volume and the quality of measurements corresponds to a sampling accuracy.

5. The method of claim 1, wherein step (d) comprises:

aggregating a plurality of samples in accordance with the at least one attribute.

6. The method of claim 1, wherein step (b) utilizes one of the at least one attribute to determine whether to sample the object.

7. The method of claim 6, wherein the one of the at least one attribute comprises a size of the object, wherein the size includes a contribution of the at least one data element.

8. The method of claim 7, wherein step (d) comprises:

normalizing the size of the object.

9. The method of claim 6, wherein the object comprises at least one data element, wherein the data element is selected from the group consisting of an octet, an Internet Protocol (IP) packet, a frame relay packet, and an Asynchronous Transfer Mode (ATM) cell.

10. The method of claim 1, further comprising the steps of:

(e) determining a measured usage of the data network in accordance with the at least one attribute; and

(f) charging a customer for the measured usage in accordance with a charging function, wherein the customer is associated with the at least one attribute and wherein the customer is presented a bill for a billing period and wherein a charging accuracy is related to the charging function and an accuracy of the measured usage.

11. The method of claim 10, further comprising the step of:

adjusting the measured usage in order to control possible overcharging to the customer.

12. The method of claim 10, wherein step (f) utilizes a minimum usage and a usage charge.

13. The method of claim 12, wherein step (f) further utilizes a fixed charge.

14. The method of claim 10, further comprising the step of:

adjusting the probabilistic parameter in order to achieve a predetermined degree of accuracy of charging the customer, wherein a sampling volume is related to the probabilistic parameter.

15. The method of claim 10, further comprising the step of:

adjusting the probabilistic parameter in order to reduce unbillable usage within a predetermined percentage of the measured usage, wherein a sampling volume is related to the probabilistic parameter.

16. The method of claim 10, further comprising the step of:

adjusting the billing period in order to control a degree of accuracy for charging the customer.

17. The method of claim 14, wherein the probabilistic parameter is adjusted.

18. The method of claim 15, wherein the probabilistic parameter is adjusted.

19. The method of claim 16, wherein the probabilistic parameter is adjusted.

20. The method of claim 1, further comprising the steps of:

(e) obtaining at least one sample from step (d); and

(f) calculating an estimated sampling volume from step (e).

21. The method of claim 20, further comprising the step of:

(g) storing the estimated sampling volume.

22. The method of claim 20, further comprising the step of;

(g) reconfiguring the data network in accordance with the estimated sampling volume.

23. The method of claim 20, further comprising the step of:

(g) adjusting the probabilistic parameter in order that the measured sampling volume approximates a targeted sampling volume.

24. The method of claim 23, wherein step (g) comprises:

updating a value of the probabilistic parameter corresponding to a sampling window.

25. The method of claim 24, wherein a current value of the probabilistic parameter equals a previous value of the probabilistic parameter multiplied by N divided by M, wherein N equals the measured sampling volume and M equals to the targeted sampling volume and wherein the previous value corresponds to a previous sampling window.

26. The method of claim 24, wherein a current value of the probabilistic parameter equals a previous value of the probabilistic parameter multiplied by (N−

R) divided by (M−

R) if M is greater than N and multiplied by N/M if N is greater than M, wherein N equals the measured sampling volume, M equals the targeted sampling volume, and R equals the sampling volume for objects having a size greater than the previous value of the probabilistic parameter.

27. The method of claim 24, wherein a current value of the probabilistic parameter is determined by a set of numbers and a target sampling volume, wherein each number corresponds to a size of a sampled object that was sampled in a previous sampling window.

28. The method of claim 24, further comprising the steps of:

immediately updating a value of the probabilistic parameter when the measured sampling volume is greater than the targeted sampling volume in proportion to a measurement time duration, wherein the measurement time duration is less than the sampling window.

29. The method of claim 28 further comprising the step of:

realigning the sampling window in accordance with the step of updating the value of the probabilistic parameter.

30. The method of claim 25, further comprising the step of:

adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.

31. The method of claim 26, further comprising the step of:

adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.

32. The method of claim 27, further comprising the step of:

adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.

33. The method of claim 1, wherein step (c) utilizes a quasi-random data sampling algorithm.

34. The method of claim 7, wherein the probabilistic parameter is associated with a probability function that is characterized by a value equal to zero when the size of the object is zero, a linearly increasing value when the size is between zero and the probabilistic parameter, and equal to one when the size is greater than the probabilistic parameter.

35. The method of claim 10, wherein the charging function comprises a fixed charge and a usage charge, wherein the usage charge is determined from a charge per unit of data, a minimum usage, and the measured usage.

36. The method of claim 1, wherein the probabilistic parameter corresponds to a first color and a second probabilistic parameter corresponds to a second color, wherein each color is associated with the at least one attribute.

37. A method for charging a customer for a usage of a data network, comprising the steps of:

(a) adjusting a probabilistic parameter in accordance with a charging accuracy;

(b) receiving an object, wherein the object is characterized by a size and a customer;

(c) determining whether to sample the object in accordance with the probabilistic parameter, wherein the probabilistic parameter approximately optimizes a cost function and wherein the cost function relates the probabilistic parameter to a sampling accuracy and a sampling volume;

(d) sampling the object in response to step (c);

(e) normalizing the sample in response to step (d);

(f) determining the usage for the customer in accordance with step (e);

(g) adjusting the usage in accordance with the charging accuracy; and

(h) determining a charge to the customer in response to step (g).

38. A method for managing a data network in accordance with a traffic volume, comprising the steps of:

(a) adjusting a probabilistic parameter for a sampling window in accordance with a targeted sampling volume;

(b) receiving an object, wherein the object is characterized by a size;

(c) determining whether to sample the object in accordance with the probabilistic parameter, wherein the probabilistic parameter approximately optimizes a cost function, wherein the cost function relates the probabilistic parameter to a sampling accuracy and a sampling volume;

(d) sampling the object in response to step (c);

(e) normalizing the sample in response to step (d);

(f) determining an estimated traffic volume in accordance with step (e); and

(g) utilizing the estimated traffic volume to manage the data network.