Method for estimating clock skew within a communications network

[0001] The present invention relates generally to the field of packet-based communication systems, and more particularly to the measurement of clock skew between clocks within such a communications system.

[0002] Clock skew is caused by the difference in clock frequency between two clocks positioned at different locations in a communications system. The problem of clock skew almost always appears when there is communication between two systems or portions of a network, each of which has its own clock. Because of variations in the quartz crystal and other oscillator components that regulate the clock frequency, some variation is usually observable between nominally similar clocks. In the context of network delay measurement, the clock skew will introduce an artificial delay. Thus, it is important to remove its effect in order to obtain an accurate estimate of the end-to-end transmission delay, which is often used to analyze the network's performance.

[0003] In Internet audio and video applications, the difference in clock frequencies also has other undesirable effects. For example, if the sender's clock frequency is higher than the receiver's clock frequency, the receiver will systematically receive more audio samples than it is able to replay according to its own clock, which leads to systematic overfill of its buffer. Conversely, if the sender's clock frequency is lower than the receiver's, the receiver will systematically find itself lacking audio samples to replay.

[0004] Thus it would be highly desirable to provide an efficient method for performing an accurate estimation of clock skew between a sender's clock and a receiver's clock in a packet-based communications network. One particular advantageous use of such a method, for example, may be to adjust buffer sizes associated with sending and/or receiving locations in a network in accordance with such an estimated clock skew.

[0005] The present invention provides, in accordance with certain illustrative embodiments thereof, an efficient and accurate method for calculating an estimate of the clock skew between a sender's clock and a receiver's clock in a packet-based communications network. In particular, an adaptive algorithm is illustratively employed in which a recursive least squares approach is used to calculate an estimate of the clock skew based on the transmission of a given (i.e., the “current”) packet, which estimate is further based on a previous estimate of the clock skew (“a first approximation” thereof). This illustrative process then iterates adaptively with each successive packet, producing increasingly accurate estimates of the clock skew.

[0006] More particularly, the present invention provides a method of calculating an estimate of a clock skew between a sender clock and a receiver clock in a packet-based communications network, the sender clock being associated with a sending location in the communications network from which one or more packets have been transmitted to a receiving location in the communications network, and the receiver clock being associated with the receiving location in the communications network. The inventive method comprises the steps of calculating a first approximation of the clock skew between the sender clock and the receiver clock based on the transmission of one or more of said packets; evaluating the transmission of a current packet (the current packet having been transmitted subsequent to the transmission of the one or more packets) to measure a predetermined characteristic of the transmission of the current packet; and calculating the estimate of the clock skew between the sender clock and the receiver clock based on the first approximation thereof and on the measured characteristic of the transmission of the current packet.

[0007] In accordance with one illustrative embodiment of the present invention, the delay jitter (i.e., variable delay) associated with the current packet is also estimated recursively. Then, this estimated delay jitter is advantageously used to more accurately estimate the clock skew between the sender clock and the receiver clock. In accordance with another illustrative embodiment of the present invention, the estimated clock skew is advantageously used to adjust the size of the input buffer associated with the receiving location in the communications network.

Introduction

[0011] In addition to the artificial delay introduced by clock skew (i.e., the difference in the frequencies between the sender clock and the receiver clock), the total end-to-end transmission delay is composed of transmission and propagation delays plus variable queuing delay. This variable queuing delay, known as delay jitter, means that the time difference between transmitting any two packets at the sender is unlikely to be the same as that observed between their arrivals at the receiver. As such, it is advantageous to model this delay jitter as a random process.

[0012] The well-known real-time protocol (RTP) for network communication, fully familiar to those of ordinary skill in the art, supports the transport of real time media content (e.g., audio and video) over packet-based networks. An RTP header contains information such as the sequence number and timestamp of a packet. This information may be advantageously used by the receiver to reconstruct the source and to determine the end-to-end transmission delay. For illustrative purposes herein, it will be assumed that such a protocol is used.

Terminology and Problem Formulation

[0013] Suppose that there is a connection between two hosts—a sender which transmits a sequence of packets through the communications network, and a receiver to whom the packets are being sent. Each host has its own clock, referred to herein as the sender clock and the receiver clock, respectively. The sender adds a timestamp (corresponding to its own clock) to a packet when it leaves, and the receiver records the time the packet arrives according to its own clock.

[0014] The following terminology will be used herein:

• [0015] c_s will be used to refer to the sender clock.
• [0016] c_r will be used to refer to the receiver clock.
• [0017] N is the number of packets sent by the sender that have arrived at the receiver.
• [0018] t_s^s(n) is the timestamp of the n'th packet leaving the sender according to c_s.
• [0019] t_s^r(n) is the timestamp of the n'th packet leaving the sender according to c_r.
• [0020] t_r^r(n) is the timestamp of the n'th packet arriving at the receiver according to c_r.
• [0021] t_r^s(n) is the timestamp of the n'th packet arriving at the receiver according to c_s.
  Note that t_r^r(n) and t_s^s(n) are known, but that t_r^s(n) and t_s^r(n) are not.

[0022] The timestamp of the n'th packet arriving at the receiver according to c_s can be written explicitly as:
t_r^s(n)=t_s^s(n)+d_f^s+v^s(n),  (1)
where d_f^s is the (fixed) transmission and propagation delay. (That is, for all of the packets transmitted during a connection, this delay is assumed to be the same.) The random variable v^s(n) characterizes the extra delay, referred to as delay jitter, which is added by the network (e.g., due to queuing) for (each particular) packet n.

[0023] It will also be assumed herein that there is no initial offset (i.e., difference in time) between the clocks and only the clock frequencies are different. Clearly, one-way measurements alone do not give enough information to distinguish a clock offset from the fixed delay. If the two clocks progress at different frequencies (that is, if they have a clock skew, α≠1), then t_s^r(n)≠t_s^s(n) and t_r^r(n)≠t_r^s(n).

[0024] The timestamp of the n'th packet arriving at the receiver according to c_r is:

[0025] $\begin{array}{cc}\begin{array}{c}{t}_r^r\left(n\right)=\alpha t_r^s\left(n\right)\\ =\alpha t_s^s\left(n\right)+\alpha d_f^s+\alpha v^s\left(n\right)\\ =\alpha t_s^s\left(n\right)+d_f^r+v^r\left(n\right),\end{array}& \left(2\right)\end{array}$
where α is the clock ratio, which is constant if c_s and c_r have constant frequencies.

[0026] The parameter α can be smaller or greater than one but is in general very close to one. In accordance with one illustrative embodiment of the present invention, the task is to estimate α, d_f^r and v^r(n), given t_r^r(n) and t_s^s(n) over N packets, n=1, 2, . . . , N.

[0027] The end-to-end transmission delay of the n'th packet consistent with c_r is:

[0028] $\begin{array}{cc}\begin{array}{c}{d}^r\left(n\right)=t_r^r\left(n\right)-t_s^r\left(n\right)\\ =t_r^r\left(n\right)-\alpha t_s^s\left(n\right)\\ =d_f^r+v^r\left(n\right).\end{array}& \left(3\right)\end{array}$
However, this delay is not known at the receiver and only the end-to-end delay measurement of the n'th packet can be determined as follows:

[0029] $\begin{array}{cc}\begin{array}{c}\tilde{d}\left(n\right)=t_r^r\left(n\right)-t_s^s\left(n\right)\\ =\left(\alpha -1\right)t_s^s\left(n\right)+d_f^r+v^r\left(n\right)\\ =\left(\alpha -1\right)t_s^s\left(n\right)+d^r\left(n\right),\end{array}& \left(4\right)\end{array}$
which is consistent with neither c_r nor c_s. Note that in Equation (4), {tilde over (d)}(n) is different from d^r(n) by (α−1)t_s^s(n). If α>1, then (α−1)t_s^s(n) grows linearly with t_s^s(n), and thus, {tilde over (d)}(n) gets larger.

[0030] Now let {circumflex over (α)} be an estimate of α. From the end-to-end delay measurement, an estimate of the end-to-end delay d^r(n) may be easily obtained as follows:
{circumflex over (d)}^r(n)={tilde over (d)}(n)−({circumflex over (α)}−1)t_s^s(n).  (5)
It is clear from the discussion above that it is natural and convenient to estimate all of the variables in accordance with the receiver clock, c_r.

[0031] As used herein, the delay jitter, v^r(n), is advantageously modeled as an independent, identically distributed (“i.i.d.”) random process with exponential probability density function (“pdf”) as follows:
ƒ(v^r)=u(v^r)λexp(−λv^r),  (6)
where u(v^r) is the unit step function:

[0032] $u\left(x\right)=\{\begin{array}{cc}x& \mathrm{if}x\ge 0\\ 0& \mathrm{if}x<0.\end{array}$
The mean and variance of the exponential distribution are E{v^r}=1/λ and E{(v^r−E{v^r})²}=1/λ², respectively, where E{·} denotes mathematical expectation. (The exponential distribution is often used to model queuing times in a service queue and it has been shown that the variable part of the delay caused by all individual router is reasonably well modeled with this pdf.)
A First Illustrative Method for Calculating an Estimate of the Clock Skew

[0033] The least squares (“LS”) estimator is a well-known technique which is widely used, primarily because it is easy to implement. It is derived from the minimization of a least squares error criterion. Specifically, we will define the error signal for packet n as follows:
e(n)={tilde over (d)}(n)−{tilde over ({circumflex over (d)}(n),  (7)
where
{tilde over ({circumflex over (d)}(n)=({circumflex over (α)}−1)t_s^s(n)+{circumflex over (d)}_f^r  (8)
is an estimate of {tilde over (d)}(n) and {circumflex over (d)}_f^r is an estimate of d_f^r. Here, the delay jitter is advantageously considered to be noise. Equation (7) can be rewritten in a more compact form as follows:

[0034] $\begin{array}{cc}e\left(n\right)=\tilde{d}\left(n\right)-x^T\left(n\right)h,\text{where}\begin{array}{c}x\left(n\right)={\left[\begin{array}{cc}{x}_1\left(n\right)& 1\end{array}\right]}^T\\ =[\begin{array}{cc}{t}_s^s\left(n\right)& {1]}^T,\end{array}\\ h={\left[\begin{array}{cc}{h}_1& h_2\end{array}\right]}^T\\ ={\left[\begin{array}{cc}\hat{\alpha }-1& {\hat{d}}_f^r\end{array}\right]}^T,\end{array}& \left(9\right)\end{array}$
and where superscript ^T denotes the transpose of a vector or a matrix.

[0035] Now consider the following cost function:

[0036] $\begin{array}{cc}J\left(h\right)=\sum _{n=1}^N{e}^2\left(n\right).& \left(10\right)\end{array}$
The minimization of Equation (10) with respect to h gives the LS estimator as follows:
h(N)=R⁻¹(N)r(N),  (11)
which is commonly referred to as the “normal equation”, where

[0037] $\begin{array}{cc}R\left(N\right)=\sum _{n=1}^{N}x\left(n\right)x^T\left(n\right),\text{and}& \left(12\right)\\ r\left(N\right)=\sum _{n=1}^{N}x\left(n\right)\tilde{d}\left(n\right).& \left(13\right)\end{array}$

[0038] If the sender begins to send packets at time 00:00 and sends them at a constant packetization time p, every p seconds (which means that t_s^s(n)−t_s^s(n−1)=p where p is a constant), we have the following:
t_s^s(n)=np, n=1,2, . . . , N.
In this case, Equation (12) then has the following form:

[0039] $\begin{array}{cc}R\left(N\right)=\left[\begin{array}{cc}\frac{p^{2}N\left(N+1\right)\left(2N+1\right)}{6}& \frac{\mathrm{pN}\left(N+1\right)}{2}\\ \frac{\mathrm{pN}\left(N+1\right)}{2}& N\end{array}\right].& \left(14\right)\end{array}$
Using Equations (11), (13), (4), and (14), it can easily be seen that:

[0040] $\begin{array}{cc}E\left\{h\left(N\right)\right\}=\left[\begin{array}{c}\alpha -1\\ d_f^r\end{array}\right]+\left[\begin{array}{c}0\\ 1/\lambda \end{array}\right],& \left(15\right)\end{array}$
which means that the LS estimator is unbiased for α but biased for d_f^r with a bias equal to the mean of the delay jitter. If one is only interested in finding an estimate of the end-to-end transmission delay, d^r(n), the fact that {circumflex over (d)}_f^r is biased will have no influence on the result according to Equation (5).

[0041] In practice, however, it would be highly advantageous to compute the normal equation recursively. Thus, in accordance with a first illustrative embodiment of the present invention, a recursive least squares (RLS) algorithm is used to calculate an estimate of a clock skew between a sender clock and a receiver clock in a packet-based communications network as follows:
R(n)=R(n−1)+x(n)x^T(n),  (16)
e(n)={tilde over (d)}(n)−x^T(n)h(n−1),  (17)
h(n)=h(n−1)+R⁻¹(n)x(n)e(n).  (18)
(Note that in accordance with one illustrative embodiment of the present invention, R⁻¹(n) may also be recursively updated, but the advantage of doing so is marginal since R is a simple 2×2 matrix.)

[0042] FIG. 1 shows a flowchart of an illustrative method for calculating an estimate of a clock skew between a sending clock and a receiving clock in accordance with the first illustrative embodiment of the present invention as described in Equations (16), (17) and (18). Block 10 performs the initialization for the recursion and blocks 11, 12 and 13 implement the calculations of Equations (16), (17) and (18), respectively. Then, decision block 14 determines whether the adaptive estimation process has resulted in the convergence of the clock skew estimate, and if so, the resultant estimate may be reliably used (block 15).

[0043] Note that when the noise signal is assumed to be zero-mean, white, and Gaussian, the least squares estimator used above is equivalent to the maximum likelihood (“ML”) estimator, well known to those skilled in the art, and hence it is asymptotically efficient. As such, it may be advantageous to use the ML estimator since the noise (i.e., the delay jitter) may be modeled best with an exponential distribution as discussed above. The ML estimator advantageously has the asymptotic properties of being unbiased and achieving the Cramer-Rao lower bound (familiar to those skilled in the art).

[0044] In this regard, first define the following error vector:
e=[e(1)e(2) . . . e(N)]^T.
Because of the i.i.d. assumption with respect to the delay jitter (see the discussion above), the joint probability (parameterized by h) of the whole vector e is the product of the marginal densities:

[0045] $\begin{array}{cc}\begin{array}{c}f\left(e\right)=\prod _{n=1}^{N}u\left[e\left(n\right)\right]\lambda \exp \left[-\lambda e\left(n\right)\right]\\ ={\lambda }^N\exp \left[-\lambda \sum _{n=1}^{N}e\left(n\right)\right]\prod _{n=1}^{N}u\left[e\left(n\right)\right].\end{array}& \left(19\right)\end{array}$
The ML estimator is obtained by maximizing ƒ(e), which is equivalent to the following linear programming problem:

[0046] $\begin{array}{cc}\max \left[-\sum _{n=1}^{N}e\left(n\right)\right]=\min \left[\sum _{n=1}^{N}e\left(n\right)\right]=\min \left[-\sum _{n=1}^N{x}^T\left(n\right)h\right]\mathrm{subject}\mathrm{to}{x}^T\left(n\right)h\le \tilde{d}\left(n\right),n=1,2,\dots ,N.& \left(20\right)\end{array}$
Note that the N constraints in Equation (20) come from the likelihood function in Equation (19), which for ƒ(e)≠0 requires e(n)≧0, ∀n≧1. Thus, because of the exponential distribution, it turns out that using the ML estimator results in a classical linear programming problem.
A Second Illustrative Method for Calculating an Estimate of the Clock Skew

[0047] Note that the accuracy of the estimation of the clock skew in accordance with the first illustrative embodiment of the present invention described above depends upon the delay jitter generally being small with respect to the total end-to-end transmission delay. That is, if the delay jitter is consistently large with respect to the end-to-end delay, the accuracy of the algorithm described above may be reduced. In accordance with a second illustrative embodiment of the present invention, however, the delay jitter is also recursively estimated, thereby providing a more accurate estimate of the clock skew even in the presence of consistently large delay jitter.

[0048] Specifically, the following derivation shows how, in accordance with the second illustrative embodiment of the present invention, we can recursively estimate the delay jitter of the n'th packet from the previous one. Recall that the end-to-end delay measurements of packets n and n−1, respectively, are as follows:
{tilde over (d)}(n)=(α−1)t_s^s(n)+d_f^r+v^r(n),  (21)
{tilde over (d)}(n−1)=(α−1)t_s^s(n−1)+d_f^r+v^r(n−1).  (22)
Taking the difference of the Equations (21) and (22), gives the following:
v^r(n)=v^r(n−1)+{tilde over (d)}(n)−{tilde over (d)}(n−1)−(α−1)[t_s^s(n)−t_s^s(n−1)],  (23)
and if the sender transmits packets at a constant packetization time p, then Equation (23) can be simplified to the following:
v^r(n)=v^r(n−1)+{tilde over (d)}(n)−{tilde over (d)}(n−1)−p(α−1).  (24)
Note that Equation (24) depends on the clock skew but is independent of the fixed delay. Note also that one advantage of using a recursive algorithm in accordance with the principles of the present invention is that even when the parameter α is not known, it can be advantageously replaced by its estimate. Hence, in accordance with the second illustrative embodiment of the present invention, the following recursion may be advantageously used to estimate the delay jitter for the n'th packet:
{circumflex over (v)}^r(n)=|{circumflex over (v)}^r(n−1)+{tilde over (d)}(n)−{tilde over (d)}(n−1)−ph₁(n−1)|,  (25)
where h₁(n−1)={circumflex over (α)}(n−1)−1 is advantageously computed with the RLS algorithm in accordance with the principles of the present invention. Note that the use of the absolute value function in Equation (25) advantageously avoids negative delays.

[0049] Thus, in accordance with the second illustrative embodiment of the present invention, calculating an estimate for the delay jitter advantageously provides for an improvement to the RLS algorithm described above in Equations (16), (17) and (18) in accordance with the first illustrative embodiment of the present invention. Indeed, by subtracting {circumflex over (v)}^r(n) from the error signal in Equation (17), the RLS algorithm of the first illustrative embodiment is, essentially, made unbiased. A complete unbiased RLS algorithm for use in calculating an estimate of a clock skew between a sender clock and a receiver clock in a packet-based communications network in accordance with the second illustrative embodiment of the present invention is, therefore, as follows:
{circumflex over (v)}^r(n)=|{circumflex over (v)}^r(n−1)+{tilde over (d)}(n)−{tilde over (d)}(n−1)−[x₁(n)−x₁(n−1)]h₁(n−1)|,  (26)
R(n)=R(n−1)+x(n)x^T(n),  (27)
e₀(n)={tilde over (d)}(n)−x^T(n)h(n−1)−{circumflex over (v)}^r(n),  (28)
h(n)=h(n−1)+R⁻¹(n)x(n)e₀(n).  (29)

[0050] FIG. 2 shows a flowchart of an illustrative method for calculating an estimate of a clock skew between a sending clock and a receiving clock in accordance with the second illustrative embodiment of the present invention as described in Equations (26), (27), (28) and (29). Block 20 performs the initialization I-or the recursion and blocks 21, 22, 23 and 24 implement the calculations of Equations (26), (27), (28) and (29), respectively. Then, decision block 25 determines whether the adaptive estimation process has resulted in the convergence of the clock skew estimate, and if so, the resultant estimate may be reliably used (block 26).

An Illustrative Embodiment for Adjusting Input Buffer Sizes Based on Clock Skew

[0051] FIG. 3 shows a flowchart of an illustrative method for adjusting an input buffer size based on a calculated estimate of a clock skew between a sending clock and a receiving clock in accordance with one illustrative embodiment of the present invention. As shown in block 31, the RLS algorithm of either the first or the second illustrative embodiments of the present invention (as illustratively shown in FIGS. 1 and 2, respectively) are performed to estimate the clock skew between a sending clock and a receiving clock in a packet-based communications network. Then, decision block 32 determines whether the clock skew requires that an adjustment be made to the size of the input buffer at the receiving location. If so, block 33 makes the necessary adjustment.

Addendum to the Detailed Description

[0052] It should be noted that all of the preceding discussion merely illustrates the general principles of the invention. It will be appreciated that those skilled in the art will be able to devise various other arrangements, which, although not explicitly described or shown herein, embody the principles of the invention, and are included within its spirit and scope.

[0053] Furthermore, all examples and conditional language recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventors to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. It is also intended that such equivalents include both currently known equivalents as well as equivalents developed in the future—i.e., any elements developed that perform the same function, regardless of structure.

[0054] Thus, for example, it will be appreciated by those skilled in the art that the block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudocode, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. Thus, the blocks shown, for example, in such flowcharts may be understood as potentially representing physical elements, which may, for example, be expressed in the instant claims as means for specifying particular functions such as are described in the flowchart blocks. Moreover, such flowchart blocks may also be understood as representing physical signals or stored physical data, which may, for example, be comprised in such aforementioned computer readable medium such as disc or semiconductor storage devices.

[0055] The functions of the various elements shown in the figures, including functional blocks labeled as “processors” or “modules” may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term “processor” or “controller” should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitations digital signal processor (DSP) hardware, read-only memory (ROM) for storing software, random access memory (RAM), and non-volatile storage. Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the figures are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context.