1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
# Clock Synchronization
How it works
## Step 1 - rough sync
T0 = current_time()
Tell the remote to zero clock.
Wait for confirmation from remote
maxE = current_time() - T0
All further local time is measured from T0
After this step we are sure that the remote clock lags behind the local clock by
some value E. And we know that E >= 0 because remote was zeroed *after* we
zeroed the local time (recored T0). And also E<= maxE. So 0 = minE < E < maxE.
## Step 2 - find better lower bound - `minE`
Send some messages from local to remote, note the time right before sending the
message (denote it as `t_local`) and have the remote reply with his timestamps
of when it received the messages according to his clock that lags by unknown
positive value `E` behind the local clock, denote it by `t_remote`.
t_remote = t_local - E + travel_time
E = t_local - t_remote + travel_time > t_local - t_remote
since travel_time > 0
E > t_local - t_remote
set minE to max(minE, t_local - t_remote)
Repeat
We need to first send a bunch of messages with some random small delays, and
only after that get the remote timestamps for all of them. This helps deal with
unwanted buffering and delay added by the kernel of hardware in the outgoing
direction.
## Step 3 - find better upper bound `maxE`
Same idea, but in the opposite direction. Remote device sends us messages and
then the timestamps according to his clock of when they were sent. We record the
local timestamps when we receive them.
t_local = t_remote + E + travel_time
E = t_local - t_remote - travel time < t_local - t_remote
set maxE = min(maxE, t_local - t_remote)
Repeat
## Comparison with NTP
NTP measures the mean travel_time (latency) and assumes it to be symmetric - the
same in both directions. If the symmetry assumption is broken, there is no way
to detect this. Both, systematic asymmetry in latency and clock difference would
result in exactly the same observations -
[explanation here](http://cs.stackexchange.com/questions/103/clock-synchronization-in-a-network-with-asymmetric-delays).
In our case the latency can be relatively small compared to network, but is
likely to be asymmetric due to the asymmetric nature of USB. The algorithm
described above guarantees that the clock difference is within the measured
bounds `minE < E < maxE`, though the resulting interval `deltaE = maxE - minE`
can be fairly large compared to synchronization accuracy of NTP on a network
with good latency symmetry.
Observed values for `deltaE`
- Linux desktop machine (HP Z420), USB2 port: ~100us
- Same Linux machine, USB3 port: ~800us
- Nexus 5 ~100us
- Nexus 7 (both the old and the newer model) ~300us
- Samsung Galaxy S3 ~150us
## Implementation notes
General
- All times in this C code are recored in microseconds, unless otherwise
specified.
- The timestamped messages are all single byte.
USB communication
- USB hierarchy recap: USB device has several interfaces. Each interface has
several endpoints. Endpoints are directional IN = data going into the host,
OUT = data going out of the host. To get data from the device via an IN
endpoint, we must query it.
- There are two types of endpoints - BULK and INTERRUPT. For our case it's not
really important. Currently all the comms are done via a BULK interface
exposed when you compile Teensy code in "Serial".
- All the comms are done using the Linux API declared in linux/usbdevice_fs.h
- The C code can be compiled for both Android JNI and Linux.
- The C code is partially based on the code of libusbhost from the Android OS
core code, but does not use that library because it's an overkill for our
needs.
## There are two ways of communicating via usbdevice_fs
// Async way
ioctl(fd, USBDEVFS_SUBMITURB, urb);
// followed by
ioctl(fd, USBDEVFS_REAPURB, &urb); // Blocks until there is a URB to read.
// Sync way
struct usbdevfs_bulktransfer ctrl;
ctrl.ep = endpoint;
ctrl.len = length;
ctrl.data = buffer;
ctrl.timeout = timeout; // [milliseconds] Will timeout if there is nothing to read
int ret = ioctl(fd, USBDEVFS_BULK, &ctrl);
|
