# US 2002/0120416 A1 · Clock synchronization for network measurements

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2002/0120416 A1
- Document ID: US20020120416A1
- Status: Published application
- Kind: A1
- Application number: 09/920,138
- Filed: 2001-07-31
- Published: 2002-08-29
- Earliest claimed: 2000-10-30
- Assignees: International Business Machines Corporation
- Inventors: Zhen Liu; Cathy Honghui Xia; Li Zhang
- Web page: https://patentgrep.com/patent/US20020120416A1

## CPC

- G06F 1/10: Distribution of clock signals {, e.g. skew}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method, computer program product, and data processing system for estimating and correcting the amount of clock skew in end-to-end network timing measurements is disclosed. Measured delays are combined with their time of measurement to create ordered pairs. These ordered pairs represent points within a Cartesian plane. The convex hull of these points is determined, and an optimal line segment from the resulting polygon is selected and extrapolated to create an affine function estimating clock skew over time. The optimal line segment of the polygon is one that optimizes a selected objective function. The objective function is selected so as to be an appropriate measurement of the accuracy of the resulting linear function as an estimate of the actual clock skew.

## Claims

### Claim 1

A method for removing the effect of clock skew between data processing systems, comprising:
making delay measurements between two data processing systems connected by a network;
forming a set of data points, wherein each data point in the set of data points comprises a time and a delay measurement for the respective time;
finding a convex hull of the set of data points, wherein the convex hull is bounded by a number of line segments;
selecting a one of the line segments that optimizes an objective function;
extrapolating the one of the line segments to obtain an affine function; and
removing the effect of clock skew between the two data processing systems as characterized by the affine function.

### Claim 2 (depends on 1)

The method of claim 1, wherein the one of the line segments is selected so that a line containing the one of the line segments will contain a maximal number of data points from the set of data points.

### Claim 3 (depends on 1)

The method of claim 1, wherein the one of the line segments is selected so that the sum of the vertical distances between each of the set of data points and a line containing the one of the line segments will be minimized.

### Claim 4 (depends on 3)

The method of claim 3, wherein selecting the one of the line segments includes:
calculating an arithmetic mean of x-coordinates of all of the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 5 (depends on 1)

The method of claim 1, wherein the one of the line segments is selected so that the area between a plot of a piecewise-linear function containing the set of data points and a line containing the one of the line segments will be minimized.

### Claim 6 (depends on 5)

The method of claim 5, wherein selecting the one of the line segments includes:
calculating an arithmetic mean of an x-coordinate of a first data point and an x-coordinate of a second data point, wherein the x-coordinate of the first data point is the lowest of any data point in the set of data points, and wherein the x-coordinate of the second data point is the greatest of any data point in the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 7 (depends on 1)

The method of claim 1, wherein the x-coordinate of each data point in the set of data points represents a time measurement.

### Claim 8 (depends on 1)

The method of claim 1, wherein the y-coordinate of each data point in the set of data points represents a delay measurement.

### Claim 9 (depends on 8)

The method of claim 8, wherein the delay measurement is a communication delay between two data processing systems connected by a network.

### Claim 10

A computer program product, in a computer-readable medium, for removing the effect of clock skew between data processing systems, comprising instructions for:
making a delay measurement between two data processing systems connected by a network;
forming a set of data points, wherein each data point in the set of data points comprises a time and a delay measurement for the respective time;
finding a convex hull of the set of data points, wherein the convex hull is bounded by a number of line segments;
selecting a one of the line segments that optimizes an objective function;
extrapolating the one of the line segments to obtain an affine function; and
removing the effect of clock skew between the two data processing systems as characterized by the affine function.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein the one of the line segments is selected so that a line containing the one of the line segments will contain a maximal number of data points from the set of data points.

### Claim 12 (depends on 10)

The computer program product of claim 10, wherein the one of the line segments is selected so that the sum of the vertical distances between each of the set of data points and a line containing the one of the line segments will be minimized.

### Claim 13 (depends on 12)

The computer program product of claim 12, wherein the instructions for selecting the one of the line segments include instructions for:
calculating an arithmetic mean of x-coordinates of all of the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 14 (depends on 10)

The computer program product of claim 10, wherein the one of the line segments is selected so that the area between a plot of a piecewise-linear function containing the set of data points and a line containing the one of the line segments will be minimized.

### Claim 15 (depends on 14)

The computer program product of claim 14, wherein the instructions for selecting the one of the line segments include instructions for:
calculating an arithmetic mean of an x-coordinate of a first data point and an x-coordinate of a second data point, wherein the x-coordinate of the first data point is the lowest of any data point in the set of data points, and wherein the x-coordinate of the second data point is the greatest of any data point in the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 16 (depends on 10)

The computer program product of claim 10, wherein the x-coordinate of each data point in the set of data points represents a time measurement.

### Claim 17 (depends on 10)

The computer program product of claim 10, wherein the y-coordinate of each data point in the set of data points represents a delay measurement.

### Claim 18 (depends on 17)

The computer program product of claim 17, wherein the delay measurement is a communication delay between two data processing systems connected by a network.

### Claim 19

A data processing system for removing the effect of clock skew between data processing systems, comprising:
a bus system;
a processing unit connected to the bus system, wherein the processing unit contains at least one processor;
a memory connected to the bus system; and
a set of instructions,
wherein the processing unit executes the set of instructions to perform the acts of:
making a delay measurement between two data processing systems connected by a network;
forming a set of data points, wherein each data point in the set of data points comprises a time and a delay measurement for the respective time;
finding a convex hull of the set of data points, wherein the convex hull is bounded by a number of line segments;
selecting a one of the line segments that optimizes an objective function; and
extrapolating the one of the line segments to obtain an affine function; and
removing the effect of clock skew between the two data processing systems as characterized by the affine function.

### Claim 20 (depends on 19)

The data processing system of claim 19, wherein the one of the line segments is selected so that a line containing the one of the line segments will contain a maximal number of data points from the set of data points.

### Claim 21 (depends on 19)

The data processing system of claim 19, wherein the one of the line segments is selected so that the sum of the vertical distances between each of the set of data points and a line containing the one of the line segments will be minimized.

### Claim 22 (depends on 21)

The data processing system of claim 21, wherein the act of selecting the one of the line segments includes:
calculating an arithmetic mean of x-coordinates of all of the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 23 (depends on 19)

The data processing system of claim 19, wherein the one of the line segments is selected so that the area between a plot of a piecewise-linear function containing the set of data points and a line containing the one of the line segments will be minimized.

### Claim 24 (depends on 23)

The data processing system of claim 23, wherein the act of selecting the one of the line segments includes:
calculating an arithmetic mean of an x-coordinate of a first data point and an x-coordinate of a second data point, wherein the x-coordinate of the first data point is the lowest of any data point in the set of data points, and wherein the x-coordinate of the second data point is the greatest of any data point in the set of data points; and
selecting a one of the line segments that contains a point whose x-coordinate is equal to the arithmetic mean.

### Claim 25 (depends on 19)

The data processing system of claim 19, wherein the x-coordinate of each data point in the set of data points represents a time measurement.

### Claim 26 (depends on 19)

The data processing system of claim 19, wherein the y-coordinate of each data point in the set of data points represents a delay measurement.

### Claim 27 (depends on 26)

The data processing system of claim 26, wherein the delay measurement is a communication delay between two data processing systems connected by a network.
