Clock synchronization for network measurements with clock resets

• US 20020188881A1
• Filed: 05/29/2002
• Published: 12/12/2002
• Est. Priority Date: 10/30/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Zhang, Li, Xia, Cathy Honghui
• Granted Patent: US 7,194,649 B2
• Time in Patent Office: Days
• US Class Current: 713/401
• CPC Class Codes: G06F 1/10 Distribution of clock signals , e.g. skew

Abstract

Several algorithms are provided to estimate and remove relative clock skews from delay measurements based on the computation of convex hulls. The algorithms are linear in the number of measurement points for the case with no clock resets. For the more challenging case with clock resets, i.e., the clocks are reset to some reference times during the measurement period, linear algorithms are provided to identify the clock resets and derive the best clock skew lines. The algorithms are also extended to environments in which at least one of the clocks is controlled by Network Time Protocol. These algorithms can also be extended for active clock synchronization to replace or further improve Network Time Protocol.

Claims

1. A method for correcting delay measurement data with clock resets, comprising:

examining possible clock reset combinations;

for each possible clock reset combination, dividing the delay measurement data into a predetermined number of segments, calculating a convex hull, and calculating a skew slope;

identifying a best skew slope for all possible clock reset combinations;

identifying clock reset times associated with the best skew slope; and

removing the effect of identified clock resets from the delay measurement data.

2. The method of claim 1, wherein the step of calculating a skew slope comprises identifying a line that is closest to the delay measurement data.

3. The method of claim 2, wherein the step of identifying a line that is closest to points in the delay measurement data comprises identifying a line that satisfies an objective function.

4. The method of claim 3, wherein the objective function minimizes a sum of vertical distances between the line and the points.

5. The method of claim 3, wherein the objective function minimizes an area between the line and a curve defined by the points.

6. The method of claim 3, wherein the objective function maximizes a number of points on the line.

7. A method for correcting delay measurement data with clock resets, comprising:

dividing the delay measurement data into a predetermined number of segments;

determining a skew slope for each segment;

marking segments that are candidates for having a clock reset;

identifying marked segments with exactly one clock reset;

identifying the best clock reset for each marked segment with exactly one clock reset; and

removing the effect of identified clock resets from the delay measurement data.

8. The method of claim 7, wherein the step of determining a skew slope for each segment comprises identifying a line that is closest to points in the delay measurement data for the segment.

9. The method of claim 8, wherein the step of identifying a line that is closest to the points for the segment comprises identifying a line that satisfies an objective function.

10. The method of claim 9, wherein the objective function minimizes a sum of vertical distances between the line and the points for the segment.

11. The method of claim 9, wherein the objective function minimizes an area between the line and a curve defined by the points for the segment.

12. The method of claim 9, wherein the objective function maximizes a number of points on the line.

14. The method of claim 13, wherein the best skew line has a skew slope and wherein the step of determining whether the data point is a turning point comprises:

calculating a sum of the skew slopes; and

determining whether the sum of the skew slopes is small enough and whether incorporating the data point makes the sum farther away from origin.

15. The method of claim 13, further comprising:

keeping a history list of turning points;

wherein the step of determining whether the data point is a turning point comprises, when the algorithm detects a turning point, using a best candidate turning point in the history list as a true turning point.

16. The method of claim 15, wherein the step of identifying a best skew line comprises calculating the best skew line using the true turning point.

19. The computer program product of claim 18, wherein the instructions for calculating a skew slope comprise instructions for identifying a line that is closest to the delay measurement data.

20. The computer program product of claim 19, wherein the instructions for identifying a line that is closest to points in the delay measurement data comprises instructions for identifying a line that satisfies an objective function.

21. The computer program product of claim 20, wherein the objective function minimizes a sum of vertical distances between the line and the points.

22. The computer program product of claim 20, wherein the objective function minimizes an area between the line and a curve defined by the points.

23. The computer program product of claim 20, wherein the objective function maximizes a number of points on the line.

25. The computer program product of claim 24, wherein the instructions for determining a skew slope for each segment comprise instructions for identifying a line that is closest to points in the delay measurement data for the segment.

26. The computer program product of claim 25, wherein the instructions for identifying a line that is closest to the points for the segment comprise instructions for identifying a line that satisfies an objective function.

27. The computer program product of claim 26, wherein the objective function minimizes a sum of vertical distances between the line and the points for the segment.

28. The computer program product of claim 26, wherein the objective function minimizes an area between the line and a curve defined by the points for the segment.

29. The computer program product of claim 26, wherein the objective function maximizes a number of points on the line.

13. A method for correcting delay measurement data with clock resets, comprising:

for each data point in the delay measurement data, calculating a best skew line for a current section, determining whether the data point is a turning point, identifying a clock reset time and the best skew line for the current section and starting a new section if the data point is a turning point; and

removing the effect of identified clock resets from the delay measurement data.

17. A method for online clock synchronization, comprising:

collecting delay measurement data between a time reference and local machine;

determining a relative clock speed;

adjusting the speed of the local clock according to the relative clock speed; and

setting a future time for the next possible clock adjustment.

18. A computer program product, in a computer readable medium, for correcting delay measurement data with clock resets, comprising:

instructions for examining possible clock reset combinations;

instructions for dividing the delay measurement data into a predetermined number of segments, calculating a convex hull, and calculating a skew slope, for each possible clock reset combination;

instructions for identifying a best skew slope for all possible clock reset combinations;

instructions for identifying clock reset times associated with the best skew slope; and

instructions for removing the effect of identified clock resets from the delay measurement data.

24. A computer program product, in a computer readable medium, for correcting delay measurement data with clock resets, comprising:

instructions for dividing the delay measurement data into a predetermined number of segments;

instructions for determining a skew slope for each segment;

instructions for marking segments that are candidates for having a clock reset;

instructions for identifying marked segments with exactly one clock reset;

instructions for identifying the best clock reset for each marked segment with exactly one clock reset; and

instructions for removing the effect of identified clock resets from the delay measurement data.

30. A computer program product, in a computer readable medium for correcting delay measurement data with clock resets, comprising:

instructions for calculating a best skew line for a current section, determining whether the data point is a turning point, identifying a clock reset time and the best skew line for the current section and starting a new section if the data point is a turning point, for each data point in the delay measurement data; and

instructions for removing the effect of identified clock resets from the delay measurement data.

31. The computer program product of claim 30, wherein the best skew line has a skew slope and wherein the instructions for determining whether the data point is a turning point comprise:

instructions for calculating a sum of the skew slopes; and

instructions for determining whether the sum of the skew slopes is small enough and whether incorporating the data point makes the sum farther away from origin.

32. The computer program product of claim 30, further comprising:

instructions for keeping a history list of turning points;

wherein the instructions for determining whether the data point is a turning point comprise, when the algorithm detects a turning point, using a best candidate turning point in the history list as a true turning point.

33. The computer program product of claim 32, wherein the instructions for identifying a best skew line comprise instructions for calculating the best skew line using the true turning point.

34. A computer program product, in a computer readable medium, for online clock synchronization, comprising:

instructions for collecting delay measurement data between a time reference and local machine;

instructions for determining a relative clock speed;

instructions for adjusting the speed of the local clock according to the relative clock speed; and

instructions for setting a future time for the next possible clock adjustment.

35. An apparatus for correcting delay measurement data with clock resets, comprising:

a processor; and

a memory electrically connected to said processor, the memory having stored therein a program to be executed on said processor for performing the following steps;

examining possible clock reset combinations;

for each possible clock reset combination, dividing the delay measurement data into a predetermined number of segments, calculating a convex hull, and calculating a skew slope;

identifying a best skew slope for all possible clock reset combinations;

identifying clock reset times associated with the best skew slope; and

removing the effect of identified clock resets from the delay measurement data.

36. An apparatus for correcting delay measurement data with clock resets, comprising:

a processor; and

a memory electrically connected to said processor, the memory having stored therein a program to be executed on said processor for performing the following steps;

dividing the delay measurement data into a predetermined number of segments;

determining a skew slope for each segment;

marking segments that are candidates for having a clock reset;

identifying marked segments with exactly one clock reset;

identifying the best clock reset for each marked segment with exactly one clock reset; and

removing the effect of identified clock resets from the delay measurement data.

37. An apparatus for correcting delay measurement data with clock resets, comprising:

a processor; and

a memory electrically connected to said processor, the memory having stored therein a program to be executed on said processor for performing the following steps;

for each data point in the delay measurement data, calculating a best skew line for a current section, determining whether the data point is a turning point, identifying a clock reset time and the best skew line for the current section and starting a new section if the data point is a turning point; and

removing the effect of identified clock resets from the delay measurement data.

38. An apparatus for online clock synchronization, comprising:

a processor; and

a memory electrically connected to said processor, the memory having stored therein a program to be executed on said processor for performing the following steps;

collecting delay measurement data between a time reference and local machine;

determining a relative clock speed;

adjusting the speed of the local clock according to the relative clock speed; and

setting a future time for the next possible clock adjustment.