Thursday, April 29, 2010

What time is it? Part 3

In Part 1, we implemented a DAYTIME server using TCP. In Part 2, we implemented a TIME server using UDP.

Today, we will implement a simple NTP client using UDP.

The NTP (Network Time Protocol) specification has been evolving since 1985. Most of the focus has been on algorithms for synchronizing the clocks of computers to varying precisions. Currently the IETF is drafting version 4, but has only formally documented up to version 3 in RFC 1305. For use cases where less precision is required, version 4 of a variant called SNTP is documented in RFC 4330.

We will begin by referencing a set of vocabularies we depend upon:

USING: accessors arrays calendar combinators destructors
formatting kernel io io.sockets math pack random sequences ;

To parse and manipulate the NTP responses, we need to refer to the specification. These are often helpfully documented in ascii diagrams. The latest specification includes this description of a NTP packet:

1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN  |Mode |    Stratum    |     Poll      |   Precision   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          Root  Delay                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       Root  Dispersion                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                     Reference Identifier                      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                    Reference Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                    Originate Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                     Receive Timestamp (64)                    |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                     Transmit Timestamp (64)                   |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                 Key Identifier (optional) (32)                |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                                                               |
|                                                               |
|                 Message Digest (optional) (128)               |
|                                                               |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The specification contains detailed information about each of these fields and how they should be interpreted and used. For now, we will just create a tuple class to hold the values contained in a typical NTP packet:

TUPLE: ntp leap version mode stratum poll precision
root-delay root-dispersion ref-id ref-timestamp
orig-timestamp recv-timestamp tx-timestamp ;

Timestamps in the NTP protocol are stored in 64-bits. The first 32-bits are an integer number of seconds, and the last 32-bits are a fractional number of seconds. This gives the protocol a theoretical precision of 233 picoseconds. Most clocks in use by NTP servers are not that accurate, so some of the precision is wasted. Currently, this timestamp should be simply interpreted as a number of seconds since January 1, 1900 (this will change slightly when the 64-bit value overflows in the year 2036).

To parse each timestamp, we will want to convert it into a number of seconds and then use the calendar vocabulary to manipulate it into a timestamp object:

: (time) ( sequence -- timestamp )
    [ first ] [ second 32 2^ / ] bi + seconds
    1900 1 1 0 0 0 instant <timestamp> time+ ;

Now that we have that, parsing the NTP packet is fairly direct:

: (ntp) ( payload -- ntp )
    "CCCcIIIIIIIIIII" unpack-be {
        [ first -6 shift HEX: 3 bitand ]  ! leap
        [ first -3 shift HEX: 7 bitand ]  ! version
        [ first HEX: 7 bitand ]           ! mode
        [ second ]                        ! stratum
        [ third ]                         ! poll
        [ [ 3 ] dip nth ]                 ! precision
        [ [ 4 ] dip nth 16 2^ / ]         ! root-delay
        [ [ 5 ] dip nth 16 2^ / ]         ! root-dispersion
        [ [ 6 ] dip nth ]                 ! ref-id
        [ [ { 7 8 } ] dip nths (time) ]   ! ref-timestamp
        [ [ { 9 10 } ] dip nths (time) ]  ! orig-timestamp
        [ [ { 11 12 } ] dip nths (time) ] ! recv-timestamp
        [ [ { 13 14 } ] dip nths (time) ] ! tx-timestamp
    } cleave ntp boa ;

The simplest client request is a 48-byte packet encoded with no timestamp information, but only the mode of operation (e.g., 3 or "client"):

CONSTANT: REQUEST B{ HEX: 1b 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                     0 0 0 0 0 0 0 0 }

We will use the <datagram> word from the io.sockets vocabulary to send and receive UDP packets. Note that the resolve-host word is used to lookup the IP addresses for domain names, and picks one to use at random.

: <ntp> ( host -- ntp )
    123 <inet> resolve-host [ inet4? ] filter random
    f 0 <inet4> <datagram> [
        [ REQUEST ] 2dip [ send ] [ receive drop ] bi (ntp)
    ] with-disposal ;

We can make some convenience words for well-known hosts:

: default-ntp ( -- ntp )
    "pool.ntp.org" <ntp> ;

: local-ntp ( -- ntp )
    "localhost" <ntp> ;

Putting this all together, a NTP request/response can look like this:

( scratchpad ) default-ntp .
T{ ntp
    { leap 0 }
    { version 3 }
    { mode 4 }
    { stratum 3 }
    { poll 0 }
    { precision -8 }
    { root-delay 6453/65536 }
    { root-dispersion 4379/65536 }
    { ref-id 2903084642 }
    { ref-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 25 }
            { second 55+819995115/2147483648 }
        }
    }
    { orig-timestamp
        T{ timestamp { year 1900 } { month 1 } { day 1 } }
    }
    { recv-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 36 }
            { second 19+729484793/4294967296 }
        }
    }
    { tx-timestamp
        T{ timestamp
            { year 2010 }
            { month 4 }
            { day 30 }
            { minute 36 }
            { second 19+732746657/4294967296 }
        }
    }
}

This could be improved by parsing some of the fields as "human-readable" (like the leap indicator, mode, stratum, and reference id) and adding support for handling unresponsive servers or dropped packets. From here, one could learn the clock synchronization algorithms, or even use this as the basis to begin implementing a NTP server.

No comments: