5.2 Physical Clock

Physical clock
synchronization
Cristian’s algorithm
Compensate for delays
– Note times:
• request sent: T0
• reply received: T1
– Assume network delays are symmetric

Tserver
server
request reply
client
T0 T1 time
Client sets time to:
Tserver
server
request reply
client
T0 T1 time
= estimated overhead
in each direction
Cristian’s algorithm: example
• Send request at 5:08:15.100 (T0)
• Receive response at 5:08:15.900 (T1)
– Response contains 5:09:25.300 (Tserver)
• Elapsed time is T1 -T0

5:08:15.900 - 5:08:15.100 = 800 msec
• Best guess: timestamp was generated
400 msec ago
• Set time to Tserver+ elapsed time
5:09:25.300 + 400 = 5:09.25.700
Berkeley Algorithm
Berkeley Algorithm
Berkeley Algorithm
• Gusella & Zatti, 1989

• Assumes no machine has an accurate time
source
• Obtains average from participating
computers
• Synchronizes all clocks to average
• Machines run time dæmon
– Process that implements protocol
• One machine is elected (or designated) as the
server (master)
– Others are slaves
Berkeley Algorithm
• Master polls each machine periodically

– Ask each machine for time
• Can use Cristian’s algorithm to compensate for network
latency
• When results are in, compute average
– Including master’s time
• Hope: average cancels out individual clock’s
tendencies to run fast or slow
• Send offset by which each clock needs
adjustment to each slave
– Avoids problems with network delays if we send a
time stamp
Berkeley Algorithm
Algorithm has provisions for ignoring readings

from clocks whose skew is too great
– Compute a fault-tolerant average
If master fails
– Any slave can take over
Berkeley Algorithm: example
3:00
9:
25 10
3: 2:50
3:25 2:50 9:10
1. Request timestamps from all slaves

3:00
9:
25 10
3: 2:50
3:25 2:50 9:10
2. Compute fault-tolerant average:

+0.15
3:00
-6
:20 :0
5
-0 +0:15
3:25 2:50 9:10
3. Send offset to each client

Network Time Protocol, NTP
Network Time Protocol, NTP
NTP: The Network Time Protocol
• To provide a service enabling clients across the internet to be synchronized
accurately to UTC
– NTP employs statistical techniques for filtering of timing data and it
discriminates between the quality of timing data from different servers.
• To provide a reliable service that can survive lengthy losses of connectivity:
– There are redundant servers and redundant paths between servers; server
can reconfigure in case of failures.
• To enable clients to re-synchronize frequently to offset the rates of drift
found in most computers; this service will scale to large number of clients and
servers
• To provide protection against interference with the time service whether
accidental or malicious
• Hierarchical structure for the time servers: primary and secondary at different
strata.
• NTP servers synchronize with each other in one of three modes: multicast,
procedure-call, symmetric-mode in the order of accuracy
• All messages use UDP and so deliver unreliably
NTP Goals
• Enable clients across Internet to be accurately

synchronized to UTC despite message delays
– Use statistical techniques to filter data and gauge quality of
results
• Provide reliable service
– Survive lengthy losses of connectivity
– Redundant paths
– Redundant servers
• Enable clients to synchronize frequently
– offset effects of clock drift
• Provide protection against interference
– Authenticate source of data
NTP servers
Arranged in strata
– 1st stratum: machines 1
connected directly to 2
accurate time
source 3
– 2nd stratum: machines 4
synchronized from
1st stratum machines
– …
SYNCHRONIZATION SUBNET
NTP Synchronization Modes
Multicast mode
– for high speed LANS
– Lower accuracy but efficient
Procedure call mode
– Similar to Cristian’s algorithm
Symmetric mode
– Intended for master servers
– Pair of servers exchange messages and retain data
to improve synchronization over time
All messages delivered unreliably with UDP

NTP message structure
• T1: originate timestamp

– Time request departed client (client’s time)
• T2: receive timestamp
– Time request arrived at server (server’s time)
• T3: transmit timestamp
– Time request left server (server’s time)
T4 :
SNTP
Simple Network Time Protocol

– Based on Unicast mode of NTP
– Subset of NTP, not new protocol
– Operates in multicast or procedure call mode
– Recommended for environments where server is
root node and client is leaf of synchronization
subnet
– Root delay, root dispersion, reference timestamp
ignored
RFC 2030, October 1996

SNTP
T2 T3
server
request reply
client
T1 T4 time
Roundtrip delay: Time offset:
d = (T4-T1) - (T2-T3)
SNTP example
T2=800 T3=850
server
request reply
client time
T1=1100
T4=1200
=((-300)
Offset = + (-350))/2 Time offset:
= -650/2
((800 = -325
- 1100) + (850 - 1200))/2
Set time to T4 + t
= 1200 - 325 = 875
T2=800 T3=850
server
request reply
Ts=825 time
client
T1 =1100 T4=1200
Offset = (1200 - 1100)/2 = 50
Set time to Ts + offset

= 825 + 50 = 875

5.2 Physical Clock

Uploaded by

Copyright:

Available Formats

5.2 Physical Clock

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

5.2 Physical Clock

Uploaded by

Copyright:

Available Formats

Physical clock

– Assume network delays are symmetric

– Response contains 5:09:25.300 (Tserver)

• Elapsed time is T1 -T0

• Gusella & Zatti, 1989

• Master polls each machine periodically

Algorithm has provisions for ignoring readings

3:25 2:50 9:10

1. Request timestamps from all slaves

3:25 2:50 9:10

2. Compute fault-tolerant average:

3:25 2:50 9:10

3. Send offset to each client

• Enable clients across Internet to be accurately

All messages delivered unreliably with UDP

• T1: originate timestamp

Simple Network Time Protocol

RFC 2030, October 1996

Roundtrip delay: Time offset:

Offset = (1200 - 1100)/2 = 50

Set time to Ts + offset

You might also like