How Does the Network Time Protocol Work?

Question

The Wikipedia entry doesn't give details and the RFC is way too dense. Does anyone around here know, in a very general way, how NTP works?

I'm looking for an overview that explains how Marzullo's algorithm (or a modification of it) is employed to translate a timestamp on a server into a timestamp on a client. Specifically what mechanism is used to produce accuracy which is, on average, within 10ms when that communication takes place over a network with highly variable latency which is frequently several times that.

Answer 1

The trick is that some packets are fast, and the fast packets give you tight constraints on the time.

Answer 2

1. The NTP client asks all of its NTP servers what time it is.
2. The different servers will give different answers, with different confidence levels because the requests will take different amounts of time to travel from the client to the server and back.
3. Marzullo's algorithm will find the smallest range of time values consistent with all of the answers provided.
4. You can be more confident of the accuracy of the answer from this algorithm than of that from any single time servers because the intersection of several sets will likely contain fewer elements than any individual set.
5. The more servers you query, the more constraints you'll have on the possible answer, and the more accurate your clock will be.

Answer 3

(This isn't Marzullo's algorithm. That's only used by the high-stratum servers to get really accurate time using several sources. This is how an ordinary client gets the time, using only one server)

First of all, NTP timestamps are stored as seconds since January 1, 1900. 32 bits for the number of seconds, and 32 bits for the fractions of a second.

The synchronization is tricky. The client stores the timestamp (say A) (all these values are in seconds) when it sends the request. The server sends a reply consisting of the "true" time when it received the packet (call that X) and the "true" time it will transmit the packet (Y). The client will receive that packet and log the time when it received it (B).

NTP assumes that the time spent on the network is the same for sending and receiving. Over enough intervals over sane networks, it should average out to be so. We know that the total transit time from sending the request to receiving the response was B-A seconds. We want to remove the time that the server spent processing the request (Y-X), leaving only the network traversal time, so that's B-A-(Y-X). Since we're assuming the network traversal time is symmetric, the amount of time it took the response to get from the server to the client is [B-A-(Y-X)]/2. So we know that the server sent its response at time Y, and it took us [B-A-(Y-X)]/2 seconds for that response to get to us.

So the true time when we received the response is Y+[B-A-(Y-X)]/2 seconds. And that's how NTP works.

Example (in whole seconds to make the math easy):

• Client sends request at "wrong" time 100. A=100.
• Server receives request at "true" time 150. X=150.
• The server is slow, so it doesn't send out the response until "true" time 160. Y=160.
• The client receives the request at "wrong" time 120. B=120.
• Client determines the time spend on the network is B-A-(Y-X)=120-100-(160-150)=10 seconds
• Client assumes the amount of time it took for the response to get from the server to the client is 10/2=5 seconds.
• Client adds that time to the "true" time when the server sent the response to estimate that it received the response at "true" time 165 seconds.
• Client now knows that it needs to add 45 seconds to its clock.

In a proper implementation, the client runs as a daemon, all the time. Over a long period of time with many samples, NTP can actually determine if the computer's clock is slow or fast, and automatically adjust it accordingly, allowing it to keep reasonably good time even if it is later disconnected from the network. Together with averaging the responses from the server, and application of more complicated thinking, you can get incredibly accurate times.

There's more, of course, to a proper implementation than that, but that's the gist of it.

Answer 4

IF you are using timestamps to decide ordering, specific times may not be nessisary. You could use lamport clocks instead, which are less of a pain than network syncronization. It can tell you what came "first", but not the exact difference in times. It doesn't care what the computer's clock actually says.