Method for Determining a Master Clock in a Communication Network

Abstract

The disclosure relates to a method for determining a master clock in a communication network having a plurality of stations that are communicatively connected to each other and each have a clock, wherein the master clock is used for time synchronization of the clocks of the stations, comprising the steps: determining by means of a model of the communication network, a synchronization path measure for each station to every other station of the stations, which specifies a synchronization accuracy between two stations; determining for each station on the basis of the synchronization path measure in each case a synchronization metric, which specifies a synchronization accuracy for this station; and determining on the basis of the synchronization metrics of all the stations the station whose clock is meant to be used as the master clock.

Claims

1. A method for determining a master clock in a communication network having a plurality of stations that are communicatively connected to each other and each have a clock, wherein the master clock is used for time synchronization of the clocks of the plurality of stations, the method comprising: determining, using a model of the communication network, a respective synchronization path measure for each respective station of the plurality of stations to each other station of the plurality of stations, which specifies a synchronization accuracy between two stations of the plurality of stations; determining, for each respective station of the plurality of stations, based on the respective synchronization path measures, a respective synchronization metric that specifies a synchronization accuracy for the respective station; and determining, on the basis of the respective synchronization metrics of all of the plurality of stations, a station of the plurality of stations whose clock is to be used as the master clock.

2. The method according to claim 1, the determining the respective synchronization path measure for each respective station of the plurality of stations further comprising: determining, using the model of the communication network, for each respective station of the plurality of stations, a respective synchronization path weight of the respective station to each other station of the plurality of stations; and determining, using the model of the communication network, for each respective station of the plurality of stations, a respective synchronization path redundancy value for the respective station to each other station of the plurality of stations.

3. The method according to claim 2, wherein the respective synchronization path weight for the respective station to each other station of the plurality of stations comprises a sum of weights of each intermediary station and weights of each connection path between two adjacent stations on a respective synchronization path.

4. The method according to claim 3, wherein for each respective station of the plurality of stations, a clock model is used to represent a weight of the clock of the respective station, the clock model specifying at least one of a clock accuracy, a clock variance, and a clock priority.

5. The method according to claim 3, wherein for each respective connection path between two adjacent stations, a connection model is used to represent a weight of the respective connection path, the connection model specifying at least one of a transmission error rate, a transmission delay, and an availability.

6. The method according to claim 1, wherein the plurality of stations are communicatively connected to each other in at least one of a wired manner and a wireless manner.

7. The method according to claim 6, wherein weights of a connection path between two adjacent stations that are communicatively connected to each other in a wired manner are different from weights of a connection path between two adjacent stations that are communicatively connected to each other in a wireless manner.

8. A computer for determining a master clock in a communication network having a plurality of stations that are communicatively connected to each other and each have a clock, wherein the master clock is used for time synchronization of the clocks of the plurality of stations, the computer being configured to: determine, using a model of the communication network, a respective synchronization path measure for each respective station of the plurality of stations to each other station of the plurality of stations, which specifies a synchronization accuracy between two stations of the plurality of stations; determine, for each respective station of the plurality of stations, based on the respective synchronization path measures, a respective synchronization metric that specifies a synchronization accuracy for the respective station; and determine, on the basis of the respective synchronization metrics of all of the plurality of stations, a station of the plurality of stations whose clock is to be used as the master clock.

9. The method according to claim 1, wherein the method is carried out by a computer program executed by a computer.

10. The method according to claim 9, wherein the computer program is stored on a non-transitory machine-readable storage medium.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0032] The disclosure is shown schematically in the drawing using an exemplary embodiment, and is described in detail below with reference to the drawing.

[0033] FIG. 1 shows schematically a communication network having a plurality of stations, in which a method according to the disclosure can be implemented.

[0034] FIG. 2 shows schematically a procedure of a method according to the disclosure in a preferred embodiment.

DETAILED DESCRIPTION

[0035] FIG. 1 shows schematically a communication network 100 having a plurality of stations 110, 120, 130, 140 and 150, in which a method according to the disclosure can be implemented. Each of the stations has a clock 112, 122, 132, 142 and 152 respectively, and is communicatively connected to at least one other station via a communication connection 160 or 170. The communication connections 160 are wired communication connections such as Ethernet; the communication connections 170 are wireless communication connections such as WLAN or WiFi.

[0036] The stations may be, for example, devices or machines in an industrial environment, or computer units or control units thereof. For example, it is conceivable that the stations 130 and 150, which are linked only wirelessly, are mobile or movable stations, whereas the other stations may be stationary stations.

[0037] A computer unit 190 in the form of a PC is also shown, which can be used, for instance, to determine in the network or communication network 100 one of the stations whose clock is meant to be used as the master clock. This shall be explained below by way of example.

[0038] In this regard, FIG. 2 shows schematically as a flow diagram a procedure of a method according to the disclosure in a preferred embodiment.

[0039] A network model 200 is used here to represent the network, for instance the communication network 100 of FIG. 1. The network consists of a set V of nodes and a set E of edges. A node v ∈ V constitutes a station (e.g. one of the stations 110-150 from FIG. 1), which is assigned to a clock (e.g. one of the clocks 112-152 from FIG. 1). An edge e ∈ E constitutes a directional (direct) connection or communication connection between two nodes (e.g. the connection 160 between the stations 110 and 120 in FIG. 1).

[0040] For a given grandmaster candidate (GMC) vm ∈ V is hence obtained a synchronization hierarchy H.sub.m. This is a set of all the synchronization paths P.sub.m.fwdarw.s between v.sub.m and the remaining slave candidates (SCs) v.sub.s ∈ V/v.sub.m. In order to quantify the suitability of a given GMC v.sub.m, i.e. to specify a measure of its synchronization accuracy, all the synchronization paths P.sub.m.fwdarw.s that exist for the GMC are taken into account. The synchronization accuracy of a SC v.sub.s is influenced by the clocks of the intermediary stations and by the individual connections between v.sub.m and v.sub.s. Therefore a synchronization path, for example, is defined as a sorted list of tuples

[00001]$P_{m.fwdarw.s}=\left(<v_{m,}{e}_{m.fwdarw.1}>,<v1,e{1}_{.fwdarw.2}>,.Math.,<v_{i-1,}{e}_{i-1.fwdarw.s}>\right).$

[0041] A combined clock and connection model is defined in order to find a quantity or measure for the synchronization paths with regard to its implications for the synchronization accuracy. For example, it consists of a generic clock model 210 (see equation 1 below) and a generic connection model 220 (see equation 2 below):

[00002]$w_c\left(i\right)=f_c\left(.Math.\right)\text{where}{w}_c\left(i\right)\in \left[0,1\right]$

[00003]$w_l\left(i,j\right)=f_l\left(.Math.\right)\text{where}{w}_l\left(i,j\right)\in \left[0,1\right]$

[0042] The clock model 210 results in weights or weightings 212 for the clocks. These weights are combined, for instance, in order to define the weight 222 of a path segment (a direct connection between two stations), i.e. a tuple <v.sub.i-1, e.sub.i-1.fwdarw.i>. This then yields the generic combined clock/connection model:

[00004]$w_{cl}\left(i,j\right)=\lambda \cdot w_c\left(i\right)+\left(1-\lambda \right)\cdot w_l\left(i,j\right)\text{where}{\text{w}}_{cl}\left(i,j\right)\in \left[0,1\right]$

resulting in a combined clock/connection weight. The sum of the clock/connection weights then yields the path weight or synchronization path weight (230 in FIG. 2):

[00005]$w_{m.fwdarw.s}={\displaystyle \underset{i=m}{\overset{s-1}{.Math.}}{w}_{cl}\left(i,t+1\right)}$

[0043] Assuming that there may be a plurality of alternative paths P.sub.m.sup.alt.sub..fwdarw.s from v.sub.m to v.sub.s, it is of interest to evaluate the redundancy of these paths, resulting in a generic redundancy valuation, or a synchronization path redundancy value (240 in FIG. 2):

[00006]$r_m=f_r\left(P_m{{}^{\text{all}}}_{.fwdarw.s}\right)\text{where}{r}_m\in \left[0,1\right]$

[0044] In summary, using the given network model 200, it is possible to determine the weighting of the primary synchronization path w.sub.m.fwdarw.s from a given GMC v.sub.m to each remaining slave candidate v.sub.s, making it possible to find the weight of the resultant synchronization hierarchy, i.e. the totality of the primary synchronization paths. In addition, a redundancy value r.sub.m can be found for a given GMC v.sub.m, which makes it possible to take into account availability aspects of a specific GMC. Altogether, this allows a synchronization path measure 250 to be determined for every possible path for each station as the potential GMC.

[0045] In addition to the generic network model, examples of the clock and connection models (see equations (6) and (7) below) and a model for determining the redundancy shall be presented. For the clock model, a subset of the existing BMCA data set can be used, namely the clock accuracy (v.sub.i.acc), the clock variance (v.sub.i.var) and the clock priority (v.sub.i.prio). For example, the clock weight is normalized by the specified maximum values in accordance with the generic specification.

[00007]$f_c\left(.Math.\right)=\left(\frac{{\upsilon }_i,\text{acc}}{\text{max}\left({\text{υ}}_{\text{i}}\text{,acc}\right)}+\frac{{\upsilon }_i,\text{var}}{\text{max}\left({\upsilon }_i,\text{var}\right)}\right),\frac{{\upsilon }_i,\text{prio}}{\text{max}\left({\upsilon }_i,\text{pro}\right)}$

[0046] The connection model works similarly. It uses attributes that may influence the synchronization, namely the transmission or packet error rate (e.sub.i.fwdarw.j.err), the propagation delay or transmission delay (e.sub.i.fwdarw.j.delay) and the availability (e.sub.i.fwdarw.j.fail).

[00008]$f_l\left(.Math.\right)=\left(\frac{e_{i.fwdarw.j},\text{err}}{\text{max}\left(e_{i.fwdarw.j},\text{err}\right)}+\frac{e_{i.fwdarw.j},\text{delay}}{\text{max}\left(e_{i.fwdarw.j},\text{delay}\right)}\right).Math.e_{i.fwdarw.j},\text{fail}$

[0047] The model for determining the redundancy works, for instance, on the basis of an algorithm in which, for all possible paths from a potential grandmaster to another station, are selected the nodes or stations therebetween that are duplicates, i.e. appear in a plurality of paths. The redundancy valuation, or the synchronization path redundancy value, is then, for example, an average of duplicate nodes across all the paths from v.sub.m to v.sub.s. If, for instance, a node v.sub.i appears in all the paths from v.sub.m to v.sub.s, this is a single error point.

[0048] The proposed method also uses the provided network model 200, for example, to resolve the shortcomings of the traditional BMCA. The method can be used for the network design and for provisioning the network, because it is carried out offline. The proposed method evaluates each station or node in a given network as the GMC v.sub.m by finding its resultant synchronization hierarchy metric M.sub.m, or simply just synchronization metric (260 in FIG. 2). The synchronization hierarchy metric M.sub.m comprises the weights of the primary synchronization paths from GMC v.sub.m to each of the remaining SCs v.sub.s, and, if applicable, other information such as the redundancy valuation r.sub.m for the GMC v.sub.m. Once the synchronization hierarchy metric M.sub.m has been found for all (potential) GMCs, the metrics can be sorted. This allows the best GMC to be found, and, if applicable, suitable fallback solutions (i.e. the next-best GMCs), in a step 270.

[0049] The method is described generally by an algorithm, for example, which works as follows:

[0050] For a network having a set V of nodes and a set E of edges, the method finds the synchronization metrics M.sub.m or 260 for all possible GMCs. For a GMC v.sub.m ∈ V, the synchronization hierarchy metric is first reset to 0, for example.

[0051] Then for each resultant SCs vs ∈ V/vm, the method finds the shortest path P.sub.m.sup.short.sub..fwdarw.s, i.e. the path with the lowest costs, and finds the corresponding path weight w.sub.m.sup.short.sub..fwdarw.s, for instance using a dedicated routing algorithm according to Hart et al., as mentioned above. The routing algorithm uses the combined connection weight w.sub.cl(i,j) as the weight metric. Here P.sub.m.sup.short.sub..fwdarw.s is the primary synchronization path for synchronization of v.sub.s by v.sub.m. In addition, the method checks all possible paths P.sub.m.sup.all.sub..fwdarw.s from v.sub.m to v.sub.s.

[0052] Then the method uses P.sub.m.sup.all.sub..fwdarw.s to evaluate the redundancy r.sub.m.fwdarw.s between v.sub.m and v.sub.s in order to incorporate a robustness aspect for a synchronization hierarchy. The weighting of the primary synchronization path and the redundancy valuation are each stored in a dedicated vector, so for instance w.sub.m.sup.short and r.sub.m.

[0053] After checking all the SCs, the method uses the generic function f.sub.m to find the synchronization hierarchy metric Mm. It uses the weighting of the primary synchronization path and the redundancy valuation as the input parameters.

[0054] Then the GMC v.sub.m, together with the resultant synchronization hierarchy metric M.sub.m, are added as candidate metric tuples <v.sub.m, M.sub.m> to the solution set S. This process is repeated for every potential GMC v.sub.m, i.e. every node from V. After considering all possible scenarios for time-synchronization, the solution set S is sorted according to the synchronization hierarchy metric, for instance from best to worst value, so that the best GMCs and fallback candidates can be obtained.

[0055] In addition to the generic description of the procedure, equation (8) shows an example for determining the synchronization hierarchy metric M.sub.m. The given examples minimize the worst-case primary synchronization paths, i.e. the primary synchronization path having the greatest weight.

[00009]$f_m\left(.Math.\right)=\left(1-\left(\text{max}\left({\omega }_m^{\text{short}}\right)\cdot {\overline{r}}_m\right)\right)$

[0056] As mentioned, two approaches can be used to solve finding the port states. In one approach, starting from a given grandmaster GM v.sub.m, which can be determined by the method mentioned, the synchronization paths to each of the remaining stations SCs v.sub.s are determined using a dedicated routing algorithm, for instance the A* routing algorithm. It should be noted that the routing algorithm must use the same weight metric as the method that is used, in order to achieve an optimum synchronization hierarchy by setting the port state correctly. Another approach is to use the BMCA itself for configuring the port states. In this case, the GM priorities (“grandmasterPriority1”) of the BMCA data set are configured for each node according to the solution of the method used. For example, the best priority, i.e. 0, is assigned to the best GMC v.sub.i having M.sub.i = max(M.sub.m). Then the second-best priority, i.e. 1, is assigned to the second-best GMC v.sub.j, and so on. Then the BCMA can be used to decide the port states.