Clock skew estimation and removal

Details Clock skew estimation and removal Clock skew estimation and removal

1999-03-19

2003-12-09

Pham, Chi (Department: 2677)

Multiplex communications

Communication techniques for information carried in plural...

Combining or distributing information via time channels

Reexamination Certificate

active

06661810

ABSTRACT:

DESCRIPTION OF RELATED ART
The advent of computer networks has enabled a wide range of distributed computing applications. Among other things, computer networks allow users to access, store and manipulate data that is located in remote locations, to share data and applications from remote locations, and to communicate between remote locations. The effectiveness of these and other aspects of computer networks depends on network performance. Therefore network performance metrics have been developed to assist network engineers in analyzing and improving performance of networks and applications that take advantage of networks. End-to-end delay and loss traces are frequently used in analyzing the network performance. The accuracy of such measurements is important for several reasons. First, end-to-end measurements may be the only way of measuring network performance, especially when there is no provision inside the network to provide end-systems with information about the current status of the network. The current Internet has no mechanism for providing feedback on network congestion to end-systems at the IP layer, and neither does the Internet Protocol version 6 specification. Second, protocols and applications that behave adaptively at the end-system base their control on observed network performance, and it is critical that they obtain correct measurements.
Packet loss can be detected if a sender puts a sequence number on every packet it sends out, and the receiver sees a gap in the sequence numbers of packets arriving within a reasonable amount of time. For delay measurements, a sender needs to add time stamps to packets for a receiver to gather delay information. Since the clocks at both end-systems are involved in measuring delay, the synchronization between the two clocks becomes an issue in the accuracy of delay measurement. The Network Time Protocol (NTP) is widely used on the Internet for clock m synchronization, and provides accuracy in the order of milliseconds under reasonable circumstances. The accuracy, however, is not guaranteed, and not all hosts on the Internet support it.
Packet loss and delay are crucial in understanding the performance and reliability of the Internet and other computer networks. To provide unbiased and quantitative measures of performance, there has been much effort to define one-way loss and delay metrics. To obtain an accurate measurement of one-way delay, errors and uncertainties related to clocks need to be accounted for. When two clocks involved in the measurement run at different frequencies (that is, have a clock skew), inaccuracies are introduced in the measurement.
Methods and systems have been proposed to measure clock skew based on end-to-end delay measurements with respect to transmission times between a sender system with a sender clock and a receiver system with a receiver clock. Such methods typically rely on the fact that the minimum observed delay increases or decreases over time, depending on whether a receiver clock is faster or slower in frequency than a sender clock. The rate of increase of the minimum observed delay, which can be graphically represented as the slope of the minimum observed delay plotted against the time of transmission, is the difference in frequency, or the skew, between the clocks.
Known estimation methods for the clock skew include the work of Vern Paxson in a Ph.D. thesis, University of California, Berkeley, 1997, entitled Measurements and Analysis of End-to-End Internet Dynamics, and in an article entitled On Calibrating Measurements of Packet Transit Times, published in Proceedings of SIGMETRICS '98, Madison, Wis., June 1998. The disclosure of such thesis and paper are incorporated by reference herein. The Paxson algorithm uses forward and reverse path measurements of delay between a pair of hosts to deal with clock synchronization problems. The Paxson algorithm relies on robust line fitting based on robust statistics. It uses the median as a robust estimate for the slope. De-noised one-way transit times and cumulative minima are used in the algorithm. The algorithm can be extended to use with one-way delay measurements. In particular, for N delay measurements, the measured delays can be partitioned into N segments, and the minimum delay measurement can be picked from each segment. The selected measurements are the “de-noised” one-way transit times (OTTs). Next, the user can pick the median of the slopes of all possible pairs of de-noised OTTs. If the median slope is negative, the user can assume a decreasing trend. Next, the user can select a cumulative minima test from the de-noised OTTs and test whether the number of cumulative minima is large enough to show that the decreasing trend is probabilistically not likely, if there is no trend. If the cumulative minima test is passed, then the user can pick the median from the slopes of all possible pairs of the cumulative minima and output it as the estimate of the ratio of the frequencies of the two clocks minus one.
Other known techniques include linear regression, in which a line is fit to the delay data points by minimizing the sum of squares of the distances between the line and the data points. Also, a piecewise minimum algorithm is known that partitions the delay into segments, picks a minimum from each segment, and connects them to obtain a concatenation of line segments. The minima are the same as the “de-noised” one-way transit times of the Paxson algorithm. The resulting concatenation of line segments is an estimate of the skew.
Known algorithms are either quite complex, unreliable in certain cases, or both. Accordingly, a need exists for a simple, efficient, reliable measurement of clock skew that can be obtained from one-way delay measurements.
SUMMARY
Provided herein is a linear programming-based algorithm to estimate the clock skew in network delay measurements based on one-way delay measurements. The algorithm has the time complexity of O(N), leaves the delay after the skew removal positive, and is robust in the sense that the error margin of the skew estimate is independent of the magnitude of the skew. The algorithm is understood to be unbiased, and the sample variance of the skew estimates is small.
Provided herein are methods and systems for estimating the skew between a sender clock and a receiver clock on a network. The methods may include, for a set of packets sent over a network, obtaining a set of measurements consisting of the time duration between a first packet's departure and each subsequent packet's departure consistent with the time measured by a sender clock, obtaining a calculated set of delay measurements consisting of the amounts determined by subtracting the time duration between the first packet's departure and each subsequent packet's departure as measured by the sender clock from the time duration between the first packet's arrival and each subsequent packet's arrival as measured by the receiver clock, defining a feasible region of solution for an estimate a of the ratio between the speed of the sender clock and the speed of the receiver clock and for an estimate p of the end-to-end delay of the first packet consistent with the receiver clock, wherein the feasible region is defined by the following condition:
{tilde over (d)}
i
−({circumflex over (&agr;)}−1)
{overscore (t)}
i
s
+&bgr;≧0, 1
≦i≦N
and minimizing the vertical distance between the line and all delay measurements according to the formula
min
⁢
{
∑
i
=
1
N
⁢
(
d
_
i
-
(
α
^
-
1
)
⁢
t
_
i
s
+
β
)
}
.
The methods may further include eliminating the requirement that certain constraints be examined in processing by using the data point for the immediately prior packet as the minimum delay between the sender clock and the receiver clock for a subsequent packet.
The methods may further include for a data set of transmissions of different packet sizes, determining the mode packet size for the set of transmissions and using only measurements of transmissions of packets of the m

Affiliated with

Also associated with

Rating

Clock skew estimation and removal does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Clock skew estimation and removal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clock skew estimation and removal will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3158527