ISO/IEC 10164-20:1999 情報技術—オープンシステム相互接続—システム管理：時間管理機能—パート20： | ページ 9

H.3 Probabilistic clock synchronization

The Probabilistic Clock Synchronization (PCS) approach to achieving time synchronization between two processes addresses:

- an assumption about the PCS algorithm;

• a technique on how to read a remote clock with a specified accuracy;
• a method on how to keep clocks synchronized;
• a method on how to adjust a software clock.

PCS does not address:

• a synchronization model;
• the achievement of fault tolerance;
• the solicitation of timestamps;
• a service interface.

All the equations quoted in this contribution can be found in [2] and [3],

H.3.1 Assumption

In distributed systems, process to process communication is affected by an unpredictable random real-time delay. This makes the task of synchronization difficult. From the study on message delay for process communication in distributed systems [2], the distribution of the message delay has a shape resembling that illustrated in Figure H.6. The distribution has a maximum density at a mode point between the minimum delay (rmin) and the median delay, usually close to rmin, with a long thin tail to the right. The rmin value can be computed by counting the time needed to prepare, transmit and receive an empty message in the absence of transmission errors and system load. This rmin value contributes to the algorithm of Probabilistic Clock Synchronization (PCS).

The synchronization algorithm is based on the following assumptions:

• clocks have a much finer resolution than the time intervals;
• min is half of the minimum round-trip message delay rmin;
• p is the maximum drift rate;
• a local clock implemented by software is adjustable.

When referencing a time of a process, a notation of CTx, where CT is the time value of the clock at process x, is used. For an estimated time of another process, CTx(y) is used to denote the time value of process y estimated at process x. For instance, a time value of a clock at process S is denoted as CTs, whereas a time value of process S estimated by C is CTc(s).

H.3.2 Reading a remote clock

Assuming two processes, S and C, C sends a request message for a time from S. When S receives the request, it replies with a time message which is timestamped with its clock's time. If process C does not receive any response within a predefined waiting period, the attempt at reading the clock S fails. The time at S, when C receives the replies message from process S, can be calibrated as:

CTs + min * (1 - p)

and

CTs + 2 * De * (1 + 2 * p) - min * (1 + p)

or it can be expressed as an interval of:

CTs + min * (1 - p) = CTc(s) = CTs + 2 * De * (1 + 2 * p) - min * (1 - p)

Figure H.7 illustrates the reading clock path.

Also, it can be shown that the estimated clock value at S by CCTc(s) is:

@CTc(s) = CTs + Dc * (1 + 2 * p) - m?n * p

and the maximum error of the estimated value (or inaccuracy) is:

e = Dc * (1 + 2 * p) - min

In practice, the value Dc can be obtained by process C taking the time when it sends out the request message and the instance when it receives the replies message. The maximum drift rate is normally given by the clock manufacturer.

H.3.3 Reading a remote clock with a specified precision

For a process C to achieve a certain accuracy (i.e. the maximum reading error), say 'e', process C must discard any reading attempts for which the measured actual round-trip delay 2 * Dc' is greater than the specified maximum round-trip delay '2 * Uc'. 'Uc' can be calculated based on the following equation:

Uc = (1 - 2 * p) * (e + min)

When process C observes a successful round-trip, the process C is said to reach rapport with process S.

For completion of precision measurement, one has to consider the waiting period W' and maximum attempt k' retry. The former is to ensure that both processes stay correct, and any transient network traffic bursts do not affect their communication. It is evident that the higher the accuracy (i.e. the lower the value of 's), the closer the acceptable maximum round-trip 2 * Uc' is to reaching the *2 * min' value. A higher probability of reaching rapport between processes can be achieved by attempting to read more messages. On the other hand, if the maximum round-trip delay 2 * Uc'is chosen to be closer to the maximum message delay, the algorithm becomes deterministic. This also results in lower accuracy and few attempts at sending messages.

Hence as *2 * U' is chosen closer to the 'rmin' as illustrated in Figure H.7, one can achieve higher precision on the clock reading, but it would also result in higher frequency of failure in reaching rapport. This may be accomplished by taking more k' attempts to reach rapport. As U tends to max, one would result in less accuracy and relatively fewer k' retry attempts in order to reach rapport. The average number of messages 'n'required for achieving rapport can be shown as a function of probability of not achieving precision 'p', that is:

n = 2/ (l-p)

H.3.4 Keeping clocks synchronized

In order to keep a clock at C synchronized with S, C attempts periodically to reach rapport with S. Each attempt at rapport consists of at most k' attempts, where readings are separated by W' clock units. Intuitively, w > 2 * U. In the case where 'k' attempts have failed, S and C cannot be synchronized with the specific accuracy.

The maximum real-time delay, 'DNA', between a rapport and the next attempt at rapport can be expressed as:

DNA = ((1 - p)/ p) * (sc - y) - k * W

where 'sc' is the deviation between S and C. It is also shown that 'sc' should be:

sc > Uc - min + p*k*(l + p)*W

H.3.5 Clock adjustment

Given a local clock at process C with adjustable speed implemented in software, the value of clock at C can be represented as the sum of the local hardware clock H at C and a periodically computed adjustment function A; therefore:

C(t) = H(t) + A(t)

and

A(t) = m * H(t) + N

To avoid local clock discontinuities (i.e. jumps), 'A(t)'must be a continuous function of time, and for simplicity, A is a linear adjustment function. The value of'm' and 'N' can be obtained as follows:

m = (CTc(s) -CTc)/ a

and

N =CTc- (1 + m) * H

'a' is a clock with a positive error which is defined as the time units following rapport for which a process C synchronized with S. After the adjustment period which corrects for 'a' has elapsed at C, the clock timeCTcbecomes:

CTc(at rapport) =CTc(s) + a

Process C can be allowed to run again at the speed of local hardware clock until the next rapport by setting:

m = 0

and

N = local time of C at the end of the time adjustment period-hardware clock at the end of the same period

Notice that m and N are changed at the beginning and the end of each time adjustment period.

H.3.6 Conclusion

The Probabilistic Clock Synchronization (PCS) algorithm gives a controllable accuracy when reading a remote clock value. However, it does not guarantee that a processor can always read a remote clock with a specified accuracy. A process can read the clock of another process with a given accuracy with a probability as close to one as desired, by retrying a sufficient number of times while reaching rapport. When a rapport is achieved, a process knows the actual reading accuracy obtained. The algorithm also shows how to adjust a clock continuously within the time adjustment period and how to calculate the time for next rapport.