Tutorial 2: Physical clocks

Question 1

A client attempts to synchronize its clock with a time server using Christian’s algorithm. Therefore, the client records the

round-trip times of requests and the timestamps returned by the server as depicted in Table 1.1:

(a) Which of these times should the client use to adjust its clock?
(b) To what time should the client set its clock?
(d) If it is known that the time between sending and receiving a message in the system is at least 8 ms, do your answers to the above questions change?
(e) Discuss if we can synchronize the client’s clock with the time server to within 0 milliseconds, (i.e., fully accurately).

Answer 1

1. Solution: The one with the minimal RTT, which is 10 : 54 : 28.
2. Solution: The client should set it’s clock to: t_C =t_S+RTT/2 = t_C =10:54:28:000+20ms/2=10:54:28:010.
3. Solution: The accuracy is calculated by: acc = ± RTT/2 − min. As we have no information about min, we consider min = 0ms. ⇒ acc = ±20ms/2−0 = ±10ms.
4. Solution: acc = ± 20/2 ms − 8ms = ±2ms.
5. Solution: It is impossible to do that. Fully accurate synchronization with physical clocks is impossible.

Question 2

A collection of five processes (P1 - P5) want to synchronize their clocks according to the Berkeley algorithm. Process P3 has been elected as the master. The threshold value for acceptable deviation δ = ±3000ms. For the given round of the algorithm, the times of all individual processes have been collected by the Master (cf. Table 2.2). (Hint: Different to the original Berkeley algorithm, the master did not record any RTTs in this setting. So for this task, you can omit the calculation of a better estimate for the individual process times and instead work with the times given in the table.)

(a) What is the main difference between the Berkeley algorithm compared to Christians algorithm?
(b) What time will the master process P3 calculate as the reference time for synchronization.
(c) What information, i.e., which values will P3 send to the other processes for synchronization? What is the content of the message?
(d) Give an advantage and a disadvantage for sending, in particular, those kind of values that have been calculated in subtask (c) to synchronize the clocks.

Answer 2

1. Solution: The Berkeley algorithm performs an internal synchronization, while Christian’s algorithm performs exter- nal synchronization. Hence, the Berkeley algorithm does not require a dedicated time server.
2. Solution: Process P3 calculates the mean value of the process times that have been reported by P2, P3, P4, and P5. It will not consider the time reported by P1 because its value deviates from P3’s own time by more than δ. The new referencetimetref is consequently calculated by:
   t_ref = (08:44:52:874 + 08:44:53:123 + 08:44:53:100 + 08:44:50:996)/4 =08:44:52:523
3. Solution: The master process P3 estimates the clocks of all processes and only send the amount of time (positive or negative) that the individual processes must adjust their clocks for. Hence, the message content is comprised of the skew between the newly calculated reference clock and the clocks of the individual processes. (see picture)
4. Solution:

Advantage: There is less additional error introduced by another transmission delay between the master the slaves. Disadvantage: The skew value (update value) has to be calculated for every process in the set individually, which might influence scalability.

Question 3

The Network Time Protocol (NTP) defines the architecture for a time service and a communication protocol to trans- fer timing information between individual nodes over the internet. Time servers in NTP form a hierarchy of so called “stratum” servers as depicted in Figure 3.1.

1. What are the four main features and design goals of NTP?
2. Name the three different synchronization modes NTP supports. For each mode assess its accuracy compared to the other modes? In addition, provide a suitable usage scenario for each mode.
3. Two NTP servers (A and B) are trying to synchronize as shown in Figure 3.2. Based on the timestamps associated with messages m and m′ try to estimate the offset θ between B and A and calculate the accuracy of this estimation.

Answer 3

1. • It provides a service for clients to synchronize with UTC over the internet.
2. see picture
3. Let θ be the actual offset between B’s clock relative to A’s clock. Let t and t′ be the actual transmission times for m and m′, respectively. Then,
   T_i−2 = T_i−3 + t + θ
   T_i =T_i−1+t′−θ
   results in total delay ,
   δi = t +t′ = T_i−2 −T_i−3 +T_i −T_i−1 and offset,
   θ_i = (T_i−2 −T_i−3 +T_i−1 −T_i)/2
   For the sample scenario this means the offset θi for the synchronization round (i.e., the pair of messages m and m′) is θi = 10.0125 ≈ 10.013s,
   The delay δi is δi = 0.075.

Becauseδi =t+t′ andt, t′ ≥0 it is possible to show that θi − δi ≤θ≤θi+δi. The estimated offset θ is therefore within the range:
θ_i−(δ_i/2) ≤ θ ≤ θ_i + δ_i/2
9.976 ≤ θ ≤ 10.051