Clock synchronization for network measurements
First 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
27 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
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.
-
Specification