Clock Synchronization

[tanneberger]

Protocol

Initialization

Reactors are annotated by users as time-synchronization anchors. They are assumed to be federates that have more precise physical clocks and run an NTP or PTP daemon that synchronizes their time.

1.) All federates with are time-sync anchors send out AnnounceSynchronizationAnchor messages to all their neighbors. The distance field is initialized to zero.
2.) Federates who are not time-synchronization anchors have a table with the following format:

Neighbor-Federate	Distance to Time-Sync Anchor
0	3
1	2
2	4

In this example, you can see that neighbor 0 is 3- hops away from the nearest time-sync anchor away, so less preferred than neighbor 2. If now an AnnounceSynchronizationAnchor message with distance 2 is received from federate 0 then our the first row of this table is updated because distance 2 is smaller than distance 3. The message AnnounceSynchronizationAnchor is now forwarded to all neighbors with a distance greater than 3 (distance + 1).

Time-Sync

1.) Federate sends RequestTimeUpdate to the neighbor that has the smallest distance value inside our time-sync table. The field my_current_time is filled with the current time when the message is sent.
2.) The neighboring reactor receives this message and responds with a ResponseTimeUpdate message. The my_current_time field is copied over and the reference_time is initialized with the local time of this reactor.
3.) The federate receives this message and can update its time with the following equation: msg->reference_time + (now() - msg->my_current_time) / 2

The reason why this protocol works is that all reactors synchronize with their neighbors that are closer to the time-synchronized federates.

Messages

message AnnounceSynchronizationAnchor  {
  required int32 distance = 1;
}

message ReqeustTimeUpdate {
  required int64 my_current_time = 1;
}

message ResponeTimeUpdate {
  required int64 my_current_time = 1;
  required int64 reference_time = 2;
};

message FederateMessage {
  required MessageType type = 1;
  oneof message {
    TaggedMessage tagged_message = 2;
    StartTagSignal start_tag_signal = 3;
    AnnounceSynchronizationAnchor announce_sync_anchor = 4;
    RequestTimeUpdate = 5;
    ResponeTimeUpdate = 6;
  }
}

Open Questions:

1.) Is this precise enough?
2.) Does this scale?

[erlingrj]

This is a very nice start.

When it comes to the actual clock correction protocol we can just copy what they do in PTP (which is what reactor-c also implements). It requires four messages:

1. SYNC_REQUEST: sent from slave to master to initiate a synchronization
2. SYNC_RESP: Sent from master to slave
3. DELAY_REQ: Sent from slave to master
4. DELAY_RESP: Sent from master to slave

(1) is not part of PTP, because in PTP the master just sends (2) regularity on a multicast address.

(2) is used to estimate apparent latency from master to slave.
(3)+(4) is used to estimate apparent altency from slave to master (we need two messages because that info has to go back to the slave)

Apparent latency can now be divided into clock sync offset and network latency based on the assumption that the network latency is the same both ways.

A few notes:

• I would call them clock-sync masters, not anchors because this is what it is called everywhere else.
• The announce mechanism makes it so that each federate might swap back and forward which is its closes clock-sync master, eventually, it will stabilize. In an ideal world, you wouldn't start synchronizing with anyone until you knew that you wouldn't get any more announce messages. But I think this might be very hard due to cycles, but it is worth exploring if it is possible. If not, we have to be very careful to properly support changing which clock-sync master we are using at runtime and handling in-flight messages, etc.

The announce algorithm

The announce algorithm needs to be specified further. Each federate needs the notion of his own distance as well as the distance reported by all neighbour federates. His current distance is the minimum of his neighbours' distances, plus one. Upon receiving an announce message that triggers a change to a federate distance. I.e. it is less than the distances of the other federates, or it increases the distance of the federate previously closest. Then we should send out an announce message to all other federates, including the one he received it from.

It is important that you send updates, also back the federate that triggered the update. What we should aim for, is supporting topology changes, if one master disconnects/connects this should propagate through the federation as announcements and the federation should reconfigure the master-slave relationships between neighbours. I believe cycles can make this tricky, perhaps a proof of convergence would be good.

[tanneberger]

So what I have written down is basically what NTP does. I also discussed this with Edward yesterday and he recommended adding a bit more to turn this implementation into huygens algorithm.

And to avoid misunderstandings, I'm not saying that each federate communicates directly with a clock master, but only with its neighbor that is closest to a clock-master.

[erlingrj]

It occurred to me that figuring out the master/slave relationships for clock sync between federates, AND agreeing on startup tag might be solved together. I propose that we create a startup message like this:

message StartupMessage {
  Tag start_tag;
  int32 distance_from_gm ;
}

The first field is the sender's proposal for the startup tag. The second field is the sender's assumption about his distance from a grand master.

The startup procedure works in rounds. And each round every federate sends a single such message to every other federate. Each federate considers the round completed when he has received a message from every federate he is connected to. At the end of each round the federate updates:

• The startup proposal (if he has received a proposal from another federate that is larger than his existing proposal)
• His table regarding other federates distance to a grand master, and possibly his own distance to a grandmaster.

When one round is completed, the federate starts the next round by sending out a new StartupMessage, note that it is sent even if it is unchanged.

Since we know the size of the federation at compile time, we can compute the number of rounds needed before we can guarantee that the startup value and distance_from_gm values have converged for all federates. I believe the number of rounds needed is equal to the longest path through the federation when you consider it an undirected graph.

[tanneberger]

Yes I also thought about this. But in my mind we should keep those things separate. Merging these kinds of things requires all the future protocol implementations to implement this as well, and for example for federations running on top of Linux or similar this just becomes dead weight. It also increases the amount of work you need to have protocol compliant runtime.

I like to think about these things as optional capabilities.

message ClockSyncStartup {
      int32 distance_from_gm = 0;
}

message StartupMessage {
  Tag start_tag = 0;
  optional ClockSyncStartup clock_sync = 1;
  // ...
}

This would also make it more convenient to support experimental or use-case specific features.

In this case, if a federate leaves the clock_sync feature field empty, this signals the other federate that this federate is unable to provide clock synchronization.

[erlingrj]

Making the field optional makes sense 👍