The One Man MMO Project
The story of a lone developer's quest to build an online world :: MMO programming, design, and industry commentary
Time Synchronization - One Step Forwards, One Step Back
By Robert Basler on 2011-01-25 16:11:52
Homepage: www.onemanmmo.com email:one at onemanmmo dot com

I've been trying to get my camera simulation working. Last week, I realized that the network was misbehaving resulting in multi-second packet round trips. A week of optimization work, and that issue is resolved. Now I looked at the camera motion system I worked out, and I remember that in order for the simulation to be somewhat rational, that all of the servers need to have synchronized clocks.

I was going to try to soldier on with my camera work leaving time for later, but the problem is that I've already figured out most of the time synchronization issues this morning, and if I go back to the camera work, I have to figure that out, then when I come back to the time, figure the time out again. So the efficient solution for a single developer is to do time synchronization first, and put off the gratification of seeing the camera work.

Sigh.

### Time Synchronization

Some initial research gave me RFC 1305 (Network Time Protocol version 3) which is pretty darn scary, SNTP (Simple Network Time Protocol RFC 2030) is quite a bit less scary, and frankly, I don't need all the features of the full NTP. All I really need is approximate millisecond accuracy between all the servers and clients in the simulation.

The main thing to figure out of course is what the client needs to do to adjust the clock in order to keep everybody in sync.

From RFC 2030:

Timestamp NameIDWhen Generated
Originate TimestampT1time request sent by client
Transmit TimestampT3time reply sent by server

The roundtrip delay d and local clock offset t are defined as

d = (T4 - T1) - (T2 - T3)

t = ((T2 - T1) + (T3 - T4)) / 2.

Cool, that's pretty simple. Just one other consideration, we never want time to go backwards. Other than that, when we get a time update, we adjust the time immediately. The clock stops for a couple milliseconds if needed. Generally once the time is synchronized it shouldn't drift too much.

The RFCs also indicate that those timestamps need to be as close to packet transmit/receive as possible. That multithreaded datagram code I added should give sub-millisecond packet delays, so we're good to go on that front.

The client needs to store the last Originate Timestamp so it knows when it has processed responses to make sure that responses are only processed once, and only processed in response to actual requests. Having a udp packet repeat would kind of screw up the clock.

### Server Considerations

To keep the latency for the time server down, I don't want time requests being handled by the proxy server which isolates the internal network from the public internet for the rest of the game. Since the time server will be on the public internet, it needs to be able to resist denial of service attacks, replay attacks and other nonsense. How are we going to make it not fall over if multiple clients are sending a zillion time requests to it.

I had originally considered using authentication, where the client would have to provide a cryptographic digest with the packet to authenticate they are who they say they are. We then have the problem of having the server verify those digests (which takes time) and distributing the keys to the clients.

Instead I think I'm going to take a different tack. The server will rate limit clients based on their IP. I can use a hash table to look up the IP's, so that is very fast. It uses a bit of memory, but that is not a huge deal today. It is cheaper for me to add RAM, than for a DOS attacker to add IP's.

Of course a DOS attack could still saturate the bandwidth to the server, so we also need a way to add servers at runtime and have clients switch time servers at runtime. Ok, we can do that easy.