Small footprint clock synchronization without NTP

Question

I'm looking for a simple clock synchronization protocol that would be easy to implement with small footprint and that would work also in the absence of internet connection, so that it could be used e.g. within closed laboratory networks. To be clear, I'm not looking for something that can be used just to order events (like vector clocks), but something that would enable processes on different nodes to synchronize their actions based on local clocks. As far as I understand, this would require a solution that can take clock drift into account. Presence of TCP/IP or similar relatively low-latency stream connections can be assumed.

Answer 1

Not really a proper answer, but just a reminder to make sure that you understand exactly what the hardware clock sources are and any caveats about them - especially if you are planning to use some slightly exotic possibilities like the low-power CPU / RTOS combination you mention.

Even the x86 case has at least 2 or 3 clocks which could be in use, depending on the setup - all with different properties.

Answer 2

Might using http://www.ietf.org/rfc/rfc5905.txt be appropriate?

Even if it is much more than what you need, you could certainly implement a "compatible" client that works with an NTP server (even if you run your own NTP server), but where the client implementation is purposely naive?

Eg, if you don't care about small time adjustments, don't implement them. If you don't care about bidirectional synchronisation, don't implement that, etcetera.

(Be warned: Most of the functionality present in that RFC is there for a reason - Accurate time synchronisation has many pitfalls - including the fact that many OS's do not like it if the time suddenly changes)

Answer 3

ntp is the right tool for the job. You do not need an internet connection, and for an extra $105 and a few hours of your life, you can even be GPS synchronized for an absolute time reference without an internet connection, though that appears to not be important to you.

Ignoring the slight additional complexity of GPS synchronization, you can get synchronized to a chosen system's clock using a few configuration file lines (four lines on each client, five lines on the server). The ntpd binary is 505kB on my system. You can also use ntpdate which can be periodically run to adjust the system clock (zero lines of configuration on the client, other than the call to the ntpdate application with the right arguments). That binary is 80kb. There is a SNTP protocol which allows even smaller footprints for embedded appliations (talking to a normal ntp server). There is also an alternate NTP implementation called chrony.

There is also a program called rdate (typically only on older systems, though source is available) which works kinda like ntpdate but much less precisely. You also need an RFC 868 server, often provided in inetd.

The only other alternative is the Precision Time Protocol already mentioned.

Answer 4

Disclaimer: I'm not an NTP expert by any means. Just a hobbyist having fun on the weekend.

I realize you said you didn't want an NTP implementation, because of the perceived complexity and because an Internet NTP server may not be available in your environment.

However, an simplified NTP look-up may be easy to implement, and if you have a local NTP server you can achieve good synchronization.

Here's how:

Review RFC 5905

You'll see NTP v4 packets look something like:

• LI (2 bits)
• VN (3 bits) - Use '100' (4)
• Mode (3 bits)
• Stratum (8 bits)
• Poll (8 bits)
• Precision (8 bits)
• Root Delay (32 bits)
• Root Dispersion (32 bits)
• Reference Id (32 bits)
• Reference Timestamp (64 bits)
• Origin Timestamp (64 bits)
• Receive Timestamp (64 bits)
• Transmit Timestamp (64 bits)
• Extension Field 1 (variable)
• Extension Field 2 (variable)
• ...
• Key Identifier
• Digest (128 bits)

The digest is not required, so forming a valid client request is very easy. Following the guidance in the RFC, use LI = '00', VN = '100' (decimal 4), Mode = '011' (decimal 3).

Using C# to illustrate:

byte[] ntpData = new byte[48]
Array.Clear(ntpData, 0, ntpData.Length);
ntpData[0] = 0x23;  // LI = 00, VN = 100, Mode = 011

Open a socket to your target server and send it over.

int ntpPort = 123;
IPEndPoint target = new IPEndPoint(Dns.GetHostEntry(serverDnsName).AddressList[0], ntpPort);
Socket s = new Socket(AddressFamily.InterNetwork, SocketType.Dgram, ProtocolType.Udp);
s.Connect(target);
s.Send(ntpData);

In the response, the current time will be in the Transmit Timestamp (bytes [40 - 48]). Timestamps are 64-bit unsigned fixed-point numbers. The integer part is the first 32 bits, the fractional part is the last 32 bits. It represents the number of seconds since 0h on Jan-1-1900.

s.Receive(ntpData);
s.Close();

ulong intPart = 0;
ulong fractPart = 0;

for (int i = 0; i < 4; i++)
    intPart = (intPart << 8) | ntpData[40 + i];

for (int i = 4; i < 8; i++)
    fractPart = (fractPart << 8) | ntpData[40 + i];

To update the clock with (roughly) second granularity, use: # of seconds since 0h Jan-1-1900 = intPart + (fractPart / 2^32). (I say roughly because network latency isn't accounted for, and we're rounding down here)

ulong seconds = intPart + (fractPart / 4294967296);

TimeSpan ts = TimeSpan.FromTicks((long)seconds * TimeSpan.TicksPerSecond);

DateTime now = new DateTime(1900, 1, 1);
now = DateTime.SpecifyKind(now, DateTimeKind.Utc);
now += ts;

"now" is now a DateTime with the current time, in UTC.

While this might not answer your question, hopefully it makes NTP a little less opaque. =)

Answer 5

Might Precision Time Protocol fit the bill? It doesn't look real simple, but it seems to do more or less exactly what you are asking for. (There are some open source implementations referenced on the Wikipedia page.)

I think the problem is that this is an inherently tricky problem, so the solutions tend to be complex. NTP is trying to provide a correct absolute time, which definitely goes beyond what you need, but it does have the advantage of being well known and widely implemented.

Answer 6

I was able to implement a parred down version of the Precision Time Protocol very quickly and easily based solely on the wikipedia article. If all you are interested in is synchronizing them with each other as opposed to synchronizing them with the outside world, you should be able to get millisecond accuracy with minimal effort.

The fundamental basics of the protocol involve the following:

1. A master clock broadcasts a sync message with the timestamp of when he sent the message (T1).
2. The clients record the time at which they received the sync message as T1'.
3. The clients send a delay request back to the master and record the time they sent the message as T2.
4. The master responds to the delay request with the time he received the message. This time is T2'.
5. Client adjusts their clock by (T1' - T1 - T2' + T2)/2.

If you need better stability, you can implement a phase locked loop or a linear regression or something similar to better control your jitter and avoid large swings due to network lags. There are a number of more complicated features specified by the protocol, but if you want to implement them depends on how close 'good enough' is.