US7080136B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for size-dependent sampling for managing a data network
Assignee: AT&T Inc
•
Filing: 2002-01-24
•
Granted: 2006-07-18
•
Expires: 2022-01-24
Abstract
Abstract The present invention provides a method and apparatus 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.
Inventors
- 👤 Nicholas G. Duffield
- 👤 Carsten Lund
- 👤 Mikkel Thorup
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 17:53
CPC Classifications
H; H04; H04L; H04L43/00; H04L12/00; H04L12/02; H04L12/14; H04L41/00; H04L41/08; H04L41/0896; H04L41/50; H04L41/5003; H04L41/5009; H04L43/02; H04L43/022; H04L43/024; H04L43/026; H04L43/028; H04L43/16
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
88 words
A method for managing a data network containing a data Interface and a processor connected to the data interface in order to receive objects, the objects containing traffic information, the method comprising: (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).
Claim 2
Independent Claim
88 words
A method for managing a data network containing a data Interface and a processor connected to the data interface in order to receive objects, the objects containing traffic information, the method comprising: (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).
Claim 3
Dependent Claim
17 words
The apparatus method of claim 1 , wherein the probabilistic parameter is determined from a cost function.
Claim 4
Dependent Claim
19 words
The method of claim 2 , wherein the cost function relates a network resource to a quality of measurements.
Claim 5
Dependent Claim
26 words
The apparatus method of claim 3 , wherein the network resource corresponds to a sampling volume and the quality of measurements corresponds to a sampling accuracy.
Claim 6
Dependent Claim
23 words
The method of claim 1 , wherein step (d) comprises: aggregating a plurality of samples in accordance with the at least one attribute.
Claim 7
Dependent Claim
24 words
The method of claim 1 , wherein step (b) utilizes one of the at least one attribute to determine whether to sample the object.
Claim 8
Dependent Claim
34 words
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.
Claim 9
Dependent Claim
16 words
The method of claim 7 , wherein step (d) comprises: normalizing the size of the object.
Claim 10
Dependent Claim
44 words
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.
Claim 11
Dependent Claim
84 words
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.
Claim 12
Dependent Claim
25 words
The method of claim 10 , further comprising the step of: (g) adjusting the measured usage in order to control possible overcharging to the customer.
Claim 13
Dependent Claim
17 words
The method of claim 10 , wherein step (f) utilizes a minimum usage and a usage charge.
Claim 14
Dependent Claim
15 words
The apparatus method of claim 12 , wherein step (f) further utilizes a fixed charge.
Claim 15
Dependent Claim
39 words
The method of claim 10 , further comprising the step of: (g) 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.
Claim 16
Dependent Claim
40 words
The method of claim 10 , further comprising the step of: (g) 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.
Claim 17
Dependent Claim
28 words
The method of claim 10 , further comprising the step of: (g) adjusting the billing period In order to control a degree of accuracy for charging the customer.
Claim 18
Dependent Claim
12 words
The method of claim 14 , wherein the probabilistic parameter is adjusted.
Claim 19
Dependent Claim
12 words
The method of claim 15 , wherein the probabilistic parameter is adjusted.
Claim 20
Dependent Claim
13 words
The apparatus method of claim 16 , wherein the probabilistic parameter is adjusted.
Claim 21
Dependent Claim
31 words
The apparatus 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).
Claim 22
Dependent Claim
17 words
The method of claim 20 , further comprising the step of: (g) storing the estimated sampling volume.
Claim 23
Dependent Claim
23 words
The method of claim 20 , further comprising the step of: (g) reconfiguring the data network in accordance with the estimated sampling volume.
Claim 24
Dependent Claim
29 words
The apparatus 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.
Claim 25
Dependent Claim
22 words
The method of claim 23 , wherein step (g) comprises: updating a value of the probabilistic parameter corresponding to a sampling window.
Claim 26
Dependent Claim
54 words
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.
Claim 27
Dependent Claim
77 words
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.
Claim 28
Dependent Claim
45 words
The method of claim 24 , wherein a current value of the probabilistic parameter is determined by a set of numbers end a target sampling volume, wherein each number corresponds to a size of a sampled object that was sampled In a previous sampling window.
Claim 29
Dependent Claim
50 words
The method of claim 24 , further comprising the steps of: (h) 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.
Claim 30
Dependent Claim
29 words
The method of claim 28 , further comprising the step of: (i) realigning the sampling window in accordance with the step of updating the value of the probabilistic parameter.
Claim 31
Dependent Claim
27 words
The method of claim 25 , further comprising the step of: (h) adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.
Claim 32
Dependent Claim
27 words
The method of claim 26 , further comprising the step of: (h) adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.
Claim 33
Dependent Claim
27 words
The method of claim 27 , further comprising the stop of: (h) adjusting the measured sampling volume in accordance with a variance of the measured sampling volume.
Claim 34
Dependent Claim
16 words
The apparatus method of claim 1 , wherein step (c) utilizes a quasi-random data sampling algorithm.
Claim 35
Dependent Claim
60 words
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.
Claim 36
Dependent Claim
38 words
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.
Claim 37
Dependent Claim
36 words
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.
Claim 38
Independent Claim
155 words
A method for charging a customer for usage of a data network containing a data interface and a processor connected to the data interface in order to receive objects, the objects containing traffic information, the method comprising: (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).
Claim 39
Independent Claim
155 words
A method for charging a customer for usage of a data network containing a data interface and a processor connected to the data interface in order to receive objects, the objects containing traffic information, the method comprising: (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).
Claim 40
Independent Claim
144 words
A method for managing a data network in accordance with a data volume, wherein the data network contains a data interface and a processor connected to the data interface in order to receive objects, the method comprising: (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.
Claim 41
Independent Claim
144 words
A method for managing a data network in accordance with a data volume, wherein the data network contains a data interface and a processor connected to the data interface in order to receive objects, the method comprising: (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.
Claim 42
Dependent Claim
73 words
A computer-readable medium containing instructions for controlling a computer system to manage a data network, by: receiving an object, wherein the object is characterized by at least one attribute and wherein the object comprises at least one data element; determining whether to sample the object in accordance with a probabilistic parameter; sampling the object in response to determining whether to sample the object; and processing the sample in response to sampling the object.
Claim 43
Dependent Claim
73 words
A computer-readable medium containing instructions for controlling a computer system to manage a data network, by: receiving an object, wherein the object is characterized by at least one attribute and wherein the object comprises at least one data element; determining whether to sample the object in accordance with a probabilistic parameter; sampling the object in response to determining whether to sample the object; and processing the sample in response to sampling the object.
Claim 44
Dependent Claim
92 words
The computer-readable medium of claim 39 , further containing instructions for controlling the computer system to manage the data network, by: determining a measured usage of the data network in accordance with the at least one attribute; and 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.
Claim 45
Dependent Claim
34 words
The computer-readable medium of claim 40 , further containing instructions for controlling the computer system to manage the data network, by: adjusting the measured usage in order to control possible overcharging to the customer.
Claim 46
Dependent Claim
49 words
The computer-readable medium of claim 40 , further containing instructions for controlling the computer system to manage the data network, by: 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.
Claim 47
Dependent Claim
37 words
The computer-readable medium of claim 40 , further containing instructions for controlling the computer system to manage the data network, by: adjusting the billing period in order to control a degree of accuracy for charging the customer.
Claim 48
Dependent Claim
32 words
The computer-readable medium of claim 39 , further containing instructions for controlling the computer system to manage the data network, by: obtaining at least one sample; and calculating an estimated sampling volume.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-07-17 | 2010-01-16 | 2010-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-07-17 | 2014-01-16 | 2014-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-07-17 | 2018-01-16 | 2018-07-18 | $7700.00 | Window Closed / Lapsed |