Timekeeping in the Interplanetary Internet

Researchers involved: David Mills, graduate student Harish Nair

Funding: Jet Propulsion Laboratory/NASA

Briefing Slides

Interplanetary Timekeeping PostScript | PowerPoint | PDF

Importance of the Problem

There is a long tradition in the planetary science community of controlling experiments entirely from Earth, although there is some progress using semi-autonomous vehicles for Mars surface exploration. Most missions require some kind of clock to determine windows of communication opportunities, for example. During periods where communication with Earth is not possible, there is need to synchronize clocks among the orbiters, base stations and exploration vehicles participating in the mission.

The Interplanetary Internet (IPIN) consists of Earth stations, Mars planetary orbiters, base stations and exploration vehicles participating in a space mission. This project explores synchronization issues in the IPIN using suitable modifications to the Network Time Protocol (NTP). NTP is widely used to synchronize computers in the Earth Internet and has been deployed in low-orbit Earth orbiters, but not in interplanetary missions. There are three issues which distinguish the Earth Internet from the IPIN: bodies are moving, connectivity between them is necessarily not continuous and transmission delays can be very long.

Brief Description of Work and Results

With support from Jet Propulsion Laboratories (JPL) and NASA, we have begun a study of timekeeping issues in the Interplanetary Internet, specifically for Mars missions and supporting infrastructure. Currently, the clocks for all space vehicles are coordinated on Earth using a software library called SPICE. With new technology, timekeeping in space would be distributed so that timed experiments could be accurately controlled autonomously and without intervention from Earth. There are three issues which distance the new technology from current practice: bodies are moving, connectivity between them is necessarily not continuous and transmission delays can be very long.

The Mars internet includes three segments. The Earth segment consists of the current Internet, including experiment hosts and NASA Deep Space Network (DSN) earth station gateways in California, Spain and Australia. The Mars segment consists of orbiters, base stations and rovers near and on Mars. The DSN segment consists of the space between DSN gateways, spacecraft transport buses and Mars orbiters. The orbiters function as gateways, experiment data buffers and supporting infrastructure, including time synchronization.

The current NTP technology has no provisions for mobile servers and clients, where range and range rates can vary with time, and only minimal provisions for intermittent connectivity. In the Mars internet, orbiters and surface stations may have only intermittent connectivity, while in the DSN segment real-time connectivity is possible only at scheduled opportunities and then only with very long delays. These considerations are mitigated by the fact that ranges and range rates can be predicted with some accuracy from the known positions of the spacecraft bus, orbiters and surface stations using ephemerides maintained by astronomical means.

The mission of this project is to develop an understanding of the timekeeping issues in the IPIN, including Mars missions and beyond. The technology must be able to Extract ephemerides data from mission housekeeping files both on Earth, the spacecraft bus and Mars orbiters to compute range and range rate for useful transmission opportunities. The goals of the project are to

Enhance the NTP protocol to encode and transmit ephemerides and/or orbit element data along with NTP timestamp data.
Develop new or modified algorithms using these data to determine accurate time and frequency offsets between moving objects.
Demonstrate a proof-of-concept in the form of a space simulator using suitably modified components of the existing NTP software distribution embedded in a special purpose discrete time simulator.

The Network Time Protocol

Time is maintained throughout the mission infrastructure using onboard clocks. Clocks control the science instruments, antenna pointing and communication functions. Like all computer clocks the clock includes a reference oscillator, clock counter and software to provide time in some format to the onboard operating system. Additionally in order to synchronize this clock to other clocks in the infrastructure a time synchronization protocol such as NTP is required.

NTP synchronizes clocks be exchanging timestamped messages between a server and its clients. These timestamps are used to determine roundtrip delay and clock offset as well as provide reliable error estimates. Each NTP message includes the latest three timestamps T1, T2, T3 with the fourth timestamp T4 determined upon arrival of the message. These timestamps are determined at the following times.

T1 = time at which the client sent the packet
T2 = time at which the server received the packet
T3 = time at which the server sent the reply
T4 = time at which the client received the reply

Let a = T2 –T1 and b = T3 – T4. Then the roundtrip delay ‘d’ and offset ‘O’ of the client relative to the server are:

d = (a – b)
O = (a + b)/2

The above equations assume an ideal scenario in which the client-server and server-client delays are identical. In practice, error due to stochastic network delays dominate; however it is not usually possible to characterize network delays as a stationary random process, since network queues can grow and shrink in chaotic fashion and arriving customer traffic is frequently bursty. Nevertheless it is a simple exercise to calculate bounds on network errors E as a function of measured delay.

(-d/2) <= E <= (d/2)

In other words, the true clock offset must lie in the interval of size equal to the measured delay and centered around the measured offset.

The NTP is in a continuous state of transmitting and receiving NTP packets. The computed delays and offsets are first processed in data filters to derive the most accurate and reliable subset. The resulting offsets of this subset are first combined on a weighted average basis and then processed by a phase lock loop (PLL). In the PLL the combined effects of filtering, selection and combining operations are to produce a phase-correction term, which is processed by a loop filter to control the local clock.

From the above discussion we can see that the accuracy of synchronization depends mainly on the accuracy of offset subset that is provided to the loop filter. The accuracy of the offsets, on the other hand is bounded by one-half the roundtrip delay. When we move from the static earth internet to the dynamic interplanetary internet these delays fluctuate heavily and become quite large. Under these conditions the accuracy that can be obtained will become unacceptable.

Approach

Our model is that the timescales for all platforms, be they in space or on the surface, run at a constant rate relative to atomic time (TAI). This creates somewhat of a problem in that for an event like a supernova explosion the flash should be observed by all platforms consistent with the quasi-planar wavefront from the source. This requires all platforms calculate the offset from solar barycentric time (TDB) relative to the local clock and assumed position and velocity relative to barycentric coordinates, which change continuously. However, the ephemeris for each platform is presumed known by astronomical observation or other means, so that a common-view technique can be used.

The lightwave propagation time between two moving objects in space can be determined by an iterative procedure. Let P_s(t) be the position of the server at TDB time t according to the server ephemeris and P_c(t) be the position of the client at time t according to the client ephemeris. The propagation time T_p between the server and client (called lighttime in SPICE) is the unique number that satisfies

      | P_c(T_s + T_p) - P_s(T_s) |
T_p =  -----------------------,
                c

where the quantity in brackets is the distance between the server and client at the times specified and c is the speed of light. The following iterative procedure is adapted from SPICE, and the description is adapted from the SPICE documentation.

Time can be disciplined on a one-way or two-way basis. In a one-way scheme a server with a presumed correct clock broadcasts a packet including the TDB time T_s and ephemeris position P_s(t) at time t = T_s. When the packet arrives, the client determines a ephemeris position P_c(t) at time t = T_s + T_p(0), where T_p(0) = 0 is an initial estimate. At each new iteration i, the client finds a new position P_c(t) at time t = T_s + T_p(i- 1). The algorithm can be concisely expressed

T_p(0) = 0;

        | P_c(T_s + T_p(i - 1)) - P_s(T_s) |
T_p(i) = ------------------------------  (i > 0).
                       c

The SPICE documents state that the sequence T_p(0), T_p(1), ... converges geometrically. Moreover, it can be shown that the difference between T_p and T_p(i) satisfies the following inequality.

| T_p - T_p(i) | < T_p * (V / c)ⁱ⁺¹,

where V is the speed of the client with respect to the solar system barycenter and c is the speed of light. For nearly all objects in the solar system V is less than 60 km/s, so after only one iteration the relative error | T_p - T_p(i) | is not more than 20 microseconds per astronomical unit (AU) of distance between server and client. For objects within the solar system, the error is less than 1 ms, which is within the error expectations for NTP timekeeping in the Interplanetary Internet. The difference between the final time estimate T_s + T_p(1) and the local clock is the offset presented to the NTP filtering and discipline algorithms, which function in the normal way.

A two-way scheme is similar to the NTP symmetric mode involving two peers. Each peer sends a packet at intervals to be determined. The packet contains the same information as in the one-way scheme and in addition the originate and receive timestamps as in NTP symmetric mode. In addition, the barycentric coordinates for each of the three timestamps is convened in extension fields. The advantage of this scheme is the same as for NTP symmetric mode. Each peer can independently measure the TDB offset of the other as well as the overall roundtrip delay.

We anticipate a network of NTP peers where each platform is in intermittent contact with one or more other peers and where the NTP subnet is continuously evolving and reconfiguring according to a fixed or ad hoc schedule. Existing features of NTP, especially the Manycast autoconfiguration mode are directly applicable, as well as the Autokey authentication scheme.

It may will happen that residual clock frequency offsets may introduce considerable error if the time between updates is relatively long, as would be expected during communication opportunities between Earth and mission spacecraft. After a few measurements the frequency can be disciplined in the usual way, but this affects the position and velocity vectors and residuals with respect to the ephemeris. What makes frequency-induced errors more nasty is that the frequency may fluctuate due to spacecraft thermal cycles and power management. Assuming primary servers on Earth together with ephemerides of the transmitter location, the above scheme continues to refine the residuals and develop global time. Kalman filters or ARIMA methods might be a good tool to deal with the residuals and steer to the best time.

There is some concern that the expense of these calculations, both in processor cycles and thermal management, may not be justified in all cases. For instance, NTP between Mars orbiters and the surface is no different than NTP between Earth orbiters and the ground. In fact, NTP has flown in space before on an AMSAT satellite where the embedded Intel processor ran the same code as used on Earth. This assumes the satellite doesn't move very far during the roundtrip propagation time for the NTP message and reply. If finer correction is required, orbital elements could be derived from radio rise and set times and corrections computed on the fly.

There has been some discussion on what the Mars orbiters can do with respect to antenna orientation. There is a limited fuel supply to point the antenna to Earth and it may not be a good idea spending fuel to point it at other orbiters or the ground in order to exchange NTP packets. Also, it is not likely the orbiters can communicate with each other using an omnidirectional antenna and low power, at least most of the time. However, omnidirectional antennas would seem to be the choice when communicating with surface platforms. Assuming the surface platforms can discipline their own local clock to some degree of precision, the surface clock could be used as a flywheel to synchronize orbiter clocks as they pass over the platform.

Deterministic Model

Our model is that the timescales for all platforms, be they in space or on the surface, run at a constant rate relative to atomic time (TAI). This requires all platforms calculate the offset from solar barycentric time (TDB) relative to the local clock and assumed position and velocity relative to barycentric coordinates, which change continuously. However, the ephemeris for each platform is presumed known by astronomical observation or other means, so that a common-view technique can be used.

Time can be disciplined on a one-way or two-way basis. In the one-way scheme a server with a presumed correct clock broadcasts a packet including the TDB time Ts and ephemeris position Ps(t) at time t = Ts. When the packet arrives, the client determines the lightwave propagation time Tp between the server and client at time t. The algorithm to mathematically compute to arbitrary precision is well known and is given in Appendix 9.1 below. Tp is the lightwave propagation time between the server and client. The difference between the final time estimate Ts + Tp and the local clock is the offset presented to the NTP filtering and discipline algorithms, which function in the normal way.

The accuracy of the above model depends on the accuracy with which we can calculate the lighttime between the client and the server at any point of time. Provided we can calculate the ephemeris (3-dimensional position vector) of both nodes with repect to a reference cordinate system for any given time t, the lightwave propagation time between two moving nodes in space can be determined by an iterative procedure. Let Ps(t) be the position of the server at TDB time t according to the server ephemeris and Pc(t) be the position of the client at time t according to the client ephemeris. The propagation time Tp between the server and client (also called lighttime) is the unique number that satisfies

      | Pc(Ts + Tp) - Ps(Ts) |
Tp =  -----------------------,
                c

where the quantity in brackets is the distance between the server and client at the times specified and c is the speed of light. Mathematically, Tp can be computed to arbitrary precision via the following algorithm:

Tp(0) = 0;

        | Pc(Ts + Tp(i - 1)) - Ps(Ts) |
Tp(i) = ------------------------------  (i  >  0).
                       c

The sequence Tp(0), Tp(1), ... converges geometrically. Moreover, it can be shown that the difference between Tp and Tp(i) satisfies the following inequality.

| Tp - Tp(i) | <  Tp * (V / c)i+1,

where V is the speed of the client with respect to the solar system barycenter and c is the speed of light. For nearly all objects in the solar system V is less than 60 km/s, so after only one iteration the relative error | Tp - Tp(i) | is not more than 20 microseconds per astronomical unit (AU) of distance between server and client. For objects within the solar system, the error is less than 1 ms, which is within the error expectations for NTP timekeeping in the Interplanetary Internet.

The algorithm needs precise ephemeredes for accurate lighttime calculation. Planets and Satellies move in elliptical orbits following the kepler's laws of orbital dynamics. the motion of a satellite oa planet in its elliptical orbit is given by its "orbital elements". The six orbital elemnts rae semi-major axis, eccentrcity, mean anomaly, logngitude of ascending node, argument of perigee and inclination of orbit. Given these orbital elemnts it is a simple exercise to calculate the ephemeredes. However orbital elements specify the position of the satellite at a certain time called the epoch and are only accurate for a limited period around the epoch. The orbital elemets have higher order derivatives with respect to time and these derivatived also need to be considered for better accuracy. Many models have developed over the years for precise ephemeris determination. These include NASA's SDP4/SGP4 modles and Spice SPK kernels.

We anticipate a network of NTP peers where each platform is in intermittent contact with one or more other peers and where the NTP subnet is continuously evolving and reconfiguring according to a fixed or ad hoc schedule. It is to be noted that all ntp asoociations are on a one-to-one direct basis without any hops in between. Only when the client and server are "within range" are timestamps exchanged. It may will happen that residual clock frequency offsets may introduce considerable error if the time between updates is relatively long, as would be expected during communication opportunities between orbiting nodes. After a few measurements the frequency can be disciplined in the usual way, but this affects the position and velocity vectors and residuals with respect to the ephemeris.

Nondeterministic Model

The deterministic model assumes that the client is able to predict its position accurately for any given time. However it may not be possible always to come up with an accurate model beforehand for calculating ephemeredes for any given time. This means that we have to account for the fact that even the ephemeredes calculated may have an inherent error. The most probable scenario would be that there would be that the client and server ephemeredes model may be for different timescales i.e. there may be a time and frequency offset in the ephemeredes. The problem can be formulated as given below.

Suppose that there is a client node and a server node orbiting in space. The server is known to be a “true chimer” i.e. it correctly knows its time and position. At client time t1 the client sends a packet to the server with is time and position (t1, x1, y1, z1). This packet reaches the server at server time t2 (t2, x2, y2, z2). The server sends back the response at server time t3 (t3, x3, y3, z3). Finally the response reaches the client back at client time t4 (t4, x4, y4, z4). The client now has 4 time stamps to work with.

T1 = (t1, x1, y1, z1)

T2 = (t2, x2, y2, z2)

T3 = (t3, x3, y3, z3)

T4 = (t4, x4, y4, z4)

Now the client has to calculate, using the data above, the offset with the server which can be input to the NTP filtering and discipline algorithms. The client can assume that T2 and T3 provided by the server are accurate, but T1 and T4 can have errors in both position and time. Moreover positions calculated by the client using its ephemeredes for any time can have errors. The client can transmit and receive more packets if required. Finally it has to provide NTP with four timestamps that gives NTP an illusion that the client and server are stationary but still allows it to calculate the offset correctly.

Current Status

Harish Nair has searched the JPL SPICE library and documentation for means to predict position and velocity vectors for moving objects in space and on planetary surfaces. He has used the available algorithms and ephemerides to convert TDB time to entity position, which is the basis for the time transfer technique described above. We have found example data for the Earth, Moon, other planets and an interplanetary mission. While these data are highly useful in initial testing and evaluation, we will eventually need additional interesting scenarios involving Mars orbiters and surface platforms.

We have adapted the NTP software distribution to function both as a daemon for ordinary time synchronization means and also as a simulator for space operations. This capability has been integrated in the public release for others to experiment with. The adaptations include replacing the routines to read and set the clock, some routines of the I/O system and the main program, which implements the simulator queue and utility routines. Whether the daemon or simulator function is enabled is selected in the software configuration process. A description and status report is on the NTP Discrete Event Simulator page

The graphs above show the results of these experiments. The graph on the left shows the light time between the Moon and Mars calculated from the ephemerides over more than a year. Clearly, the range narrows from over a second to abou 270 milliseconds and then widens again. The graph on the right shows the fine structure of the offset computed by NTP after light time correction. The residual errors appear as complex wiggles with amplitude a few milliseconds. Very likely these are due to residuals incident to the polynomial approximation used in the ephemeris calculation. This might not surprise hardened space hands, but it sure surprised the simulator. However, all this means is that the clock discipline tuning parameters for near-Earth baselines might be quite different for interplanetary baselines and the accuracy and precisions achievable might not be nearly be as good.

Future Plans

The general plan is to evaluate the above approach in detail, especially the impact of ephemerides jitter and oscillator wander. We can simulate the effects of oscillator wander, but the effects of ephemerides jitter will need to be explored in more detail. Our immediate plans are to run experiments with different clock discipline tuning parameters.

	Internet Research Laboratory
	DCnet Research Network
	Backroom Test Facility
	CAIRN/DARTnet Collaboration