• Stars
    star
    122
  • Rank 292,031 (Top 6 %)
  • Language
    C++
  • License
    BSD 3-Clause "New...
  • Created almost 7 years ago
  • Updated over 5 years ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

TimeSync: Time Synchronization Library in Portable C++

TimeSync

TimeSync: Time Synchronization library in C++

Motivation:

This library provides a single-header implementation of network time synchronization, suitable for synchronizing clocks between two mobile phones (iOS or Android), Linux, Windows, or Mac computers using UDP/IP sockets. It provides a new method for time synchronization that provides several advantages over prior implementations:

(1) This new time synchronization works better over cellular networks than PTP/NTP and is more accurate in general due to its novel N:M probing approach (see Algorithm section below).

(2) The API provides time synchronization as a feature for applications, enabling millisecond-accurate dead reckoning for multiplayer games with just 16-bit (2 byte) timestamps, and 16-microsecond-precise timing for scientific applications with 23-bit (3 byte) timestamps. This is in contrast with typical timestamps that are between 4 and 8 bytes.

(3) The API provides network trip time for every UDP datagram that arrives.

(4) Delay-based Congestion Control systems should use One Way Delay (OWD) on each packet as a signal, which allows it to e.g. avoid causing latency in realtime games while delivering a file transfer in the background. All existing Delay-based CC algorithms use differential OWD rather than proper time synchronization. By adding time synchronization, CC becomes robust to changes in the base OWD as the end-points remain synced.

(5) Peer2Peer NAT hole-punch can be optimized because it can use time synchronization to initiate probes simultaneously on both peers.

Usage:

This is a bit more of a cookbook than an API to use.

Ingredients:

(1) Microsecond-accurate 64-bit timestamp. I recommend the portable implementation here: https://github.com/catid/siamese/blob/master/SiameseTools.cpp#L52

(2) (Highly Recommended) UDP/IP sockets. You can use TCP (or other reliable-in-order sockets) for time synchronization but the quality will be much lower than with UDP due to the extra delays. I recommend the portable Asio library that is actually stand-alone (boost not required). To use it without boost you'll need something like this: https://github.com/catid/mau/blob/master/thirdparty/IncludeAsio.h

(3) Include TimeSync.cpp into your project and #include "TimeSync.h". Create a TimeSynchronizer object in your netcode on both the client/server code.

(4) Just before sending each UDP datagram, get the current time in microseconds nowUsec and call TimeSynchronizer::LocalTimeToDatagramTS24(nowUsec) to get the 24-bit (3 byte) value to attach to each outgoing UDP datagram.

(5) Periodically, each peer must call TimeSynchronizer::GetMinDeltaTS24() and send the 24-bit (3 byte) value to the remote peer. I recommend sending this value once every 2 seconds using your reliable transport's "unordered reliable" mode if it supports that, because it is fine if they arrive out of order. Ideally, sending the value once every 500 milliseconds for the first 20 seconds or so. When receiving a MinDeltaTS24 value, it should be passed to TimeSynchronizer::OnPeerMinDeltaTS24(). After this call, IsSynchronized() will start to return true.

(6) When a UDP datagram arrives, get the current time in microseconds and call TimeSynchronizer::OnAuthenticatedDatagramTimestamp(Counter24 remoteSendTS24, uint64_t localRecvUsec) with the 24-bit (3 byte) timestamp attached the datagram.

With each datagram received, the timestamp accuracy improves.

The function will return the OWD of each datagram, or 0 if IsSynchronized() is returning false.

The TimeSynchronizer::GetMinimumOneWayDelayUsec() will return the speed of light in microseconds - the smallest OWD seen so far.

To attach a timestamp for game physics or camera frames or audio or whatever the application is doing, use the ToRemoteTime23(uint64_t localUsec) and FromLocalTime23(uint64_t localUsec, Counter23 timestamp23) methods.

Call ToRemoteTime23 with the local timestamp to send, which produces a 23-bit (3 byte) timestamp that can be sent in a UDP or TCP message. The receiver of the message must get a current microsecond timer and can then call FromLocalTime23(localUsec, timestamp23) to decompress the 23-bit (3 byte) timestamp back into a 64-bit local timestamp in microseconds. The LSB precision of 23-bit (3 byte) TS23 is 8 microseconds. There is also a 16-bit (2 byte) TS16 version with 0.5 millisecond precision.

Background:

Network time synchronization can be done two ways: (a) Broadcast - Infeasible on the Internet and so not used. (b) Assuming that the link is symmetric, and trusting Min(RTT/2) = OWD. Meaning that existing network time synchronization protocols like NTP and PTP work by sending multiple probes, and then taking the probe with the smallest round trip time to be the best data to use in the set of probes.

Time synchronization at higher resolutions needs to be performed constantly because clocks drift at a rate of about 1 millisecond per 10 seconds. So, a common choice for reliable UDP game protocols is to probe for time synchronization purposes (running NTP all the time) at a fixed interval of e.g. 5 to 10 seconds.

The disadvantage of all of these existing approaches is that they only use a finite number of probes, and all probes may be slightly skewed, especially when jitter is present, or cross-traffic, or self-congestion from a file transfer.

For cellular networks, existing time synchronization approaches provide degraded results due to the 4-10 millisecond jitter on every packet. "An End-to-End Measurement Study of Modern Cellular Data Networks" (2014) https://www.comp.nus.edu.sg/~bleong/publications/pam14-ispcheck.pdf

when a link is asymmetrical there is no known practical method for performing time synchronization between two peers that meet on the Internet, so in that case a best effort is done, and at least it will be consistent.

Algorithm:

This TimeSync protocol overcomes this jitter problem by using a massive number of probes (every packet is a probe), greatly increasing the odds of a minimal RTT probe.

How it works is that every packet has a 3 byte microsecond timestamp on it, large enough to prevent roll-over. Both sides record the receive time of each packet as early as possible, and then throw the packet onto another thread to process, so that the network delay is more accurate and each client of a server can run in parallel.

While each packet is being processed the difference in send and receive times are compared with prior such differences. And a windowed minimum of these differences is updated. Periodically this minimum difference is reported to the remote peer so that both sides have both the minimum (outgoing - incoming) difference and the minimum (incoming - outgoing) difference.

These minimum differences correspond to the shortest trips each way. Effectively, it turns every single packet into a time synchronization probe, guaranteeing that it gets the best result possible.

The (Simple) Math for TimeSync:

We measure (Smallest C2S Delta) and (Smallest S2C Delta) through the per-packet timestamps.

C2S = (Smallest C2S Delta)
    = (Server Time @ Client Send Time) + (C2S Propagation Delay) - (Client Send Time)
    = (C2S Propagation Delay) + (Clock Delta)

S2C = (Smallest S2C Delta)
    = (Client Time @ Server Send Time) + (S2C Propagation Delay) - (Server Send Time)
    = (S2C Propagation Delay) - (Clock Delta)

Such that (Propagation Delay) for each direction is minimized
independently as described previously.

We want to solve for (Clock Delta) but there is a problem:

Note that in the definition of C2S and S2C there are three unknowns and only two measurements. To resolve this problem we make the assumption that the min. propagation delays are almost the same in each direction.

And so:

(S2C Propagation Delay) approx equals (C2S Propagation Delay).

Thus we can simply write:

(Clock Delta) = (C2S - S2C) / 2

This gives us 23 bits of the delta between clocks, since the division by 2 (right shift) pulls in an unknown high bit. The effect of any link asymmetry is halved as a side effect, helping to minimize it.

The (Simple) Math for Network Trip Time:

It also provides a robust estimate of the "speed of light" between two network hosts (minimal one-way delay). This information is then used to calculate the network trip time for every packet that arrives:

Let DD = Distance from the current packet timestamp difference and minimal. DD = (Packet Receive - Packet Send) - Min(Packet Receive - Packet Send) Packet trip time = (Minimal one-way delay) + DD.

More Repositories

1

supercharger

Supercharge Open-Source AI Models
Python
348
star
2

dora

Implementation of DoRA
Python
276
star
3

Zpng

Better lossless compression than PNG with a simpler algorithm
C
267
star
4

wirehair

Wirehair : O(N) Fountain Code for Large Data
C++
267
star
5

self-discover

Implementation of Google's SELF-DISCOVER
Python
263
star
6

WLANOptimizer

Single-header C library that fixes WiFi performance issues for online gaming and other low-latency real-time network traffic.
C++
223
star
7

longhair

Longhair : O(N^2) Cauchy Reed-Solomon Block Erasure Code for Small Data
C++
156
star
8

leopard

Leopard-RS : O(N Log N) MDS Reed-Solomon Block Erasure Code for Large Data
C++
135
star
9

shorthair

Shorthair : Generational Block Streaming Erasure Codes
C++
128
star
10

cm256

Fast GF(256) Cauchy MDS Block Erasure Codec in C
C++
107
star
11

tonk

Tonk : Reliable UDP (rUDP) Network Library and Infinite Window Erasure Code
C++
101
star
12

Zdepth

Zdepth :: Streaming Depth Compressor in C++ for Azure Kinect DK
C++
97
star
13

xrcap

Azure Kinect multi-camera secure network capture/record/replay
C++
76
star
14

snowshoe

Snowshoe - Portable, Secure, Fast Elliptic Curve Math Library in C
C++
62
star
15

XRmonitors

XRmonitors : User-Friendly Virtual Multi-Monitors for the Workplace
C++
54
star
16

tabby

Tabby - Strong, Fast, and Portable Cryptographic Signatures, Handshakes, and Password Authentication
C++
50
star
17

gf256

GF256 - Fast 8-bit Galois Field Math in C
C++
50
star
18

kvm

Low-Bandwidth IP KVM using Raspberry Pi 4
C++
48
star
19

siamese

Siamese : Infinite-Window Streaming Erasure Code (HARQ)
C++
47
star
20

bitnet_cpu

Experiments with BitNet inference on CPU
C++
46
star
21

ZdepthLossy

Lossy version of Zdepth using video encoders
C++
41
star
22

fecal

FEC-AL : O(N^2) Fountain Code for Small Data
C++
36
star
23

CauchyCaterpillar

Cauchy Caterpillar : O(N^2) Short-Window Streaming Erasure Code
C++
35
star
24

aiwebcam2

Second attempt at AI webcam, this time with OpenAI API
Python
32
star
25

upsampling

Image Upsampling with PyTorch
Python
22
star
26

calico

Calico - Strong, Fast, and Portable Authenticated Encryption
C++
21
star
27

cymric

Cymric - Portable secure random number generator
C++
20
star
28

loraftp

File transfer between two Raspberry Pis using the LoRa Pi HAT from Waveshare
C
19
star
29

mau

Network simulator for reliable UDP testing in C++
C++
16
star
30

oaillama3

Simple setup to self-host LLaMA3-70B model with an OpenAI API
16
star
31

lllm

Latent Large Language Models
Python
16
star
32

PacketAllocator

C++ Memory allocator for packet queues that free() in roughly the same order that they alloc().
C++
15
star
33

spectral_ssm

Implementation of Spectral State Space Models
Python
15
star
34

libcat

Common code library
C++
14
star
35

AutoAudiobook

Automatically create an audiobook using OpenAI
Python
14
star
36

minigpt4

MiniGPT-4 :: Updated to Torch 2.0, simple setup, easier API, cut out training code
Python
13
star
37

sdxl

SDXL GPU cluster scripts
Python
13
star
38

dataloader

High-performance tokenized language data-loader for Python C++ extension
C++
12
star
39

fp61

Experiment: Fast finite field Fp=2^61-1 in C++
C++
11
star
40

cuda_float_compress

Python package for compressing floating-point PyTorch tensors
Cuda
10
star
41

phind

Locally hosted: 60% HumanEval
Python
8
star
42

rtmp_receiver

Simple unidirectional RTMP video stream receiver
C++
7
star
43

counter

C++ wrapper for counters that can roll-over (e.g. timestamps/ack-ids)
C++
6
star
44

z16

16-bit monochrome image compressor based on Zstd
C
5
star
45

AQLM

Fixes for AQLM
Python
5
star
46

llamanal.cpp

Static code analysis for C++ projects using llama.cpp and the best LLM you can run offline without an expensive GPU.
C
5
star
47

unfiltered-diffusers

Simple fork that disables NSFW filter
Python
5
star
48

hloc

Python
4
star
49

boss-balloon

BossBalloon.io
TypeScript
4
star
50

libcatid

Automatically exported from code.google.com/p/libcatid
C++
3
star
51

voron

Voron 3D Printer files
3
star
52

halide-test

Test v14/v15 performance regression
CMake
3
star
53

logger

Feature-rich portable C++ logging subsystem in 650 lines of code
C++
3
star
54

cifar10deepspeed

Using DeepSpeed and Nvidia DALI to train various models to solve CIFAR-10
Python
3
star
55

chainlit-anthropic

Chainlit AI UI with Anthropic Backend
Python
3
star
56

fastest_gf_matrix_mult

A fairly hacked together piece of code that can quickly search for the optimal GF polynomials and Cauchy matrices for XOR-based GF matrix multiplication for erasure code encoders. May be useful if the matrices are of fixed size.
C++
3
star
57

recfilter-2020-fail

This is a failed attempt to port Recfilter to latest Halide from 2020. Maybe someone else can figure this out?
C++
2
star
58

bentpipe

Simple UDP rebroadcaster
C++
2
star
59

whisper3

Testing out Whisper 3
Python
2
star
60

sphynx

Sphynx - High Performance Network Transport Layer
C++
2
star
61

textworld_llm_benchmark

TextWorld LLM Benchmark
Python
2
star
62

pixel-perfect-sfm

pixel-perfect-sfm with some minor fixes
C++
2
star
63

train_ticket

Gated PRNGs are all you need? Spoilers: No.
Python
2
star
64

CatsChoice

PRNG Parameter Generation
C++
1
star
65

CRC16Recovery

Optimized CRC16 with error recovery in C
C++
1
star
66

Splane

Archived old code - /ban_ids/ is kind of interesting
C
1
star
67

rust_webgl_demo

Hello World : Rust Web Assembly
Rust
1
star
68

blog2022

HTML
1
star
69

swe_agent_playground

swe_agent_playground
1
star
70

Exapunks_Solutions

Exapunks Walkthrough Solutions
1
star
71

audio_prediction

Simple audio prediction example with RNN
Python
1
star
72

never_forget

Implementation of Overcoming Catastrophic Forgetting
Python
1
star
73

DependencyInjected

DependencyInjected : Light-weight and powerful Dependency Injection pattern for C++
C++
1
star
74

quicsend

quicsend :: Super-fast Internet-ready file transfer right from Python
C++
1
star