Clock synchronization system and method using a continuous conversion function for a communication network

• US 6,157,957 A
• Filed: 08/13/1998
• Issued: 12/05/2000
• Est. Priority Date: 01/22/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Berthaud, Jean-Marc
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): TRIM, NKOSI N
• Application Number:
  US09/133,396
• Time in Patent Office: 845 Days
• Field of Search: 709/248, 713/400, 713/401, 713/600, 713/601
• US Class Current: 709/248
• 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

Abstract

A clock synchronization system and method in a communication network comprise a plurality of nodes in communication with each other by data transfer over communication links. Each of the nodes has its own local time base and exchanges timing information with a predefined node called master whose time base is the master clock against which said local time base is to be synchronized. At predefined moments in time, each node having a master exchanges timing information with the master node, calculates therefrom a timing data and stores said timing data into a predefined storage location called History; such as to obtain after at least two exchanges, a sequence of timing data stored in the History. From said sequence of timing data, a set of parameters is calculated and stored. The stored parameters are further used for computing a conversion function whereby the node local time is converted upon request into the master time base with a pre-specified and guaranteed precision.

Claims

1. In a communication network comprising a plurality of nodes in communication with each other by data transfer over communication links, with each of the nodes having its own local time base and exchanging timing information with a predefined master node having a master time base which serves as a master clock against which said local time base is to be synchronized, a clock synchronization method for converting the node local time into the master time base, comprising the steps of:

assigning a master at each node;

at predefined moments in time, exchanging timing information with the master node;

calculating therefrom a timing data and storing said timing data into a predefined storage location called History, such as to obtain after at least two exchanges a sequence k of timing data stored in the History;

calculating and storing a set of parameters from said sequence of stored timing data;

computing a conversion function using said calculated parameters whereby local time is converted upon request into the master time base with a pre-specified and guaranteed precision η

.

2. The method of claim 1 wherein:

said conversion function is defined by the following relation;

space="preserve" listing-type="equation">T.sub.M =(1+σ

)·

T.sub.S +δ

where;

T_S is a local time value to be converted, T_M is the master time value obtained, and σ

, δ

are computed constants; and

said pre-specified and guaranteed precision η

is determined by the provision of a maximum value max(T_M) and a minimum value min(T_M) associated with the master time value T_M obtained by conversion such that;

η

=max(T_M)-min(T_M).

3. The method of claim 1 wherein each of said timing data k comprises a local time value t_S (k) an estimation of the corresponding master time value t_M (k), and an error Δ

(k) which applies to said estimated master time value.

4. The method of claim 1 wherein the step of calculating said parameters further comprises the steps of:

computing a software representation of two sets of points S_U and S_L of timing data in the History and defined as follows;

space="preserve" listing-type="equation">S.sub.U ={points P.sub.k of coordinates (t.sub.S (k), t.sub.M (k)+Δ

(k)), ∀

k}

space="preserve" listing-type="equation">S.sub.L ={points Q.sub.k of coordinates (t.sub.S (k), t.sub.M (k)-Δ

(k)), ∀

k}

where k designates any timing data stored in the History;

computing a software representation of an inferior convex closure or C_U of S_U, and of a superior convex closure or C_L of S_L ; and

computing a software representation of lines D_max and D_min defined as being lines of respectively maximum and minimum gradient joining closures C_U and C_L without crossing them, thereby obtaining a position of the conversion function in terms of gradient of the extreme lines between which a conversion line D representing said conversion function lies.

5. The method of claim 4 wherein said lines D_max and D_min, D are defined by the following equations:

space="preserve" listing-type="equation">D.sub.max ;

t.sub.M =(1+σ

.sub.max)·

t.sub.S +δ

.sub.max

space="preserve" listing-type="equation">D.sub.min ;

t.sub.M =(1+σ

.sub.min)·

t.sub.S +δ

.sub.min

where t_S, t_M, represent respectively a local time value and a master time value, and σ

_min, σ

_max, δ

_min, δ

_max are computed constants.

6. The method of claim 5 wherein said computed constants σ

, δ

in the relation defining said conversion function are determined by;

space="preserve" listing-type="equation">σ

=1/2·

(σ

.sub.max +σ

.sub.min)

and

space="preserve" listing-type="equation">δ

=1/2·

(δ

.sub.max +δ

.sub.min).

7. The method of claim 1 further comprising the steps of:

each node of the network using its own conversion function for converting a received time stamp information and transmitting the converted time stamp information with an associated precision to its master node, so as to achieve a propagation of the time stamp information over the network towards a destination node, whereby when reaching the destination node, said time stamp information is already converted into the destination node time base.

8. The method of claim 1 wherein said predefined moments in time at which timing information is exchanged with the master node, are predefined such as to guarantee a pre-specified precision η

.

9. A communication network node comprising:

means for exchanging a sequence of timing information with a master node having a master time base;

means for calculating timing data for the node;

the master node and uncertainty information from the timing information;

means for storing the calculated timing data in a History;

means for calculating and storing a set of parameters for local--master time conversion from the calculated timing data; and

means for converting the node local time into the master time base with a pre-specified and guaranteed precision using the set of stored parameters.

10. In a communication network, a clock synchronization system using a continuous conversion function for synchronizing local clocks of nodes in the network, comprising:

means for communication among the nodes by data transfer over communication links, with each of the nodes having its own local time base;

means for exchanging timing information of a node with a predefined master node having a master time base which serves as a master clock against which said local time base is to be synchronized;

means for calculating timing data from the timing information and a set of parameters for local--master time conversion from the calculated timing data; and

means for computing a conversion function and using the parameters whereby local time is converted into the master time base η

.

11. The clock synchronization of claim 10 wherein each node of the network using its own conversion function for converting a received time stamp information and transmits converted time stamp information with an associated precision to its master node, so as to achieve a propagation of the time stamp information over the network towards a destination node, whereby when reaching the destination node, said time stamp information is already converted into the destination node time base.

12. The clock synchronization system of claim 11 further comprising:

means for storing a sequence of the calculated timing data in a History.

13. The clock synchronization system of claim 12 further comprising:

means for computing the conversion function to have a pre-specified and guaranteed precision.

14. The clock synchronization system of claim 13 further comprising:

means at each node for computing a conversion function for converting the local time base into a master time base of a master node.

15. The clock synchronization system of claim 14 wherein the sequence of timing data k comprises a local time value t_S (k), an estimation of the corresponding master time value t_S (k), and an error Δ

(k) which applies to said estimated master time value.