Removing delay fluctuation in network time synchronization

BACKGROUND

0001A wide variety of devices may include a local clock that maintains a time-of-day. Examples devices that may have a local time-of-day clock include computer systems, test instruments, industrial control devices, environmental control devices, and home appliances.

0002A time synchronization protocol may be used to synchronize a local clock in a device. A time synchronization protocol may be one in which a local clock exchanges timing packets with a reference clock via a communication network. The transmit and receive times of the timing packets may be used to determine a time offset between a local clock and a reference clock so that the local clock may be adjusted to match the time in the reference clock. One example of a time synchronization protocol that includes the exchange of timing packets is the IEEE 1588 time synchronization protocol. Another example is the network time protocol (NTP).

0003A time offset that is derived from the exchange of timing packets may include a network delay associated with the transfer of the timing packet over a communication network. The network delay may be removed from a time offset before applying the time offset to a local clock. For example, a running average of the network delays for a series of timing packets may be determined and the running average may be subtracted from the time offset calculations.

0004The network delays of timing packets may fluctuate in response to changes in network conditions. For example, a timing packet transferred during a period of relatively high network traffic may experience a much larger network delay than a timing packet transferred during a period of relatively low network traffic. Fluctuations in network delay may reduce the precision of a time synchronization protocol. For example, timing packets having a network delay that significantly exceeds a running average of network delays may cause an unneeded adjustment to a local clock.

SUMMARY OF THE INVENTION

0005Techniques are disclosed for removing delay fluctuations from network time synchronization so that timing packets that experience an inordinate network delay to not cause unneeded adjustments to a local clock. Time synchronization according to the present techniques includes measuring a network delay associated with a timing packet and discarding the timing packet if the network delay exceeds an adjustable threshold. The adjustable threshold enables balancing the quality of delay measurements in terms of delay fluctuation against the number of delay measurements that are sufficient to maintain time synchronization.

0006Other features and advantages of the present invention will be apparent from the detailed description that follows.

BRIEF DESCRIPTION OF THE DRAWINGS

0007The present invention is described with respect to particular exemplary embodiments thereof and reference is accordingly made to the drawings in which:

0008<figref idref="DRAWINGS">FIG. 1</figref> shows a pair of devices that include mechanisms for removing delay fluctuations in network time synchronization according to the present teachings;

0009<figref idref="DRAWINGS">FIG. 2</figref> shows a method for removing delay fluctuations in network time synchronization according to the present teachings;

0010<figref idref="DRAWINGS">FIG. 3</figref> shows a method for removing fluctuations from time offset adjustments according to the present teachings.

DETAILED DESCRIPTION

0011<figref idref="DRAWINGS">FIG. 1</figref> shows a pair of devices <b>10</b> and <b>12</b> that include mechanisms for removing delay fluctuations in network time synchronization according to the present teachings. Example embodiments of the devices <b>10</b> and <b>12</b> include computer systems, test instruments, industrial control devices, environmental control devices, home appliances, etc.

0012The device <b>10</b> includes a local clock <b>14</b> and the device <b>12</b> includes a local clock <b>16</b>. The devices <b>10</b> and <b>12</b> include respective time synchronization circuits <b>40</b> and <b>42</b> that maintain time synchronization in the local clocks <b>14</b> and <b>16</b> by exchanging timing packets via a communication network <b>30</b>, e.g. a set of timing packets <b>20</b>-<b>22</b>.

0013In one embodiment, the time synchronization circuits <b>40</b> and <b>42</b> maintain time synchronization according to the IEEE 1588 time synchronization protocol. In the example shown, the time synchronization circuit <b>42</b> adjusts the time-of-day in the local clock <b>16</b> to conform to the time-of-day held in the local clock <b>14</b> of the device <b>10</b>, i.e. the local clock <b>14</b> is a master clock and the local clock <b>16</b> is a slave clock.

0014For example, the time synchronization circuit <b>40</b> generates the timing packet <b>20</b> and transfers it to the time synchronization circuit <b>42</b> via the communication network <b>30</b> and the time synchronization circuit <b>42</b> generates the timing packet <b>22</b> and transfers it to the time synchronization circuit <b>40</b> via the communication network <b>30</b>. The time synchronization circuit <b>40</b> measures a transmit time (T<b>1</b>) of the timing packet <b>20</b> and the time synchronization circuit <b>42</b> measures a receive time (T<b>2</b>) of the timing packet <b>20</b>. Similarly, the time synchronization circuit <b>42</b> measures a transmit time (T<b>3</b>) of the timing packet <b>22</b> and the time synchronization circuit <b>40</b> measures a receive time (T<b>4</b>) of the timing packet <b>22</b>. A time offset (OFFSET) to be applied to the local clock <b>16</b> is derived from the time-stamps T<b>1</b>-T<b>4</b> (according to the IEEE 1588 time synchronization protocol in one embodiment)

0015In one embodiment, the network delay of the timing packet <b>20</b>, i.e. the network delay from master to slave (MSD), is assumed to be equal to the network delay of the timing packet <b>22</b>, i.e. the network delay from slave to master (SMD). The time offset for the local clock <b>16</b> is as follows. <br />OFFSET=<i>T</i>2−<i>T</i>1−ONE WAY DELAY  (equation 1) <br />where <br />ONE WAY DELAY=(<i>MSD+SMD</i>)/2 <br />and <br /><i>MSD</i>=(<i>T</i>2−OFFSET)−<i>T</i>1 <br /><i>SMD=T</i>4−(<i>T</i>3−OFFSET).  (equation 2)

0016Equation 1 shows that the time offset to be applied to the local clock <b>16</b> is a function of the network delay experienced by a timing packet carried via the communication network <b>30</b> between the devices <b>10</b> and <b>12</b>. It is likely that the network delay experienced by a timing packet will fluctuate depending on the amount of network traffic underway. For example, the communication network <b>30</b> may handle traffic for other devices (not shown) or may handle data packets for application-specific functions of the devices <b>10</b> and <b>12</b> that are not timing packets. High volumes of network traffic at times may cause some of the timing packets exchanged by the devices <b>10</b> and <b>12</b> to experience inordinately long delays. For example, a timing packet may experience a substantially higher delay by waiting in a queue in a communication switch of the communication network <b>30</b> during a period of high traffic volume. A queuing delay imposed on a timing packet may cause an inordinately large time offset to be applied to the local clock <b>16</b> according to equation 1. A time offset yielded by an excessively delayed timing packet may degrade the accuracy in the time synchronization of the local clock <b>16</b>.

0017The present techniques for removing network delay fluctuations include discarding timing packets that have experienced excessively high network delay using an adjustable threshold of excessive delay. The discarding of timing packets that experience an excessive network delay avoids unneeded time adjustments to the local clock <b>16</b>. For example, equation 2 may be used to determine the network delay of a timing packet so that the timing packet may be discarded if its network delay is substantially larger than the network delay associated with timing packets exchanged by the devices <b>10</b> and <b>12</b> that do not experience excessive network delay. If a timing packet is discarded then the timing information derived from the timing packet is not used to determine a time offset to be applied to the local clock <b>16</b>.

0018In some embodiments, the time-of-day held in the local clock <b>16</b> may advance relatively smoothly. In such embodiments, once a time synchronization servo settles it need not follow excursions accurately. The updates to the local clock <b>16</b> may be of relatively low bandwidth and still maintain adequate time synchronization. Therefore, the balance between the quality of delay measurements and the number of delay measurements may be tipped toward higher quality and fewer delay measurements.

0019Timing packets occasionally encounter a path through the communication network <b>30</b> with no queuing delays. All timing packets that take that path have substantially similar amounts of network delay. Timing packets that are queued have a much larger network delay than the network delay experienced by timing packets having no queuing delay so that timing packets that are queued may be recognized.

0020The devices <b>10</b> and <b>12</b> include respective communication subsystems that are adapted for communication via the communication link <b>30</b> and that enable the time synchronization circuits <b>40</b> and <b>42</b> to exchange timing packets via the communication link <b>30</b>. For example, the communication subsystems may include media access controller, (MAC) and physical interface (PHY) elements, etc., depending on the implementation of the communication network <b>30</b>. The time synchronization circuits <b>40</b> and <b>42</b> may include processor subsystems that implement a network protocol stack and that generate timing packets and that obtain timing information from timing packet. The time synchronization circuits <b>40</b> and <b>42</b> may also include time packet recognizer circuitry for recognizing and time stamping inbound and outbound timing packets.

0021<figref idref="DRAWINGS">FIG. 2</figref> shows a method for removing delay fluctuations in network time synchronization according to the present teachings. The method step shown may be used to determine a minimum network delay path for a timing packet carried on the communication network <b>30</b> between the device <b>10</b> and <b>12</b> so that timing packets exchanged by the devices <b>10</b> and <b>12</b> having excessive delay may be selected and discarded. In the following, the minimum network delay is represented by the variable delta. An adjustable threshold of epsilon includes the expected network delay jitter on the communication network <b>30</b> without queuing delays.

0022Initially, a relatively large initial value is chosen for delta. An example of a large initial value for delta is an estimate of the time for sending a timing packet around the world via a network.

0023At step <b>100</b>, the timing information associated with an incoming timing packet, e.g. measured and/or transported time stamps, is used to determine a network delay between the devices <b>10</b> and <b>12</b>. In one embodiment, the network delay determined at step <b>100</b> is the round-trip network delay. The network delay at step <b>100</b> may be determined according to IEEE 1588 calculations or NTP calculations or other similar time synchronization protocol depending on a particular embodiment.

0024At step <b>102</b>, if the network delay from step <b>100</b> is greater than delta+epsilon, then the corresponding timing packet is discarded, i.e. ignored and not used in determining a time offset to be used in adjusting the local clock <b>16</b>.

0025At step <b>104</b>, if the network delay from step <b>100</b> is within epsilon of delta, then delta is set to an average of the previous value of delta and the network delay from step <b>100</b>. Any running average may be used, e.g. exponential averaging.

0026At step <b>106</b>, if the network delay from step <b>100</b> is smaller than delta-epsilon, then the previously computed running average, if any, is discarded and delta is set to the network delay from step <b>100</b>.

0027The above process repeats with for each incoming timing packet.

0028The discarding of timing packets having an excessive network delay reduces the number of timing packets available for time synchronization. The present techniques include controlling the discarding of timing packets using the adjustable threshold so that the quality of delay measurements may be balanced against the number of measurements needed given the capability of the local clock <b>16</b> in maintaining time synchronization in the absence of time updates.

0029For example, the path taken by a timing packet through the communication network <b>30</b> may be represented as a series of queues, i.e. a series of i delay elements each having a delay distribution with a practical minimum. The delay elements may be regarded as mutually independent and as having substantially similar delay distributions. The delay introduced by each delay element averaged over an acceptable time between delay estimates is d<b>1</b>, d<b>2</b> . . . dn. The value of epsilon may be adjusted by adding d<b>1</b> to it, and then adding d<b>2</b> to it, and then adding d<b>3</b> to it, etc., until the probability of the remaining n−i elements simultaneously introducing their minimum delay is sufficiently large, i.e. the expected time between timing packets that are not discarded is sufficiently small.

0030It may not be known how many delay elements in a communication network cause significant delay. Given that the delay di is mapped onto values of epsilon, a smallest and largest delay fluctuation may be estimated and the span between the smallest and the largest may be partitioned into n ranges. This enables an adjustment of the balance between frequency and variance of the network delay corrections.

0031The above technique for subdividing the largest network delay in timing packet transfer provides a set of control steps in an adjustable threshold. The number of control steps used for the adjustable threshold may depend on how efficiently the local clock <b>16</b> coasts, i.e. on how frequently time updates to the local clock <b>16</b> are needed to maintain sufficient synchronization.

0032Several instances of a process embodying the steps <b>100</b>-<b>106</b> may be executed in parallel. Each instance may have a different value of i, and different weights may be assigned to the network delay estimates yielded by the instances. The instance with 1=1 will produce network delay estimates least often but with the highest weight. The instance with i=n will produce a network delay estimate for every incoming timing packet but with the lowest weight.

0033A time offset to be applied the local clock <b>16</b> is determined in response to each incoming timing packet received via the communication network <b>30</b>. If a time offset is relatively large, i.e. significantly greater than epsilon, then it may be assumed that the large time offset is a result of excessive network delay in a timing packet rather than a sudden erratic behavior of the local clock <b>16</b> that requires correction. Therefore, the inordinately large time adjustments may be discarded.

0034<figref idref="DRAWINGS">FIG. 3</figref> shows a method for removing fluctuations from time offset adjustments to be applied to the local clock <b>16</b> according to the present teachings.

0035Initially, a value for epsilon is selected. The initial value for epsilon is an estimate of the expected time offset fluctuation for timing packets that are not delayed. The initial value for epsilon may the standard deviation of time offsets from the timing packets which have been used so far for time synchronization. For the first one or two timing packets this may be a very large value.

0036At step <b>120</b>, a time offset is determined in response to a timing packet. For example, a time offset may be determined using equation 1 above.

0037At step <b>122</b>, if the absolute value of the time offset from step <b>120</b> is algebraically larger than epsilon, then the timing packet is ignored and the time offset is discarded.

0038At step <b>124</b>, if the time offset from step <b>120</b> is within epsilon of 0, then the time offset is applied to the local clock <b>16</b>.

0039At step <b>126</b>, if the absolute value of the time offset from step <b>120</b> is algebraically smaller than epsilon, then any previously-computed running average is discarded and the time offset is applied to the local clock <b>16</b>.

0040The timing packets that are discarded may include information that is useful in time synchronization. The timing packets that are subject to queuing delay may be characterized by a collective distribution, e.g. a Poisson distribution, which may be time-varying depending on the traffic on the communication network <b>30</b>. The distribution may be modeled as a member of a family of distributions with a finite number (e.g. 1) of parameters. As a consequence, the network delay experienced by all of the timing packets including those discarded may be used to estimate the parameters and formulate a prediction of the time until the next usable timing packet in terms of network delay.

0041If the next timing packet that is not discarded is too far in the future, allowing for an imprecise parameter estimation, and an inexact prediction, an appropriate action may be taken. One example of an action is to change the value of i in the series of delay elements discussed above. The value of i may be changed back when statistics improve. Another example of an action is to temporarily request forward or reverse time synchronization measurements at an increased rate. Reverse measurements are performed by the device <b>12</b> having the local clock <b>16</b>. For forward measurements, the available actions depend on the clock synchronization protocol. In NTP, forward timing packets are always requested by the slave. In IEEE 1588 time synchronization, the slave may request an additional or an earlier reverse measurement.

0042Another example of an action is to use past statistics of accepted timing packets to extrapolate a time offset. This is a normal operation in IEEE 1588 time synchronization given that delay timing packets arrive less often than synchronization timing packets. This prediction can be used to choose an optimum value for epsilon. For example, the modeled distribution may state that there is 95% confidence that a timing packet with queuing delay less than epsilon will arrive within any 30 second interval. If the local clock can coast for 30 seconds with the desired accuracy, then epsilon is large enough. If the clock can only coast accurately for 10 seconds, then epsilon may be increased until the model predicts that, with 95% confidence, a usable packet will arrive within 10 seconds. Similarly, the model may be used to choose an epsilon such that there is a 99% probability that a usable packet will arrive within the desired interval.

0043The foregoing detailed description of the present invention is provided for the purposes of illustration and is not intended to be exhaustive or to limit the invention to the precise embodiment disclosed. Accordingly, the scope of the present invention is defined by the appended claims.