Subject: RE: Time-stamp server. TimePrecision info

From: Michael Zolotarev <[email-masked]>
Date: Thu, 1 Apr 1999 17:59:39 +1000

Tony,

I guess there is a neater solution to the 'gain a leap second' problem, 
using the serialNumber field of the response. If the serialNumebr is 
properly maintained by the TSS, and returned to the client, a second can 
last as long as we want it:

time:  0.21           0.22              0.23        0.23        0.23 
      0.24
S/N:  1,2,3,4...   x,x+1,x+2...    n,n+1,n+2,n+3, n+4, n+..      m,m+1...

The issue is, the problem only exists when we COMPARE two stamps produced 
by THE SAME TSS. And this is exactly where the serialNumber will help us 
out.

In a situation when you compare the stamps produced by different servers, 
or compare a stamp to a 'Golden Rolex' time, a one second difference should 
be tolerated, as the sources are not expected to be highly synchronised 
anyway.

Michael Zolotarev
Technical Architect, Baltimore Technologies Limited (Australia)

Happy Easter!

-----Original Message-----
From:	Tony Bartoletti [SMTP:[email-masked]]
Sent:	Thursday, April 01, 1999 4:31 AM
To:	Todd S. Glassey; Paul Koning; [email-masked]
Cc:	[email-masked]
Subject:	Re: Time-stamp server. TimePrecision info

At 07:44 PM 3/30/99 -0800, Todd S. Glassey wrote:
>How will you deal with leap seconds?
>

The only solution I can think of would be UGLY, but would preserve
the all-important monotonicity.  At least it would work when a
leap-second is added. (Subtracting is another matter.  You would
already have monotonicity, but differencing might be difficult.)

Add another field to the "seconds", as little as one "bit", that
is always zero except for a leap-second, when it is "one."

  E.G.   leap.seconds.milliseconds

Now, if (say) the 23rd second of this minute had to be "repeated"
(the clock is being set back 1 second, "gaining" a leap second,)
then it would first occur as 0.23.ms, and then a second later
as 1.23.ms.

Thus, the sequence of timestamps of seconds from 21 to 25 might
be recorded as 0.21, 0.22, 0.23, 1.23, 0.24, 0.25, with

    0.23 < 1.23, and 1.23 < 0.24

Losing a leap-second (should that ever happen) is another matter.
One could just drop the "missing" second as the clock advances.
E.G.

    0.21, 0.22, 0.24, 0.25

Monotonicity is preserved.  Differencing is a headache.

I wonder how they will actually deal with this.

___tony___

Tony Bartoletti                                             LL
Center for Information Operations and Assurance          LL LL
Lawrence Livermore National Laboratory                LL LL LL
PO Box 808, L - 303                                   LL LL LL
Livermore, CA 94551-9900                              LL LL LLLLLLLL
phone: 925-422-3881   fax: 925-423-8002               LL LLLLLLLL
email: [email-masked]                                   LLLLLLLL

---

From: Paul Koning <[email-masked]>
Date: Thu, 1 Apr 1999 10:48:38 -0500

>>>>> "Michael" == Michael Zolotarev <[email-masked]> writes:

 Michael> In a situation when you compare the stamps produced by
 Michael> different servers, or compare a stamp to a 'Golden Rolex'
 Michael> time, a one second difference should be tolerated, as the
 Michael> sources are not expected to be highly synchronised anyway.

I guess that works perfectly well if the inaccuracy (i.e., difference
between timestamp and actual UTC) is large enough.  In particular, if
you ignore leap seconds then you have to report that value as one
larger than the nominal amount.  By the way, if that's your
expectation it probably should be mentioned explicitly, because it's
not obvious otherwise that it would be expected.  Also, if you don't
expect to be accurate to better than a second, it would be logical to
remove the fractional seconds information since it is meaningless.

As far as I can see you have time represented as ...hhmmss and
fractional seconds.  So you can clearly represent leap seconds
directly.  The only issue is a local implementation one: can you
reliably convert internal time format to that representation?

If you use NTP, then that's no problem.  If you use an external time
source that either uses a similar date/time format (e.g., WWV) again
no problem.  

If you have an internal time format encoded as seconds since X, then
you have several possible cases:

a. If "seconds since X" really means "seconds ignoring leap seconds"
then you can convert that easily to the other format but you should
probably add a second to the inaccuracy to account for the possibility 
that there was a leap second recently that hasn't been reflected yet
in the local time.

b. If you really have seconds since X including leap seconds, then to
convert to hhmmss... format you either need to know the number of leap 
seconds that have been inserted between X and now, or you have to
assume the worst case (two per year) and increase the inaccuracy by
that worst case.

---

From: Michael McNeil <[email-masked]>
Date: Thu, 01 Apr 1999 08:29:50 -0800

Michael Zolotarev wrote:
>properly maintained by the TSS, and returned to the client, a second
>can last as long as we want it:
>
>The issue is, the problem only exists when we COMPARE two stamps
>produced by THE SAME TSS. And this is exactly where the serialNumber
>will help us out.

While tacking a serial number onto the seconds field of a UTC time count
would work in maintaining monotonicity for that server's timestamps (and
I am a supporter of including a serial number field in timestamps), I
hardly think it's "neater".  It works only if fractional seconds are not
included in the time, and while monotonically increasing (if fractional
seconds are left out), doesn't allow any comparison beyond seconds for
timestamps from a single server other than one is earlier than another.
One can't even determine that for timestamps from different servers.

Looking at Tony Bartoletti's proposed solution, on the other hand:

>is always zero except for a leap-second, when it is "one."

Tony proposed that a leap-second-in-progress flag bit be the logical
lowest-order bit of the seconds count.  This would allow monotonicity
without any special coding being required, but would fuzz taking a
difference between second counts (two timestamps) to simply indicating
which is earlier, seconds-wise.  Placing the leap second flag in another
location allows timestamps (which can now include fractional seconds) to
be compared, but would necessitate extra code to check the leap second
flag and alter the difference if a leap second is indicated as being in
progress.  It requires looking up the history of leap seconds in order
to determine whether one has occurred between any two dates and times.
This approach is also not a "neat" solution, as Tony says, but works.

Paul Koning mentioned the method of simply adding a 61st second to a
year-month-day hours:minutes:seconds.fractional time representation:

Paul Koning wrote:
>The NTP RFC (RFC 1305) has an excellent discussion on this and the
>approaches it describes would be good to use.  In particular, it
>suggests using a two part date/time coding (day separate from
>time-in-day).  That way the existence of leap seconds merely increases 
>the range of the second field by one.  (Analogy: if you sent the
>timestamp as yyyymmddhhmmss.ssss the impact is merely that ss can be
>from 0 to 60, not 0 to 59.)

This approach works, but has the disadvantage of requiring numerous
conversions from one unit to another (i.e., year-month-day hours-
minutes-seconds-milliseconds, say), involving leap years and other
calendric oddities, in order to compare the times in two timestamps.
As in Tony's proposal, it also requires looking up the history of leap
seconds to find out whether one has occurred between any two dates.

A desirable solution ought to both maintain strict monotonicity over
leap seconds (without complicated manipulations if possible) as well
as not hinder comparisons down to the fractional seconds, should that be
desired.  In my view, the easiest response to these requirements is to
maintain two counters, both of whose values get emplaced in generated
timestamps -- one the usual NTP UTC seconds count, including 32-bits of
fractional seconds information; the other a leap seconds count field.

During ordinary seconds, the UTC seconds (and fractional) count would
increment as usual, but not the leap second counter.  During a leap
second, on the other hand, the UTC seconds count would not increment
(though fractional seconds would indicate its proper value), while the
leap-second count would increment.  To perform comparisons between two
dates and times, each UTC seconds count would first be added to the leap
second count -- thus producing essentially TAI (International Atomic)
time -- following which the two dates/times can be directly subtracted
in a single 64-bit subtract operation.  This method will work across
leap seconds, including all the 32-bit fractional second information.

Michael Zolotarev goes on to say:
>In a situation when you compare the stamps produced by different
>servers, or compare a stamp to a 'Golden Rolex' time, a one second
>difference should be tolerated, as the sources are not expected to be
>highly synchronised anyway.

I disagree that fractional second resolution will not be important in
the future.  The present primitive time synchronization situation is not
likely to last, in my opinion, when better and more secure time becomes
widely available and a required component of secure systems.  In
particular, timestamping servers will be expected to issue good time.

>Technical Architect, Baltimore Technologies Limited (Australia)

Thanks!  And thanks for posting.

Michael McNeil
[email-masked]
1-831-335-2069

IETF Secure Time Working Group: http://www.stime.org

---

From: Paul Koning <[email-masked]>
Date: Thu, 1 Apr 1999 11:44:17 -0500

>>>>> "Michael" == Michael McNeil <[email-masked]> writes:

 Michael> Paul Koning wrote:
 >> time-in-day).  That way the existence of leap seconds merely
 >> increases the range of the second field by one.  (Analogy: if you
 >> sent the timestamp as yyyymmddhhmmss.ssss the impact is merely
 >> that ss can be from 0 to 60, not 0 to 59.)

 Michael> This approach works, but has the disadvantage of requiring
 Michael> numerous conversions from one unit to another (i.e.,
 Michael> year-month-day hours- minutes-seconds-milliseconds, say),
 Michael> involving leap years and other calendric oddities, in order
 Michael> to compare the times in two timestamps.  As in Tony's
 Michael> proposal, it also requires looking up the history of leap
 Michael> seconds to find out whether one has occurred between any two
 Michael> dates.

 Michael> A desirable solution ought to both maintain strict
 Michael> monotonicity over leap seconds (without complicated
 Michael> manipulations if possible) as well as not hinder comparisons
 Michael> down to the fractional seconds, should that be desired. 

Agreed.  But if by comparison you mean the operators <, =, and >, then 
what I described (which is what's in the current draft, once you make
it clear that the ss field has 60 as a legal value) works.

A strcmp operation on time strings in GeneralizedTime format yields
the correct answer for all cases including leap seconds.  It's pretty
clear why that is so: the characters in that string are in descending
order of significance reading left to right...

As I mentioned elsewhere, whether conversion to this format requires
you to know about leap seconds depends on what you start from.  If you 
start from NTP format then I believe it does not.  In any case, that's 
an internal matter.

	paul

---

From: Michael McNeil <[email-masked]>
Date: Sat, 03 Apr 1999 10:13:35 -0800

My comments below.

>>Michael> == Michael McNeil <[email-masked]> writes:

>it clear that the ss field has 60 as a legal value) works.

I quite agree that for simple greater than comparisons, this method
works.  However, determining earlier-later than relationships are not
(only) what I'm talking about.  I believe it's desirable to be able to
compare timestamps for the exact time difference (in seconds + fraction)
between them, without convoluted computations and reference to tables.
The method I described (storing away leap seconds) accomplishes this.

Clearly, pegging specific timestamp times to the particular day, hour,
etc., that they took place in requires conversion to calendric formats.
The question is, which source format the time should be stored away in
in the timestamp.  I suggest a pure seconds count makes sense for this. 
Utility programs will be on hand to do what conversions are necessary.

>order of significance reading left to right...

Agreed.

>start from NTP format then I believe it does not.  In any case, that's

When comparing two NTP times (which are purely UTC and ignore leap
seconds), one first has ambiguity if the indicated UTC time happens to
be left adjacent to a leap second.  Second, one must refer to external
tables of historic leap seconds to correctly place a leap second (or
more) between two indicated dates.  If the count of leap seconds is
stored away in the timestamp along with the UTC time for that moment,
computing the difference between any two timestamp times becomes quite
simple, and any ambiguity in the vicinity of leap seconds is eliminated.

--
Michael McNeil
[email-masked]