Method and system for time synchronization

• US 7,023,816 B2
• Filed: 12/13/2000
• Issued: 04/04/2006
• Est. Priority Date: 12/13/2000
• Status: Expired due to Fees

• Current Assignee: Rainbow Technologies, Inc. (Thales SA)
• Original Assignee: SafeNet Incorporated (Thales SA)
• Inventors: Couillard, Bruno
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Shew, John
• Application Number:
  US09/735,941
• Publication Number:
  US 20030123491A1
• Time in Patent Office: 1,938 Days
• Field of Search: 370/252, 370/255, 370/282, 370/324, 370/422, 370/463, 370/503, 370/507, 370/508, 370/509, 370/510, 370/512, 370/518, 370/519, 370/520, 375/222, 375/326, 375/346, 375/354, 375/356, 375/357, 375/358, 455/11.1, 455/502, 701/213
• US Class Current: 370/324
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0667 Bidirectional timestamps, e.g. NTP or PTP for compensation of clock drift and for compensation of propagation delays arrangements for monitoring round trip delays in packet switching networks H04L43/0864
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

A method for synchronizing a timing device of a client station via a communications network is disclosed. A plurality of packets is sent from a time server to the client station via the communications network. Upon receipt of the plurality of packets at the client station a time indicative of a local time of receipt of the plurality of packets is determined and the plurality of packets are returned to the time server via the communications network. Upon receipt of the plurality of packets at the time server data in dependence upon round trip delay of the packets and variance in packet spacing are determined and compared to threshold values. If the determined data are within the threshold values data indicative of a time correction are determined and sent from the time server to the client station.

Claims

1. A method of synchronizing a timing device of a client station comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time and having a predetermined temporal spacing from other packets, from a time server to the client station via a communications network having unknown transmission time variations;

b) receiving the plurality of packets at the client station;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the client station and storing time data in dependence thereon;

d) returning the plurality of packets to the time server via the communications network;

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the time server; and

,

f) determining synchronization data in dependence upon round trip delay of the packets and in dependence upon variance in temporal spacing of received packets relative to the predetermined temporal spacing, the synchronization data relating to an estimate of a minimum travel time of a packet between the time server and the client station via a communications network having unknown transmission time variations that are significant relative to the minimum travel time,

wherein each packet comprises a binary signal of m bits, the binary signal comprising an identifier of the packet and an identifier of the time server.

2. A method of synchronizing a timing device of a client station as defined in claim 1, wherein the identifier of the time server comprises at least a random number.

3. A method of synchronizing a timing device of a client station as defined in claim 1, comprising the step of:

attaching to at least one of the packets authentication data for identifying the client station, the data attached by the client station.

4. A method of synchronizing a timing device of a client station as defined in claim 3, comprising the steps of:

comparing upon receipt of the packets at the time server the authentication data identifying the client station with reference authentication data; and

,

if the comparison result is not indicative of a match, repeating steps a) to e).

5. A method of synchronizing a timing device of a client station as defined in claim 1, comprising the steps of:

comparing upon receipt of the packets at the time server the identifier of the time server with a reference identifier; and

,

if the comparison result is not indicative of a match, repeating steps a) to e).

6. A method of synchronizing a timing device of a client station as defined in claim 5, comprising the steps of:

g) comparing the synchronization data to threshold values;

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station, wherein step h) comprises the steps of;

determining a round trip delay value for each of the plurality of packets;

determining a minimum round trip delay value; and

,

calculating data indicative of a correct time by adding half of the minimum round trip delay value to the predetermined time the packet having the minimum round trip delay value has been sent by the server.

7. A method of synchronizing a timing device of a client station as defined in claim 1, comprising the step of:

time-stamping each of the packets at the client station by adding time data indicative of the client station'"'"'s timing device time at the time instance of receipt of each of the packets.

8. A method of synchronizing a timing device of a client station as defined in claim 7, comprising the steps of:

g) comparing the synchronization data to threshold values;

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station;

wherein step h) comprises the steps of;

determining a round trip delay value for the first packet of the plurality of packets;

determining for each packet following the first packet a first time difference between the first packet and the each packet at the time sent from the server;

determining for the each packet following the first packet a second time difference between the first packet and the each packet at the time received at the client station;

determining a third time difference by subtracting the second time difference from the first time difference for the each packets;

determining a maximum third time difference and a corresponding packet, the corresponding packet having a minimum travel time from the server to the client station;

determining the minimum travel time by subtracting the maximum third time difference from half of the round trip delay value of the first packet; and

,

calculating data indicative of a correct time by adding the minimum travel time to the predetermined time of the corresponding packet.

9. A method of synchronizing a timing device of a client station as defined in claim 7, comprising the steps of:

g) comparing the synchronization data to threshold values;

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station, wherein step h) comprises the steps of;

determining a round trip delay value for each of the plurality of packets;

determining a minimum round trip delay value;

determining for each packet a first time difference between the packet having the minimum round trip delay and the each packet at the time sent from the server, wherein time differences of packets sent before the packet having the minimum round trip delay are of negative value;

determining for the each packet a second time difference between the packet having the minimum round trip delay and the each packet at the time received at the client station, wherein time differences of packets received before the packet having the minimum round trip delay are of negative value;

determining a third time difference by subtracting the second time difference from the first time difference for the each packets;

determining a maximum third time difference and a corresponding packet, the corresponding packet having a minimum travel time from the server to the client station;

determining the minimum travel time by subtracting the maximum third time difference from half of the round trip delay value of the packet having the minimum round trip delay;

calculating data indicative of a correct time by adding the minimum travel time to the predetermined time of the corresponding packet.

10. A method of synchronizing a timing device of a client station as defined in claim 7, comprising the steps of:

g) comparing the synchronization data to threshold values,

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station, wherein step h) comprises the steps of;

determining a travel time for each of the plurality of packets from the time server to the client station, the travel time being the difference between the predetermined time the packet was sent from the server and the local time the packet was received at the client station, wherein the time of the client station is within known error bounds;

determining a minimum travel time from the travel times of the plurality of packets; and

,

calculating data indicative of a correct time by adding the minimum travel time to the predetermined time of the corresponding packet.

11. A method of synchronizing a timing device of a client station comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time and having a predetermined temporal spacing from other packets, from a time server to the client station via a communications network having unknown transmission time variations;

b) receiving the plurality of packets at the client station;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the client station and storing time data in dependence thereon;

d) returning the plurality of packets to the time server via the communications network;

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the time server;

f) determining synchronization data in dependence upon round trip delay of the packets and in dependence upon variance in temporal spacing of received packets relative to the predetermined temporal spacing, the synchronization data relating to an estimate of a minimum travel time of a packet between the time server and the client station via a communications network having unknown transmission time variations that are significant relative to the minimum travel time;

g) comparing the synchronization data to threshold values;

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station, wherein step i) comprises the step of;

signing securely at the time server the signal comprising the data indicative of a time correction.

12. A method of synchronizing a timing device of a client station as defined in claim 11, comprising the steps of:

receiving the signal comprising the data indicative of a correct time at the client station;

verifying the signature of the time server; and

,

if the signature is verified, synchronizing the timing device of the client station in dependence upon the received signal.

13. A method of synchronizing a timing device of a client station, comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time and having a predetermined temporal spacing from other packets, from a time server to the client station via a communications network having unknown transmission time variations;

b) receiving the plurality of packets at the client station;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the client station and storing time data in dependence thereon;

d) returning the plurality of packets to the time server via the communications network,

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the time server;

f) determining synchronization data in dependence upon round trip delay of the packets and in dependence upon variance in temporal spacing of received packets relative to the predetermined temporal spacing, the synchronization data relating to an estimate of a minimum travel time of a packet between the time server and the client station via a communications network having unknown transmission time variations that are significant relative to the minimum travel time; and

,

g) providing a warning signal if the round trip delays of the packets are not within a threshold value, the threshold value being determined using a statistical estimate of round trip delays of the communications network.

14. A method of synchronizing a timing device of a client station comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time and having a predetermined temporal spacing from other packets, from a time server to the client station via a communications network having unknown unknown transmission time variations;

b) receiving the plurality of packets at the client station;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the client station and storing time data in dependence thereon,

d) returning the plurality of packets to the time server via the communications network;

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the time server;

f) determining synchronization data in dependence upon round trip delay of the packets and in dependence upon variance in temporal spacing of received packets relative to the predetermined temporal spacing, the synchronization data relating to an estimate of a minimum travel time of a packet between the time server and the client station via a communications network having unknown transmission time variations that are significant relative to the minimum travel time

g) comparing the synchronization data to threshold values;

h) determining data indicative of a time correction if the determined data of step f) are within the threshold values; and

,

i) sending a signal comprising the data indicative of a time correction from the time server to the client station, wherein step h) comprises the steps of;

determining a round trip delay value for each of the plurality of packets;

determining a minimum round trip delay value by interpolating using at least two round trip delay values;

determining an interpolated predetermined time corresponding to the interpolated round trip delay value; and

,

calculating data indicative of a correct time by adding half of the interpolated minimum round trip delay value to the interpolated predetermined time.

15. A method of synchronizing a timing device coupled to a communications network comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time, from a first node to a second node via a communications network having unknown transmission time variations;

b) receiving the plurality of packets at the second node;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets and providing time data in dependence thereon;

d) returning the plurality of packets to the first node via the communications network;

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the first node; and

,

f) determining data in dependence upon round trip delay of the packets and variance in packet spacing and comparing the data to threshold values, the data relating to an estimate of a minimum travel time of a packet between the first node and the second node via a communications network having unknown transmission time variations that are significant relative to the minimum travel time,

g) determining data indicative of a time correction if the determined data of step f) are within the threshold values, wherein the provided time data is appended to a packet and is returned with the packet to the first node.

16. A method of synchronizing a timing device coupled to a communications network comprising the steps of:

a) sending a plurality of packets, each packet being sent at a predetermined time, from a first node to a second node via a communications network having unknown transmission time variations;

b) receiving the plurality of packets at the second node;

c) determining a time indicative of a local time of receipt of each packet of the plurality of packets and providing time data in dependence thereon;

d) returning the plurality of packets to the first node via the communications network;

e) determining a time indicative of a local time of receipt of each packet of the plurality of packets at the first node; and

,

f) determining data in dependence upon round trip delay of the packets and variance in packet spacing and comparing the data to threshold values, the data relating to an estimate of a minimum travel time of a packet between the first node and the second node via a communications network having unknown transmission time variations that are significant relative to the minimum travel time,

wherein in step (c) each of the packets is time stamped with a local time of the second node.

17. A system of synchronizing a timing device of a client station via a communications network comprising:

first processing means connected to the communications network and a time clock; and

, second processing means connected to the communications network and the tinning device,

wherein the first processing means comprise;

means for sending in real time a plurality of packets, each packet being sent at a predetermined time, via the communications network to second processing means;

means for receiving the plurality of packets from the second processing means in real time;

means for determining in real time a time indicative of a time of receipt of each of the plurality of packets;

means for determining data in dependence upon round trip delay of the packets and variance in packet temporal spacing and comparing the data to threshold values;

means for determining data indicative of a correct time in dependence upon time data from the time clock and the data in dependence upon round trip delay of the packets and variance in packet temporal spacing; and

,

means for sending a signal comprising the data indicative of a time correction to the second processing means via the communications network;

and,

wherein the second processing means comprise;

means for receiving a plurality of packets from the first processing means in real time;

means for determining in real time a time indicative of a time of receipt of each of the plurality of packets;

means for returning the plurality of packets in real time to the first processing means;

means for receiving a signal comprising the data indicative of a time correction from the first processing means;

means for synchronizing the timing device in dependence upon the data indicative of the time correction; and

,

means for time-stamping each of the packets in real time.

18. A system of synchronizing a timing device of a client station via a communications network as defined in claim 17, the first processing means comprising means for retrieving time data from each time stamped packet.

19. A system of synchronizing a timing device of a client station via a communications network comprising:

first processing means connected to the communications network and a time clock; and

, second processing means connected to the communications network and the timing device,

wherein the first processing means comprise;

means for sending in real time a plurality of packets, each packet being sent at a predetermined time, via the communications network to second processing means;

means for receiving the plurality of packets from the second processing means in real time;

means for determining in real time a time indicative of a time of receipt of each of the plurality of packets;

means for determining data in dependence upon round trip delay of the packets and variance in packet temporal spacing and comparing the data to threshold values;

means for determining data indicative of a correct time in dependence upon time data from the time clock and the data in dependence upon round trip delay of the packets and variance in packet temporal spacing; and

,

means for sending a signal comprising the data indicative of a time correction to the second processing means via the communications network;

and,

wherein the second processing means comprise;

means for receiving a plurality of packets from the first processing means in real time;

means for determining in real time a time indicative of a time of receipt of each of the plurality of packets;

means for returning the plurality of packets in real time to the first processing means;

means for receiving a signal comprising the data indicative of a time correction from the first processing means;

means for synchronizing the timing device in dependence upon the data indicative of the time correction; and

,

means for attaching in real time to at least one of the packets an authenticator identifying the client station.

20. A system of synchronizing a timing device of a client station via a communications network as defined in claim 19, the first processing means comprising means for identifying the client station by its authenticator.