Multi-Hop Synchronization Algorithm

At the high level, the root (R) of the spanning tree periodically (say every P) sends out a new time stamp, and every other node's clock is re-synchronized with respect to this new time stamp.

The algorithm has 3 primitives :

Primitives

1. send-beacon-now (n, win)

This primitive allows node n to send out a beacon after a random back-off limited by win. This can be implemented by setting the beacon timer to a random value from 0-win (usec).

2. time-jump (n,x)

This primitive causes node n to send out a beacon with timestamp (x + current time stamp). This does not cause its own clock to move forward. That can be only done by an incoming beacon. This can be implemented by modifying the contents of a beacon in the beacon queue and calling a send-beacon-now. The back-off is needed to avoid all children of a parent to send out beacons at the same time causing collision / loss.

3. check-jump (n)

This primitive causes a node to check if an incoming beacon caused the clock to jump by a large value. To implement this, a node can maintain the time stamp received in the last beacon and compare it with the timestamp of the current beacon, if this value is greater than a threshold (500 msec) the beacon caused a jump.

The following is a detailed algorithm to implement this high-level picture:

Algorithm

1. At the beginning of every interval (P msec) , R performs a time-jump (1 sec). After this, R continues to poll its local clock until it is brought into the new time stamp's range. (At this time Root and level 0 children should be in synch).

2. All the other non-leaf nodes in the network keep calling the check-jump primitive to check if a beacon caused the time to jump. Once such a beacon is received they call the send-beacon-now primitive with 100-200usec backoff.

3. After experiencing a clock-jump every node sets its beacon timer to a predefined value (say 100 msec) so that clock values are continuously being exchanged through the entire P interval. This is meant to prevent bad things from happening even when beacons are lost.

Question:

· What is the time typical synchronization time for the network?

Given that beacons take 40 usec to transmit. (conservative estimate of 100usec including backoff). And every level of the tree takes additional 300usec in propagation delay (setting up timer). The time to synchronize a tree of 10 levels is ~ 5 msec

· What should be nodes do with the remaining slot time?

If the TDMA period is set as P - 10msec, and 10msec is left as synchronization time, no node should be within a TDMA sending slot.

· What should period P be?

If P is selected as 100 msec (regular beacon period) - 10% of the time has been spent in synchronization. This overhead would reduce if P is increased.

o If P is close to a beacon period, then beacon timers are not needed on any node other than the root. Also the number of beacons would be less than that of the 802.11 clock synchronization mechanism.

o If P is very large, then the synchronization overhead is less. But nodes will have to exchange beacons within time P to ensure that there is no drift. These these beacons could affect TDMA and may cause additional overhead.

· Do the control messages such as "timer set-up" and "clock propagate" have to be based on TCP?

TCP is only affected if synchronization takes a long time (Greater than few msec) , or it causes packet losses. Both of these situations need to be explored further.

Following is a diagrammatic description of the protocol: