Let’s synchronize our watches: Determining Clock Skew with Christian’s Algorithm and the Reactive Framework

In every playground race, there’s always one child who sets off somewhere between “On your marks” and “Get set”, gaining an unfair advantage over the honest ones who wait for “Go!”. I faced a similar problem in the design of my Windows Phone 7 multi-player game, Simon Squared, though it was unsynchronized clocks and network latency that were to blame rather than cheats.

The multi-player mode in the game relies on puzzles being shown to all players at the same time, and players race to complete them. Since some puzzles can be solved in a matter of seconds, players who get to see them even slightly sooner than their competitors stand a good chance of getting to the solution first. So I needed a plan for avoiding the digital equivalent of playground squabbles.

Any such plan has to take into account network latency: an unpredictable amount of time can elapse between the server shouting “Go!”, and the phones hearing the message. So I got my server to send out a message announcing that it would shout “Go!” at time T, where T is 4 seconds on from the time on the server’s clock (and broadcast in UTC obviously). This gives even the most far-flung phone plenty of time to receive the message, check its own clock, and then start a count-down.

Bet you’ve spotted the flaw in that straight-away! What if the server’s clock and the phones’ clocks are out of sync?

An Overview of Christian’s Algorithm

That’s where Christian’s algorithm comes in. It gives us a simple method of broadcasting the time at the server to a client whilst allowing for network latency. It works like this:

1. Client sends a message to the server: “What’s the time?” [adding ‘Mr. Wolf’ is optional]. Crucially, it notes the time that it sent the message (call it T_sent)
2. Server responds as quick as it can, giving the time according to its own clock, T_server.
3. When Client gets the message, it notes the time of receipt (call it T_received). Then it does some maths: the round-trip time, RTT, is T_received – T_sent . So assuming that the server responded instantly, and that the network latency was the same in both directions, that means that the server actually sent the message RTT/2 seconds ago. Thus, at the instant Client receives the message, the time at the server is T_server + RTT/2. Then the Client can compare with its own clock and determine the difference – the clock skew.

Since network latency can vary with each request we can get an improved result by trying the whole exercise several times then cherry picking the result which had the shortest round trip time, since that minimises the error in our estimate of the network latency.

So what does that look like in code?

The Server Side – with WCF REST

Well first we need the server to be able to serve up the time:

[AspNetCompatibilityRequirements(RequirementsMode = AspNetCompatibilityRequirementsMode.Allowed)]
[ServiceContract]
public class TimeService
{
    [WebGet(UriTemplate = "/?timeAtClient={clientReportedTime}")]
    public TimeCheck GetTime(string clientReportedTime)
    {
        return new TimeCheck()
                   {
                       ClientReportedTime = DateTimeOffset.Parse(clientReportedTime, CultureInfo.InvariantCulture, DateTimeStyles.AssumeUniversal),
                       TimeAtServer = DateTimeOffset.UtcNow,
                   };
    }
}

This is making use of WCF 4’s REST capabilities. Notice the WebGet attribute on the method, with it’s UriTemplate. If I add the appropriate route  to my Global.ascx file,

routes.Add(new ServiceRoute("Time", new WebServiceHostFactory(), typeof(FeedbackService)));

that will ensure that HTTP GET requests like http://localhost/MyApp/Time/?timeAtClient=2011-03-17T20:19:30.2196972Z get routed to the CheckTime method with the appropriate part of the query string passed into the clientReportedTime parameter.

So that's the server side done.

RestSharp and Rx for Asynchronous Web Requests

Then the client needs to be able to call the server. I’ve been making use of the excellent RestSharp library here:

_restClient = new RestClient(ServerUrl);

...

private IObservable<TimeCheck> GetServerTime()
{
    var request = new RestRequest("Time?timeAtClient={timeNow}");
    request.AddUrlSegment("timeNow", DateTime.UtcNow.ToString("O"));

    return ExecuteRequest<TimeCheck>(request);
}

private IObservable<TResult> ExecuteRequest<TResult>(RestRequest restRequest) where TResult : new()
{
    var subject = new AsyncSubject<TResult>();

    _restClient.ExecuteAsync<TResult>(restRequest, response => HandleResponse(response, subject));

    return subject;
}

private void HandleResponse<T>(RestResponse<T> response, AsyncSubject<T> subject)
{
    subject.OnNext(response.Data);
    subject.OnCompleted();
}

This is where things start hotting up. The first part of GetServerTime is obvious enough: in lines 7-8 I’m constructing a RestRequest consisting of a url and the appropriate query string parameter. Then I Execute it. Now since we’re talking Windows Phone here, I can’t make synchronous web requests – the phone UI has to remain responsive. So I can’t wait and then return the response from the method.

Instead I return an IObservable, an interface you might not be familiar with. This creature is the brain-child of the clever folks on the Reactive Framework team. They like to call IObservable the mathematical dual of IEnumerable. And what they mean is this: IEnumerable is used when you want to pull elements one by one out of a collection. IObservable is used when you want elements to be pushed one by one to you. You can think of an IObservable as being a stream of events. And just like you can build queries on top of IEnumerable, using Where and Select, so you can build queries on top of IObservable.

Here I’m using an IObservable as the channel to push back the result of the Web request when it becomes available – you can see that happening in the HandleResponse method, which is the callback that RestRequest calls when it gets a response back from the web server.

Finally – the Algorithm

Finally we get to the implementation of the algorithm itself: and with the underpinnings in place, it turns out to be one big LINQ query:

public IObservable<TimeSpan> DetermineClockSkew()
{
    var timeOffset = (from tick in Observable.Interval(TimeSpan.FromMilliseconds(100)).Take(5)
                      from timeCheck in GetServerTime().Timestamp()
                      let estimatedOneWayLatency =
                          (timeCheck.Timestamp.UtcDateTime - timeCheck.Value.ClientReportedTime).
                              TotalMilliseconds/2
                      let estimatedTimeAtServer =
                          timeCheck.Value.TimeAtServer + TimeSpan.FromMilliseconds(estimatedOneWayLatency)
                      let predictedClockSkew = estimatedTimeAtServer - timeCheck.Timestamp
                      select new {predictedClockSkew, estimatedOneWayLatency})
        .MinBy(p => p.estimatedOneWayLatency)
        .Select(p => p.predictedClockSkew);

    return timeOffset;
}

Let's step through this line by line:

• Line 1: We start things off by generating a stream of 5 tick events, at 100 millisecond intervals – we’re going to ping the server 5 times, and use the result with the shortest round trip time
• Line 2: Each time we hear a tick we fire off a what’s-the-time request to the server using GetServerTime which we discussed above. The Timestamp() method will stamp each response that we get back from the server with the time at which we received it.
• Line 3: For each response we get back from the server we estimate the one-way latency from server to client by taking half of the round-trip time (when we send a request to the server we send our own time, and the server echoes this back in the ClientReportedTime property of the message)
• Line 4: Now that we have an estimate of how long the message took to get from the server, we can estimate the time at the server at this precise moment.
• Line 5: We can now figure out the difference between the clock on the phone and the server’s clock by comparing the time at which we received the server’s response with our estimate of the server’s time at that moment.
• Line 6: We stash our estimate of the latency, and the estimate of the clock skew into an anonymous type
• Line 7 - 8: We look over all 5 attempts at estimating the clock skew, and we take the one which had the smallest latency. Notice how MinBy returns an IObservable rather than an actual value as it might in good old Linq-to-Objects: it has to be this way, otherwise the whole method would block waiting for all the web requests to complete, rather defeating the our use of asynchronous calls elsewher.

So there you have it: thanks to Christian, the WCF REST framework and the Rx team, a neat and elegant way of determining clock skew between server and phone.

See it in Action

Remember, for a limited time only you can see this in action by downloading my game to your phone or Emulator (for free!) and playing with your friends. Full source code to the whole game is also available.

Finally, judging for the Windows Phone 7 app contest finishes on March 31st, so make sure you check out the entries, and be sure to tell Red Gate what you think of mine!

Developers: try out Simon Squared, my multi-player Windows Phone 7 game, for free

If usage is like oxygen for ideas, then my Windows Phone 7 game, Simon Squared, must be pretty blue in the face right now. It’s not on the Marketplace yet, you see. Sure, nearly 25 people have download the source code. But how many of them will have bothered to compile it? Well, as of now, I’m demolishing your excuses: here is the Xap file - so you developers out there with unlocked phones can deploy the game and try it out.

Remember, the game has a multi-phone multi-player mode: and I’ve pre-configured the Xap file to run against our Windows Azure hosted server. So challenge your office mates! It doesn’t matter where in the world they are.

Let me know what you think – but don’t do it here: write your comments on the Simon Squared competition entry page so Red Gate can see what you think.

A reminder: Deploying Xap files to your phone

Building a project in Visual Studio and having it deployed to your phone is straightforward enough. Deploying a Xap file by itself is not quite so obvious, so here’s a reminder of how it’s done:

1. Remember to fire up the Zune software
2. Browse to C:\Program Files (x86)\Microsoft SDKs\Windows Phone\v7.0\Tools\XAP Deployment – drop the (x86) if you’re not on Windows 64-bit
3. Load the XapDeploy tool, select Windows Phone 7 Device as the target, browse for the Xap file, then hit deploy.

Unpacking Simon Squared: My mini framework-independent animation library

Animation is the trick a computer uses to make math come alive. Our minds are wired to see movement. A video game where the characters and props jumped instantly between the positions where the math says they ought to be would be incomprehensible and unplayable. Which explains why I spent a good part of the few precious days I had building Simon Squared on developing a little animation framework.

I’m pretty pleased with the result. It’s by no means polished or complete, but it makes it very easy to implement one-off animations, and to schedule groups of animations together. Best of all, it’s not tied to the XNA framework – you could use it to implement animation in Windows Forms if you so desired!

Fluent Animations

Here’s one example:

_storyboard.Plan()
    .AfterDelay(TimeSpan.FromSeconds(0.5))
    .Begin(b => b.Animate(this, (Shape target, float value) => target.RotationY = value)
                 .From(RotationY)
                 .To(RotationY + MathHelper.Pi)
                 .In(TimeSpan.FromSeconds(MovementAnimationTime)));

This shows off several aspects of the framework.

First, the Storyboard class. This is responsible for keeping track of all the animations that are currently in flight, or scheduled for later on. In my Game’s Update method I call

_storyboard.AdvanceTimeTo(gameTime.TotalGameTime);

and that takes care of updating all the animations that are in progress. 

The Plan() method returns a StoryboardPlanner which is used to schedule animations using a fluent interface. No prizes for guessing what AfterDelay does: it leaves a gap of what ever duration you specify before starting subsequent animations. These animations are scheduled using the Begin method: you pass it a function which uses the AnimationFactory it supplies to fabricate animations to your exact specifications.

Most important of all is the Animate method. In the definition of the Animate is the secret sauce that makes this animation framework independent of whatever framework it is you’re trying to animate. It works like this:

1. you set up an animation, RotationY goes from Pi to Pi/2 in 2 seconds, for example;
2. the animation framework calculates values as the animation progresses;
3. every time it calculates a new value, it calls the lambda function that you’ve provided, so that you can update the appropriate object with the new value.

The first parameter I’m passing to Animate is the object that has the property I want to animation, RotationY. Then I pass in a lambda function that receives both the target object, and the value that should be assigned to the target property or field¹.

How the animations work

When it comes to the actual animations, I’ve abstracted the majority of the animation logic into a couple of base classes, which makes it very easy to add animations for different types.

Here are the critical parts of the Animation base class:

public abstract class Animation
{
    // snip

    public void UpdateForTime(TimeSpan currentElapsedTime)
    {
        var normalisedTime = GetNormalisedTimeInAnimation(currentElapsedTime);
        if (normalisedTime.HasValue)
        {
            SetValueForTime(normalisedTime.Value);
        }
    }

    protected abstract void SetValueForTime(double normalisedTime);

    protected double? GetNormalisedTimeInAnimation(TimeSpan currentElapsedTime)
    {
        var normalisedPosition = 0.0;

        var millisecondsAfterStart = currentElapsedTime.TotalMilliseconds - StartTime.TotalMilliseconds;
        if (millisecondsAfterStart < 0)
        {
            return null;
        } 
        else if (millisecondsAfterStart > Duration.TotalMilliseconds && RepeatMode == RepeatMode.None)
        {
            return 1;
        }
        else
        {
            var quotient = millisecondsAfterStart / Duration.TotalMilliseconds;
            var integerPart = Math.Floor(quotient);

            normalisedPosition = quotient - integerPart;

            if (AutoReverse && (integerPart % 2) == 1)
            {
                normalisedPosition = 1 - normalisedPosition;
            }
        }

        return normalisedPosition;
    }
}

Start at the top: UpdateForTime is called by the Storyboard on every frame, to inform the animation of the time, and to give it an opportunity to update its target.

The first thing Animation does then is to work out the normalised time – that is a value between 0 and 1 indicating the progress through the animation. If the clock says that we’re bang on the animation’s start time then we return 0; halfway through (however long the animation lasts), and the normalised time is 0.5; and a clock time of StartTime + Duration gets a normalised time of 1. All this is calculated by GetNormalisedTimeInAnimation. Notice from the code how it is also smart enough to handle animations that repeat over and over, and animations that cycle -  repeating, but reversing when they get to the end value.

Once the normalised value has been calculated it is passed to SetValueForTime which is an abstract method on the Animation base class.

Next level down in the hierarchy we have SetterInvokingAnimation: 

public abstract class SetterInvokingAnimation<TValue, TTarget> : Animation where TTarget : class 
{
    public TValue StartValue { get; set; }

    public TValue EndValue { get; set; }

    private WeakReference _target;
    private readonly Action<TTarget, TValue> _setter;

    public SetterInvokingAnimation(TTarget target, Action<TTarget, TValue> setter)
    {
        _setter = setter;
        _target = new WeakReference(target);
    }

    protected override void SetValueForTime(double normalisedTime)
    {
        var value = GetValueForNormalisedTime(normalisedTime);
        var target = _target.Target as TTarget;
        if (target != null)
        {
            _setter(target, value);
        }
    }

    protected abstract TValue GetValueForNormalisedTime(double normalisedTime);
}

This is the class that takes care of pushing calculated values to the target - though it doesn't actually calculate any values itself – it leaves that to derived classes, by way of the GetValueForNormalisedTime abstract method.

And here is one of those derived class, FloatAnimation. Since it is descended from some hard-working ancestors, there’s little it has to do – just a simple mathematical interpolation between the StartValue and EndValue of the animation:

public class FloatAnimation<TTarget> : SetterInvokingAnimation<float,TTarget> where TTarget : class 
{
    public FloatAnimation(TTarget target, Action<TTarget, float> propertySetter) : base(target, propertySetter)
    {
    }

    protected override float GetValueForNormalisedTime(double normalisedTime)
    {
        var delta = EndValue - StartValue;
        var value = StartValue + delta * normalisedTime;

        return (float)value;
    }
}

So there you have it: a whistle-stop tour of my mini-animation framework.

See it for yourself

You can see the full source code - in use - in my Simon Squared game up on Codeplex. And if you shout loud enough, I might pull it out of there and stick it in a NuGet for easy consumption in your own games.

Go check it out – and then make sure you tell Red Gate how much you love it, over on my Simon Squared competition entry page!

---

1. I could have defined Animate like this:

   Animate(value => this.RotationY = value);

   which would have looked a lot neater. But that has the downside of capturing a reference to my target object in a closure and smuggling it down into the animations which are held by the Storyboard; and since my Storyboard is longer-lived than many of the objects that I’m animating, this would have had the effect of keeping my target objects alive when they would otherwise have been Garbage Collection. So I pass in the target object separately so that I can hold it using a WeakReference, and then I use a lambda function that is, in effect, a static method.

   Another way, of course, would be to remove animations from the Storyboard explicitly (and it does support that). But I'm lazy, and it's much easier to use this fire-and-forget approach!

Want to see inside a Windows Phone 7 game? I’ve opened-sourced Simon Squared

The deed is done: I’ve thrown my hat into the ring. Simon Squared is now officially standing for election as the App developers will love most. Go and vote for it here.

Why does it deserve your vote? Because, not only is it a thoroughly addictive little puzzle game, with a multi-phone-multi-player mode that will have you coming back for more, but I’ve just released the source code! It’s all there on CodePlex, released under the GPL v2 license. Build it, try it out, and let me know what you think.

Over the next little while I’m intending to publish some posts highlighting the points of interest in the source code. In the meantime:

• Take a look at my mini animation framework, under Flatlings/Flatlings/Animation – I’m quite fond of that fluent interface
• See how I implemented Christian’s algorithm using the Reactive Framework: Flatlings/Flatlings/GameServerClient.cs – DetermineClockSkew()
• Discover how easy it is to fix the WCF HTTP CTP so that it uses the DataContractSerializer: FlatlingsServer/Infrastructure/ DataContractXmlProcessor.cs

If you visit my blog, you’ll find a new page dedicated to Simon Squared. I’ll be updating that as I blog about the source code; and I’ve also indexed all the posts I made during development – bookmark it, because I’m sure you’ll want to go back and re-live those hectic days!

It only remains for me to thank everyone who has spurred me on over the last few months with comments, tweets and links, and to remind you all to go and exercise your democratic right.