Tech-invite3GPPspaceIETFspace
96959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 5905

Network Time Protocol Version 4: Protocol and Algorithms Specification

Pages: 110
Proposed Standard
Errata
Obsoletes:  13054330
Updated by:  782285739109
Part 4 of 5 – Pages 61 to 75
First   Prev   Next

Top   ToC   RFC5905 - Page 61   prevText

Appendix A. Code Skeleton

This appendix is intended to describe the protocol and algorithms of an implementation in a general way using what is called a code skeleton program. This consists of a set of definitions, structures, and code fragments that illustrate the protocol operations without the complexities of an actual implementation of the protocol. This program is not an executable and is not designed to run in the ordinary sense. Most of the features of the reference implementation are included here, with the following exceptions: there are no provisions for reference clocks or public key (Autokey) cryptography. There is no huff-n'-puff filter, anti-clockhop hysteresis, or monitoring provisions. Many of the values that can be tinkered in the reference implementation are assumed constants here. There are only minimal provisions for the kiss-o'-death packet and no responding code. The program is not intended to be fast or compact, just to demonstrate the algorithms with sufficient fidelity to understand how they work. The code skeleton consists of eight segments, a header segment included by each of the other segments, plus a code segment for the main program, kernel I/O and system clock interfaces, and peer, system, clock_adjust, and poll processes. These are presented in order below along with definitions and variables specific to each process.

A.1. Global Definitions

A.1.1. Definitions, Constants, Parameters

#include <math.h> /* avoids complaints about sqrt() */ #include <sys/time.h> /* for gettimeofday() and friends */ #include <stdlib.h> /* for malloc() and friends */ #include <string.h> /* for memset() */ /* * Data types * * This program assumes the int data type is 32 bits and the long data * type is 64 bits. The native data type used in most calculations is * floating double. The data types used in some packet header fields * require conversion to and from this representation. Some header * fields involve partitioning an octet, here represented by individual * octets. * * The 64-bit NTP timestamp format used in timestamp calculations is * unsigned seconds and fraction with the decimal point to the left of
Top   ToC   RFC5905 - Page 62
 * bit 32.  The only operation permitted with these values is
 * subtraction, yielding a signed 31-bit difference.  The 32-bit NTP
 * short format used in delay and dispersion calculations is seconds and
 * fraction with the decimal point to the left of bit 16.  The only
 * operations permitted with these values are addition and
 * multiplication by a constant.
 *
 * The IPv4 address is 32 bits, while the IPv6 address is 128 bits.  The
 * message digest field is 128 bits as constructed by the MD5 algorithm.
 * The precision and poll interval fields are signed log2 seconds.
 */
typedef unsigned long long tstamp;   /* NTP timestamp format */
typedef unsigned int tdist;     /* NTP short format */
typedef unsigned long ipaddr;   /* IPv4 or IPv6 address */
typedef unsigned long digest;   /* md5 digest */
typedef signed char s_char;     /* precision and poll interval (log2) */

/*
 * Timestamp conversion macroni
 */
#define FRIC        65536.                  /* 2^16 as a double */
#define D2FP(r)     ((tdist)((r) * FRIC))   /* NTP short */
#define FP2D(r)     ((double)(r) / FRIC)

#define FRAC       4294967296.             /* 2^32 as a double */
#define D2LFP(a)   ((tstamp)((a) * FRAC))  /* NTP timestamp */
#define LFP2D(a)   ((double)(a) / FRAC)
#define U2LFP(a)   (((unsigned long long) \
                       ((a).tv_sec + JAN_1970) << 32) + \
                       (unsigned long long) \
                       ((a).tv_usec / 1e6 * FRAC))

/*
 * Arithmetic conversions
 */
#define LOG2D(a)        ((a) < 0 ? 1. / (1L << -(a)) : \
                            1L << (a))          /* poll, etc. */
#define SQUARE(x)       (x * x)
#define SQRT(x)         (sqrt(x))

/*
 * Global constants.  Some of these might be converted to variables
 * that can be tinkered by configuration or computed on-the-fly.  For
 * instance, the reference implementation computes PRECISION on-the-fly
 * and provides performance tuning for the defines marked with % below.
 */
#define VERSION         4       /* version number */
#define MINDISP         .01     /* % minimum dispersion (s) */
Top   ToC   RFC5905 - Page 63
#define MAXDISP         16      /* maximum dispersion (s) */
#define MAXDIST         1       /* % distance threshold (s) */
#define NOSYNC          0x3     /* leap unsync */
#define MAXSTRAT        16      /* maximum stratum (infinity metric) */
#define MINPOLL         6       /* % minimum poll interval (64 s)*/
#define MAXPOLL         17      /* % maximum poll interval (36.4 h) */
#define MINCLOCK        3       /* minimum manycast survivors */
#define MAXCLOCK        10      /* maximum manycast candidates */
#define TTLMAX          8       /* max ttl manycast */
#define BEACON          15      /* max interval between beacons */

#define PHI             15e-6   /* % frequency tolerance (15 ppm) */
#define NSTAGE          8       /* clock register stages */
#define NMAX            50      /* maximum number of peers */
#define NSANE           1       /* % minimum intersection survivors */
#define NMIN            3       /* % minimum cluster survivors */

/*
 * Global return values
 */
#define TRUE            1       /* boolean true */
#define FALSE           0       /* boolean false */

/*
 * Local clock process return codes
 */
#define IGNORE          0       /* ignore */
#define SLEW            1       /* slew adjustment */
#define STEP            2       /* step adjustment */
#define PANIC           3       /* panic - no adjustment */

/*
 * System flags
 */
#define S_FLAGS         0       /* any system flags */
#define S_BCSTENAB      0x1     /* enable broadcast client */

/*
 * Peer flags
 */
#define P_FLAGS         0       /* any peer flags */
#define P_EPHEM         0x01    /* association is ephemeral */
#define P_BURST         0x02    /* burst enable */
#define P_IBURST        0x04    /* intial burst enable */
#define P_NOTRUST       0x08    /* authenticated access */
#define P_NOPEER        0x10    /* authenticated mobilization */
#define P_MANY          0x20    /* manycast client */
Top   ToC   RFC5905 - Page 64
/*
 * Authentication codes
 */
#define A_NONE          0       /* no authentication */
#define A_OK            1       /* authentication OK */
#define A_ERROR         2       /* authentication error */
#define A_CRYPTO        3       /* crypto-NAK */

/*
 * Association state codes
 */
#define X_INIT          0       /* initialization */
#define X_STALE         1       /* timeout */
#define X_STEP          2       /* time step */
#define X_ERROR         3       /* authentication error */
#define X_CRYPTO        4       /* crypto-NAK received */
#define X_NKEY          5       /* untrusted key */

/*
 * Protocol mode definitions
 */
#define M_RSVD          0       /* reserved */
#define M_SACT          1       /* symmetric active */
#define M_PASV          2       /* symmetric passive */
#define M_CLNT          3       /* client */
#define M_SERV          4       /* server */
#define M_BCST          5       /* broadcast server */
#define M_BCLN          6       /* broadcast client */

/*
 * Clock state definitions
 */
#define NSET            0       /* clock never set */
#define FSET            1       /* frequency set from file */
#define SPIK            2       /* spike detected */
#define FREQ            3       /* frequency mode */
#define SYNC            4       /* clock synchronized */

#define min(a, b)   ((a) < (b) ? (a) : (b))
#define max(a, b)   ((a) < (b) ? (b) : (a))
Top   ToC   RFC5905 - Page 65

A.1.2. Packet Data Structures

/* * The receive and transmit packets may contain an optional message * authentication code (MAC) consisting of a key identifier (keyid) and * message digest (mac in the receive structure and dgst in the transmit * structure). NTPv4 supports optional extension fields that * are inserted after the header and before the MAC, but these are * not described here. * * Receive packet * * Note the dst timestamp is not part of the packet itself. It is * captured upon arrival and returned in the receive buffer along with * the buffer length and data. Note that some of the char fields are * packed in the actual header, but the details are omitted here. */ struct r { ipaddr srcaddr; /* source (remote) address */ ipaddr dstaddr; /* destination (local) address */ char version; /* version number */ char leap; /* leap indicator */ char mode; /* mode */ char stratum; /* stratum */ char poll; /* poll interval */ s_char precision; /* precision */ tdist rootdelay; /* root delay */ tdist rootdisp; /* root dispersion */ char refid; /* reference ID */ tstamp reftime; /* reference time */ tstamp org; /* origin timestamp */ tstamp rec; /* receive timestamp */ tstamp xmt; /* transmit timestamp */ int keyid; /* key ID */ digest mac; /* message digest */ tstamp dst; /* destination timestamp */ } r; /* * Transmit packet */ struct x { ipaddr dstaddr; /* source (local) address */ ipaddr srcaddr; /* destination (remote) address */ char version; /* version number */ char leap; /* leap indicator */ char mode; /* mode */ char stratum; /* stratum */
Top   ToC   RFC5905 - Page 66
        char    poll;           /* poll interval */
        s_char  precision;      /* precision */
        tdist   rootdelay;      /* root delay */
        tdist   rootdisp;       /* root dispersion */
        char    refid;          /* reference ID */
        tstamp  reftime;        /* reference time */
        tstamp  org;            /* origin timestamp */
        tstamp  rec;            /* receive timestamp */
        tstamp  xmt;            /* transmit timestamp */
        int     keyid;          /* key ID */
        digest  dgst;           /* message digest */
} x;

A.1.3. Association Data Structures

/* * Filter stage structure. Note the t member in this and other * structures refers to process time, not real time. Process time * increments by one second for every elapsed second of real time. */ struct f { tstamp t; /* update time */ double offset; /* clock ofset */ double delay; /* roundtrip delay */ double disp; /* dispersion */ } f; /* * Association structure. This is shared between the peer process * and poll process. */ struct p { /* * Variables set by configuration */ ipaddr srcaddr; /* source (remote) address */ ipaddr dstaddr; /* destination (local) address */ char version; /* version number */ char hmode; /* host mode */ int keyid; /* key identifier */ int flags; /* option flags */ /* * Variables set by received packet */ char leap; /* leap indicator */ char pmode; /* peer mode */
Top   ToC   RFC5905 - Page 67
           char    stratum;        /* stratum */
           char    ppoll;          /* peer poll interval */
           double  rootdelay;      /* root delay */
           double  rootdisp;       /* root dispersion */
           char    refid;          /* reference ID */
           tstamp  reftime;        /* reference time */
   #define begin_clear org         /* beginning of clear area */
           tstamp  org;            /* originate timestamp */
           tstamp  rec;            /* receive timestamp */
           tstamp  xmt;            /* transmit timestamp */

           /*
            * Computed data
            */
           double  t;              /* update time */
           struct f f[NSTAGE];     /* clock filter */
           double  offset;         /* peer offset */
           double  delay;          /* peer delay */
           double  disp;           /* peer dispersion */
           double  jitter;         /* RMS jitter */

           /*
            * Poll process variables
            */
           char    hpoll;          /* host poll interval */
           int     burst;          /* burst counter */
           int     reach;          /* reach register */
           int     ttl;            /* ttl (manycast) */
   #define end_clear unreach       /* end of clear area */
           int     unreach;        /* unreach counter */
           int     outdate;        /* last poll time */
           int     nextdate;       /* next poll time */
   } p;
Top   ToC   RFC5905 - Page 68

A.1.4. System Data Structures

/* * Chime list. This is used by the intersection algorithm. */ struct m { /* m is for Marzullo */ struct p *p; /* peer structure pointer */ int type; /* high +1, mid 0, low -1 */ double edge; /* correctness interval edge */ } m; /* * Survivor list. This is used by the clustering algorithm. */ struct v { struct p *p; /* peer structure pointer */ double metric; /* sort metric */ } v; /* * System structure */ struct s { tstamp t; /* update time */ char leap; /* leap indicator */ char stratum; /* stratum */ char poll; /* poll interval */ char precision; /* precision */ double rootdelay; /* root delay */ double rootdisp; /* root dispersion */ char refid; /* reference ID */ tstamp reftime; /* reference time */ struct m m[NMAX]; /* chime list */ struct v v[NMAX]; /* survivor list */ struct p *p; /* association ID */ double offset; /* combined offset */ double jitter; /* combined jitter */ int flags; /* option flags */ int n; /* number of survivors */ } s;
Top   ToC   RFC5905 - Page 69

A.1.5. Local Clock Data Structures

/* * Local clock structure */ struct c { tstamp t; /* update time */ int state; /* current state */ double offset; /* current offset */ double last; /* previous offset */ int count; /* jiggle counter */ double freq; /* frequency */ double jitter; /* RMS jitter */ double wander; /* RMS wander */ } c;

A.1.6. Function Prototypes

/* * Peer process */ void receive(struct r *); /* receive packet */ void packet(struct p *, struct r *); /* process packet */ void clock_filter(struct p *, double, double, double); /* filter */ double root_dist(struct p *); /* calculate root distance */ int fit(struct p *); /* determine fitness of server */ void clear(struct p *, int); /* clear association */ int access(struct r *); /* determine access restrictions */ /* * System process */ int main(); /* main program */ void clock_select(); /* find the best clocks */ void clock_update(struct p *); /* update the system clock */ void clock_combine(); /* combine the offsets */ /* * Local clock process */ int local_clock(struct p *, double); /* clock discipline */ void rstclock(int, double, double); /* clock state transition */ /* * Clock adjust process */ void clock_adjust(); /* one-second timer process */
Top   ToC   RFC5905 - Page 70
  /*
   * Poll process
   */
  void    poll(struct p *);               /* poll process */
  void    poll_update(struct p *, int); /* update the poll interval */
  void    peer_xmit(struct p *);  /* transmit a packet */
  void    fast_xmit(struct r *, int, int); /* transmit a reply packet */

  /*
   * Utility routines
   */
  digest  md5(int);               /* generate a message digest */
  struct p *mobilize(ipaddr, ipaddr, int, int, int, int); /* mobilize */
  struct p *find_assoc(struct r *); /* search the association table */

  /*
   * Kernel interface
   */
  struct r *recv_packet();        /* wait for packet */
  void    xmit_packet(struct x *); /* send packet */
  void    step_time(double);      /* step time */
  void    adjust_time(double);    /* adjust (slew) time */
  tstamp  get_time();             /* read time */

A.2. Main Program and Utility Routines

/* * Definitions */ #define PRECISION -18 /* precision (log2 s) */ #define IPADDR 0 /* any IP address */ #define MODE 0 /* any NTP mode */ #define KEYID 0 /* any key identifier */ /* * main() - main program */ int main() { struct p *p; /* peer structure pointer */ struct r *r; /* receive packet pointer */
Top   ToC   RFC5905 - Page 71
        /*
         * Read command line options and initialize system variables.
         * The reference implementation measures the precision specific
         * to each machine by measuring the clock increments to read the
         * system clock.
         */
        memset(&s, sizeof(s), 0);
        s.leap = NOSYNC;
        s.stratum = MAXSTRAT;
        s.poll = MINPOLL;
        s.precision = PRECISION;
        s.p = NULL;

        /*
         * Initialize local clock variables
         */
        memset(&c, sizeof(c), 0);
        if (/* frequency file */ 0) {
                c.freq = /* freq */ 0;
                rstclock(FSET, 0, 0);
        } else {
                rstclock(NSET, 0, 0);
        }
        c.jitter = LOG2D(s.precision);

        /*
         * Read the configuration file and mobilize persistent
         * associations with specified addresses, version, mode, key ID,
         * and flags.
         */
        while (/* mobilize configurated associations */ 0) {
                p = mobilize(IPADDR, IPADDR, VERSION, MODE, KEYID,
                    P_FLAGS);
        }

        /*
         * Start the system timer, which ticks once per second.  Then,
         * read packets as they arrive, strike receive timestamp, and
         * call the receive() routine.
         */
        while (0) {
                r = recv_packet();
                r->dst = get_time();
                receive(r);
        }

        return(0);
}
Top   ToC   RFC5905 - Page 72
/*
 * mobilize() - mobilize and initialize an association
 */
struct p
*mobilize(
        ipaddr  srcaddr,        /* IP source address */
        ipaddr  dstaddr,        /* IP destination address */
        int     version,        /* version */
        int     mode,           /* host mode */
        int     keyid,          /* key identifier */
        int     flags           /* peer flags */
        )
{
        struct p *p;            /* peer process pointer */

        /*
         * Allocate and initialize association memory
         */
        p = malloc(sizeof(struct p));
        p->srcaddr = srcaddr;
        p->dstaddr = dstaddr;
        p->version = version;
        p->hmode = mode;
        p->keyid = keyid;
        p->hpoll = MINPOLL;
        clear(p, X_INIT);
        p->flags = flags;
        return (p);
}

/*
 * find_assoc() - find a matching association
 */
struct p                        /* peer structure pointer or NULL */
*find_assoc(
        struct r *r             /* receive packet pointer */
        )
{
        struct p *p;            /* dummy peer structure pointer */

        /*
         * Search association table for matching source
         * address, source port and mode.
         */
        while (/* all associations */ 0) {
                if (r->srcaddr == p->srcaddr && r->mode == p->hmode)
                        return(p);
        }
Top   ToC   RFC5905 - Page 73
        return (NULL);
}

/*
 * md5() - compute message digest
 */
digest
md5(
       int     keyid           /* key identifier */
       )
{
       /*
        * Compute a keyed cryptographic message digest.  The key
        * identifier is associated with a key in the local key cache.
        * The key is prepended to the packet header and extension fields
        * and the result hashed by the MD5 algorithm as described in
        * RFC 1321.  Return a MAC consisting of the 32-bit key ID
        * concatenated with the 128-bit digest.
        */
       return (/* MD5 digest */ 0);
}

A.3. Kernel Input/Output Interface

/* * Kernel interface to transmit and receive packets. Details are * deliberately vague and depend on the operating system. * * recv_packet - receive packet from network */ struct r /* receive packet pointer*/ *recv_packet() { return (/* receive packet r */ 0); } /* * xmit_packet - transmit packet to network */ void xmit_packet( struct x *x /* transmit packet pointer */ ) { /* send packet x */ }
Top   ToC   RFC5905 - Page 74

A.4. Kernel System Clock Interface

/* * System clock utility functions * * There are three time formats: native (Unix), NTP, and floating * double. The get_time() routine returns the time in NTP long format. * The Unix routines expect arguments as a structure of two signed * 32-bit words in seconds and microseconds (timeval) or nanoseconds * (timespec). The step_time() and adjust_time() routines expect signed * arguments in floating double. The simplified code shown here is for * illustration only and has not been verified. */ #define JAN_1970 2208988800UL /* 1970 - 1900 in seconds */ /* * get_time - read system time and convert to NTP format */ tstamp get_time() { struct timeval unix_time; /* * There are only two calls on this routine in the program. One * when a packet arrives from the network and the other when a * packet is placed on the send queue. Call the kernel time of * day routine (such as gettimeofday()) and convert to NTP * format. */ gettimeofday(&unix_time, NULL); return (U2LFP(unix_time)); }
Top   ToC   RFC5905 - Page 75
/*
 * step_time() - step system time to given offset value
 */
void
step_time(
        double  offset          /* clock offset */
        )
{
        struct timeval unix_time;
        tstamp  ntp_time;

        /*
         * Convert from double to native format (signed) and add to the
         * current time.  Note the addition is done in native format to
         * avoid overflow or loss of precision.
         */
        gettimeofday(&unix_time, NULL);
        ntp_time = D2LFP(offset) + U2LFP(unix_time);
        unix_time.tv_sec = ntp_time >> 32;
        unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) <<
            32) / FRAC * 1e6);
        settimeofday(&unix_time, NULL);
}


/*
 * adjust_time() - slew system clock to given offset value
 */
void
adjust_time(
        double  offset          /* clock offset */
        )
{
        struct timeval unix_time;
        tstamp  ntp_time;

        /*
         * Convert from double to native format (signed) and add to the
         * current time.
         */
        ntp_time = D2LFP(offset);
        unix_time.tv_sec = ntp_time >> 32;
        unix_time.tv_usec = (long)(((ntp_time - unix_time.tv_sec) <<
            32) / FRAC * 1e6);
        adjtime(&unix_time, NULL);
}


(next page on part 5)

Next Section