Clock Synchronization in IEEE 802.11 Wireless Network

The clock synchronization has become an indispensable component for several mechanisms in wireless networked systems. The common mechanisms such as power management and time-division multiplexing both require the synchronous operation among nodes in the network. In this work, we explore the clock synchronization problem in wireless networks based on the IEEE 802.11 standard. A simple way to achieve the synchronization is to let the node with fastest clock to drive the clock of the entire network. For multi-hop network, a Clock Jumpling Algorithm is proposed by explicitly creating one node with fastest clock and distributing its clock to the entire network.

Mechanism

First Version
Current version:

(1)   Root node will jump and send out beacon every 100ms, while each node will forward it upon receiving.

(2)   Upon receiving a beacon, each node set its virtual clock (vclock) to the current TSF, and record the current TSC (old_tsc) as the following pesudocode (here we assume the TSC has been uniformed by the corresponding cpu frequency):

vclock = sync_with_current_tsf();

old_tsc = get_current_tsc();

(3)   One server will send out Ethernet packet as a Pulse every 1 second. Upon receiving a Pulse, each node will record its current TSC (new_tsc), and print out the virtual clock as the following code:

new_tsc = get_current_tsc();

vclock = vclock + (new_tsc – old_tsc);

record(vclock);

(4)   Each child is equipped with 2 wifi cards, and keeps recording the virtual clock of each interface independently (without synchronizing the TSF of 2 cards)

(5)   In the end, we measure the clock difference between 2 neighboring nodes (without concerning about other nodes)

Experiment result

(1) Calibration of TSF

Setup: one pair of node with one wifi interface on each; no beacon transmission between the 2 nodes

Here, we might assume the drift to be linear to time, and the spike of the histogram happens when the Ethernet pulse packet arrives at each node, but at different time to trigger the SoftIRQ of kernel socket (each node use the kernel socket to listen to the Ethernet packet).

So, the problem is to eliminate the kernel socket overhead right now.

The result shows that the clock drift difference between these 2 nodes will increment 15.26 micro-second every 1 second

So, the ground truth of the TSF synchronization is: within 100 ms beacon interval, the maximum drift will be 1.526 micro-second

[following graph: x-axis is the experiment time line (second), y-axis is the Clockdrift in micro-second]


(2) Calibration step (to measure the accuracy of TSC on each PC)

 

Root:  Intel Celeron, family 15, model 2, stepping 9, 1995.063MHz (ip: 130.245.134.156)

Child1: Intel Pentium 4, family 15, model 0, stepping 10, 1495.192MHz (ip: 130.245.134.157)

Child2: Intel Pentium 4, family 15, model 0, stepping 10, 1495.188MHz (ip: 130.245.134.238)

Child3: Intel Pentium 4, family 15, model 0, stepping 10, 1495.193MHz (ip: 130.245.134.86)


Method

Here we build a server to periodically (per second) send out UDP broadcast packet on Ethernet (as a Pulse).

When one node gets the packet, it records it's current TSC (implementation could be seen in UDP_Broadcast)

 

Clockrate = (TscDiff-RootTscDiff)/RootTscDiff (from this, we know whose TSC is faster, result is Child3 > Child2 > Root > Child1).
The average Clockrate (compare to root) is 0.00006


Clockdrift = Absolute(Clockrate – 1)*Time, where Time is equal to BeaconPeriod (100ms) in our case; So the average TSC clock drift of child in 100ms would be 0.00005*100ms = 5 micro-seconds.

Every 100ms:     5 micro-second

Every 1 second: 50 micro-second


[following graph: x-axis is the experiment time (second), y-axis is the Clockrate comparing to root node]

(3) Jumping mechanism

Root: 0 (we use root's clock as basis for comparison)

Child1: -44 us to root

Child2: +3 us to child1 (-41 us to root)

Child3: -14 us to child2 (-55 to root)

Average clock drift = 51 micro-second


[following graph: x-axis is the experiment time (second), y-axis is the Clock Drift comparing to root node (micro-second)]
(4) Original TSF mechanism
Best case
What's the best running case of the original TSF sync mechanism? Take a pair of nodes, if the one with faster TSF clock always send out the beacon to the slower, then everything is perfect, and the drift would be the smallest.
Average clock drift = 53 micro-second

[following graph: x-axis is the experiment time (second), y-axis is the Clock Drift comparing to root node (micro-second)]


(5) 12-hops
Setup 8 wifi cards on child1, child2, and child3

What can be done and What can NOT be done in madwifi-0.9.3.1

Enviroment: Desktop PC, Intel CPU, Linux 2.4.26 (built from Redhat 9)

What can be done:

1. Disable the veol mode (small patch is necessary)

2. Jump the higher 32-bit of TSF

3. Reset the TSF.

4. Trigger beacon forward after receiving a beacon with jump TSF. (can NOT in mint node)

 

What can NOT be done

1. Can NOT simulate beacon suppression in driver level (it is done in h/w)

2. Can NOT modify lower 32-bit TSF, otherwise the h/w beacon timer will act weird. (so it's not possible to synchronize the TSF between 2 wifi cards on the same node)

3. Can NOT perform Uni-cast for TSF updating (the TSF is updated always when it receives new value)

4. Can NOT disable the SWBA flag while setting up h/w beacon timer.

Programming reference

Time reference
Beacon Control
Programming Modules in Linux
UDP_Broadcast
Networking stack in kernel