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