WO2005002100A1

WO2005002100A1 - High accuracy network clock synchronization

Info

Publication number: WO2005002100A1
Application number: PCT/IB2004/051057
Authority: WO
Inventors: Laurent P. F. Bousis
Original assignee: Koninklijke Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 2003-06-30
Filing date: 2004-06-30
Publication date: 2005-01-06
Anticipated expiration: 2005-12-30

Abstract

Skew and offset of a first clock (280) at a first node (200) of a network relative to a second clock (270) at a second node (220) is estimated by recording times of transmission and receipt of a series of messages exchanged (100, 110) between the nodes, determining (115) a series of instantaneous offsets at a series of time instants, from the recorded times and deriving offset and skew from the series using a linear regression (130). Accuracy still depends on the skew being fairly constant, the measurements being accurate and well defined, an appropriate number of measurements, and the delays in each direction tending to be symmetric on average. The measurements can be repeated periodically (120) to update the estimates. Applications include audio or visual packet data steamed to multiple nodes to enable them to be synchronized so that a user does not perceive distortion from relative delays or delay variation.

Description

High accuracy network clock synchronization

This invention relates to methods and apparatus for estimating clock offset and clock skew, and for synchronizing clocks in remote devices, for application to internet coupled devices and to synchronization of time sensitive streams of data such as digital bit streams especially video or audio streams.

Clock synchronization between different devices on networks such as Personal Area Networks (PAN), Controller Area Networks (CAN), Local Area Networks (LAN), Wide Area Networks (WAN), Metropolitan Area Networks (MAN), wireless or satellite networks or the internet for example is becoming more important. Applications include providing time information or time interval information, or determining an order of events at distributed locations. This can be useful for a wide variety of advanced applications on distributed hosts or distributed clients. Currently clocks of internet hosts and clients can be synchronized using the Network Time Protocol NTP, (RFC-1305), to within a few milliseconds. This involves exchanging timestamps, computing delays and offsets and selecting and filtering the values from different sources. Higher accuracy synchronization can be achieved in more strictly controlled environments such as telephone networks or the Global Positioning System GPS. For example, a network may be provided with a reference clock. One way of implementing a reference clock is to provide a master device and the time reported by a clock of the master device is considered to be the reference clock for that network. This often makes sense since the content streamed by the master device will most likely contain timestamps issued by that clock. However, the present invention is not limited to this definition of how a reference clock is provided. The offset of the clock of a client device is defined as the difference at a particular moment in time between the time reported by that clock and the time reported by the reference clock. The skew of the clock of a client device is defined as the difference at a particular moment in time between the frequency of that clock and a frequency of the reference clock. Note that in this definition the skew of the clock of a client device is in fact the first derivative of its offset with respect to the time of the reference clock. "Estimation of clock offset from one-way delay measurement on asymmetric paths" by Masato Tsuru, Tetsuya Takine and Yuji Oie (Saint 2002 Workshop, Feb 1 2002, Nara) acknowledges that it was known to estimate the clock offset, clock skew and bandwidth separately. The clock skew could be estimated from one-way delay measurements with fixed size packets in one direction. Alternatively, the clock offset could be estimated from one-way delay measurements with fixed size packets in both directions (like NTP) when delay is symmetric. Yet another alternative was to estimate the bandwidth information in one direction from one-way delay measurement with variable size packets in one direction when skew is negligible. To improve on these, a method is proposed which estimates the clock offset and skew from one-way delay measurements with variable size packets in both directions, even in case of asymmetric bandwidths, but still needing the assumption of symmetric propagation delays. It can be regarded as a three-variable Linear Programming which is an extension of skew estimation method based on a two-variable Linear

Prograrnrning. It involves finding a minimum of a function Qi (α, λ, μ) where 1/α is the skew, λis a function of transmission delays, and μ is a function of propagation delays, over many timestamped messages. It is known from International patent publication WO 00/16509 to estimate relative skew between clocks in packet networks from timestamps in received packets and the local time of receipt. The delay in receipt is calculated, then compared to a previous delay to determine jitter. Average jitter is then used to determine skew. It is known from "Improved Algorithms for synchronizing computer network clocks" Mills, JJEEE/ACM transactions on networking Vol. 3 no 3, June 1995, to provide improvements to the NTP protocol. The improvements include refining the calculation of offsets, and how the local clock is controlled and adjusted, and adaptation to prevailing network conditions. "On Calibrating Measurements of Packet Transit Times" by Paxson, Sigmetrics 1998, suggests that using "echo" techniques involving sending packets and receiving replies is inaccurate as return paths over the internet often have different delays. Hence it is suggested to use "receiver based" measurements and compare time stamps with the local clock. Short term synchronization is improved by detecting clock adjustments and skew. One advanced example calling for higher accuracy is a household network for sending content such as audio or video streams in separate channels to or from separate devices on the network. This needs network clock synchronization with an accuracy that is several orders of magnitudes better than that achieved with traditional network synchronization protocols like NTP. When sfreaming separate audio channels over a network to several client devices, special care needs to be taken to maintain synchronization between those devices during playback. Consider for example the sfreaming of left and right audio channels in the form of Internet Protocol (IP) data packets to two separate speakers respectively in the same room, where the packets are used to drive the speakers. Audio travels at 343 m/s (at a normal atmospheric pressure and at 20 deg. Celsius). This means that a delay of 1ms between the left and right audio channels will be perceived by a listener as a distance difference from the listening position of 34.3 cm for one of the two speakers. Worse, variations of that delay during playback will be perceived as a movement of the speakers or of the perceived noise source.

According to a first aspect, the invention provides apparatus for estimating skew and offset of a first clock at a first node of a network relative to a second clock at a second node of the network, the apparatus having means for: - . recording times of transmission and receipt of a series of messages exchanged between the nodes, deteπnining a series of instantaneous offsets at a series of time instants, from the recorded times of transmission and receipt, and determining an estimated offset, and an estimated skew from the series using a statistical method. By statistical method is meant a method used to find relationships between the measurements in order to predict future values. A suitable statistical method is regression analysis, especially linear regression. The combination of the series of instantaneous offsets and applying a statistical method to the series to estimate the skew and offset can produce more accurate results than other methods such as the Network Time Protocol [NTP] using other variables as set out above. Accuracy still depends on the skew being fairly constant, the measurements being accurate and well defined, an appropriate number of measurements, and the delays in each direction tending to be symmetric on average, and other practical factors. By applying a well-defined statistical analysis to a well-defined series of measurements the skew and offset of the clock of the client can be precisely estimated. As a preferred additional feature, the statistical method is regression, especially linear regression. This is one suitable way of fitting a line to the points in the series. It assumes the skew is constant, otherwise a non-linear regression might be more appropriate. As a preferred additional feature, the linear regression is determined using a least squares algorithm. This is one suitable and efficient way of fitting a line to the series. As a preferred additional feature, the steps are repeated to update the set and determine an updated estimated offset and an updated estimated skew. This enables the estimates to be continuously updated to maintain accuracy and adapt to changing conditions. As a preferred additional feature, the instantaneous offset is determined from the relation

_{0 ^} TT_M + RT_u -OT_c - CT_c + e 2 where OT_c is the time of the client sending the first message, RT_M is the time of receipt of the first message at the master, and TT_M is the time of transmission of the second message from the master, CTc is defined as the time the second message is received, and the offset O is defined as the offset between the clock of the client device and the clock of the master device, and e is the difference between TD, the transmission delay of the first message, and RD, the transmission delay in the other direction of the second message. As a preferred additional feature, the apparatus is located at the first node. As a preferred additional feature, the network is an IP network. As a preferred additional feature, the messages comprise ICMP (Internet Control Message Protocol) timestamp request and reply messages. As a preferred additional feature, the apparatus further comprises means for correcting the first clock to match the second clock. As a preferred additional feature, the apparatus is arranged to carry out the recording of times of transmission and receipt during transmission of user data between the nodes. As a preferred additional feature, the apparatus is arranged to delay user data passing through the first node on the basis of the estimated offset and skew. This is another way of reducing errors or distortion caused by the offset and skew. As a preferred additional feature, the user data is video or audio or multimedia data for presentation to a user from a number of network nodes synchronously, or for recording from a number of network nodes synchronously. Another aspect of the invention provides consumer equipment having an interface for coupling to a network, a first clock, and means for estimating skew and offset of the first clock relative to a second clock at a second node of the network by determining a series of instantaneous offsets at a series of time instants, from the recorded times of transmission and receipt, and determining an estimated offset, and an estimated skew from the series using a statistical method. Other aspects of the invention include methods of estimating the skew and offset, methods of using the skew and offset estimated by this method, methods of synchronizing consumer equipment using the estimated skew and offset, and signals synchronized using the estimated skew and offset. How the present invention may be put into effect will now be described with reference to the appended schematic drawings. Obviously, numerous variations and modifications can be made without departing from the scope of the claims of the present invention. Therefore, it should be clearly understood that the form of the present invention is illustrative only and is not intended to limit the scope of the claims.

The features of the invention will be better understood by reference to the accompanying drawings, which illustrate preferred embodiments of the invention. In the drawings: Fig. 1 shows an example of an ICMP timestamp request/reply, Fig. 2 shows an example of the time flow of an exchange of messages between a client-master pair of nodes, Fig. 3 shows a graph of a normal distribution of values of the difference of delay between the two directions of transmission, Fig. 4 shows a graph of a series of offsets for a series of messages at different times, Fig. 5 shows a flow chart of estimating skew and offset according to an embodiment of the invention, and Fig. 6 shows an application of the estimated skew and offset, for synchronization, according to another embodiment. The present invention will be described with respect to particular embodiments and with reference to certain drawings but the invention is not limited thereto but only by the claims. The drawings described are only schematic and are non-limiting. In the drawings, the size of some of the elements may be exaggerated and not drawn on scale for illustrative purposes. Where the term "comprising" is used in the present description and claims, it does not exclude other elements or steps. Furthermore, the terms first, second, third and the like in the description and in the claims, are used for distinguishing between similar elements and not necessarily for describing a sequential or chronological order. It is to be understood that the terms so used are interchangeable under appropriate circumstances and that the embodiments of the invention described herein are capable of operation in other sequences than described or illustrated herein. Moreover, any such terms as top, bottom, over, under and the like in the description and the claims are used for descriptive purposes and not necessarily for describing relative positions. It is to be understood that the terms so used are interchangeable under appropriate circumstances and that the embodiments of the invention described herein are capable of operation in other orientations than described or illustrated herein. Embodiments of this invention are preferred that concern clock synchronization of devices in an IP based network where the difference between the network reception delay and the network transmission delay is non-negligible but the present invention is not limited thereto. Rather, the present invention can have advantage use in a wide variety of networks comprising nodes linked by communications paths. Having a difference between the network reception delay and the network transmission delay that is non-negligible contrasts with the known Network Time Protocol (RFC 1305) that has traditionally been used to synchronize the clocks of workstations and servers on the Internet, where this difference is assumed to be negligible compared to the accuracy that is aimed for. The estimation of skew and offset starts with measurements of times of transmission and receipt of messages sent between nodes. A client device at a first node of the network sends an ICMP Timestamp Request to a master device at a second node. The master device answers the request and sends an ICMP Timestamp Reply to the client device. Fig. 1 shows the format of an ICMP Timestamp Request/Reply as specified in RFC792. Of interest here is the originate timestamp which is "the time the sender last touched the message before sending it" [RFC792], the receive timestamp which is "the time the echoer first touched it on receipt" [RFC792] and the transmit timestamp which is "the time the echoer last touched the message on sending it" [RFC792]. The time is recorded as a 32bit value with the higher order bit set to one to "indicate this non-standard value"

[RFC792]. The precision of this time value should be equal to that of the most precise clock in this client- master pair. Fig. 2 illustrates the time flow for the exchange of these messages between the client-master pair. A subscript of C on time values indicates the time has been reported by the clock of the client device; a subscript of M on time values indicates the time has been reported by the clock of the master device. Hence OT_c is the time of the client sending the first message, RT_M is the time of receipt of the first message at the master, and TT_M is the time of transmission of the second message from the master. The completion timestamp CT is defined as the time the sender of the ICMP Timestamp request first touched the ICMP Timestamp reply on receipt and the offset O is defined as the offset between the clock of the client device and the clock of the master device. TD is the transmission delay of the first message, RD is the transmission delay in the other direction of the second message, and PD is the processing delay at the master between the first and second messages. The relationships between these times can be stated as follows: CT_c - OT_c = TD + PD + RD RT_u - OT_M = TD TT_M - RT_M = PD OT_M = 0T_c + O CT_C -OT_c = RT_M - OT_c - 0 + TT_u -RT_M + RD => CT_C = -O + TT_M + RD The network reception delay RD can be approximated by the network transmission delay TD, where e is the difference between the delays:

RD = TD + e ^ CT_c = -0 + TT_M + RT_M - OT_c-0 + e = CT_c = TT_M + RT_M - OT_c - 2 - 0 + e

The instantaneous offset O can thus be found by the following equation: 2 -, σ-c ^e 2 ^{TTM +RTM} 2 ^{~ 0TC ~ CTC}

All values except e (the difference between the network reception delay and the network transmission delay) are known with timestamp time value precision. If e was zero or at least one order of magnitude smaller than the accuracy we wish to achieve (this assumption is the basis of the Network Time Protocol [NTP] which obtains accuracies in the order of a few ms on LANs), the offset O' could be used to precisely synchronize the clock of the client with the clock of the master. For the application of streaming audio channels to speakers over a distribution network like Ethernet however, e will most likely not be negligible compared to the accuracy desired, namely at least 22 microseconds (= 1 sample) for audio sampled at 44.1 kHz. However, since the distribution of e tends to normal for a large number of measurements taken in a network where the conditions remain more or less the same, and since it is centered around zero for measurements taken in a network that is symmetrical in nature, the value of O' can be averaged and thereby the effect of e can be reduced. This is shown in Fig. 3. e « 0

If the skew was zero or negligible, it would have been sufficient to make a large number of measurements to find the average value of O' and use that value as the estimated offset O between the client device and the master device. However, since the skew is non-negligible compared to the desired accuracy, the estimate based on the average value of O' will no longer be representative of the offset O between the client device and the master device. Indeed, the effect of the skew will start to show during the measurements and if it is assumed the drift is negligible (meaning the skew will be constant) the measurements will trend towards a non-horizontal (non-horizontal if the skew is non-zero) straight line over time. Fig. 4 illustrates an example of a set of instantaneous offsets and the resulting best fit line through the set, to derive the estimated offset at OTc and the skew. The line can be derived by various statistical methods, one preferred method involves applying linear regression to the set of samples (0 OTa). A filter could optionally be applied on the values O'i of the collected samples in order to reduce or eliminate noise in the samples. The linear regression to find an estimation of the skew S (= slope of the line) and the offset O (= vertical intersect of the line) for the clock of the client device is as follows: _θ'= s-oτ_c + o

=> O = O - S O with

_^ T_Ci

A suitable value of n, the number of measurements, can be experimentally determined for the type of distribution network that will be used, and for the desired level of accuracy. Below is a pseudo-code illustration of the complete measurement: on the client device: for (i = 0; i < n; i++) { get OTci and send ICMP Timestamp Request; wait for ICMP Timestamp Reply and get CTα; extract TT_MJ and RT_MJ from ICMP Timestamp Reply; calculate O'_J; add (O'j, OTci) to measurement list; } calculate S and O using measurement list;

on the master device: while (client is measuring) { wait for ICMP Timestamp Request and get RT_MJJ get TT_Mi and send ICMP Timestamp Request; } A flow chart of these steps leading to the estimated values of skew and offset is shown in Fig. 5. At step 100, the client at the first node sends the first message with a timestamp request to the second node. In networks where there is more than one master there can be a preliminary step of choosing which master to synchronize to, or choosing to synchronize to an average of multiple masters. At step 110, the client receives the reply, the second message, records the time of receipt, and extracts from it a time of receipt of the first message and a time of transmission of the second message. These are used at step 115 to calculate the instantaneous offset O'j. These measurements are repeated by sending more messages, to build up a list at step 120 of instantaneous values. At step 130, the linear regression is carried out as discussed above, to derive the estimated values of skew and offset. At step 140, more measurements are taken and the estimated values are updated using the more recent measurements. There are a number of different uses for the estimated values. Once the value of the offset O and the skew S have been estimated, the client has enough information (in combination with the originate timestamp OTco of the first measurement) to know with high accuracy how its clock T_c relates to the clock of the master T_M at every moment in time i:

T_u ^l = T^l +0 + {τ,L -OT_Cύ)- S

This knowledge can be used to continuously synchronize the client to the master. This can involve correcting the clock of the client or involve feeding a PLL or adaptive sample rate converter to delay the data directly, when streaming content. Fig. 6 shows an embodiment in which a first node (the client) is household consumer equipment such as an audio speaker 200. It is connected to receive an audio signal in the form of packets over a household LAN 210 from a second node (the master) which is a Personal Computer PC 220. The LAN can use the household power supply wiring or be a wireless LAN, to overcome the inconvenience of conventional speaker cables. The speaker is accurately synchronized to the PC to avoid the problems described above. The speaker includes a network interface card or chip 230, a packet processing part 240 for recording time of receipt and transmission, and for extracting information from received measurement packets. An estimation part 250 uses the measured times to create the set of offsets and derive the estimated skew and offset, using a statistical method. This can be implemented as discussed above, or in other ways. An audio generator part 260 recreates the audio signal from the received streamed packets, with a clock variation according to the estimated skew and offset. For the speaker, the clock to be synchronized is the first clock 280 used by the audio generator part 260 to produce sound. This will for example typically be 44100 Hz for CD quality sound. This clock is adapted to speed up or slow down the clock time based on the estimated skew and offset of that clock with regards to the master clock. The speeding up or slowing down is a typically small change. The link between the first clock 280 and the audio generator part 260 is provided through estimation part 250. These parts can be implemented in various conventional types of hardware and software depending on the application, following established principles. A single general purpose microprocessor or Application Specific Integrated Circuit can be used to implement the NIC, the packet processing part and the estimation part for example. In order to produce better estimations of the offset O and skew S with fewer measurements, the measurements can be carried out on an idle network right before the content is being streamed. Alternatively, the measurements could be done continuously during the streaming thereby producing updated values of the offset O and skew S at fixed time intervals. The present invention provides several advantages. Being able to accurately synchronize the clocks of devices inside home or other networks is of importance if content is to be streamed in separate channels to separate devices. Not only synchronization between audio channels, but also synchronization between audio and video channels has to be achieved with accuracies that are orders of magnitude higher than that achieved by traditional network synchronization protocols used in the PC environment. The embodiments of the invention described here are able to achieve better accuracies and could therefore be implemented in any consumer electronic devices (and PCs) that stream and receive content inside home networks for example. Network clock synchronization can be implemented with an accuracy that is orders of magnitudes better than traditional network synchronization protocols like NTP by applying a well-defined statistical analysis to a well-defined series of measurements to precisely estimate the skew and offset of the clock of the client. The skilled person will appreciate from the above that skew and offset of a clock at a first node of a network relative to a second clock at a second node is estimated by recording times of transmission and receipt of a series of messages exchanged between the nodes, determining a series of instantaneous offsets at a series of time instants, from the recorded times and deriving offset and skew from the series using a statistical method such as regression, especially linear regression. Accuracy still depends on the skew being fairly constant, the measurements being accurate and well defined, an appropriate number of measurements, and the delays in each direction tending to be symmetric on average. The measurements can be repeated periodically to update the estimates. Apphcations include audio or visual packet data streamed to multiple nodes to enable them to be synchronized so that a user does not perceive distortion from relative delays or delay variation. Other variations can be envisaged by those skilled in the art and are intended to be encompassed by the claims.

Claims

CLAIMS:

1. Apparatus for estimating skew and offset of a first clock (280) at a first node

(200) of a network relative to a second clock (280) at a second node (220) of the network, the apparatus having: means (240) for recording times of transmission and receipt of a series of messages exchanged between the nodes, means (250) for deterrnining a series of instantaneous offsets at a series of time instants, from the recorded times of transmission and receipt, and means (250) for determining an estimated offset, and an estimated skew from the series using a statistical method.

2. The apparatus of claim 1, the statistical method being regression.

3. The apparatus according to claim 2, wherein the regression is linear regression.

4. The apparatus of claim 3, arranged to determine the linear regression using a least squares algorithm.

5. The apparatus of any preceding claim, arranged to repeat the steps to update the set and determine an updated estimated offset and an updated estimated skew.

6. The apparatus of any preceding claim, arranged to determine the instantaneous offset O using the relation:

₀ _ TT_M + RT_M -OT_c - CT_c + e 2 where OT_c is the time of the first node sending a first message to the second node, RT_M is the time of receipt of the first message at the second node, TT_M is the time of transmission of a second message from the second node, CTc is the time of receipt of the second message at the first node, O is the offset between the clock of the first node and the clock of the second node, and e is the difference between TD the transmission delay of the first message and RD the transmission delay in the other direction of the second message.

7. The apparatus of any preceding claim, the apparatus being incorporated in the first node.

8. The apparatus of any preceding claim, the network being an IP network.

9. The apparatus of any preceding claim, the messages comprising ICMP timestamp request and reply messages.

10. The apparatus of any preceding claim, further comprising means for correcting the first clock to match the second clock.

11. The apparatus of any preceding claim, arranged to carry out the recording of times of transmission and receipt during transmission of user data between the nodes.

12. The apparatus of any preceding claim, having means (260) for delaying user data passing through the first node on the basis of the estimated offset and skew.

13. The apparatus of any preceding claim, the first node being arranged to process user data representing video or audio or multimedia data for presentation to a user from a number of network nodes synchronously, or for recording from a number of network nodes synchronously.

14. Consumer equipment (200) having an interface (230) for coupling to a network (210), a first clock (280), means (250) for estimating skew and offset of the first clock relative to a second clock (270) at a second node (220) of the network by determining a series of instantaneous offsets at a series of time instants, from the recorded times of transmission and receipt, and using a statistical method to determine an estimated offset, and an estimated skew from the series.

15. A method of estimating skew and offset of a first clock at a first node of a network relative to a second clock at a second node of the network by determining (115) a series of instantaneous offsets at a series of time instants, from the recorded times of transmission and receipt, and using a statistical method (130) to deterrnine an estimated offset, and an estimated skew from the series.

16. A method of synchronizing signals received or transmitted by a first node of a network using skew and offset estimated by the method of claim 15.

17. A signal received or transmitted by a first node of a network having a first clock, the signal being synchronized to a second clock at a second node using estimates of skew and offset of the first clock relative to the second clock, estimated by the method of claim 15.