src/sys/time/httpsdate_time_source/README.md - fuchsia - Git at Google

 # HTTPSDate Timesource

 The HTTPSDate Timesource implements the
 [`fuchsia.time.external.PushSource`][time-fidl] protocol. It retrieves time
 samples by calling an HTTPS URL specified in the component configuration and
 pulling the time off the Date header in the response. HTTPSDate relies on the
 underlying TLS connection for server authentication. As the device on which
 HTTPSDate is running may not have a valid UTC time, expiry dates on TLS
 certificates are checked for consistency against the time reported by the
 server.

 ## Key Assumptions
 HTTPSDate relies on the server to conform to the standards defined for the Date
 HTTP header as defined in [RFC 2616][rfc-2616], in particular that the server
 has a reasonably accurate time, and that the date is sampled at the time of
 message generation.

 HTTPSDate also relies on some assumptions not in the RFC:
 * The servers polled to produce a single sample are synced to the same time
 source.
 * The servers truncate time down to the second.

 When these additional assumptions break down, the accuracy of time on the
 device is affected:
 * If servers are inconsistently synced or truncated the time samples produced
 will likely contain more noise.
 * If servers consistently round time in a different manner (such as rounding
 up) the time samples will contain a systemic error of up to a second.

 ## Design Overview
 HTTPSDate contains an algorithm to produce a sample from network polls, and a
 scheduler that determines when to produce a sample.

 ### Sampling Algorithm
 The sampling algorithm is responsible for producing a single time sample.
 A fundamental limitation of using HTTP Date headers is that the header has a
 resolution of seconds. The sampling algorithm attempts to improve the
 resolution of a produced sample by combining the results of multiple polls.
 Note that for simplicity the discussion here ignores the effects of network
 latency and drift between the device and server's clock, but they are taken
 into account in the implementation.

 The algorithm encapsulates the information obtained from polling a server once
 in a _bound_. A _bound_ is a tuple `(monotonic, utc_min, utc_max)` that defines
 the range of possible UTC times for a given monotonic time. When a server is
 polled at monotonic time `t_mono`, the server returns some UTC time `t_server`.
 Because the server is assumed to truncate time down to the nearest second,
 `t_server` is a whole number of seconds, and the actual UTC time at `t_mono` is
 in the range `[t_server, t_server + 1]`. This is expressed as the bound
 `(t_mono, t_server, t_server + 1)`.

 The following operations are possible on bounds:
 * _Projection_ - A bound `(t_mono, t_utc_min, t_utc_max)` may be _projected_ to
 a later monotonic time `t_mono_later` by adding `t_mono_later - t_mono` to each
 value in the tuple.
 * _Combination_ - Two bounds at the same monotonic time may be _combined_ by
 taking the intersection of their UTC ranges. _Combining_ two polls produces
 a single bound that usually has a smaller bound and therefore lower
 uncertainty.

 These operations allow combining the results of any two polls by _projecting_
 the earlier bound to the time of the later poll, then _combining_ the resulting
 polls.

 The algorithm polls the server a few times and combines the resulting bounds
 into a single tighter bound. The algorithm makes a best effort to poll at
 intervals such that the size of the accumulated bound is halved after each
 poll. The final bound is then converted to a single sample.

 ### Scheduler
 The scheduler is responsible for periodically producing samples by invoking the
 sampling algorithm, and retrying in case of failure. The scheduler progresses
 through three phases that invoke the sampling algorithm at different timings
 and parameters:
 * _Initial phase_ - comprised of the first sample only, which is produced with
 fewer polls than subsequent polls. This optimizes to start the system clock as
 early as possible at the cost of accuracy.
 * _Converge phase_ - comprised of the first few subsequent samples. Samples are
 produced relatively frequently so that the system clock can converge on an
 accurate time.
 * _Maintain phase_ - comprised of all remaining samples. Samples are produced
 infrequently so that an accurate time can be maintained.

 [time-fidl]: https://fuchsia.dev/reference/fidl/fuchsia.time.external#PushSource
 [rfc-2616]: https://tools.ietf.org/html/rfc2616
	# HTTPSDate Timesource

	The HTTPSDate Timesource implements the
	[`fuchsia.time.external.PushSource`][time-fidl] protocol. It retrieves time
	samples by calling an HTTPS URL specified in the component configuration and
	pulling the time off the Date header in the response. HTTPSDate relies on the
	underlying TLS connection for server authentication. As the device on which
	HTTPSDate is running may not have a valid UTC time, expiry dates on TLS
	certificates are checked for consistency against the time reported by the
	server.

	## Key Assumptions
	HTTPSDate relies on the server to conform to the standards defined for the Date
	HTTP header as defined in [RFC 2616][rfc-2616], in particular that the server
	has a reasonably accurate time, and that the date is sampled at the time of
	message generation.

	HTTPSDate also relies on some assumptions not in the RFC:
	* The servers polled to produce a single sample are synced to the same time
	source.
	* The servers truncate time down to the second.

	When these additional assumptions break down, the accuracy of time on the
	device is affected:
	* If servers are inconsistently synced or truncated the time samples produced
	will likely contain more noise.
	* If servers consistently round time in a different manner (such as rounding
	up) the time samples will contain a systemic error of up to a second.

	## Design Overview
	HTTPSDate contains an algorithm to produce a sample from network polls, and a
	scheduler that determines when to produce a sample.

	### Sampling Algorithm
	The sampling algorithm is responsible for producing a single time sample.
	A fundamental limitation of using HTTP Date headers is that the header has a
	resolution of seconds. The sampling algorithm attempts to improve the
	resolution of a produced sample by combining the results of multiple polls.
	Note that for simplicity the discussion here ignores the effects of network
	latency and drift between the device and server's clock, but they are taken
	into account in the implementation.

	The algorithm encapsulates the information obtained from polling a server once
	in a _bound_. A _bound_ is a tuple `(monotonic, utc_min, utc_max)` that defines
	the range of possible UTC times for a given monotonic time. When a server is
	polled at monotonic time `t_mono`, the server returns some UTC time `t_server`.
	Because the server is assumed to truncate time down to the nearest second,
	`t_server` is a whole number of seconds, and the actual UTC time at `t_mono` is
	in the range `[t_server, t_server + 1]`. This is expressed as the bound
	`(t_mono, t_server, t_server + 1)`.

	The following operations are possible on bounds:
	* _Projection_ - A bound `(t_mono, t_utc_min, t_utc_max)` may be _projected_ to
	a later monotonic time `t_mono_later` by adding `t_mono_later - t_mono` to each
	value in the tuple.
	* _Combination_ - Two bounds at the same monotonic time may be _combined_ by
	taking the intersection of their UTC ranges. _Combining_ two polls produces
	a single bound that usually has a smaller bound and therefore lower
	uncertainty.

	These operations allow combining the results of any two polls by _projecting_
	the earlier bound to the time of the later poll, then _combining_ the resulting
	polls.

	The algorithm polls the server a few times and combines the resulting bounds
	into a single tighter bound. The algorithm makes a best effort to poll at
	intervals such that the size of the accumulated bound is halved after each
	poll. The final bound is then converted to a single sample.

	### Scheduler
	The scheduler is responsible for periodically producing samples by invoking the
	sampling algorithm, and retrying in case of failure. The scheduler progresses
	through three phases that invoke the sampling algorithm at different timings
	and parameters:
	* _Initial phase_ - comprised of the first sample only, which is produced with
	fewer polls than subsequent polls. This optimizes to start the system clock as
	early as possible at the cost of accuracy.
	* _Converge phase_ - comprised of the first few subsequent samples. Samples are
	produced relatively frequently so that the system clock can converge on an
	accurate time.
	* _Maintain phase_ - comprised of all remaining samples. Samples are produced
	infrequently so that an accurate time can be maintained.

	[time-fidl]: https://fuchsia.dev/reference/fidl/fuchsia.time.external#PushSource
	[rfc-2616]: https://tools.ietf.org/html/rfc2616